1. If you are on a boat and you throw out a suitcase, will the level of water increase?

2. Given a simple program designed to take inputs of integers from 1-1000 and to output the factorial value of that number, how would you test this program? You do not have access to the code.

3. How would you weigh a plane without using scales?

4. Given a string, search it in a set of strings (say among 1000s of string). What data structure would you use to store those 1000 strings and get the results fastest?

Tree sort of Data Structure

5. Write a routine that takes input as a string such as   "aabbccdef" and o/p "a2b2c2def"     or          "a4bd2g4" for "aaaabddgggg"

6. What new feature would you add to MS WORD if you were hired?

7. Mike has $20 more than Todd. How much does each have given that combined they have $21 between them. You can't use fractions in the answer. (Hint: This is a trick question, pay close attention to the condition)

8. How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?

time O(N) and space O(1)

Use two pointers.

// error checking and checking for NULL at end of list omitted
p1 = p2 = head;

do {
p1 = p1-gt;next;
p2 = p2-gt;next->next;
} while (p1 != p2);

p2 is moving through the list twice as fast as p1. If the list is circular, (i.e. a cycle exists) it will eventually get around to that sluggard, p1.

9. How would you reverse a doubly-linked list?

Start at the head of the list, and iterate to the end. At each node, swap the values of pNext and pPrev. Finally, set pHead to the last node in the list.

Node * pCurrent = pHead, *pTemp;
while (pCurrent)
{ pTemp = pCurrent-gt;pNext;
pCurrent-gt;pNext = pCurrent->pPrev;
pCurrent-gt;pPrev = temp;

pHead = pCurrent;

pCurrent = temp;
}

10. If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?