Prepare IT Interviews

Question:  Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. Answer:  We can do a binary search with some modified checks. public int rotatedSearch(int[] values, int start, int end, int x){ if(values[start] == x){ return start; } else if(values[end] == x){ return end; } else if(end - start == 1) { return -1; } int middle = (start + end) / 2; if(values[start] <= values[middle]){ if(x <= values[middle] && x >= values[start]){ return rotatedSearch(values, start, middle, x); } else { return rotatedSearch(values, middle, end, x); } } else if(values[middle] <= values[end]){ if(x >= values[middle] && x <= values[end] ){ return rotatedSearch(values, middle, end, x); } else { return rotatedSearch(values, start,

Question:  How would you use stacks to implement a queue? Answer:  So how could we go about doing this? What if we used two stacks and used one as the incoming stack and the other as the outgoing stack? A queue is a FIFO structure, so when we enqueue something, we need to make sure that it does not get popped off before something that was already there. Similarly, when we dequeue something, we have to make sure that elements that were inserted earlier get ejected first. What’s better than some code! Stack in; Stack out; void enqueue( int value ) { while( !out.isEmpty() ) { in.push( out.pop() ); } in.push( value ); } int dequeue() { while( !in.isEmpty() ) { out.push( in.pop() ); } return out.pop(); }

Question:  Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’. Answer:  Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic. char returnFirstNonRepeatedChar( char * str ) { int i, repeated = 0; int len = strlen(str); for( i = 0; i < len; i++ ) { repeated = 0; for( j = 0; j < len; j++ ) { if( i != j && str[i] == str[j] ) { repeated = 1; break; } } if( repeated == 0 ) { // Found the first non-repeated character return str[i]; } } return ''; } This approach seems to work perfectly well. But

Question:  Write a function that determines the number of bits set to 1 in the binary representation of an integer. Answer:  Going by the brute force approach, it would be easy to come up with the following solution. If the least significant bit of a number is 1, it will return a result of 1 when we AND it with 1. Using this logic, we can shift bits in the number to the right and keep testing if the least significant bit is 1. When there are no 1’s left in the number, it will become zero. Here’s some code to illustrate this simple logic. int numOnesInInteger( int num ) { int numOnes = 0; while( num != 0 ) { if( ( num & 1 ) == 1 ) { numOnes++; } num = num >> 1; } return numOnes; } Think we can do better? The above algorithm runs in O(n) where n in the number of bits in the integer. Maybe we can make this a tad better. But this would need some real creative bit manipulation skills. So let’s think, wha

Question:  You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be placed in the jars. Answer:  Seems tricky at first right? Given that the number of red and blue marbles are the same, you would tend to think that the odds are 50-50. You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%. So lets think of a better way to distribute the marbles. What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice).  Now that you have 49 red marbles left in the other j

Question:  The probability of a car passing a certain intersection in a 20 minute windows is 0.9. What is the probability of a car passing the intersection in a 5 minute window? (Assuming a constant probability throughout) Answer:  This is one of the basic probability question asked in a software interview. Let’s start by creating an equation. Let  x  be the probability of a car passing the intersection in a 5 minute window. Probability of a car passing in a 20 minute window = 1 – (probability of no car passing in a 20 minute window) Probability of a car passing in a 20 minute window = 1 – (1 – probability of a car passing in a 5 minute window)^4 0.9 = 1 – (1 – x)^4 (1 – x)^4 = 0.1 1 – x = 10^(-0.25) x = 1 – 10^(-0.25) =  0.4377

Question:  In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same) Answer:  This is a very simple probability question in a software interview. This question might be a little old to be ever asked again but it is a good warm up. Assume there are C number of couples so there would be C boys. The number of girls can be calculated by the following method. Number of girls = 0*(Probability of 0 girls) + 1*(Probability of 1 girl) + 2*(Probability of 2 girls) + … Number of girls = 0*(C*1/2) + 1*(C*1/2*1/2) + 2*(C*1/2*1/2*1/2) + … Number of girls = 0 + C/4 + 2*C/8 + 3*C/16 + … Number of girls = C (using mathematical formulas; it becomes apparent if you just sum up the first 4-5 terms) The proportion of boys to girls is  1 : 1 .

Question:  You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer:  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it? Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time. When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After pick

Question:  Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide? Answer:  So let’s think this through. The ants can only avoid a collision if they all decide to move in the same direction (either clockwise or anti-clockwise). If the ants do not pick the same direction, there will definitely be a collision. Each ant has the option to either move clockwise or anti-clockwise. There is a one in two chance that an ant decides to pick a particular direction. Using simple probability calculations, we can determine the probability of no collision. P(No collision) = P(All ants go in a clockwise direction) + P( All ants go in an anti-clockwise direction) = 0.5 * 0.5 * 0.5 + 0.5 * 0.5 * 0.5 =  0.25

Question:  Is your machine little or big endian? Answer:  Let first take a look at the solution before we discuss about it. int isLittleEndian( void ) { unsigned int temp = 0x12345678; char * tempAddress = &temp; if( *tempAddress == 0x12 ) { return 0; // Indicating False } else { return 1; // Indicating True } } To answer this, you have to obviously know what little and big endian are. Also you need some basic understanding of variable assignments for data types of varying sizes. A major mistake which you could make is with the temp variable. When I was asked this question, I answered it by taking a fixed address for temp which is insanely dangerous (I know I was dumb). The address could have been used for something else or even been a reserved address for all you know. By creating a local variable, temp will be placed on the stack so we don’t have to worry about whether it will be safe or not.

Question:  How would you find a loop in a singly-linked list? Answer:  This is a very typical tech interview question that has a very elegant solution that runs in O(n) time and O(1) space. Also referred to as the “Tortoise and Hare Algorithm”,  the solution uses a fast pointer (traversing the list two items at a time) and a slow pointer (traversing the list one item at a time). If there is a loop, then the fast pointer will go around the loop twice as fast as the slow pointer. At one point, these two pointers will point to the same item. Here’s some code to make this clearer. bool hasLoop( Node *startNode ) { Node *slowNode, *fastNode; slowNode = fastNode = startNode; while( slowNode && fastNode && fastNode->next ) { if( slowNode == fastNode->next || slowNode == fastNode->next->next ) { return true; } slowNode = slowNode->next; fastNode = fastNode->next->next; } return

Question:  Reverse a Linked-list. Write code in C. Answer:  There are multiple ways to go about this. Let’s first look at a recursive solution. Node * reverse( Node * ptr , Node * previous) { Node * temp; if(ptr->next == NULL) { ptr->next = previous; return ptr; } else { temp = reverse(ptr->next, ptr); ptr->next = previous; return temp; } } reversedHead = reverse(head, NULL); Now for a non-recursive solution. Node * reverse( Node * ptr ) { Node * temp; Node * previous = NULL; while(ptr != NULL) { temp = ptr->next; ptr->next = previous; previous = ptr; ptr = temp; } return previous; } I personally prefer the non-recursive solution but it is always good to know both of them.

Question:  You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C. Answer:  To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. So what do we do? We can easily get away by moving the data from the next node into the current node and then deleting the next node.  This solution has O(1) runtime. Here’s some code to illustrate this simple logic. void deleteNode( Node * node ) { Node * temp = node->next; node->data = node->next->data; node->next = temp->next; free(temp); } Some things to consider. This method could pose potential problems. For instance, let’s consider we have a linked list A -> B -> C -> D and we are given a pointer to B to delete it. Theoretically, you would expect B to be delet

uestion:  Devise an algorithm to determine the Nth-to-Last element in a singly linked list of unknown length. If N = 0, then your algorithm must return the last element. Answer:  Given that the only way to traverse a singly linked list is forwards from the head, it is not possible to just count N elements from the end of the linked list. Furthermore, the length of the linked list is unknown. We could traverse the list once to determine the number of elements and then traverse the list again to stop at the Nth element from the last element. But this seems a little inefficient. What if we could use 2 pointers? So what if we use a current pointer and another pointer that is N elements behind the current pointer. When the current pointer reaches the end of the list, the second pointer will be pointing to the element N elements from the end of the list. Here’s some code to illustrate this logic. Node * findNToLastNode( Node *head, int N ) { int i = 0; Node *current, *behind

Question:  You are given two hourglasses. One measures 4 minutes and one measures 7 minutes. How would you measure exactly 9 minutes? Answer:  This question is similar to 4 Quarts of Water. With water, we were able to fill and pour out the pail multiple times. We can use the same logic and easily come up solutions which start measuring 9 minutes somewhere in the middle of the procedure but those will not be ideal. If possible, we want to measure the 9 minutes right from the start. Step Time 4 minute timer 7 minute timer 1 0 min Start Start 2 4 mins Flip 3 minutes left 3 7 mins 1 minute left Flip 4 8 mins Stop Flip (1 minute left) 5 9 mins Stop

Question:  You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer:  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it? Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time. When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After pick

Question:  You are standing outside a room next to three switches, all of which are off. Each switch operates a different light bulb in the room. The room door is closed, so you cannot see which switch operates which bulb. You are only allowed to go into the room once. Determine which switch operates which bulb. Answer:  Stumped? The issue lies in the fact that there are only two possible positions for each switch (on or off), but three bulbs to identify. Identifying one bulb is super easy, just set one switch on and then go into the room to check which one is on. But then, how do we detect the other two? So let’s think deeper, what are the other properties of a light bulb operated by a switch? Light bulbs definitely produce light, but they also produce heat (a not so very important characteristic!). Any chance we can use this idea to help solve our problem? Since a light bulb would take sometime to lose its heat after being switched off, you could still determine if it had ever

void permutate( char[] str, int index ) { int i = 0; static lastChar = 0; if( index == strlen(str) ) { // We have a permutation so print it printf(str); return; } // Permutate once without any swaps. permutate( str, index + 1 ); lastChar = str[index]; for( i = index + 1; i < strlen(str); i++ ) { if( lastChar == str[i] ) { continue; } else { lastChar = str[i]; } swap( str[index], str[i] ); // It doesn't matter how you swap. permutate( str, index + 1 ); swap( str[index], str[i] ); } } permutate( sort("Hello World"), 0 );

Question:  A farmer bought a goat, a wolf and a cabbage from the market. On his way home, he has to cross a river. He has a small boat which only allows him to take one thing with him at a time. The farmer cannot leave the cabbage and the goat together (the goat would eat the cabbage) nor can he leave the goat and the wolf together (the wolf would eat the goat). How does he cross the river without losing any of the things he bought? Answer:  Seems easy enough, right? So let’s start with the goat. The farmer takes the goat with him and leaves it on the other side of the river. Then he comes back to the side of the river where he left the wolf and cabbage together. He then takes the cabbage with him. When he reaches the other side, he leaves the cabbage and brings the goat back with him. Then he leaves the goat and takes the wolf with him. He then drops the wolf off with the cabbage and finally comes back for the goat. So this way, the farmer avoids leaving the goat and the cabbage o

Question:  You are give two red balls, two green balls and two yellow balls. One ball from each color is heavier than the other one. All the heavier balls weigh the same and all the lighter balls weigh the same. You are only provided with a weighing balance. How many tries would it take to identify which one is heavier and which one is lighter? Answer:  Let’s label the balls R1, R2 (Red ones), G1, G2 (Green ones) and Y1, Y2 (Yellow ones). First weigh R1, G1 on one side and R2, Y1 on the other. If they are equal, we know that one of G1 or Y1 is heavy. We can just weigh them both and find out which one is heavier. If G1 is heavy, the heavier set is {G1, R2, Y2} and the others are lighter. If Y1 is heavy, the heavier set is {G2, R1, Y1}. If R1, G1 is heavy, we know that either G1 is heavy or Y1 is light. We proceed to weigh G1, Y1 with G2, Y2. If they are equal, G1 is the heavy one. The heavier set is {G1, Y2, R1}. If G1, Y1 is heavy, G1 and Y1 are both heavy. The heavier set is

Question:  Write an algorithm to print all possible combinations of characters in a string. Answer:  Any thoughts? One thing is for sure, we can definitely use some recursive logic here. Let’s approach this problem methodically. Since we need to generate combinations, we can start with a single character and then continue to add a character to combinations we have seen so far. Let’s use “abc” as an example. Here’s some code in Java (for a change :)) to achieve what we’ve described above. void combine(String instr, StringBuffer outstr, int index) { for (int i = index; i < instr.length(); i++) { outstr.append(instr.charAt(i)); System.out.println(outstr); combine(instr, outstr, i + 1); outstr.deleteCharAt(outstr.length() - 1); } } combine("abc", new StringBuffer(), 0);

Question:  How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut. Answer:  Simple question right? There are two possible solutions to this problem. People often overlook the easier solution to this problem. Let’s start with the easiest solution. If you make one straight horizontal cut along the height of the cake, the resulting slices are of equal sizes. But this solution may not work so well on a cake with icing. So let’s rethink. In general, when a straight cut is made at any angle through the center of a  rectangle, the resulting pieces are always of equal area. So let’s consider our situation. What if we make a straight cut such that it passes through the center of both the rectangles? Since the cut halves both the rectangles, the resulting two pieces are guaranteed to have equal area. Each piece has an area equal to hal

Question:  How many times a day do the minute and hour hands of a clock overlap? Answer:  Did you think the answer was 24 times? Well if you did, it’s time you think again. Let’s do some math. In T hours, the minute hand completes T laps. In the same amount of time, the hour hand completes T/12 laps. The first time the minute and hour hands overlap, the minute hand would have completed 1 lap more than the hour hand. So we have T = T/12 + 1. This implies that the first overlap happens after T = 12/11 hours (~1:05 am). Similarly, the second time they overlap, the minute hand would have completed two more laps than the hour hand. So for N overlaps, we have T = T/12 + N. Since we have 24 hours in a day, we can solve the above equation for N 24 = 24/12 + N 24 = 2 + N N = 22 Thus, the hands of a clock overlap 22 times a day. Thus the hands of the clock overlap at 12:00, ~1:05, ~2:10, ~3:15, ~4:20, ~5:25, ~6:30, ~7:35, ~8:40, ~9:45, ~10:50. Note that there is no ~11:55. This bec

Question:  How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started? Answer:  The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again!  Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile. So what if we were standing at any point one mile north of this ring? If we walked one mile south, we would be on the ring. Then one mile east would bring us back to same point on the ring (since it’s circumference is one mile). One mile north from that point would bring us back to the point were we started from. If we count, there would be an infinite number of points north of this one mile ring. So what’s our running total of possible points? We have 1 + infinite points. But we’re not done yet! Co

Question:  A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again, and so forth. The bird continues to do this until the trains collide. How far would the bird have traveled in the meantime? Answer:  Yes, you read it right. The bird is actually the fastest moving object in the problem! Knowing that the bird is the faster than both the trains, you would only imagine that theoretically, the bird could fly an infinite number of times between the trains before they collide. This is because you know that no matter how close the trains get, the bird will always complete its trip before the crash happens. At the tim

Question:  You have two sticks and matchbox. Each stick takes exactly an hour to burn from one end to the other. The sticks are not identical and do not burn at a constant rate. As a result, two equal lengths of the stick would not necessarily burn in the same amount of time.  How would you measure exactly 45 minutes by burning these sticks? Answer:  This puzzle used to be asked in Wall Street interviews long time ago. It is very rare for this question to be asked now but it is a very good question to help you think a little outside the normal thought process. The answer is really simple. Since the sticks do not burn at a constant rate, we can not use the length of the stick as any sort of measurement of time. If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely. 0 minutes – Light stick 1 on both sides and stick 2 on one side. 30 minutes – Stick 1

Question:  A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground? Answer:  One would think that the duck could swim directly away from the fox. So the duck would have to swim a distance r. The fox would have to cover half the circumference of the pond (pi * r). Since the fox is four times faster than the duck, we know that (pi * r) < (4 * r) This would make it seem like it is impossible for the duck to escape. So how could the duck make life most difficult for the fox? If the duck just tries to swim along a radius, the fox could just sit along that radius and the duck would continue to be trapped. The duck could swim in concentric c

Question:  You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be placed in the jars. Answer:  Seems tricky at first right? Given that the number of red and blue marbles are the same, you would tend to think that the odds are 50-50. You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%. So lets think of a better way to distribute the marbles. What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice).  Now that you have 49 red marbles left in the other j

Question:  There are four dogs each at the corner of a unit square. Each of the dogs starts chasing the dog in the clockwise direction. They all run at the same speed and continuously change their direction accordingly so that they are always heading straight towards the other dog. How long does it take for the dogs to catch each other and where? Answer:  Let the dogs be A, B, C and D where A is chasing B, B is chasing C, C is chasing D and D is chasing A. All the dogs will eventually meet in the center of the square. Since all the dogs move in symmetry, the only logical answer to the location of their meeting is the center of the square. At any point in time, dog A is perpendicular to dog B and B perpendicular to C and so on. Dog A moves towards dog B but dog B does not move towards or away from dog A since it is moving perpendicular to dog A. Therefore, the distance that dog A needs to cover to reach dog B is the same as the original distance between them, one unit. The spe

Question:  You are given  b  boxes and  n  dollar bills. The money has to be sealed in the  b  boxes in a way such that without thereafter opening a box, you can give someone a requested whole amount of dollars from 0 to  n . How should  b  be related to  n  for this to happen? Answer:  Stumped? Let’s think of an example to approach this problem. Say we have $100. A good approach to distributing $100 would be the binary number system. So you’d have $1, $2, $4, $8, $16, $32 in the first six boxes. We can’t fill the next box with $64 dollars because we are only left with $37 dollars (from a total of $100). So we’d have to put $37 in the seventh box. To supply any requested amount, we’d have to use a combination of these boxes. To find out the restrictions on the values of b and n, we have to think of different scenarios. For instance, with a million dollars and just one box, we would never be able to dispense any requested amount less than a million. However, if we are ever in a

Question:  John and Matt decide to play a game using a deck of cards. The game involves flipping two cards at a time. If both cards are black, they go into John’s pile and if both cards are red, they go into Matt’s pile. If one card is red and one card is black, they go into a discard pile. The game is played until all 52 cards have been flipped. The person with the most cards in their pile wins. If there is a tie, John wins. If Matt has more cards than John, then John pays Matt a dollar. What is the chance of Matt getting a dollar? Answer:  Any guesses? The chance of Matt getting any money is zero. Do you know why? Say the deck is arranged in a way such that there are 13 black pairs. In this situation, John gets 13 black pairs. And since there are no other black cards left, Matt gets 13 red pairs too. So there’s a tie and John wins. Suppose there are 12 black pairs in the deck. In this case, there would be 2 black cards left in the deck that would pair up with 2 other red card