当前位置：网站首页>An interesting interview question

An interesting interview question

2022-04-23 11:01:00 【Hollis Chuang】

In Alibaba's culture , Full of all kinds of martial arts elements . In the interview with Ali , Some interesting topics often appear .

today , Let's take a look at the question of Alibaba interview ：

In the Wulin , A friend's friend or a friend , For example, the relationship between friends is shown in the table below , So Zhou Zhiruo 、 zhang wuji 、 Han Xiaozhao belongs to a circle of friends , Cheng Kun and Chen Youliang belong to a circle of friends , Yang Xiao and Ji Xiaofu belong to a circle of friends . Final , The number of different circles of friends is 3.

figure	figure	Relationship
Zhou Zhiruo	zhang wuji	friend
zhang wuji	Han Xiaozhao	friend
Quint	Chen Youlang	friend
Yang Xiao	Ji Xiaofu	friend

(1) Any given two people , Judge whether they belong to the same circle of friends .

(2) Program to find the number of different circles of friends .

Topic understanding

First , Let's take a look at Zhou Zhiruo 、 What do Zhang Wuji and Han Xiaozhao look like , It's still lovely .

Let me explain what is “ A friend's friend or a friend ”： Zhou Zhiruo and Zhang Wuji are friends , Zhang Wuji and Han Xiaozhao are friends . therefore , The three of them are friends , Belong to the same circle of friends . Interest Moving graph Explain the following ：

Thought analysis

Before we solve this problem , We have to think of a reasonable data structure , However , It seems that the data structures in books are inappropriate , Then what shall I do? ？

Let's tell a story about Zhou Zhiruo and his collection . Let's analyze first , Friends are as follows ：

{ Zhou Zhiruo , zhang wuji }

{ zhang wuji , Han Xiaozhao }

{ Quint , Chen Youlang }

{ Yang Xiao , Ji Xiaofu }

The logic diagram of their relationship is as follows ：

It can be seen from the figure above , These people belong to different 3 Circle of friends , So this 3 How did you get a circle of friends ？

Obviously , We can define a nominal... In each circle of friends leader.

If you want to judge whether two people belong to a circle of friends , Just judge their leader Whether it's the same person , This is a query process .
If two people are friends , You need to merge two people into the same circle of friends , This is a merger process .

This operation of checking together , We can tell how many circles of friends there are in the end , The corresponding data structure is the union query set . In many written examinations, interviews or ACM In the race , It is not uncommon to search collections .

Programming to realize

According to the above ideas , We use it C++ Code to implement and query the set , The test and results are given . The comments of the code are very detailed , So let's not go back to ：

#include <iostream>
#include <map>
using namespace std;


map<string, string> leader; 


//  Each line represents a pair of friends 
string input[] = 
{
  " Zhou Zhiruo ", " zhang wuji ",
  " zhang wuji ", " Han Xiaozhao ",
  " Quint ", " Chen Youlang ", 
  " Yang Xiao ", " Ji Xiaofu ",
};


//  Test whether two people in each line are friends 
string test[] =
{
  " Zhou Zhiruo ", " Han Xiaozhao ",
  " zhang wuji ", " Quint ",
};


//  initialization 
void setLeader()
{
  int i = 1;
  int totalPerson = 8;
  for(i = 0; i < totalPerson; i++)
  {
    leader[input[i]] = input[i]; //  Initialize yourself as your leader 
  }
}


//  Find leaders , See who it is 
string findLeader(string s) 
{
  string r = s;
  while(leader[r] != r)
  {
    r = leader[r]; //  If I can't find it , Keep looking up 
  }


  return r;
}


//  Merge the circle of friends of the two leaders , From now on ,leaderX and leaderY It's a circle of friends 
void uniteSet(string leaderX, string leaderY)
{
  leader[leaderX] = leaderY; 
}


int main()
{
  int numberOfSets = 7; //  At the beginning there was 7 A person who doesn't repeat 


  //  Initialize leadership 
  setLeader();


  int i = 0;
  int j = 0;
  int n = 4; //  The array of character relationships is 4 That's ok 
  for(j = 0; j < n; j++)
  {
    string u = input[i++];
    string v = input[i++];


    //  Find a leader 
    u = findLeader(u);
    v = findLeader(v);


    //  Leadership is not equal , Then merge two circles of friends 
    if(u != v)
    {
      uniteSet(u, v);
      numberOfSets--;
    }
  }


  i = 0;
  n = 2; //  The array of people to be tested is 2 That's ok 
  for(j = 0; j < n; j++)
  {
    string u = test[i++];
    string v = test[i++];


    //  Find a leader 
    u = findLeader(u);
    v = findLeader(v);


    //  If the leaders are different , You don't belong to a circle of friends 
    if(u != v)
    {
      cout << "NO" << endl;
    }
    else //  If two leaders are the same , It must belong to a circle of friends 
    {
      cout << "YES" << endl;
    }
  }
 
  cout << numberOfSets << endl;


  return 0;
}

The result of the program is ：

YES
NO
3

Obviously , Zhou Zhiruo and Han Xiaozhao are friends , Zhang Wuji and Cheng Kun are not friends , and , The number of circles of friends is 3, The above procedure can pass Ali's interview .

It's interesting to check the collection , It is also a test site often involved , The key is thinking . I hope you know the collection like the back of your hand , Successfully passed the written examination 、 interview , Get better offer.

End

Previous recommendation