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