## Google Interview Question Software Engineer / Developers

• 0

You are at a political convention with n delegates, each one a member of exactly one political
party. It is impossible to tell which political party any delegate belongs to; in particular, you will
be summarily ejected from the convention if you ask. However, you can determine whether any
two delegates belong to the same party or not by introducing them to each otherâ€”members of the
same party always greet each other with smiles and friendly handshakes; members of different
parties always greet each other with angry stares and insults.
(a) Suppose a majority (more than half) of the delegates are from the same political party.
Describe an efficient algorithm that identifies a member (anymember) of the majority party.

Country: United States

Comment hidden because of low score. Click to expand.
6
of 6 vote

This can be done in O(n) time and O(1) space. Since we have "more than a half" of the candidates we take the politicions in pairs. To explain it clearly I would use array A[] of n elements which only use equal() and an KeyValueEntry - here the key is the polition and value is int (count) of the politiotions. So what we do:

1.) for each A we check if the key in KeyValueEntry
1.1.) if they match count++ the value (KeyValueEntry ).
1.2.) if the KeyValueEntry is empty or the count == 0 we change the element with the new one and count = 1
1.3) if the KeyValueEntry has count > 0 we change the element with "count - 1"
2.) as soon as there are no more elements in A[] we know that the element left in the KeyValueEntry is the majority one since they have "more than a half".

I think that is it. If I miss something please write a comment :)

Comment hidden because of low score. Click to expand.
0

If I understand the question correctly, you will not be able to tell which party a person belongs to. The only way to know some thing about the person's party association is from this person's interaction with other people. So what are you going to use as the "key"? Could you elaborate on that? Thanks.

Comment hidden because of low score. Click to expand.
0

``````GKalchev is just hinting at Majority Vote algorithm

Comment hidden because of low score. Click to expand.
0

@yc
We don't need to tell which party a person belongs to,
we just need to check whether another person is the same party as the candidate person.
The following is my Java implementation with some simple tests:

``````class FindMajority
{
public static void main(String[] args)
{
int[] party1 = {1, 2, 1, 3, 1, 4, 1, 5, 1};
System.out.println("majorityIndex1 = " + findMajority(party1));
int[] party2 = {2, 2, 1, 3, 1, 1, 1, 2, 1};
System.out.println("majorityIndex2 = " + findMajority(party2));
}

public static int findMajority(int[] party)
{
int N = party.length;
int candidate = 0;
int count = 1;

for (int i = 1; i < N; i++)
{
if (party[candidate] == party[i]) {count++;}
else
{
if (0 == count) {candidate = i; count = 1;}
else {count--;}
}
}

return candidate;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

The simple O(n^2) is evident where each delegate is made to greet every other and hence checked if it belong to the majority party.

There is an elegant O(n) algorithm: Go through all delegates. Keep a counter and current guess for delegate of majority party, for each delegate the guessed delegate meet with smile, increase the counter and for each stare decrease the counter. When counter is zero, update the guess with the next delegate that you pick (at initialization, the first delegate is the guess).
When you have gone through all delegates, confirm that the delegate that you have chosen is indeed the one from majority party (this check not required if question ensures that there is a majority party)

For correctness of O(n) algorithm, search for 'Finding majority element in an array'

Comment hidden because of low score. Click to expand.
0

As you say, the majority vote algorithm is best here.

Union-find is also tempting, but seems to be O(n log n).

Comment hidden because of low score. Click to expand.
0

There at least one case where this does not work.

Say there are 3 delegates (n=3). Say there are two people in the majority party.

If we started with someone in the majority party and introduce them to an outsider, their counter is 0. So we move to the next person (the minority). Introduce him to the majority, and the counter is 0 again.

In summary, we just ran through everyone and iterated our counter 0 times. We therefore do not have a good guess.

If we let M be the number of people in the majority and m be the people in the minority, then

``M - 2 >= m``

implies that the counter would be iterated at least once for a person in the majority.

Comment hidden because of low score. Click to expand.
0

You missed a minute detail, when you introduced the minority person to the majority person, the counter is zero, but the current guess also changes to the next person which is the majority person.
Since we are assuming that data ensures there is always a majority person, we need not check if this guess is correct (it has to be), otherwise we would have introduced this person with everyone else to confirm it is from majority.

Comment hidden because of low score. Click to expand.
0

Although you guarantee to have a majority person in the end, the question asked was to tell if *any* person is in the majority. How do you go about that?

Comment hidden because of low score. Click to expand.
0

OK I think you can just go through it again once you found a majority person. This keeps the algorithm still O(n) in time (with a coefficient 2), and O(1) in space.

Comment hidden because of low score. Click to expand.
1
of 1 vote

This is similar to majority vote algorithm, compare the successive members by making them greet. if they stare at each other the count remains 0 , else make the count 2 to begin with.
Also when you increment the count , mark the political party(call it X)

Now when 2 persons (adjacent to each other ) meet and they stare, then you make him meet one of the member's from party X. if they smile then he is also from party X, so increment the counter, else decrement the counter.
The rest is straight forward

Comment hidden because of low score. Click to expand.
0
of 0 vote

* Majority party has more than half delegates.

1.for each delegate make set, mark set with smell flag.
2. keep union smell set to half of previous smell set number.
--compare root in each set , if friendly, then mark smell, else, remove both from smell sets.
3. keep union until only one smell set, then any element in set is major party delegate.

Why this may correct:
1. will generate n smell sets.
first time run 2. will reduce smell set to at most n/2, but no less than 1 smell set. get from *.
3. each run of 2 can at least shrink smell set by half.* still hold in each iteration result.
4. output smell set must be majority party delegates set with no less than one element.

Time complexity:
O(n lgn )

Comment hidden because of low score. Click to expand.
0
of 0 vote

create an array of size n e.g. Arr[n] (all elements initialised to 0)
pick a person randomly say x1 (out of x1, x2....xn)
compare this person with other n-1 persons.
for x1's interaction with x2 -> make Arr[1]=1 for smile else let it remain 0
similarly for x1's interaction with kth x, make Arr[k-1]=1 for smile else let it remain 0
after this one round of interaction. just find the sum of values in Arr[0] to Arr[n-1]
If x1 was of non-majority party then he gave more stares than smiles and hence the sum is less than n/2. in such a case drop all the x's corresponding to the entry of 1 in the Arr (since they were of the same party as that of x1;
now repeat the whole process for remaining people.
we need to repeat this till the sum of All 1's in the Arr after a particular round of interactions is greater than ORIGINAL n/2.
This is because as soon as a randomly chosen (e.g.suppose x1) member makes smiling interaction for at least n/2 times then that member (and all those with whom he smiled during interaction ... i.e. all those corresponding to entry 1 in Arr) belong to the majority party

Thus for any given X1 ... we can find if he belongs to majority or not in n-1 interactions itself.
and if wish to dissect the majority from others, we actually keep dissecting parties till we fortunately dissect a party which occupies more than half space/count

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0

Why do you need to go again? Just after first run,
if the sum of array is less than n/2.. then it means this person is from minority and all the persons with 1 in their positon is from minority otherwise majority...
If sum is more than n/2, x1 is from majority and all persons with 1 in array are from majority...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Think it as a circular array. A[n].
Politicians are from 1 to n.
Introduce 1->2, 2-> 3,....... ,n->1.
A[i] = 1 if smile else 0.

iterate array and find the maximum number of contiguous 1s.

That contiguous sequence will be from majority party.

O(n) complexity.

How it will work. let say n is even. if people are kept at random position irrespective of their party. and we know that more than n/2 people are from majority class then definitely there will a set in array having most number of 1s.

in case of n being odd, circular array will take care of that.

Please let me know if I am wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's an algorithm with O(n) time and O(1) space. Have one variable keep track of current member and another variable keep track of the counter:

1. Initially current member is the first member and counter is 1.
2. introduce the next member to current member. If they belong to the same party then increment the counter of current member; otherwise decrement the counter. If the counter becomes 0 then replace the current member with the next member and set its counter to 1.
3. repeat step 2 until either counter exceeded majority half or all members have been introduced. The current member remaining is the majority member.

The idea is to get rid off each minority member by pairing it up with either a majority member or another minority member. For example, say there are 9 total members of 5 majority and 4 minority, in the worst case, the order of introduction results in 4 minority cancel out with 4 majority, there is still one majority left to give the correct result.

Comment hidden because of low score. Click to expand.
0

this is a n^2 algorithm with space of O(1).
Let's say majority party is A. (Like 51%) The the rest of the 49% could all be in their own parties. Worse case is that you pick all 49% from the party. that will be (n/2)-1 people times n meets. Therefore n^2

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Convention
{
private PoliticalParty majorityParty;

enum PoliticalParty
{
A, B;
}

static class Delegate
{
private PoliticalParty party;

private Delegate(PoliticalParty party)
{
this.party = party;
}

private boolean hasSamePartyGreeting(Delegate other)
{
return (party == other.party);
}

public String toString()
{
return party.name();
}
}

private Delegate[] delegates;

public void init(int conventionSize)
{
int m = PoliticalParty.values().length;
Random random = new Random();
int idx = random.nextInt(m);
majorityParty = PoliticalParty.values()[idx];

int mpCount = 0;

delegates = new Delegate[conventionSize];

for (int i = 0; i < conventionSize; i++)
{
boolean finished = false;
PoliticalParty randomParty = null;
while (!finished)
{
random = new Random();
idx = random.nextInt(m);
randomParty = PoliticalParty.values()[idx];
if (majorityParty == randomParty)
{
mpCount++;
finished = true;
} else
{
if ( i - mpCount + 1 < (conventionSize / 2 + conventionSize % 2) )
{
finished = true;
}
}
}
delegates[i] = new Delegate(randomParty);
}
}

public boolean findMajority(int j)
{
int majority = 0;
int n = delegates.length;

for (int i = 0; i < n; i++)
{
if ( i != j )
{
if (delegates[j].hasSamePartyGreeting(delegates[i])) majority++;
if (majority >= n / 2) return true;
}
}
return false;
}

public static void main(String[] args)
{
int j = 0;
Convention c = new Convention();
c.init(3);
System.out.println( String.format( "Is %s a member of the majority party %s: %s",
c.delegates[j],
c.majorityParty, c.findMajority(j)));
for (Delegate d : c.delegates)
{
System.out.print(d + ", ");
}
}``````

}

The algorithm seems pretty straightforward. O(n). So the exit clause of checking if we met more than 1/2 the majority of delegates who belong to the party, then we can quit checking. The solution above works for any arbitrary number of political parties as well.

Did I overlook something?

Comment hidden because of low score. Click to expand.
0
of 0 vote

1 randomly select one person, introduce him to all other people.
If more than half smiles to him, already find all members of the majority party,
Otherwise the selected people does not belong to the majority party,
and all people smiles to him belong to one minority party. Then

2 Randomly choose one people does not belong to any known minority party,
introduce him to all other people does not belong to any known minority party.

3. Repeat 2 until find one people belongs to the majority party.

Assume there are m parties, the algorithm complxity is O(n x m)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public Politician FindMajorPoliticalParty(Politician[] input)
{
if (input == null || input.Length == 0)
{
throw new ArgumentException();
}

List<PoliticianAlien> symbol = new List<PoliticianAlien>();

int max = 1;
bool findGroup = false;
for (int i = 1; i < input.Length; i++)
{
findGroup = false;
for (int j = 0; j < symbol.Count; j++)
{
if (symbol[j].Symbol.IsTheSameParty(input[i]))
{
symbol[j].AlienCount++;
if (symbol[j].AlienCount > max)
{
symbol.Sort((m, n) => { return m.AlienCount > n.AlienCount ? 1 : 0; });
max = symbol[j].AlienCount;

if (max > input.Length /2)
{
return symbol[j].Symbol;
}
}
findGroup = true;
break;
}

if (findGroup)
{
continue;
}
else
{
}
}
}

return symbol[0].Symbol; ;
}

internal class PoliticianAlien
{
public Politician Symbol { get; set; }
public int AlienCount { get; set; }

public PoliticianAlien(Politician user, int count)
{
this.Symbol = user;
this.AlienCount = count;
}
}

public class Politician
{
public string Name{get;set;}
private PoliticalParty Party {get; set;}

public bool IsTheSameParty(Politician user)
{
return this.Party.PartyName.Equals(user.Party.PartyName, StringComparison.InvariantCultureIgnoreCase);
}
}

public class PoliticalParty
{
public string PartyName {get; set;}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Select person A to represent party A (of unknown affiliation at this point), create another set of ~A to represent his opposite.

Then for each delegate x
introduce x to A via greeting function
if A is same party add x to A

At the end person A will be very tired but you will have two sets of delegates. This algorithm would easily parallelize, we could have separate people "threads" creating two separate sets. At the end we can merge by comparison just two people from each set and merge appropriately.

This requires O(N) greetings and testing membership is O(1) since we are using a set.

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(2n).
Put all the delegates in an array.
First time, iterate and try to join delegate with the delegate on the right if they belong to the same party.
Second time, iterate and try to join delegate with the delegate on the right of the delegate on the right. That is, jump one delegate.
Since join search set can be done in constant time, and more than n/2 delegates belong to same party, after two loops, one set will be of size >= n/2.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// check the below code taken from stackoverflow
int findMajorityElement(int * arr, int size) {
int count = 0, i, majorityElement;
for (i = 0 ;  < size ; i++) {
if(count == 0) {
majorityElement = arr[i];
}
if(arr[i] == majorityElement)
count++;
else
count--;
}
count = 0;
for (i=0; i < size ; i++) {
if (arr[i] == majorityElement) {
count++;
}
}
if ( count > size/2) {
return majorityElement;
}
else return -1;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;

/*========================================Templates=============================================*/
#define Testcases(tc)	int tc;	S(tc);	while(tc--)
#define REP(i,n)		for(int i=0;i<(n);++i)
#define FOR(i,a,b)		for(int i=(a);i<=(b);++i)
#define FORN(i,a,b,n)	for(int i=(a);i<=(b);i+=n)
#define FORD(i,a,b)		for(int i=(a);i>=(b);--i)
#define FORDN(i,a,b,n)	for(int i=(a);i>=(b);i-=n)
#define FOREACH(i,c)	for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define ALL(x)			(x).begin(),(x).end()
//#define S(n)			scanf("%d",&n)
#define S2(n1,n2)		scanf("%d %d",&n1,&n2)
#define S3(n1,n2,n3)	scanf("%d %d %d",&n1,&n2,&n3)
#define SL(n)			scanf("%lld",&n)
#define SD(n)			scanf("%f",&n)
#define SS(a)			scanf("%s",a)
#define DB(x)			cout<<#x<<" : "<<x<<endl;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UINT;

/*======================================IO OPTIMISED FUNCTIONS===================================*/
int sign;
int ch;
inline void S( int &x )
{
x=0;
while((ch<'0' || ch>'9') && ch!='-' && ch!=EOF)	ch=getchar();
if (ch=='-')
sign=-1 , ch=getchar();
else
sign=1;

do
x=(x<<3)+(x<<1)+ch-'0';
while((ch=getchar())>='0' && ch<='9');
x*=sign;
}
/*===============================================================================================*/

int main()
{
int N,T, temp, x, k;

S(T);
while(T--)
{
int arr[1000];
int tempArr[503];
bool flag;
S(N);
FOR(i,1,N)
S(arr[i]);
while(1)
{
flag = false;
temp = 0;
x = 1;
k = 1;
if(N%2)
{
x = 2;
temp = arr[N];
}

FORN(i,1,N-x,2)
{
if(arr[i] == arr[i+1])
{
tempArr[k++] = arr[i];
flag = true;
}
}
if(temp)
{
tempArr[k] = temp;
}
else
{
if(flag)
k--;
}
FOR(i,1,k)
arr[i] = tempArr[i];
N = k;
if(k==1)
break;
}
printf("%d\n",arr[1]);
}
return 0;
}``````

Basically, the idea is to reduce the list to n/2 by each while(1) iteration. The order would remain n/2+n/2*2+...

Tested with following inputs -

15
10
1 2 1 3 1 4 1 5 1 1
10
1 1 2 2 3 3 1 1 1 1
10
1 2 1 1 1 2 1 2 1 2
5
1 2 1 1 3
2
1 1
3
1 2 1
5
1 2 1 3 1
5
1 1 1 2 3
5
1 2 3 1 1
5
2 3 1 1 1
5
1 2 3 1 1
5
1 2 1 1 2
5
3 2 1 1 1
5
2 3 1 1 1
5
1 1 2 3 1

And o/p is 1 for each case. Please suggest if there is something which I missed.

Comment hidden because of low score. Click to expand.
0

If you ever came up with that in an interview, there is no way I would hire you!

Comment hidden because of low score. Click to expand.
0

Any specific reason for ur comment...

Comment hidden because of low score. Click to expand.
0

I didn't leave the comment, but yes, there is a specific reason I completely agree. This is some horrifically ugly code.

Comment hidden because of low score. Click to expand.
0

I Agree with Eugene and Seattle Guy.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Assuming n is even, ask the delegates to greet in pairs (n/2 greets). Delegates in pair that laughs are from same party.

Assuming n is odd, ask delegates to greet in pairs ( (n-1)/2 greets). One delegate stands aside. Two cases are possible
1. None of the delegates greeting each other laughs ==> Delegate standing aside is from majority party
2. Delegates greeting each other laughs ==> Delegates in laughing pair are from majority party

Comment hidden because of low score. Click to expand.
0

Oh, I see. Right, this only works if you assume that the other political parties only have 1 candidate per party.

Comment hidden because of low score. Click to expand.
0

\What about the member of maority who got compared with the opposition party, how will u identify them

Comment hidden because of low score. Click to expand.
0

\What about the member of maority who got compared with the opposition party, how will u identify them

Comment hidden because of low score. Click to expand.
0

\What about the member of maority who got compared with the opposition party, how will u identify them

Comment hidden because of low score. Click to expand.
-2
of 2 vote

O(n) time is fairly straight forward. Since each person belongs exclusively to 1 party we can simply introduce the same person to all other people and keep counters for both parties as well as the first or last person of the opposite party:
int oppositeIndex = 0;
int oppositeParty = 0;
int sameParty = 0;
for (int i = 1; i < n; i++){
if (A[0] matches A[i])
sameParty++;
} else {
oppositeParty++;
oppositeIndex = i;
}

Any ideas on how to get better than O(n)?

Comment hidden because of low score. Click to expand.
0

what if A[0] doesn't belong to majority party?

Comment hidden because of low score. Click to expand.
0

Then A[oppositeIndex] does..

Comment hidden because of low score. Click to expand.
0

I dont understand the downvotes on this one, if we take any one member from the group and introduce him to all the other members. While we are introducing, we are filling the array for politicians with -1 if they belong to the opp. group and 1 if same. At the same time we keep counters of -1 and +1s so far. If the count of +1s is greater than -1s than we know the all the persons who belong to the majority and the original person we chose also belongs to the same group.
This will fail of course when there are more than 2 parties.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.