Five coworkers want to know what the average of all their salaries is, but refuse to reveal ANY information about their own salaries to their coworkers. How can they calculate the average ? courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: What you'd do if such thing happens in your life? Hit again for hints. Hints: No Hints. Hit again for solution. Solution: One of them may choose any random number (not to be known any other) and add his salary to it and tell the sum to the second person, then he will add his salary to the sum and tell the result to the third person and so on. The fifth person after adding his salary to the sum will tell it to the first person. He will subtract the random number he choose from the final sum giving them the sum of their salaries and the average.

There is a big file containing 10^8 integers, one per line. Devise an algorithm to find the largest 100 integers among them. Remember you cannot read all of them into memory at once. courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Value stored in any element of the Array reaches a maxima at certain index. Solution: We simply use Min-Heap data structure to keep list of top 100 numbers replacing next with lowest if greater. Complexity: 1. Time: O(N*logN) 2. Space: O(1) /** * Assume standard heap ADT operations : heap_min(), heap_remove() and heap_insert() **/ void top_100(FILE *fp, int output[]){ int num, count=0; while(fscanf(fp, "%d\n", &num)){ if(++count > 100 && num > heap_min(output)){ heap_remove(output); } heap_insert(output, num); } }

A truck stops at a weigh station at the entrance to a bridge and is shown to weigh exactly 2000 lbs. The operator of the weigh station notes that the bridge can hold exactly 2000 lbs, but would crumble if it were subjected to even a fraction of an ounce more. But he says that no other vehicles ever cross over the bridge and so it's fine if the truck crosses. The truck continues on. Once the truck is halfway across the 10-mile long bridge, a sparrow flies over to the truck and lands on the hood. The truck driver sees the bird lands and his heart drops as he realizes the bridge is about to collapse, but even after the bird lands, the bridge doesn't crumble. How was the bridge able to hold up despite the extra weight from the bird ? courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: Observe. Hit again for hints. Hints: An intelligent question. Just compare the states of the truck. Solution: The weight of bird was compensated by the fuel burnt during 5 mile drive.

Given an array of N distinct integers with the property that there exists an index K (0 <= K <= N-1) such that input[0], ..., input[K] is and increasing sequence and input[K], ..., input[N-1] is a decreasing sequence. Devise and algorithm to find K. Ex [1 2 4 7 10 15 13 11 5 0 -5] Answer: K=5 (input[K]=15)  courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Value stored in any element of the Array reaches a maxima at certain index. Solution: Use binary search with the following conditions : input[mid-1] < input[mid] > input[mid+1] for mid != 0 and mid != N-1 input[mid] > input[mid+1] for mid == 0 input[mid-1] < input[mid] for mid == N-1 with initial low = 0, high = N-1, mid = (high + low)/2 int bitonic_pivot(int input[], int N) { int low=0, high=N-1, mid; while(low < high) { mid=(low+high)/2; if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] > input[mid+1]))) return mid; else if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] < input[mid+1]))) low=mid+1; else if((!mid || (input[mid-1] > input[mid])) && (mid != N-1 || (input[mid] > input[mid+1]))) high=mid; } return -1; }

What is the least number of people that need to be in a room such that there is greater than a 50 % chance that at least two of the people have the same birthday ? Click here to see the solution. Courtesy: Vibhaj Rajan p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Probability, think how will it be not possible? Hit again for solution. Solution: At least 23 people should be there. To find N such that probability of two people sharing the same birthday be more than 50%, we find N such that probability of no two people sharing same birthday be less than 50%. Thus probability would be 364/365 * 363/365 * 362/365.... (N-1 terms)... (365 - (N-1) )/365 < 0.5 So, N = 23 For more information : http://en.wikipedia.org/wiki/Birthday_problem

Written Round:

1st Paper was completely a speed test.

2nd Paper had 20 question, 10 from general computer science and 10 from algorithm and data structure, few from paper 2 are below:

1. For every number that has 3 in its units place has one number which has all one's i.e. 111 that can be divided by it completely and 13 has a multiple 111111. Write a program to find such multiple for any number that has 3 at its units place.

2. write a program for checking the given number is a palindrome.

3. write a recursive program for reversing the linked list.

4. what are the maximum no of edges that can be connected in a graph of n vertices and 0 edges such that after adding edges given graph is still disconnected.

5. A question of OS on critical section.

6. write a program to return the row number which has max no of one's in an array of NxN matrix where all 1's occur before any 0's starts.

for example:

1110

1111

1000

1100

7. 1 question on deadlock and starvation

8. Given two arrays A[], B[]. Given a no. 'sum'. Find a and b such that a+b=sum ['a' from A and 'b' from B]

Technical Round 1:

1. For every number that has 3 in its units place has one number which has all one's i.e. 111 that can be divided by it completely and 13 has a multiple 111111. Write a program to find such multiple for any number that has 3 at its units place. [As I could not solve it in written round]. 

[proposed 3 different methods and their complexity]

Technical Round 2:

1. Virtual Function

2. Copy Constructor

3. Inheritance

4. Virtual Destructor

5. Suppose a Date in the format DD/MM/YYYY is palindrome, find the next palindrome date.

6. "He is a good boy" -> "boy good a is He" [He kept on adding constraints.]

7. 10 Red and 10 Blue balls are given. You have 2 jars, now a person will be picking 1 ball out of any of them. How will you maximize probability of picking Red Ball.

Technical Round 3:

1. How T9 dictionary is implemented?

2. How do Touch Phones know in which area they are touched?

3. Project info.

Technical Round 4:

1. 2 arrays A & B of numbers are given. Find combination such that a+b=c+d. [a,b from A and c,d from B] [Kept on adding constraint to minimize time and space complexity]

2. How to design a stack using 2 queues.

HR Round:

1. Tell me about yourself.

2. Why do you want to join Adobe?

Placed!

-All the very best!

Will post more as I recall them.  :)

What would be the output of the following code ? int main(int argc, char **argv){ printf("%d", 012345 + 123450); return 0; } courtesy: Mahesh Gondi Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Think of different number system representations. Hit again for solution. Solution: The number 012345 shall be considered an octal literal and thus its value will be 5349 and addition with 123450 shall result in 128799.

You have two Indian coins that add up to 6 rupees. However, one of them is not a 5 rupee coin. What are the two coins ? courtesy: Vibhaj Rajan Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Read the question loud. Hit again for solution. Solution: There are 2 coins. If one of them is not 5, the other one will be. LOL