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/)
Write a small lexical analyzer – interviewer gave tokens. expressions like “a*b” etc.
( Another from: http://www1.cs.columbia.edu/~kns10/interview/ )
Write a routine that prints out a 2-D array in spiral order! (another one from http://www1.cs.columbia.edu/~kns10/interview/)
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/)
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>
The way I found the problem on the web:
Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.
Kind of a trick question. What if the buckets only contained 1.1 cups of paint?
Since the paint is conserved we can say that if after the pouring back and fourth over N cycles (here N=1) an ammount a of paint is transfered from the red to the blue bucket then we can see that the relative ratios are:
[(X-A) Red / A Blue] in the red bucket and [A/(X-A)] in the blue bucket.
As logn as (X-A) is greater than A we have proven the above statement.
There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can’t change them. Identify each switch with its bulb.
Assumptions:
Two bulb Solution
{S1 S2} = {a,b} –> Starting test state – wait for an hour.
{S1 !S2} = {a,!b} –> Toggle switch states and open the door.
Tests 1 and 2 uniquely identify S1, and you get S2 by process of elimination.
Three bulb Solution
Decoding then is
Four temperatures possible: Ambient, Y, X-Y, X+Y
From 5 above we can collapse the temperature range to Ambient , {Y, X-Y}, X+Y. So just picking a X/Y ratio that allows for adaquade difference in heating and cooling times is all that is needed.