Write an algorithm to detect a loop in a link list
Month: June 2009
Categories
Print out a binary tree
Write a function and the node data structure to visit all of the nodes in a binary tree
(Got it from: http://www1.cs.columbia.edu/~kns10/interview/)
Categories
Detect overflow in addition
Whats the simples way to check if the sum of two unsigned integers has resulted in an overflow.
(Another from http://www1.cs.columbia.edu/~kns10/interview/)
Cool trick. Useful to know beyond just interviews.
Register_1 = Register_1 + Register_2;
Register_2 = Register_2 – Register_1;
Register_1 = Register_1 – Register_2;
Starting
1) R1=A
2) R2=B
R1 = R1 + R2
1) A+ B
2) B
R2 = R2 – R1
1)A +B
2) A+ B – B = A
R1 = R1 – R2
1) A+B -A = B
2) A
Done
1)R1=B
2)R2=A
Given two strings S1 and S2. Delete from S2 all those characters which occur in S1 also and finally create a clean S2 with the relevant characters deleted.
(Another problem from http://www1.cs.columbia.edu/~kns10/interview/)
Categories
Write a simple lexical analyzer
Write a small lexical analyzer – interviewer gave tokens. expressions like “a*b” etc.
( Another from: http://www1.cs.columbia.edu/~kns10/interview/ )
Categories
Spiral print a 2D array
Write a routine that prints out a 2-D array in spiral order! (another one from http://www1.cs.columbia.edu/~kns10/interview/)
Categories
Implement uniqe for a sorted array
Write code to extract unique elements from a sorted array. e.g. (1,1,3,3,3,5,5,5,8,8,8,8) -> (1,3,5,9)
Slow ball question but good for practice. (I got it from http://www1.cs.columbia.edu/~kns10/interview/)
Categories
Count the bits in a 32 bit integer
Give a very good method to count the number of ones in a 32 bit number. (caution: looping through testing each bit is not a solution). (Got this question from http://www1.cs.columbia.edu/~kns10/interview/ )
Same technique can be used to find loops in a liked list. If you advance through the list one pointer at rate X, and another pointer through the list at rate (1/2)X then when the faster pointer is at the end of the list the slower pointer will be pointing to the center element of the list.
<pre class=code>
// findCenterElement – finds the element at the center of the list
node *findCenter(node *curList){
node *centerNode = curList;
node *curNode = curList;
if(curList == (node *)NULL)
return((node *)NULL);
if(curNode->next != (node *)NULL){
while(((curNode->next)->next) != (node *)NULL)
{
curNode = (curNode->next)->next;
centerNode = (centerNode->next);
}
}else{
return(curNode);
}
return(centerNode);
}
</pre>