## someone

BAN USER- 0of 0 votes

AnswersRotate a n*n (square) matrix by 90 degrees.

- someone in United States| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm

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.

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)

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

class MajorityVoting

- someone December 29, 2011{

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;

}

}