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

You stand before a 100-story building with two eggs. Using only these two eggs, you must figure out the highest floor from which you can drop an egg such that the egg won't break when it hits the ground (we'll call this the "highest safe floor"). Every floor is equally likely to be the highest safe floor, including the top floor, and it's also just as likely that the egg will break from every floor. You can assume that if you drop an egg and it doesn't break, its shell is just as strong as it was before you dropped it. If you want to minimize the expected number of drops you have to perform, what strategy should you use for picking which floors to drop the eggs from ? 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: This is a famous problem with dynamic programming solution. Hit again for solution. Solution: Here I paste the solution from a webpage : The key insight to solving this problem is to realize that if you drop and egg and it doesn't break, then you are essentially going to be performing the same problem for a building of a shorter size. For example, if you were to drop an egg from floor 60 and it didn't break, you would then be solving the same problem for floors 61-100, which is like solving it on a 40-story building. Another important realization is that if your first egg breaks, you must go down to the the highest floor that you know is "safe" (or to the bottom floor if you don't know of any safe floors), and then go up one floor at a time, dropping the egg at each floor until it breaks. This is the only way to ensure that you'll then find the highet safe floor. Let's generalize these ideas. Assume we decide to drop the first egg from floor k. If it breaks, then we'll have to go down to floor 1 and drop the second egg from each floor up to (k-1), or until it breaks. In this case, we expect about k/2 more drops on average, since each of the floors below floor k is is equally likely to be the highest safe floor. In fact, the exact number of drops to expect on average is (1 + 2 + ... + (k-1) + (k-1)) / k. We'll leave it as an exercise to the reader to see why. If it doesn't break, then it's as if we're considering the same problem on a building of size (100 - k), where the bottom floor is floor k+1. There is some probability of the first egg breaking from floor k. It's actually fairly straightforward to see that this probability is (k/101), because there are 101 possible scenarios (the scenarios in which each floor is the highest safe floor, plus the scenario in which all floors are unsafe). For the general case of an n-floor building, this probability is k/(n+1) Thus the probability of the egg not breaking is (1 - k/101), or for the general case, (1 - k/(n+1)) This leads us to define the "Best" formula. The function Best(n), should return the best number of expected drops we can attain for a building with n stories. We also define the function Best(n,k), which should return the best expected number of drops we can attain for a building with n stories if our first drop is from floor k. Best(100, k) = 1 + (probability_of_breaking_from_floor_k * expected_number_of_drops_with_sequential_dropping_starting_at_floor_1) + (probability_of_not_breaking_from_floor_k * Best(100-k)) This formula is based on basic probability theory. The first 1 in the sum is for the current drop. Then we add the expected number of additional drops if the current egg does or does not break, each weighted by the probability of that situation occurring. This gives us the expected total number of drops. We are looking for Best(100), which we can find by calculating Best(100,k) for all values of k between 1 and 100, and picking the one that returns the minimal value. The value of k associated with this minimal value is the floor we should drop the first egg from. This formula isn't solvable as is, because it is recursive (it includes a call to the Best() function within itself). But we can see that the recursive call to Best() always uses a number less than 100. This suggests that if we can build up the values for Best() starting at Best(1), then we can use a program to iteratively build up a solution for Best(100)

A poor farmer went to the market to sell some peas and lentils. However, as he had only one sack and didn't want to mix peas and lentils, he poured in the peas first, tied the sack in the middle, and then filled the top portion of the sack with the lentils. At the market a rich innkeeper happened by with his own sack. He wanted to buy the peas, but he did not want the lentils. Pouring the goods anywhere else than in sacks (eg. on the ground, table etc.) is considered as devaluing. Trading sacks is not allowed. The farmer can’t cut a hole in his sack. How would you transfer the peas to the innkeeper’s sack, which he wants to keep, without soiling the produce ? 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: Don't you see the title. It is simply asking for desi jugad :). Hit again for solution. Solution: 1. Transfer lentils to innkeeper's sack. 2. Hold tightly in the middle of innkeeper's sack and turn it inside out. The open top portion is moved up so that it form another part of sack while the middle is still held tightly. 3. The peas is then transferred to this part. 4. The farmer's sack is kept below and release the hand holding the middle tightly to pour lentils back to farmer's sack.

Given a N x N matrix with 0s and 1s. Devise an algorithm such that whenever you encounter a 0 make the corresponding row and column elements 0. Eg. Input 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 Output 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 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: No hint buddy :P. Hit again for solution. Solution: We keep two arrays for rows and columns with 0 indicating the corresponding row/column contains at least one 0. Finally we use these arrays to set the required cells to 0. Complexity: 1. Time : O(N^2) 2. Space : O(N) Code: void matrix_set_zero(int *input, int N){ int *row = new int[N]; int *col = new int[N]; for(int i=0; i<N; i++){ row[i] = col[i] = 1; } for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ row[i] &= input[i][j]; col[j] &= input[i][j]; } } for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ input[i][j] = row[i] & col[j]; } } }

Given two sorted arrays of size M and N. Find Kth smallest element in the union of the two arrays in constant space. (i.e. without using additional space). 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. Both the arrays are sorted. Hit again for hints. Hints: The Kth smallest element will be within first K elements of both arrays. Solution: The Kth element will be found within first K elements of both arrays, so we consider only these elements or whole array if size is less than K We use recursive procedure. We compare (K/2)th element in arrays A(0 K) and B(0 K) if A(K/2) < B(K/2) we recursively find (K-K/2)th smallest element in A(K/2+1 K) and B(0 K/2) eliminating first K/2 elements from A else if A(K/2) > B(K/2) we recursively find (K-K/2)th smallest element in B(K/2+1 K) and A(0 K/2) eliminating first K/2 elements from B if A(K/2) == B(K/2) return A(K/2) as answer Boundaries must be checked in the procedure There are two solutions possible for this problem. I am also giving the linear O(N+M) solution which is simple but less efficient. Complexity: 1. TIme : O(log N + log M) 2. Space : O(1) Code: void kth_smallest(int[] A, int M, int[] B, int N, int K, int &result){ int a_high = (M < K) ? M : K; int b_high = (N < K) ? N : K; result = find_kth(A, 0, a_high, B, 0, b_high, K); } int find_kth(int[] A, int a_low, int a_high, int[] B, int b_low, int b_high, int K){ // boundary cases if(a_low > a_high) return B[b_low + K - 1]; if(b_low > b_high) return A[a_low + K - 1]; int mid = (K+1)/2; // finding ceiling of K/2 if(A[mid] == B[mid]) return A[mid]; else if(A[mid] < B[mid]) return find_kth(A, a_low + mid+1, a_high, B, b_low, b_low + mid, mid); else if(A[mid] > B[mid]) return find_kth(A, a_low, a_low + mid, B, b_low + mid + 1, b_high, mid); } void kth_smallest_linear(int[] A, int M, int[] B, int N, int K, int &result){ int i=0, j=0; for( ; K; K--){ if(i >= M){ result = B[j + K - 1]; break; } if(j >= N){ result = A[i + K - 1]; break; } if(A[i] == B[j]){ result = A[i++]; j++; } else result = (A[i] < B[j]) ? A[i++] : B[j++]; } }