# Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife ?
The cut (plane) should pass through the center of the two rectangles: the outer cake and the inner hollow area. Since any plane passing through the center of the cuboid will divide the volume in two halves, both the cake and hollow area are divided into two equal halves.
# Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.
Many solutions: Bit vector, sorting…
# How many points are there on the globe where by walking one mile south, one mile east and one mile north you reach the place where you started.
The answer is “many points”. The set of such points is given as {North pole, special circle}.
From north pole, walking one mile south followed by one mile east still keeps you one mile south of North pole.
The special circle consists of a set of points defined as follows. Let’s say you were to locate a spot near the South Pole where the circular distance “around” the Earth’s North-South axis is 1 mile. The path of such a journey would create a circle with a radius of approximately 840.8 feet (because C=2.r.pi). Call this point X. Now consider another point Y one mile north of X. The special circle is the circular path around North-South axis going through Y. If you begin you journey from any point (say Y1) on this special circle, and travel one mile south, you get to a point (say X1) on the circle of point X. Now one mile east will bring you back to X1, because circumference of circle of X is 1 mile. Then one mile North brings you back to Y1. (Answer supplied by Kristie Boman)
# In a X’s and 0′s game (i.e. TIC TAC TOE) if you write a program for this give a fast way to generate the moves by the computer. I mean this should be the fastest way possible.
The answer is that you need to store all possible configurations of the board and the move that is associated with that. Then it boils down to just accessing the right element and getting the corresponding move for it. Do some analysis and do some more optimization in storage since otherwise it becomes infeasible to get the required storage in a DOS machine.
# There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner.. what is the probability that they don’t collide.
All three should move in the same direction – clockwise or anticlockwise. Probability is 1/4.
# There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each man walks at a different speed. A pair must walk together at the rate of the slower mans pace.
Man 1:1 minute to cross
Man 2: 2 minutes to cross
Man 3: 5 minutes to cross
Man 4: 10 minutes to cross
1 and 2 cross together. 1 comes back. then 3 and 4 cross. 2 comes back. then 1 and 2 cross. Total time is 2+1+10+2+2 = 17.
# You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?
Take one pill from first, two from second, three from third and so on. Total pills are n(n+1)/2 and should weigh 10n(n+1)/2. If it weighs x gm less than that then the x’th jar is contaminated, since we took x pills from that jar which weighed 1 gm less.
# One train leaves Los Angeles at 15 MPH heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
If distance is X miles between NY and LA, then it takes X/(15+20) hours for the trains to collide, and bird will have travelled 25X/(15+20) = 5X/7 miles in that time.
# Imagine that you have 26 constants, labelled A through Z. Each constant is assigned a value in the following way: A = 1; the rest of the values equal their position in the alphabet (B corresponds to the second position so it equals 2, C = 3, etc.) raised to the power of the preceeding constant value. So, B = 2 ^ (A’s value), or B = 2^1 = 2. C = 3^2 = 9. D = 4^9, etc., etc. Find the exact numerical value to the following equation:
(X – A) * (X – B) * (X – C) * … * (X – Y) * (X – Z)
Answer is 0, because (X-X) is present in the product.
# You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest – it is either hollow while the rest are solid, or solid while the rest are hollow. You have a simple two-armed scale, and are permitted three weighings. Can you identify the odd ball, and determine whether it is hollow or solid.
Let the balls be numbered 1 to 12. Firstly, put 1-4 on one side and 5-8 on other side. If both are equal then one of 9-12 is odd. Then second try, weigh 9-10 vs 1-2, if equal, one of 11-12 is bad, else 9-10 is bad. Testing which one is bad can be done by (third try) weighing 11 or 9, respectively, with good ball 1. It also gives whether the odd ball is heavy or light.
Programming questions that require thinking
# Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all.
The basic idea is to draw one quadrant and replicate it to other four quadrants. Assuming the center is given as (x,y) and radius as r units, then start X from (x+r) down to (x) and start Y from y up to (y+r). In the iteration, keep comparing is the equation is satisfied or not within an error of one unit for x and y. If not then re-adjust X and Y.
# Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal.
void putlong(unsigned long x)
{
// we know that 32 bits can have 10 digits. 2^32 = 4294967296
for (unsigned long y = 1000000000; y > 0; y /= 10) {
putchar( (x / y) + ’0′);
x = x % y;
}
}
# Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]
if (x && !(x & (x-1)) == 0)
# What are the different ways to say, the value of x can be either a 0 or a 1.
Apparently the if then else solution has a jump when written out in assembly.
if (x == 0)
y=0
else
y =x
There is a logical, arithmetic and a datastructure soln to the above problem.
# I was given two lines of assembly code which found the absolute value of a number stored in two’s complement form. I had to recognize what the code was doing.
Pretty simple if you know some assembly and some fundaes on number representation.
# Give a fast way to multiply a number by 7.
Multiply by 8 (left shift by 3 bits) and then subtract the number.
(x < < 3) - x
# Write a function that returns the factorial of a number.
This is a typical, can-you-program warm-up question. Example 1 shows the iterative and recursive solutions. Notice that in both solutions, I check the input values and boundary conditions. Factorials of negative numbers are undefined, and the factorial of both 0 and 1 are 1. The functions in Example 1 handle these cases correctly, and they initialize all variables.
# Write a function that computes the nth number in the Fibonacci sequence.
Example 2 contains both the iterative and recursive solutions. The iterative version maintains variables to hold the last two values in the Fibonacci sequence, and uses them to compute the next value. Again, boundary conditions and inputs are checked. The 0th number in the Fibonacci sequence is defined as 0. The first number in the sequence is 1. Return -1 if a negative number is passed.
The recursive version of the Fibonacci function works correctly, but is considerably more expensive than the iterative version. There are, however, other ways to write this function recursively in C that are not as expensive. For instance, you could maintain static variables or create a struct to hold previously computed results.
# Write an implementation of strlen().
Given a char pointer, strlen() determines the number of chars in a string. The first thing that your strlen() implementation ought to do is to check your boundary conditions. Don't forget the case where the pointer you are given is pointing to an empty string. What about the case where the pointer is equal to NULL? This is a case where you should state your assumptions. In many implementations, the real strlen() doesn't check to see if the pointer is NULL, so passing a NULL pointer to strlen() would result in a segmentation fault. Making it clear to your interviewer that you are aware of both of these boundary conditions shows that you understand the problem and that you have thought about its solution carefully. Example 3 shows the correct solution.
# Switch the integer values stored in two registers without using any additional memory.
To swap the values, you can carry out the following instructions:
Reg_1 = Reg_1 + Reg_2;
Reg_2 = Reg_1 - Reg_2;
Reg_1 = Reg_1 - Reg_2;
# Write code for reversing a linked list.
NodePtr reversed=NULL, cur=head;
while(cur!=NULL)
{
//detach cur
head=head->next;
//link cur to reversed list
cur->next=reversed;
reversed=cur;
//move cur to next node
cur=head;
}
head=reversed;
# Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).
int main()
{
int a[10]={1, 2, 4, 4, 7, 8, 9, 14, 14, 20};
int i;
for (i = 0;i<9;i++)
{
if (a[i] != a[i+1])
printf(“%d\n”,a[i]);
}
return 0;
}
# Write an algorithm to detect loop in a linked list.
You are presented with a linked list, which may have a “loop” in it. That is, an element of the linked list may incorrectly point to a previously encountered element, which can cause an infinite loop when traversing the list. Devise an algorithm to detect whether a loop exists in a linked list. How does your answer change if you cannot change the structure of the list elements?
One possible answer is to add a flag to each element of the list. You could then traverse the list, starting at the head and tagging each element as you encounter it. If you ever encountered an element that was already tagged, you would know that you had already visited it and that there existed a loop in the linked list. What if you are not allowed to alter the structure of the elements of the linked list? The following algorithm will find the loop:
1. Start with two pointers ptr1 and ptr2.
2. Set ptr1 and ptr2 to the head of the linked list.
3. Traverse the linked list with ptr1 moving twice as fast as ptr2 (for every two elements that ptr1 advances within the list, advance ptr2 by one element).
4. Stop when ptr1 reaches the end of the list, or when ptr1 = ptr2.
5. If ptr1 and ptr2 are ever equal, then there must be a loop in the linked list. If the linked list has no loops, ptr1 should reach the end of the linked list ahead of ptr2.
# Given the time, devise an algorithm to calculate the angle between the hour and minute hands of an analog clock.
The important realization for this problem is that the hour hand is always moving. In other words, at 1:30, the hour hand is halfway between 1 and 2. Once you remember that, this problem is fairly straightforward. Assuming you don’t care whether the function returns the shorter or larger angle, Example 4 shows a solution to this problem.
# Devise an algorithm for detecting whether a given string is a palindrome (spelled the same way forwards and backwards). For example, “A man, a plan, a canal, Panama.”
For the sake of this problem, assume that the string has been stripped of punctuation (including spaces), and has been converted to a single case. The most efficient way to detect whether a string is a palindrome is to create two pointers. Set one at the beginning of the string, and one at the end. Compare the values at those locations. If the values don’t match, the string isn’t a palindrome. Otherwise, move each pointer inward and repeat the comparison. Stop when the pointers are pointing to the same position in the string (if its length is an odd-number) or when the pointers have “crossed” (if the string’s length is an even-number). Example 5 shows the correct solution.
# Given an eight-bit bitmap graphics file, devise an algorithm to convert the file into a two-bit ASCII approximation.
Assume that the file format is one byte for every pixel in the file, and that the approximation will produce one ASCII character of output for each pixel. This problem is easier to solve than it sounds. This is one of the tricks used in technical interview questions. Problems may be obscured or made to sound difficult. Don’t be fooled! Take the time to think about the core of the problem. In this case, all you want is an algorithm for reading the values in a file and outputting characters based upon those values.
Eight-bit numbers can be in the range from 0 to 255. Two-bit numbers are in the range from 0 to 3. Basically, we want to divide the 256 numbers specified by an eight-bit number into four ranges, which can be indicated by a two-bit number. So, divide the range of 0 to 255 uniformly into four separate ranges: 0 to 63, 64 to 127, 128 to 191, and 192 to 255.
You then have to assign an ASCII character to each of those four ranges of numbers. For example, you could use “_”, “~”, “+”, and “#”. Then, the algorithm is as follows:
1. Open the file.
2. For every byte in the file:
a. Read in one byte.
b. If the value is in the range 0..63, we’ll print ‘_’.
c. If the value is in the range 64..127, we’ll print ‘~’.
d. If the value is in the range 128..191, we’ll print ‘+’.
e. If the value is in the range 192..255, we’ll print ‘#’.
3. Close the file.
# Increment the variable next three different ways.
next = next + 1;
and
next++;
and
next += 1;
# Specify the skeletons of two C loops with the test at the top.
next = 0; /* setup */
while ( next < max) { /* test */ printf(“Hello “); /* body */ next++; /* update */ }
and
for ( next = 0; next < max; next++) /* setup,test */ /* and update */ printf(“Hello”); /* body */
# What does the following fragment do?
while((d=c=getch(),d)!=EOF&&(c!=’\t’||c!=’ ‘||c!=’\b’)) *buff++ = ++c;
Do the following until either the end of standard input or the variable c takes on the value of a tab, space, or backspace character: Store the character that succeeds the character stored in c into the current location pointed by buff. Then increment buff to point to the next location in memory. Meanwhile, d is assigned the same value as c and it is the value of d that is used in the comparison to EOF.
# Write an efficient C code for ‘tr’ program. ‘tr’ has two command line arguments. They both are strings of same length. tr reads an input file, replaces each character in the first string with the corresponding character in the second string. eg. ‘tr abc xyz’ replaces all ‘a’s by ‘x’s, ‘b’s by ‘y’s and so on.
have an array of length 26.
put ‘x’ in array element corr to ‘a’
put ‘y’ in array element corr to ‘b’
put ‘z’ in array element corr to ‘c’
put ‘d’ in array element corr to ‘d’
put ‘e’ in array element corr to ‘e’
and so on.
the code
while (!eof)
{
c = getc();
putc(array[/c]);
}
