CareerCup

class MajorityVoting
{
public static void main (String args[])
{
int arr[] = {2, 2, 3, 3, 3, 2, 2, 3, 2, 3};
System.out.println (findMajor (arr));
}

public static int findMajor(int[] arr)
{
int curr = arr[0];
int count = 1;
for (int i=0; i< arr.length; i++)
{
if (curr == arr[i])
count++;
else
count--;
if (count == 0 && (i+1) < arr.length)
{
curr = arr[i+1];
count = 0;
}
System.out.println (arr[i] + " " +curr+ " " + count);
}
if (count <= 0)
return -1;
return curr;
}
}

Dynamic programming:
Tree (n) is some sort of data structure which stores all possible trees with n nodes given the inorder traversal: 1 2 3 4 5
We are going through the sequence from right to left, so 5 comes first then 4 and so on.
We start by computing Tree (0) which is 0
Tree (1) = 5
Tree (2) =
4 and 5
\ /
5 4
Tree (3) =
We join node 3 with Tree (2) in two ways:
3 and Tree (2)
\ /
Tree(2) 3
This results in 4 trees in total, which are:
3 and 3 and 4 and 5
\ \ / \ /
4 5 3 5 4
\ / /
5 4 3

Similarly, compute Tree (4), Tree (5)....

Problem solved.

1
\
3
/
2

What if there are N elements in input and M distinct numbers and each occurs exactly n/m times. For example:
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
The question is to find all the elements that occur exactly 2 times.
Also you are using a hashtable, complexity of access is O(1). We are scanning the hashtable to decrease count when a row is full. This can happen N/M times in the worst case. So the complexity comes out to be O(n) + O(m*n/m) = O(n)

What if there are N elements in input and M distinct numbers and each occurs exactly n/m times. For example:
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
The question is to find all the elements that occur exactly 2 times.
Also you are using a hashtable, complexity of access is O(1). We are scanning the hashtable to decrease count when a row is full. This can happen N/M times in the worst case. So the complexity comes out to be O(n) + O(m*n/m) = O(n)

How about starting at the head of the list and pushing the numbers in a stack as we read them.
When end of list reached, pop out numbers from the stack and multiple them with increasing powers of 10 and keep adding them to the result.

Awesome! works...
How did you know? I totally bombed this q in the interview.

result looks wrong, esp. 2nd and 3rd column.

Could this algorithm create an infinite loop?
Say a has a friend b who has a friend c who has a friend a.