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

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

Given an array of integers with size 2N+1 such that N elements appear twice in arbitrary positions and 1 element appears only once. Devise an algorithm to find the lonely element. Ex : {1 2 4 5 1 4 2} Answer : 5 courtesy: Syed Wali Hamza 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 some bit manipulation techniques. Hit again for solution. Solution: Note the properties of XOR : 1. A ^ A = 0 2. 0 ^ A = A 3. A ^ (B ^ C) = (A ^ B) ^ C Thus we just XOR all integers to finally get the lonely element since all others will be made 0 for repeating twice. Complexity: 1. Space: O(1) 2. Time: O(N) int lonely_element(int input[], int N){ int result=0, i=0; for(i=0; i<N; i++) result ^= input[i]; return result; }

Write a function that takes an int array of size M, and returns (true/false) if the array consists of the numbers only within the range [N, N+M-1]. The array is not guaranteed to be sorted. For instance, {2,3,4} would return true. {1,3,1} would return true, {1,2,4} would return false. 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: No hint this time. Hit again for solution. Solution: Simply find out the maximum and minimum in one pass and check if N == (max - min + 1) Complexity: 1. Space: O(1) 2. Time: O(N) int check_range(int input[], int N){ int max = input[0], min = input[0], i; for(i=1; i<N; i++){ if(input[i] < min) min=input[i]; if(input[i] > max) max=input[i]; } return (max - min + 1) == N; }

Given an array of size N which contains all the numbers from 1 to N-1. Find the number which is repeated in O(N) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to N-1 ? 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: No hint this time. Hit again for solution. Solution: For integers use sum to find the repeated number. For floating numbers, use Hash tables. Complexity: 1. Space: O(1) [O(K), K >> N for hash table] 2. Time: O(N) int repetition_int(int input[], int N){ int i=0, sum=0; for(i=0; i<N; i++) sum += input[i]; return sum - (N*(N-1)/2); } float repetition_float(float input[], int N){ int i; for(i=0; i<N; i++){ if(hash_table_exists(input[i])) return input[i]; hash_table_insert(input[i]); } return -1.0; }

You are walking down a path when you come to two doors. Opening one of the doors will lead you to a life of prosperity and happiness, while opening the other door will lead to a life of misery and sorrow. You don't know which door leads to which life. In front of the doors are two twin brothers who know which door leads where. One of the brothers always lies, and the other always tells the truth. You don't know which brother is the liar and which is the truth-teller. You are allowed to ask one single question to one of the brothers (not both) to figure out which door to open. What question should you ask? 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: Doesn't the question name ring a bell itself. Hit again for solution. Solution: Ask "If I asked your brother what the good door is, what would he say ?". Both would point to wrong door.

You have two sand hourglasses, one that measures exactly 4 minutes and one that measures exactly 7 minutes. You need to measure out exactly 2 minutes. Using only these two hourglasses, how can you measure out exactly 2 minutes ? 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: Just think what type of actions can be responsbile for such result? Hit again for solution. Solution: 7x - 4y = 2 we have a simple soultion, x=2 and y=3 We have 7*2 - 4*3 = 2 So we start both simultaneously. When 4 completes invert it, next invert 7 when done, next invert 4 when done again twice. Time remaining for 7 to finish is 2 minutes now.

Write a function to add two integers without using mathematical operators (+, -, *, /). 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. Courtesy: Vibhaj Remarks: No remarks. Hit again for hints. Hints: No hint, think properly. One thing for sure you'll have to use some operators that are not mathematical. Hit again for solution. Solution: We use the logic used in digital circuits where sum = A XOR B and carry = A AND B. We simply add the carry again after shifting it 1 left till it become zero. Complexity: 1. Time: O(1) 2. Space: O(1) Code: int add(int a, int b){ int carry = 0; while(b){ carry = a & b; a = a ^ b; b = carry << 1; } return a; }

Given an array of N integers (both positive and negative), find the sub-sequence with largest absolute sum. For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest absolute sum is 11 with sub-sequence {-11}. 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. Courtesy: Vibhaj Remarks: A simpler variant was previously discussed [Largest consecutive sum]. Hit again for hints. Hints: Compare the maximum positive and negative sum. Hit again for solution. Solution: We use the same algorithm of O(N) here too first to get highest positive sum and then highest negative sum and find the one with higher absolute value as the answer. Complexity: 1. Time: O(N) 2. Space: O(1) Code: void largest_consecutive_sum(int input[], int N, int *start, int *end, int *max){ *start = *end = *max = -1; int current = -1; int sum = 0; for(int i=0; i<N; i++){ sum += input[i]; if(sum < 0){ sum = 0; current = i+1; } if(sum > *max){ *max = sum; *start = current; *end = i; } } } void largest_consecutive_absolute_sum(int input[], int N, int *start, int *end, int *max){ int pos_start, pos_end, pos_max, neg_start, neg_end, neg_max; int i; largest_consecutive_sum(input, N, &pos_start, &pos_end, &pos_max); for(i=0; i<N; i++){ input[i] = -1*input[i]; } largest_consecutive_sum(input, N, &neg_start, &neg_end, &neg_max); if(pos_max > neg_max){ *start = pos_start; *end = pos_end; *max = pos_max; } else { *start = neg_start; *end = neg_end; *max = neg_max; } }

You are standing in a pitch-dark room. A friend walks up and hands you a normal deck of 52 cards. He tells you that 17 of the 52 cards are face-up, the rest are face-down. These face-up cards are distributed randomly throughout the deck. Your task is to split up the deck into two piles, using all the cards, such that each pile has the same number of face-up cards. The room is pitch-dark, so you can't see the deck as you do this. How can you accomplish this seemingly impossible task ? 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 this time. Hit again for hints. Hints: Do you really think that I'll give you hint for this puzzle? :P Hit again for solution. Solution: Take 17 cards and make one pile and let the remaining be other pile. Then invert all 17 cards. Now both contains equal number of face-up cards. Initially, if x cards of 17 in first piles were face-up, in second pile there were (17-x) So inverting the first pile makes (17-x) cards face-up

Given an array of integers containing only 0s and 1s.You have to place all the 0s in even position and 1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa then keep the exceeding integers untouched. Do that in ONE PASS and without taking extra memory (modify the array in-place). For Example : Input Array: [0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1] Output Array: [0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1] 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. Courtesy: Vibhaj Remarks: No remarks this time. Hit again for hints. Hints: Find the wrong positions for 0 and 1 and swap them. Hit again for solution. Solution: Complexity: 1. Time : O(N) 2. Space : O(1) Code: void interleave_0_1(int input[], int N){ int i=0, j=1; while(1){ while(i < N && input[i] == 0) i += 2; while(j < N && input[j] == 1) j += 2; if(i < N && j < N){ input[i] ^= input[j]; input[j] ^= input[i]; input[i] ^= input[j]; } else break; } }

Devise an algorithm to print elements of linked list in reverse without reversing the linked list. State the time and space complexities. 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. Courtesy: Vibhaj Remarks: No Remarks. Hit again for hints. Hints: Use recursion. Hit again for solution Solution: A self explanatory code is here. Complexity: 1. Time : O(N) 2. Space : O(N) Code: void display_reverse(node *list){ if(list){ display_reverse(list->next); printf("%d\n", list->info); } }

Devise an efficient algorithm for finding the Nth element from last in a linked list. Eg. List [1, 2, 3, 4, 5, 6, 7, 8] 6th element from last = 3 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. Courtesy: Vibhaj Remarks: Just use your intution. Hit again for hints. Hints: No hints. Hit again for solution Solution: We use two pointers. The first pointer alone is moved N elements. Then both pointers are moved until first one reaches the end. Now the second pointer points to the Nth element from last. Complexity: 1. Time : O(N) 2. Space : O(1) Code: void nth_last(int *list, int N, int *result){ int *tmp = list, i=N; *result = list; while(N--) tmp = tmp->next; while(tmp = tmp->next) result = result->next; }

The captain of the ship needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game. The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position. Initially, standing people have numbers - 1,2,3,4,5... After first pass, people left are - 2,4,... After second pass - 4,.... And so on. You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected. 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. Courtesy: Vibhaj Remarks: No remarks this time. Hit again for hints. Hints: Generalize the pattern. Hit again for solution. Solution: The answer is the greatest power of 2 just less than N The problem was adapted from Codechef : http://www.codechef.com/problems/DCE05. The main problem is in optimizing the input/output. Interested students may try it out. Complexity 1. Time: O(1) 2. Space: O(1) Code: void power_2_floor(int N, int *result){ do { *result = N } while(N = (N & N-1)); }

Given a sequence of positive numbers, find the maximum sum that can be formed which has no 3 consecutive elements present. For example: consider the sequence 3000 2000 1000 3 10 Here, the answer would be 5013, by taking 3000, 2000, 3 & 10. Note that we can't form a sequence that takes 3000, 2000 & 1000 together because they are the consecutive elements of the array. Sample cases: 1 2 3 ans=5 100 1000 100 1000 1 ans=2101 1 1 1 1 1 ans=4 1 2 3 4 5 6 7 8 ans=27 Try to find an O(N) solution. N is the number of elements in the array. 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. Courtesy: Vibhaj Remarks: Take a look again, think more. Hit again for hints. Hints: The solution for this problem is by dynamic programing. Hit again for solution Solution: Complexity: 1. TIme : O(N) 2. Space : O(N) Code: int max_three(int[] input, int N){ int sum[] = new int[N+2]; sum[0] = 0; sum[1] = input[0]; sum[2] = input[0] + input[1]; for (int i=2; i<N ;++i){ sum[i+1] = max(input[i] + sum[i-1], input[i] + input[i-1] + sum[i-2]); sum[i+1] = max(sum[i+1], sum[i]); } return sum[N]; }