CareerCup

public class PoliticalPartiesEqual {
    public static String partiesEqual(Integer[] partyOne,Integer[] partyTwo, int states)
    {
         if (partyOne.length!=states || partyTwo.length!=states)
         {
             return "Invalid";
         }
        if (Arrays.asList(partyOne).stream().anyMatch(x->x<0) ||
                Arrays.asList(partyTwo).stream().anyMatch(x->x<0))
        {
            return "Invalid";
        }
        Arrays.sort(partyOne);
        Arrays.sort(partyTwo);
        return Arrays.equals(partyOne,partyTwo)?"Equal":"Unequal";
    }
}

public class PoliticalPartiesEqualTest {

    @Test
    public void testPartiesEqual() throws Exception {
        int nrOfStates=7;
        Integer[] partyOne={12,11,5,2,7,5,-11};
        Integer[] partyTwo={5,12,5,7,11,2,11};
        Assert.assertEquals(
                PoliticalPartiesEqual.partiesEqual(partyOne,partyTwo,nrOfStates),"Invalid");
        partyOne=new Integer[]{12,11,5,2,7,5,11};
        partyTwo=new Integer[] {5,12,5,7,11,2,11};
        Assert.assertEquals(
                PoliticalPartiesEqual.partiesEqual(partyOne,partyTwo,nrOfStates),"Equal");

        partyOne=new Integer[]{12,11,5,2,7,5,11};
        partyTwo=new Integer[] {5,0,5,7,11,2,11};
        Assert.assertEquals(
                PoliticalPartiesEqual.partiesEqual(partyOne,partyTwo,nrOfStates),"Unequal");
    }
}

void is_equal(int * party1, int * party2, int n) {
	
	
	 int i, j, total1=0, total2= 0;
	
	
	 for( i =0; i<= n-1; i++ ) {
		 
		 if( party1[i] < 0) {
			
			printf("Invalid input\n");
			exit(0);
			
		}
		 else{
	
			total1+= party1[i];
			
			
		}

	}
	
	for( j =0; j<= n-1; j++ ) {
		 
		 if( party2[j] < 0) {
			
			printf("Invalid input\n");
			exit(0);
			
		}
		 else{
			total2+= party2[j];
			
			
		}

	}
	
	if( total1 == total2)
	  printf("The seats for both parties are equal\n");
	
	else 
	  printf("The seats for both parties are not equal\n");
	
	
	
	
}

void is_equal(int * party1, int * party2, int n) {


int i, j, total1=0, total2= 0;


for( i =0; i<= n-1; i++ ) {

if( party1[i] < 0) {

printf("Invalid input\n");
exit(0);

}
else{

total1+= party1[i];


}

}

for( j =0; j<= n-1; j++ ) {

if( party2[j] < 0) {

printf("Invalid input\n");
exit(0);

}
else{
total2+= party2[j];


}

}

if( total1 == total2)
printf("The seats for both parties are equal\n");

else
printf("The seats for both parties are not equal\n");




}

No need to sort ..

Create count map for both the parties.


# Check key size for count map is same
# Then for each key check the count value is same

Space O(n)
Time O(n)
validity can be check while building count map

so for example
{12,11,5,2,7,5,11}
{5,0,5,7,11,2,11}

Count map 1
12 -1
11 - 2
5 - 2
2 -1
7 -1

Count map 2
0 -1
5 -2
7 -1
11 -2
2 -1

This will fail, since key "12" is not in map 2.

(1) Check for Invalid numbers in the array for "Invalid"
(2) Check the sum of the arrays for "Equal" / "Unequal"

Here is C++ solution running in O(n log n).
I wonder whether I misunderstood the problem or this question was not from Google interview. (considering its difficulty) Please, correct me if I am wrong.

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

bool compare(int prev, int next)
{
	return (prev< next);
}

void processResult(vector<int>& p1, vector<int>& p2, int states)
{
	sort(p1.begin(), p1.end(), compare);
	sort(p2.begin(), p2.end(), compare);

	for (int i = 0; i < states; i++)
	{
		if (p1[i] < 0 || p2[i] <0)
		{
			cout<<"Invalid"<<endl;
			return;
		} else if (p1[i] != p2[i]) {
			cout <<"inequal"<<endl;
			return;
		}
	}
	cout<<"equal"<<endl;
}

int main()
{
	int states = 7;
	vector<int> p1;
	vector<int> p2;

	p1.push_back(12);
	p1.push_back(11);
	p1.push_back(5);
	p1.push_back(2);
	p1.push_back(7);
	p1.push_back(5);
	p1.push_back(-11);

	p2.push_back(5);
	p2.push_back(12);
	p2.push_back(5);
	p2.push_back(7);
	p2.push_back(11);
	p2.push_back(2);
	p2.push_back(11);

	processResult(p1, p2, states);

	p1.clear();
	p2.clear();


	p1.push_back(12);
	p1.push_back(11);
	p1.push_back(5);
	p1.push_back(2);
	p1.push_back(7);
	p1.push_back(5);
	p1.push_back(11);

	p2.push_back(5);
	p2.push_back(12);
	p2.push_back(5);
	p2.push_back(7);
	p2.push_back(11);
	p2.push_back(2);
	p2.push_back(11);	

	processResult(p1, p2, states);

	p1.clear();
	p2.clear();

	p1.push_back(12);
	p1.push_back(11);
	p1.push_back(5);
	p1.push_back(2);
	p1.push_back(7);
	p1.push_back(5);
	p1.push_back(11);

	p2.push_back(5);
	p2.push_back(0);
	p2.push_back(5);
	p2.push_back(7);
	p2.push_back(11);
	p2.push_back(2);
	p2.push_back(11);	

	processResult(p1, p2, states);

	p1.clear();
	p2.clear();

	return 1;
}

the answers above that use 'totals' aren't following the definitions of equality e.g. {2,1,1} is not equal to {4,0,0}.
the answers that are using sorts are correct but are O(n*logn) which are not as efficient as using a hash map O(N)

enum ElectionResult
{
	Equal,
	Unequal,
	Invalid
};

// Equal { 1,1,2 } vs {2, 1, 1}
// unequal {0, 1, 3} vs {1,1,2}

// Plan
// 1. create a map of party1 values counts
// 	1:2
// 	2:1
//
// 2. walk through and subtract out party 2 seats
//
// complexity
// O(N)
//
// sort and walk is nlgn + N
#include <unordered_map>
#include <assert.h>
#include <stdio.h>
using namespace std;

ElectionResult determine_result(int party1_seats[], int party2_seats[],
				int num_states)
{
	unordered_map<int, int> seat2count;
	for (int i = 0; i < num_states; i++)
	{
		int seat = party1_seats[i];
		if (seat < 0)
			return Invalid; 	
		seat2count[seat]++;
	}	

	for (int j = 0; j < num_states; j++)
	{
		// walk through and decrement
		// hitting a 0 means unbalanced
		int seat = party2_seats[j];
		if (seat < 0)
			return Invalid; 	
		unordered_map<int,int>::iterator iter = seat2count.find(seat);
		if (iter == seat2count.end() || (*iter).second == 0)
		{
			return Unequal; 
		}
		else
		{
			(*iter).second--;
		}
	}
	return Equal;
}


// Equal { 1,1,2 } vs {2, 1, 1}
int main(int argc, char **argv)
{
	int p1[] = {1,1,2};
	int p2[] = {2,1,1};
	assert(determine_result(p1, p2, 3) == Equal);
	int p3[] = {1,1,2};
	int p4[] = {1,1,1};
	assert(determine_result(p3, p4, 3) == Unequal);
	int p5[] = {1,1,2};
	int p6[] = {1,1,-1};
	assert(determine_result(p5, p6, 3) == Invalid);
}

So a small solution:

Just XOR all the numbers together, the result is EQUAL if the XORd result is 0 and UNEQUAL if not. This is because we know that for EQUAL, each value in party 1 election results must have a duplicate in party 2 election results and we know that XOR zeros out duplicated values when XORd together.

For invalid, just do a negative check before you XOR

Here is my simple solution. This uses just 2 variables (1 for total, 1 for the i iterator) for an O(num_states) cost.

public enum PartyResult
{
	Equal,
	Unequal,
	Invalid
}

public PartyResult CalculatePartyResult(int[] party1_seats, int[] party2_seats, int num_states)
{
	if(num_states <= 0 || party1_seats == null || party2_seats == null || party1_seats.Length != num_states || party2_seats.Length != num_states)
		return PartyResult.Invalid;
	int total = 0;
	for(int i = 0; i < num_states; i++)
	{
		if(party1_seats[i] < 0 || party2_seats[i] < 0)
			return PartyResult.Invalid;
		total += party1_seats[i];
		total -= party2_seats[i];
	}

	if ( total == 0 )
		return PartyResult.Equal;
	else
		return PartyResult.Unequal;
}

Here is my quick solution. It uses 2 variables (1 for total, 1 for the iterator) and has a cost of O(num_states)

public enum PartyResult
{
	Equal,
	Unequal,
	Invalid
}

public PartyResult CalculatePartyResult(int[] party1_seats, int[] party2_seats, int num_states)
{
	if(num_states <= 0 || party1_seats == null || party2_seats == null || party1_seats.Length != num_states || party2_seats.Length != num_states)
		return PartyResult.Invalid;
	int total = 0;
	for(int i = 0; i < num_states; i++)
	{
		if(party1_seats[i] < 0 || party2_seats[i] < 0)
			return PartyResult.Invalid;
		total += party1_seats[i];
		total -= party2_seats[i];
	}

	if ( total == 0 )
		return PartyResult.Equal;
	else
		return PartyResult.Unequal;
}

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> a {12, 11, 5, 2, 7, 5, -11};
	vector<int> b {5, 12, 5, 7, 11, 2, 11};
	int size = a.size();
	int sum = 0;

	for(auto i : a)
		cout << i << " ";
	cout << endl;

	for(auto i: b)
		cout << i << " ";
	cout << endl;

	if(a.size() != b.size()){
		cout << "Invalid\n";
		return 0;
	}
		

	for(int i=0; i<size; i++) {
		if(a[i] < 0 || b[i] < 0) {
			cout << "Invalid\n";
			return 0;
		}
		sum += a[i];
		sum -= b[i];
	}

	if(sum == 0){
		cout << "Equal\n";
	}
	else{
		cout << "Unequal\n";
	}

	return 0;
}