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]; }