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

There are 5 thieves. They are all numbered one to five. They have 500 pieces of gold which need to be distributed among themselves. First the number 1 distributes it and after that a voting is done : if he gets majority votes his distribution is carried out else he is killed, if the votes are equal, then also distribution is done his way. If he is killed then next numbered person does the distribution and this goes on till number 5. Each thief values his life more than the gold. So how does the first thief distribute gold to get maximum and to not get killed also ? 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: First of all try to understand the problem. Hit again for hints. Hints: Think first for small numbers and then generalize the pattern. Solution: Observing the pattern: For 2 thieves, the proposal would be (500, 0) as even if second disagrees, it does not matter. For 3 thieves, the proposal would be (499, 0, 1). In this case, second will disagree but third will agree because if he disagrees, then 2nd will propose next as (500, 0) and he would get nothing. So on for 5 thieves, the proposal is (498, 0, 1, 0, 1)

Two friends decide to meet at a cafe between 11 am and 12 pm i.e. one hour. They also decide that the one who reaches before the other waits for 5 minutes and if the other does not arrive he leaves. What is the probability of their meeting ? 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 imagine dude :P. Hit again for hints. Hints: Are you not able to solve this? or You want to check the solution. Hit again for Solution Solution: The probability is found using areas. The colored area represents the successful meeting since the difference between x and y co-ordinates of any point in the colored area is less than or equal to 5 on absolute value. Enlarge the image by clicking on it to see the answer

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. Count of 1 is not indicated. Write a program to find RLE of given string. Eg. input = "aabbbcddeef" RLE = "a2b3cd2e2f" input = "aaabbcddeeeef" RLE = "a3b2cd2e4f" 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 remark dude :P. Hit again for hints. Hints: This is an intelligent problem, try to solve it without a hint. Hit again for Solution Solution: We simply use a switch while checking each character in input and count them if equal and print the count if count is greater than one. Complexity: 1. TIme : O(N) 2. Space : O(1) Code: void rle_encode(char[] input, int N, char[] output){ int index = 0, count = 1; char last = input[0]; for(int i=1; input[i]; i++){ if(last == input[i]){ count++; } else { output[index++] = last; if(count > 1){ output[index++] = count + '0'; count = 1; } last = input[i]; } } output[index++] = last; if(count > 1){ output[index++] = count + '0'; } }

You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest. You have a simple two-armed scale, and are permitted three weighing. Can you identify the odd ball, and determine whether it is heavier or lighter than the rest ? 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 remark dude :P. Hit again for hints. Hints: Its a puzzle to puzzle you. No hints will be provided. Hit again for solution. Solution: Due to some problem while formatting the answer, I was unable to write here. So please find the image of the answer for this question.

Given an integer N. Devise an algorithm to find out the smallest integer greater than N having the same number of bits set as that of N. (When a bit is 1, we say it is set) 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: Use concepts of bit manipulation. Hit again for hints. Hints: Try to find out general formula for number having same number of set bits. Hit again for solution Solution: Suppose N has last x bits 0 and then y bits 1, then in general the next number having same number of set bits is given by N + 2^(y-1) + 2^x - 1 -> Now 2^x is given by N&-N -> Suppose M = N + 2^x -> Similarly 2^(x+y) is given by M&-M -> So we get 2^(y-1) by (2^(x+y)/2^x >> 1) Complexity : Time : O(1) Space : O(1) Code : int next_equal_setbits(int N){ int K1 = N & -N; int M = N + K1; int K2 = M & -M; return K2 + ((K2/K1)>>1) - 1; }

Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N). 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: Find all the combinations first [:)]. I hope this was obvious. [:P] Hit again for hints. Hints: list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed. Hit again for solution. Solution: We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed. Then for each combination we permute them using another recursive procedure Complexity : Time : O(N!) Space : O(N!) when storing results; O(1) if directly output the result Code : void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } void select(char *input, int start, int N, char *selection, int length, int K, stack<string> &combinations){ if(start <= N){ if(length == K){ selection[length] = '\0'; combinations.push(string(selection)); } else { select(input, start + 1, N, selection, length, K, combinations); selection[length] = input[start]; select(input, start + 1, N, selection, length + 1, K, combinations); } } } void permute(char *input, int index, int N, stack<string> &permutations) { if (index == N) permutations.push(string(input)); else { for (int i = index; i < N; i++) { swap(input + index, input + i); permute(input, index + 1, N, permutations); swap(input + index, input + i); } } } void all_permutations(char *input, int K, stack<string> &permutations){ int N = strlen(input); stack<string> combinations; char *selection = new char[K+1]; char *temp = new char[K+1]; select(input, 0, N, selection, 0, K, combinations); while(!combinations.empty()){ strcpy(temp, combinations.top().c_str()); permute(temp, 0, K, permutations); combinations.pop(); } }