Sunday, April 4, 2010

MS interview




Algorithm Collection


Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.

Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?

Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?

Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.

Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.

Q6: Write a function to print the Fibonacci numbers

Q7: Write a function to print all of the permutations of a string.

Q8: Design a memory management scheme.

Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.

Q10: How can I swap two integers in a single line statement?

Q11: Implement an algorithm to sort a linked list.

Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp

Q13: Given a linked list which is sorted, how will you insert in sorted way.

Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.

Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.

Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.

Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)

Q18: Implement an algorithm to reverse a doubly linked list.

Q19: Delete an element from a doubly linked list.

Q20: Implement an algorithm to sort an array.

Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?

Q22: Count the number of set bits in a number without using a loop.

Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.

Q24: How would you print out the data in a binary tree, level by level, starting at the top?

Q25: Do a breadth first traversal of a tree.

Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.

Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.

Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.

Q29: Write a function to find the depth of a binary tree.

Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.

Q31: Write a small lexical analyzer for expressions like "a*b" etc.

Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).

Q33: Write efficient code for extracting unique elements from a sorted list of array.

Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).

Q35: Print an integer using only putchar. Try doing it without using extra storage.

Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).

Q37: Write source code for printHex(int i) in C/C++

Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.

Q39: How do you handle deadlock on a table that is fed with a live serial feed?

Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.

Q41: How would you implement a hash table? How do you deal with collisions.?

Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?

Q43: How would you do conditional compilation?

Q44: Write an algorithm to draw a 3D pie chart?

Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.

Q46: How would you implement a queue from a stack?

Q47: Write a funtion that finds repeating characters in a string.

Q48: Write a routine to reverse a series of numbers without using an array.

Q49: Write a function to find the nth item from the end of a linked list in a single pass.

Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).

Q51: Write a random number generator in a specified range.

Q52: Delete a node from a single linked list.

Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC. Find A, B, and C that satisfies this equation.

Q54: Give 2 nodes in a tree, how do you find the common root of the nodes?

Q99: Write a small lexical analyzer for expressions like a(b|c)d*e+.






Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.

A1: p2 is guaranteed to reach the end of the list before p1 and every link will be tested by the while condition so no chance of access violation. Also, incrementing p2 by 2 and p1 by 1 is the fastest way of finding the cycle. In general if p1 is incremented by 'n' and p2 by 'm', ('n' not == 'm'), then if we number the nodes in the cycle from 0 to k-1 (k is the number of nodes in the cycle), then p1 will take values given by i*n (mod k) and p2 will take values i*m (mod k). These will collide every n*m iterations. Clearly, n*m is smallest for n==1 and m==2.



bool HasCycle(Node *pHeadNode)
{
Node *p1, *p2;
p1 = p2 = pHeadNode;
while (p2 && p2->Next) {
p1 = p1->Next;
p2 = p2->Next->Next;
if (p1 == p2)
return true;
}
return false;
}


Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?

A2: Hash Table is the most efficient way to do this. You can use several hashing algorithms. For example, checksum of a link can be used as a key for hashing. This will ensure o(1) order provided good checksum algorithm is used which is always unique. Whenever page loads we can parse all URL's from the page and take their checksum and compare them w/ the hashtable. Whichever links matches are displayed in some different color.



Hashtable is the correct answer, but a constant order algo. sounds too fantastic. URLs are by themselves unique and so hash function should not add to the redundancy by being unique. O/w it becomes nothing but a linear sort of search, while binary can do better.



Though URLs are not inherently alphabetically ordered, one might think of ordering them that way, or making the hash function that utilizes this. This will entail a combined binary + linear search which sounds optimal and is open to complexity calculations. A good data structure can be a hash table pointing to a binary tree (an array pointing to a binary tree).




Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?

A3: Keep a list (or a binary tree) of hashes (using MD5, SHA1 or similar hash/digest algorithm) of pages you've visited. Then just compare digest of current page to the hashes in the tree.




Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.

A4: Use prim's algorithm; Kruskal's algorithm is faster than Prim's. For checking for an already seen url, use dictionary search tree. It is the most efficient i.e. O(1) for whatever number of urls you have in the database.




Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.




Q6: Write a function to print the Fibonacci numbers



int fib (int n)
{
assert(n>=1);
return (n<=2 ? 1: (fib(n-1) + fib(n-2)));
}

int fibonacci (int n)
{
if (n <= 2) return 1;
int current, one_back 1, two_back = 1;
for (int i = 3; i <= n; i++) {
current = one_back + two_back;
one_back = two_back;
two_back = current;
} /* the end of for loop */
return current;
}


Q7: Write a function to print all of the permutations of a string.



map<string, int> map_StrInt;
void PermuteString(char* str, int n)
{
char ch = str[n-1];
for(int i = 0; i < n; i++)
{
swap (str[i], str[n-1]);
PermuteString(str, n-1);
swap (str[i], str[n-1]);
}

if (n == 1)
map_StrInt[string(str)]++;
}


Q8: Design a memory management scheme.




Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.

A9: x = ((x > 0) & !(x & x - 1));




Q10: How can I swap two integers in a single line statement?

A10: Use xor operator to accomplish this: a ^= b ^= a ^= b;




Q11: Implement an algorithm to sort a linked list.

A11: The merge sort algorithm:



#include <cassert>

typedef struct MNode *PNODE;
struct MNode
{
int Key;
struct MNode *Next;
};

PNODE Merge(PNODE p, PNODE q)
{
assert(p);
assert(q);

PNODE pHead;
if (p->Key < q->Key)
{
pHead = p, p = p->Next;
}
else
{
pHead = q, q = q->Next;
}

PNODE r = pHead;
while (p && q)
{
if(p->Key < q->Key)
{
r->Next = p, r = r->Next, p = p->Next;
}
else
{
r->Next = q, r = r->Next, q = q->Next;
}
}
if(!p) r->Next = q;
if(!q) r->Next = p;
return pHead;
}

PNODE Partition(PNODE pNode)
{
PNODE p1 = pNode;
PNODE p2 = pNode->Next->Next;
while (p2 && p2->Next)
{
p2 = p2->Next->Next;
p1 = p1->Next;
}
PNODE pSav = p1->Next;
p1->Next = NULL;
return pSav;
}

PNODE Merge_Sort(PNODE p)
{
if (!p || !p->Next) return p;
PNODE q = Partition(p);
p = Merge_Sort(p);
q = Merge_Sort(q);
p = Merge(p, q);
return p;
}


Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp



char * strstr (const char *str1, const char *str2)
{
char *cp = (char *)str1;
char *endp = cp + (strlen(cp) - strlen(str2));

while (*cp & (cp <= endp))
{
char *s1 = cp;
char *s2 = (char *)str2;
while ( *s1 & *s2 && (*s1 == *s2) )
s1++, s2++;
if (!(*s2)) return(cp); // success!
cp++; // bump pointer to next char
}
return(NULL);
}

char *strcat (char * dst, const char * src)
{
char *cp = dst;
while (*cp) cp++; // find end of dst
while (*cp++ = *src++); // Copy src to end of dst
return (dst); // return dst
}

char *strcpy (char * dst, const char * src)
{
char* cp = dst;
while (*cp++ = *src++); // Copy src over dst
return(dst);
}

char *strtok (char *string, const char *control)
{
char *str;
const char *ctrl = control;

char map[32];
int count;

static char *nextoken;

/* Clear control map */
for (count = 0; count < 32; count++)
map[count] = 0;

// Set bits in delimiter table
do {
map[*ctrl >> 3] |= (1 << (*ctrl & 7));
} while (*ctrl++);

// Initialize str. If string is NULL, set str to the saved pointer
// (i.e., continue breaking tokens out of the string from the last strtok call)
if (string)
str = string;
else
str = nextoken;

// Find beginning of token (skip over leading delimiters). Note that there is
// no token iff this loop sets str to point to the terminal null (*str == '\0')
while (
*str && (map[*str >> 3] & (1 << (*str & 7))))
str++;

string = str;

// Find the end of the token. If it is not the end of the string, put a null there.
for ( ; *str ; str++)
if (map[*str >> 3] & (1 << (*str & 7))) {
*str++ = '\0';
break;
}

// Update nextoken
nextoken = str;

// Determine if a token has been found.
if (string == str)
return NULL;
else
return string;
}

int strcmp(const char *src, const char* dst)
{
int ret = 0;
while (!(ret = (*src - *dst)) & *dst);
++src, ++dst;
if (ret < 0)
ret = -1;
else
ret = 1;
return ret;
}

char *strrev (char *string)
{
char *start = (char *)string;
char *left = (char *)string;
while (*string++); // find end of string
string -= 2;
while (left < string)
{
char ch = *left;
*left++ = *string;
*string-- = ch;
}
return start;
}

char *strrchr (const char *string, int ch)
{
char *start = (char *)string;
while (*string--); // find end of string
while (--string != start && *string != (char)ch); // search forward front
if (*string == (char)ch) // char found ?
return (char *)string;
return (NULL);
}


Q13: Given a linked list which is sorted, how will you insert in sorted way.



void Insert(PNODE &pHead, PNODE pThing)
{
if (pHead == 0)
pHead = pThing;
else
{
bool fComesFirst = true;
PNODE pCurrent = pHead;
PNODE pPrevious;
while (pCurrent)
{
if (pThing->Key < pCurrent->Key)
break;
pPrevious = pCurrent;
pCurrent = pCurrent->Next;
fComesFirst = false;
}

if (fComesFirst)
pHead = pThing;
else
pPrevious->Next = pThing;
pThing->Next = pCurrent;
}
}


Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.

/* Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.



For each position i in the array we can find out the sub array ending exactly at that position and having the largest sum. At the beginning for the first element the only possible sub array it that one containing the first element so initially the largest amount is a[1]. (For algorithm sake let assume that the array is 1-indexed). Following the principle of dynamic programming it will be proved that the best sub array( with the largest sum) ending in position i+1 is somehow related to best sub array ending in position i.

Let be k the starting index of the best sub array ending in position i and S the sum of this sub array. Let be t an index strictly less than k. The sum from the index t to i+1 is T + S + a[i+1] where T is the sum of elements from t to k-1 indexes. Because of the properties of index k T+S <= S otherwise k will not point to best sub array ending in i so each sub array starting in t
Similarly , let choose an index t between k+1 and i. The sum from index t to i+1 is T+a[i+1], where is the sum of elements between t and i positions. Again T < S according to the optimality of k index so the best sub array ending in i+1 is that one starting from k and that has S+a[i+1] as sum of array elements. But there is one more situation to analyse. If S is less then zero is obvious that S+a[i+1] < a[i+1] so in this case the best sub array ending in i+1 position is exactly the sub array containing only that element. In fact this situation direct you to start a new sub array that will be candidate for the best sub array of the entire array.

In conclusion the information to be kept while going through the array only once (O(n)) is the best sub array ending in the current position and best sub array found for the entire array until the current step.(if it necessary also the starting and ending position for these sub array can be kept). After the processing of the last element the algorithm will have determined the sub array having the largest sum.



Note: The algorithm works fine even there is no negative number in the array and it will produce of course as the largest sum the sum of all array elements.



Algorithm: arr is the array of n integer; the function will return the largest sum and the limits of the sub array producing that value */


#include <iostream>
using namespace std;

int GetLargestSubArray(int* arr, int n, int &iBeginRet, int &iEndRet)
{
int iBeginSaved=0, iEndSaved=0; // the start/end positions of the saved sub array
int iBegin, iEnd; // the start/end positions of the current sub array
int nSumSaved=0, nSum=0; // the sums of whole saved largest and current sub arrays
int i = 0; // index to loop in the array

if (0 == n) // Nothing to analyze, return invalid array indexes
{
iEndRet = iBeginRet = -1;
return 0;
}

nSumSaved = nSum = arr[i];
for(i = 2; i < n; i++)
{
/* Compute the current largest sum */
if (nSum<0)
{
nSum = arr[i];
iBegin = iEnd = i;
}
else
{
nSum += arr[i];
iEnd = i;
}
if (nSum > nSumSaved)
{
nSumSaved = nSum;
iBeginSaved = iBegin;
iEndSaved = iEnd;
}
}
iBeginRet = iBeginSaved;
iEndRet = iEndSaved;
return nSumSaved;
}


Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.

A15: I'll try to do it in O(N) w/o using any additional memory. The key is to use content of the array as index into array, checking in O(1) if that number has been seen already.


bool HasDups(int * a, int N)
{
bool fHasDup = false;
for (int i = 0; i < N; i++) {
int index = a[i] % N;
if (a[index] > N) {
fHasDup = true;
break;
}
a[index] += N;
}

//restore the array
for (int j = 0; j < i; j++)
if (a[j] > N) a[j]
%= N;

return fHasDup;
}


Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.




Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)



Node *RevSList(Node *pCur, Node *pRev) {
if (!pCur) return pRev;
Node *pNext = pCur->Next;
pCur->Next = pRev;
pRev = pCur;
return (RevSList(pNext, pRev));
}

Node * RevSList(Node *pCur) {
Node *pRev = NULL;
while (pCur)
{
Node *pNext = pCur->Next;
pCur->Next = pRev;
pRev = pCur;
pCur = pNext;
}
return pRev;
}


Q18: Implement an algorithm to reverse a doubly linked list.


Node *RevDList(Node *pCur)
{
if (!pCur) return pCur;
pSav = pCur->Next;
pCur->Next = pCur->Prev;
pCur->Prev = pSav;
if (!pSav) return pCur;
return RevDList(pSav);
}

Node *RevDList(Node *pCur)
{
while (pCur)
{
Node *pSav = pCur->Next;
pCur->Next = pCur->Prev;
pCur->Prev = pSav;
if (!pSav) return pCur;
pCur = pSav;
}
return pCur;
}


Q19: Delete an element from a doubly linked list.


Node *DelDLLNode(Node *pNode)
{
if (!pNode) return pNode;
if (pNode->Next) pNode->Prev->Next = pNode->Next;
if (pNode->Prev) pNode->Next->Prev = pNode->Prev;
return pNode; // delete it if it's heap-based.
}


Q20: Implement an algorithm to sort an array.




Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?




Q22: Count the number of set bits in a number without using a loop.


#define reverse(x) \
(x=x>>16 | (0x0000ffff&x)<<16, \
x=(0xff00ff00&x)>>8|(0x00ff00ff&x)<<8, \
x=(0xf0f0f0f0&x)>>4|(0x0f0f0f0f&x)<<4, \
x=(0xcccccccc&x)>>2|(0x33333333&x)<<2, \
x=(0xaaaaaaaa&x)>>1|(0x55555555&x)<<1)

#define count_ones(x) \
(x=((0xaaaaaaaa&x)>>1)+(0x55555555&x), \
x=((0xcccccccc&x)>>2)+(0x33333333&x), \
x=((0xf0f0f0f0&x)>>4)+(0x0f0f0f0f&x), \
x=((0xff00ff00&x)>>8)+(0x00ff00ff&x), \
x=(x>>16) + (0x0000ffff&x))


Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.



for (Src = 0; Src < N; Src++)
{
Dest = rand() % N; // All N positions equally likely
Swap (X[Src], X[Dest]);
}

At first glance, it would appear that this algorithm generates all permutations with equal probability. On examination, though, one can see that this will generate NN arrangements of elements---each of the N iterations of the loop positions a value among the N available positions. It is known, though, that there are only N! possible permutations of N elements: for each permutation there are multiple ways to generate that permutation---on average, NN/N! ways.


for (Src = 0; Src < N; Src++)
{
Dest = rand() % N; // All N positions equally likely
Swap (X[Src], X[Dest]);
}

Examination of the structure of this loop shows that it will generate N! arrangements of elements. All permutations are equally likely, aside from the very minor deviation from uniform distribution by selecting a random value between 0 and Dest as (rand() % (Dest+1)).




Q24: How would you print out the data in a binary tree, level by level, starting at the top?




Q25: Do a breadth first traversal of a tree.



typedef int VertexType;
typedef class Vertex *LPVertex;

class Vertex
{
int index;
int weight;
LPVertex next;
public:
int GetIndex();
bool Visited();
Vertex &Visit();
Vertex &Mark();
Vertex *GetNext();
};

enum { kMaxVertices = 7 };
typedef LPVertex HeaderArray[kMaxVertices];
HeaderArray adjacencyList;

void BreathFirstSearch (HeaderArray adjacencyList, LPVertex pv)
{
queue Q;
pv->Visit().Mark();
Q.push(pv);
while (!Q.empty())
{
pv = Q.front(); Q.pop();
pv = adjacencyList[pv->GetIndex()];
for (; pv; pv = pv->GetNext())
if (!pv->Visited())
{
pv->Visit().Mark();
Q.push (pv);
}
}
}

void DepthFirstSearch (HeaderArray adjacencyList, LPVertex pv)
{
stack S;
pv->Visit().Mark();
S.push(pv);
while (!S.empty())
{
pv = S.top();
pv = adjacencyList[pv->GetIndex()];
for (; pv; pv = pv->GetNext())
if (!pv->Visited())
{
pv->Visit().Mark();
S.push(pv);
}
S.pop();
}
}


Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.




Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.



char *ReverseWords (char *string)
{
char *start = strrev(string);
char *left;
char *right;
char ch;

while (*string)
{
while (*string == ' ' & *string)
string++;
left = string;

while (*string != ' ' & *string)
string++;
right = string-1;

while (left < right)
{
ch = *left;
*left++ = *right;
*right-- = ch;
}
}
return start;
}


Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.




Q29: Write a function to find the depth of a binary tree.



long findDepth(Node *pNode)
{
if (
!pNode) return 0;
long depthLeft = findDepth(
pNode->Left);
long depthRight = findDepth(
pNode->Right);
return (depthLeft>depthRight ? ++depthLeft: ++depthRight);
}


Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.



char *strtokrem (char *string, const char *control)
{
char *start = string;
char *str = string;
const char *ctrl = control;

char map[32];
int count;

/* Clear control map */
for (count = 0; count < 32; count++)
map[count] = 0;

// Set bits in delimiter table
do {
map[*ctrl >> 3] |= (1 << (*ctrl & 7));
} while (*ctrl++);

// Remove each token whenever it matches
while (*str)
if (map[*str >> 3] & (1 << (*str & 7))) {
for (char *pch = str; *pch; pch++)
*pch = *(pch+1);
}
else
str++;
return start;
}


Q31: Write a small lexical analyzer for expressions like "a*b" etc.



bool is_astarb(char* string)
{
// expressions: b, ab, aab, aaab, ...
bool bRet = false;
while (*string == 'a')
++string;

if (*string == 'b')
bRet = (*++string == '\0');

return bRet;
}


Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).




Q33: Write efficient code for extracting unique elements from a sorted list of array.


void PrintUniqueElements(int rgNumb[], int cNumb)
{
assert(cNumb>0);
int iSav;
cout << (iSav = rgNumb[0]) << "\t";
for (int i = 1; i < cNumb; i++)
if (iSav != rgNumb[i])
cout << (iSav = rgNumb[i]) << "\t";
}


Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).




Q35: Print an integer using only putchar. Try doing it without using extra storage.



void putDigits(int val)
{
if (val < 0) { cout << "-"; val = -val; }
stack<int> S;
S.push(val);
while (!S.empty())
{
val = S.top(); S.pop();
if (val >= 10)
{
S.push(val%10);
S.push(val/10);
}
else
cout.put(val+'0');
}
}


Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).




Q37: Write source code for printHex(int i) in C/C++


void putHex(int val)
{
if (val < 0) {
printf("-");
val = -val;
}
if (val >= 0 & val < 16) {
printf("%c", val > 9 ? (val-10)+'A' : val+'0');
return;
}
putHex(val/16);
printf("%c", val%16 > 9 ? (val%16-10)+'A' : val%16+'0');
}


Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.




Q39: How do you handle deadlock on a table that is fed with a live serial feed?




Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.




Q41: How would you implement a hash table? How do you deal with collisions.?




Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?

A42: Overflow; If we're talking about ASP, JSP, CFML that sort of thing, I would suspect unsynchronized access to session data in a multi-threaded Servlet, JavaBean or COM object -- i.e., a non-threadsafe bug in the server application.




Q43: How would you do conditional compilation?

A43: The #if directive, with the #elif, #else, and #endif directives, controls compilation of portions of a source file. If the expression you write (after the #if) has a nonzero value, the line group immediately following the #if directive is retained in the translation unit. Plus, #ifdef and #ifndef identifier.




Q44: Write an algorithm to draw a 3D pie chart?




Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.

A45: The two common MST algorithms are by Kruskal and Prim. Djikstra gave us an algorithm for shortest path, not MST.




Q46: How would you implement a queue from a stack?



stack stk1, stk2;
void push(element e)
{
push.stk1(e);
}

element pop()
{
if(stk2.empty())
while(!stk1.empty())
stk2.push(stk1.pop());
return stk2.pop();
}


Q47: Write a funtion that finds repeating characters in a string.




Q48: Write a routine to reverse a series of numbers without using an array.


int iReverse (int iNum)
{
int iRev =0;
while(iNum !=0)
{
iRev = iRev * 10 + iNum % 10;
iNum /= 10;
}
return iRev;
}


Q49: Write a function to find the nth item from the end of a linked list in a single pass.

A49: I would think keeping a gap of "n" between fptr and sptr would do. Then, advance both together till fptr->next (fptr is the one in front) = NULL.



Aren't you traversing the list twice - once with fptr and the second time with sptr. I think you should maintain an queue of pointers. Keep pushing a pointer into the queue and whenever the size of the queue becomes greater than n, remove a pointer at the head of the queue. When you reach the end of the list. The element at the head of the queue gives a pointer to the nth element from the end.



#include <queue>
PNODE GetNthLastElement (PNODE pCur, unsigned nOffset)
{
queue<PNODE> Q;

for (; pCur && Q.size() < nOffset; Q.push(pCur), pCur = pCur->Next) ;
if (Q.size() < nOffset) return NULL;

while (pCur)
{
Q.pop();
Q.push(pCur);
pCur = pCur->Next;
}
return (Q.front());
}


Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).




Q51: Write a random number generator in a specified range.


#include <algorithm>

int random_range(int lowest_number, int highest_number)
{
¡¡¡¡if (lowest_number > highest_number)
¡¡¡¡{
¡¡¡¡¡¡¡¡swap(lowest_number, highest_number);
¡¡¡¡}

¡¡¡¡int range = highest_number - lowest_number + 1;
¡¡¡¡return lowest_number + int(range * rand()/(RAND_MAX + 1.0));
}




Q52: Delete a node from a single linked list.


Node *DelSLLNode(Node *pDelete, Node *pHead)
{
if (pHead == pDelete)
return (pHead = pHead->Next);

Node *pPrev = pHead;
for ( ; pPrev->Next; pPrev = pPrev->Next)
{
if (pPrev->Next == pDelete)
{
pPrev->Next = pPrev->Next->Next;
break;
}
}
return pHead;
}




Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC (where ABS is a three digit numbers, not A * B * C). Find A, B, and C that satisfies this equation.


1! + 4! + 5! = 145




Q54: Give 2 nodes in a tree, how do you find the common root of the nodes?




Q99: Write a small lexical analyzer for expressions like a(b|c)d*e+.


enum State {
s0 = 0, s1, s2, s3, // states
m0 = 0, m1, m2, m3, acc, err // actions: matches, accept or error
};

State DecisionTable[4][6] = {
// a b c d e other // input
m1,err,err,err,err,err, // s0
err, m2, m2,err,err,err, // s1
err,err,err, m2, m3,err, // s2
acc,acc,acc,acc, m3,acc // s3
};

State IsAcceptable (char *&theIStream)
{
State stateCur = s0, State theDecision = err;
do
{
char theChar = *theIStream++;
int theInput = (theChar - 'a') % 6;
theDecision = DecisionTable[stateCur][theInput];

switch (theDecision)
{
default:
stateCur = theDecision;
break;
case err:
case acc:
; // do nothing
}
} while (theDecision != err & theDecision != acc);
return theDecision;
}



The Six Phases of a Compiler



  • Front End

    • Lexical Analysis - Token Stream
    • Syntactic Analysis - Parse Tree
    • Semantic Analysis - Parse Tree
    • Intermediate Code Generation - IR

  • Back End

    • Code Optimization - IR
    • Code Generation - Target Program

  • Error Handling and Symbol Table




Two Parts - Analysis and Synthesis




The Six Components of a Compiler


  • Scanner, Lexer, or Lexical Analyzer

    • Groups characters into tokens - basic unit of syntax

      (character string forming a token is a lexeme)

    • Eliminates white space (blanks, tabs and returns)

  • Parser, Syntactic Analyzer

    • Groups tokens into grammatical phrases
    • Represent the grammatical phrases into a parse tree
    • The syntac of a language is specified by context-free grammar

  • semantic Analyzer

    • Variables redefined, Procedures called w/ the right number of types of args.
    • Type checking with permitted coercions, e.g. Operator called w/ incompatible types

  • Intermediate Code Generator
  • Code Optimizer - The VC++ can perform copy propagation and dead store elimination, common subexpression elimination, register allocation, function inlining, loop optimizations, flow graph optimizations, peephole optimizations, scheduling, and stack packing.
  • Code Generator



Lexers - Finite State Automata (FSA)


LEX implements this by creating a C program that consists of a general algorithm and a decision table specific to the DFSA:


state= 0; get next input character
while (not end of input) {
depending on current state and input character
match: /* input expected */
calculate new state; get next input character
accept: /* current pattern completely matched */
perform action corresponding to pattern; state= 0
error: / input unexpected /
reset input; report error; state= 0
}



Parsers - Push Down Automata (PDA)


There are two important classes of parsers, known as top-down parsers and bottom-up parsers. They are important because they provide a good trade-off between speed (they read the input exactly once, from left-to-right) and power (they can deal w/ most computer languages, but are confused by some grammars).



Top-Down Parsers

Here, the stack of the PDA is used to hold what we are expecting to see in the input. Assuming the input is correct, we repeatedly match the top-of-stack to the next input symbol and then discard them, or else replace the top-of-stack by an expansion from the grammar rules.


initialise stack to be the start symbol followed by end-of-input
repeat
if top-of-stack == next input
match -- pop stack, get next input symbol
else if top-of-stack is non-terminal and lookahead (e.g. next input) is as expected
expand -- pop stack (= LHS of grammar rule)
and push expansion for it (= RHS of grammar rule) in reverse order
else
error -- expected (top-of-stack) but saw (next input)
until stack empty or end-of-input

e.g. recognising a , b , c using:
list : id tail;
tail : ',' id tail | ;

stack next input rest of input action ($ represents end-of-input)
$ list a , b , c $ expand list to id tail
$ tail id a , b , c $ match id a
$ tail , b , c $ expand tail to ',' id tail
$ tail id , , b , c $ match ,
$ tail id b , c $ match id b
$ tail , c $ expand tail to ',' id tail
$ tail id , , c $ match ,
$ tail id c $ match id c
$ tail $ expand tail to (nothing)
$ $ accept



Bottom-Up Parsers

Here, the stack of the PDA is used to hold what we have already seen in the input. Assuming the input is correct, we repeatedly shift input symbols onto the stack until what we have matches a grammar rule, and then we reduce the grammar rule to its left-hand-side.



initialise stack (to end-of-input marker)
repeat
if complete grammar rule on stack and lookahead (e.g. next input) is as expected
reduce -- pop grammar rule and push LHS
else if lookahead (e.g. next input) is as expected
shift -- push next input, get next input symbol
else
error
until stack==start symbol and at end-of-input

e.g. recognising a , b , c using:
list : id | list ',' id;

stack next input rest of input action
$ a , b , c $ shift id a
$ id , b , c $ reduce id to list
$ list , b , c $ shift ,
$ list , b , c $ shift id b
$ list , id , c $ reduce list ',' id to list
$ list , c $ shift ,
$ list , c $ shift id c
$ list , id $ reduce list ',' id to list
$ list $ accept

e.g. here is the y.output and corresponding decision table for list : id | list ',' id ;

state 0 $accept : _list $end
id shift 1 . error list goto 2
state 1 list : id_ (1)
. reduce 1
state 2 $accept : list_$end
list : list_, id
$end accept , shift 3 . error
state 3 list : list ,_id
id shift 4 . error
state 4 list : list , id_ (2)
. reduce 2
















































state terminal symbols non-terminals

id

','

$end

list

0

shift 1 . . goto 2

1

reduce (list:id) . . .

2

. shift 3 accept .

3

shift 4 . . .

4

reduce (list : list ',' id) . . .



  • References: How LEX and YACC work and Inside Lex and Yacc


  • Monday, September 28, 2009

    Amazon interview question Collection

    General Questions and Comments [more]
    generic questions on software development


    --------------------------------------------------------------------------------

    What is the complexity of this algorithm


    --------------------------------------------------------------------------------

    What is your stronger language (Java or C#)


    --------------------------------------------------------------------------------

    Lot of design questions and OOAD stuff 2


    --------------------------------------------------------------------------------

    Programming questions asked were more or less same as the ones listed at this site


    --------------------------------------------------------------------------------

    more architectural view about solve problem capability. I think the intervier was more realistic than the other two . Not just because he recommend to 2nd interview, since I also have the experience with recuriting other employees in the past. I felt the potenial is more than anything in work. Coding is just one thing , maybe the one who can solve the tricky algorithms is good in some way, but how about the one who has been out of school for several years and I cant remeber anything about mergesort or quicksort or how to find the shortest path blah blah. But I do have the confidence I am very good at work. No matter where I go, I found most people are not that smart and if you are willing to learn, you can be the best. Of course, you must have the potenial first. Like you are willing to learn and you like your job... 5


    --------------------------------------------------------------------------------

    3rd phone interview


    --------------------------------------------------------------------------------

    what do you like in a job 2


    --------------------------------------------------------------------------------

    gave some description about the job and then it is done


    --------------------------------------------------------------------------------

    I took around 2 hours to do a good job for this becoz he wanted propper OO concepts. Created the util class as a singleton with synchronization for the add and edit methods with exceptions being thrown when employee's arent found etc. He seemed to like it from the reply mail i received


    --------------------------------------------------------------------------------

    The standard stuff had to be added to the api like synchronization, singleton etc.


    --------------------------------------------------------------------------------

    its coming up soon, hopefully ill do good :D


    --------------------------------------------------------------------------------

    How do you resolve a collision in a hash table


    Algorithm [more]
    Coding: How would you find the nth to last element in a linked list? 27


    --------------------------------------------------------------------------------

    Algorithm: Explain algorithm to shuffle cards 8


    --------------------------------------------------------------------------------

    Coding: Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function? 9


    --------------------------------------------------------------------------------

    Algorithm: You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers? 14


    --------------------------------------------------------------------------------

    Coding: How would you reverse the words in a string? (ie, "the quick brown fox" --> "fox brown quick the" 41


    --------------------------------------------------------------------------------

    How would you detect a repeated element in an integer array. Discuss various solutions and the order of the algorithm. 37


    --------------------------------------------------------------------------------

    Write a function to smooth out stock fluctuations. Asked me to layout the mathematical idea for curve smoothing before writing code. 3


    --------------------------------------------------------------------------------

    Given two sets, Write a function to provide the union of them. STL not allowed to be used.
    Optimise for Time and space. 24


    --------------------------------------------------------------------------------

    Design an algorithm to calculate the most user viewed pages 3


    --------------------------------------------------------------------------------

    Find missing element in an array of 100 elements. 16


    --------------------------------------------------------------------------------

    Design an algorithm to find duplicates in an array. Discuss different approaches. 16


    --------------------------------------------------------------------------------

    Design an algorithm and write code to find nth node from the end in a linked list 3


    --------------------------------------------------------------------------------

    Design an algorithm and write code to shuffle a standard deck of cards 1


    --------------------------------------------------------------------------------

    Design an algorithm and write code to serialize a binary tree. Discuss various solutions 18


    --------------------------------------------------------------------------------

    Design an algorithm and write code to find two numbers in an array whose sum equals a given value 19


    --------------------------------------------------------------------------------

    Given 2 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2) 9


    --------------------------------------------------------------------------------

    Given 3 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2 and file3) 3


    --------------------------------------------------------------------------------

    count bits in an integer. Solved using mask, did not attempt -1 approach. 6


    --------------------------------------------------------------------------------

    Given two binary trees, find whether or not they are similar. 12


    --------------------------------------------------------------------------------

    Determine is a graph is circular. 6


    --------------------------------------------------------------------------------

    assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability. 11


    --------------------------------------------------------------------------------

    Algorithm: You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level. Discussed on phone and asked me to email Java code for my algorithm. 4


    --------------------------------------------------------------------------------

    Unix: You have 50,000 html files in a UNIX directory structure, some of which contain phone numbers in the format ***-***-****. How would you create a list of all the files which contain phone numbers? (Assume that you already have the regular expression) 5


    --------------------------------------------------------------------------------

    Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8


    --------------------------------------------------------------------------------

    How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to access an individual element in O(1) time? 4


    --------------------------------------------------------------------------------

    Here is a tree. It's a binary tree but in no particular order. How do you write this tree to a file so that it can be reread in an reconstructed exactly as shown? 33


    --------------------------------------------------------------------------------

    Here is a graph of distribution centers and the weight to go from one to another. How would you represent this using a data structure? Code an alogrithm that allows me to check if there is a path from one node to another and what the weight of this path is. 1


    --------------------------------------------------------------------------------

    Given two dates, Design an algorithm to return whether the dates are exactly a month apart, less than a month apart or more than a month apart. 2


    --------------------------------------------------------------------------------

    Discussed the proof and solution to my card shuffle problem 1


    --------------------------------------------------------------------------------

    Write a method to shufle the deck. The constraint is it has to be a perfect shuffle - in other words, every 52! permutations of the deck has to be equally like (given a completely random function which is theoretical of course).

    I managed to do this with a simple for loop in O(n) time


    int[] deck = new int[52];
    for(int i=0; i<52; i++)
    deck[i] = i;

    Random r = new Random();
    for(int i=0; i
    int ran = r.nextInt(deck.length-i) + i;
    int temp = deck[i];
    deck[i] = deck[ran];
    deck[ran] = temp;
    }


    --------------------------------------------------------------------------------

    int[1000], numbers from 1 to 1000, but one is missed - find it 3


    --------------------------------------------------------------------------------

    reverse linked list. Why don't you use recursion? 5


    --------------------------------------------------------------------------------

    If there are two structs, TreeNode and Tree. TreeNode contains 3 elements, data, lChild and rChile. Tree contains 2 elements, int size and TreeNode *root. The tree is a complete tree. So how to find a O(logN) approach to insert a new node. 2


    --------------------------------------------------------------------------------

    Algorithm and code to detect occurence of a string(patterns) in another string ex: aab, aababa 5


    --------------------------------------------------------------------------------

    If you are given a set of 1000 integers in a set A , and 10,000,000 integers in a set B, how would you create a set C that would only contain numbers that are both in A and B? 2


    --------------------------------------------------------------------------------

    In a general tree, how would you find the lowest common ancestor of two nodes that are given to you as parameters? 1


    --------------------------------------------------------------------------------

    How do you merge n sorted lists with average length K in O(n*log(K)) time? 12


    --------------------------------------------------------------------------------

    Design an algorithm to find the 100 shortest distances to stars in the universe 1


    --------------------------------------------------------------------------------

    If you have a draft ransom note and a book, how would you determine if said ransom note can be composed from the book on its own? What if the ransom note is not necessarily in ascii (can be in chinese and such). What if you have no storage save for a few counters?


    --------------------------------------------------------------------------------

    What is a scripting language? Write a code to output the dot product of two files.


    --------------------------------------------------------------------------------

    Suggest an algorithm to find the first non-repeating character in a given string. 3


    --------------------------------------------------------------------------------

    How to find the two numbers whose difference is minimum among the set of numbers 7


    --------------------------------------------------------------------------------

    a. Findodd - given ana array of numbers return a number which appear odd number of times.
    b. isPrime
    c. Garbage Collector.
    d. OO model for Elevator, grilled a bit but successfully answered.
    e. Find if high bit is set in the integer.


    --------------------------------------------------------------------------------

    Describe the data structures you will use for implementing snake & ladder game 3


    Application / UI Design [more]
    How would you design a parking garage?


    --------------------------------------------------------------------------------

    Given an outline for an architectural plan, automate the loading of the design into a computer


    Behavioral [more]
    Why do you want to work at Amazon? 2


    --------------------------------------------------------------------------------

    Talk about your favourite project? What part of a Software Project do you enjoy most?


    --------------------------------------------------------------------------------

    Lunch - QA manager.

    1. tell me a situation when u had to face problems and the requirements were not clear. how did u handle the situation?

    2. which is the best error you have caught?

    3. which is the worst error u've ever caught?

    4. asked about a project on my resume


    --------------------------------------------------------------------------------

    Why do you want to work here?


    --------------------------------------------------------------------------------

    Favorite feature on Amazon personalization site


    --------------------------------------------------------------------------------

    How did you hear about Amazon?


    --------------------------------------------------------------------------------

    what you don't like in a job


    --------------------------------------------------------------------------------

    what kind og job do you prefer


    --------------------------------------------------------------------------------

    why amazon


    --------------------------------------------------------------------------------

    why cs


    --------------------------------------------------------------------------------

    What is Polymorphism?


    --------------------------------------------------------------------------------

    If you are already working why are you still looking?


    --------------------------------------------------------------------------------

    What's the latest book you've read?


    --------------------------------------------------------------------------------

    If there's a glitch in the system and for some reason, for a very brief moment, the website is inaccessible from your browser. You got back to it a few minutes later and the glitch is gone. Would you report this problem?


    Brain Teasers [more]
    You have eight balls: seven are the same weight, and one is heavier than the rest. Given a scale that only tells you which side is heavier, how do you find the heavy ball? 9


    --------------------------------------------------------------------------------

    Given an array of integers where every int has exactly one duplicate except one,
    find the number with odd occuring number. 27


    --------------------------------------------------------------------------------

    assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability. 11


    --------------------------------------------------------------------------------

    Brainteaser: there is a bar with 25 seats in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjecent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others. So where should the first customer sit. 9


    --------------------------------------------------------------------------------

    If there are a huge array of positive integers, all the integers show up twice except one. Find out that integer. 1


    Coding [more]
    Coding: Write code to tokenize a string (had to explain code out loud and then follow-up with the actual code in an email 3


    --------------------------------------------------------------------------------

    Coding: How would you find the nth to last element in a linked list? 27


    --------------------------------------------------------------------------------

    Coding: You have an array of ints. How would you find the two elements that sum to a particular value? 18


    --------------------------------------------------------------------------------

    Coding: Implement a binary search in a sorted array 3


    --------------------------------------------------------------------------------

    Coding: How would you reverse the words in a string? (ie, "the quick brown fox" --> "fox brown quick the" 41


    --------------------------------------------------------------------------------

    Design a graph class. Write the C++ interface for it. 3


    --------------------------------------------------------------------------------

    Write a function to smooth out stock fluctuations. Asked me to layout the mathematical idea for curve smoothing before writing code. 3


    --------------------------------------------------------------------------------

    Write a function to find the no of set bits of an integer. Optimise. Ended up giving two solutions . Could not implement the third one. 10


    --------------------------------------------------------------------------------

    Given two sets, Write a function to provide the union of them. STL not allowed to be used.
    Optimise for Time and space. 24


    --------------------------------------------------------------------------------

    Given a binary tree, write code to check whether it is a binary search tree or not 9


    --------------------------------------------------------------------------------

    Do you have unix experience? Have you heard of WC (word count). Code it in c/c++. You can use STL.


    --------------------------------------------------------------------------------

    Find missing element in an array of 100 elements. 16


    --------------------------------------------------------------------------------

    write push and pop for stack 1


    --------------------------------------------------------------------------------

    Design an algorithm and write code to find nth node from the end in a linked list 3


    --------------------------------------------------------------------------------

    Design an algorithm and write code to shuffle a standard deck of cards 1


    --------------------------------------------------------------------------------

    Design an algorithm and write code to serialize a binary tree. Discuss various solutions 18


    --------------------------------------------------------------------------------

    Design an algorithm and write code to find two numbers in an array whose sum equals a given value 19


    --------------------------------------------------------------------------------

    Print BST level by level 7


    --------------------------------------------------------------------------------

    Find Nth last element in a linked list 4


    --------------------------------------------------------------------------------

    Given 2 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2) 9


    --------------------------------------------------------------------------------

    Check if binary representation of an int is a palindrome or not. 21


    --------------------------------------------------------------------------------

    Write in java a method to parse an integer from a string 2


    --------------------------------------------------------------------------------

    Count characters in a string, wanted to see a hashtable used. 5


    --------------------------------------------------------------------------------

    count bits in an integer. Solved using mask, did not attempt -1 approach. 6


    --------------------------------------------------------------------------------

    Reverse a linked list 10


    --------------------------------------------------------------------------------

    Given two binary trees, find whether or not they are similar. 12


    --------------------------------------------------------------------------------

    Determine is a graph is circular. 6


    --------------------------------------------------------------------------------

    Algorithm: You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level. Discussed on phone and asked me to email Java code for my algorithm. 4


    --------------------------------------------------------------------------------

    Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8


    --------------------------------------------------------------------------------

    2nd phone interview: reverse linklist(so stupid, I was too focus on the rule using the exist library much better than build something new(Effctive Java) and when the intervier insisted on asking me to give the non extra memory consuming answer, I was stucked for a while then I told her to move on the next topic. Find the duplicate number from an array. I gave the hash solving method.but I also gave her other answers.


    --------------------------------------------------------------------------------

    Write code to reverse vowels of string 1


    --------------------------------------------------------------------------------

    Here is a tree. It's a binary tree but in no particular order. How do you write this tree to a file so that it can be reread in an reconstructed exactly as shown? 33


    --------------------------------------------------------------------------------

    Multiply a number by 7 without the * operator. 7


    --------------------------------------------------------------------------------

    I want to see if all the ones in a number appear on the right side of the number and all zeros appear on the left, how can I do this most efficiently? (i.e. 00000111 is true but 100010 is false) 7


    --------------------------------------------------------------------------------

    no.of 1 bits in a number ---program 3


    --------------------------------------------------------------------------------

    find dup number for n+1 numbers from 1...n 1


    --------------------------------------------------------------------------------

    Phone Screen 2: Check whether the bit representation of integer is a palindrome
    Multithreading and operating system stuff 1


    --------------------------------------------------------------------------------

    Given two dates, Design an algorithm to return whether the dates are exactly a month apart, less than a month apart or more than a month apart. 2


    --------------------------------------------------------------------------------

    Print out a multiplication table, i wasnt told what kind of data structure it is, just that it has 1*1=1, 1*2=2, ...... 200*200=40000, ..... values. 2


    --------------------------------------------------------------------------------

    Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:

    static long shuffles(int nCards,int iCut); 4


    --------------------------------------------------------------------------------

    The hardest question to date on a phone interview. he asked me to take 2 hours and write the following API.

    Create an LRU Cache that caches some key/value pair and kicks out the Least Recently Used when you run out of space. Wanted run times and asked me to comment on how good my implementation is and whether its good for industry level usage.


    --------------------------------------------------------------------------------

    Asked me to reverse a Linked list without re-creating a new one. I did it recursively going all the way to end and linking it backwards after the recursive call. Had to pass in two nodes though, one previous and one current. He said he likes iteration better becoz its more resource friendly :)


    --------------------------------------------------------------------------------

    Write a method to shufle the deck. The constraint is it has to be a perfect shuffle - in other words, every 52! permutations of the deck has to be equally like (given a completely random function which is theoretical of course).

    I managed to do this with a simple for loop in O(n) time


    int[] deck = new int[52];
    for(int i=0; i<52; i++)
    deck[i] = i;

    Random r = new Random();
    for(int i=0; i
    int ran = r.nextInt(deck.length-i) + i;
    int temp = deck[i];
    deck[i] = deck[ran];
    deck[ran] = temp;
    }


    --------------------------------------------------------------------------------

    Design a data structure for storing sparse arrays. Implement multiplications of such arrays. 2


    --------------------------------------------------------------------------------

    reverse linked list. Why don't you use recursion? 5


    --------------------------------------------------------------------------------

    Homework: Reverse all the words in a string.


    --------------------------------------------------------------------------------

    Algorithm and code to detect occurence of a string(patterns) in another string ex: aab, aababa 5


    --------------------------------------------------------------------------------

    Asked to code the 'floodFill' method used by graphic products like Paint. 2


    --------------------------------------------------------------------------------

    Design the classes for Tic Tac Toe. Implement make next move method for the computer player and make sure that the computer wouldn't lose.


    --------------------------------------------------------------------------------

    Design the game Othello. Write the code to check whether someone has won the game.


    --------------------------------------------------------------------------------

    Implement class Stack using a linked list.


    --------------------------------------------------------------------------------

    void removeChars(char *str, char *delete). Remove characters in str that is in delete. 2


    --------------------------------------------------------------------------------

    Find nth to the last node in a single linked list.


    --------------------------------------------------------------------------------

    Write a function that would find the one value that occurs an odd number of times in an array. ie; function would return "r" if "ttttjjrll" is passed in. 3


    --------------------------------------------------------------------------------

    If you are given a number as a parameter, write a function that would put commas after every third digit from the right.


    --------------------------------------------------------------------------------

    Discuss the code of pre-order traversal of a tree.


    --------------------------------------------------------------------------------

    Write code to find n-th to last node in a linked list


    --------------------------------------------------------------------------------

    Write code to delete a node in circular linked list


    --------------------------------------------------------------------------------

    A phone screen. Write a atoi function for decimal. Expected me to "tell" the code right
    from "declare a variable i of type int" to the actual logic. Once this was done generalize it do the atoi for any radix.


    --------------------------------------------------------------------------------

    How do you determine the size of an object in Java?


    --------------------------------------------------------------------------------

    Implement the unix command WordCount (wc) using lenguage of your choice. The method takes a string and returns the number of words in the string, number of chars and the number of lines.


    Computer Architecture & Low Level [more]
    When would a program crash in a buffer overrun case. Gave me,
    buff[50];
    for( int i=0; i <100; i++ )
    buff[i] = 0;

    What will happen to first 50 bytes assigned, when would the program crash 5


    --------------------------------------------------------------------------------

    What is buffer overflow and how do you exploit it? 1


    Data structure [more]
    What is the difference between arrays and linked lists? What is the advantage of contiguous memory over linked lists?


    --------------------------------------------------------------------------------

    Given a file containing approx 10 million words, Design a data structure for finding all the anagrams in that set


    Database [more]
    database question like self joint with tables given by him


    --------------------------------------------------------------------------------

    Explain how to write a stored procedure in SQL 1


    Experience [more]
    What sort of commenting standards do you use 1


    --------------------------------------------------------------------------------

    From 1 - 10, rate c++, c, java, unix, sql skills


    --------------------------------------------------------------------------------

    Most challenging project 2


    --------------------------------------------------------------------------------

    How much experience do you have with unix


    --------------------------------------------------------------------------------

    Talk about your favourite project? What part of a Software Project do you enjoy most?


    --------------------------------------------------------------------------------

    Tell me about your work experiences in the past?


    --------------------------------------------------------------------------------

    asked some questions based on my previous job


    --------------------------------------------------------------------------------

    Lunch - QA manager.

    1. tell me a situation when u had to face problems and the requirements were not clear. how did u handle the situation?

    2. which is the best error you have caught?

    3. which is the worst error u've ever caught?

    4. asked about a project on my resume


    --------------------------------------------------------------------------------

    XML: How have you used XML in your previous projects?


    --------------------------------------------------------------------------------

    focus on my last project


    --------------------------------------------------------------------------------

    What was your hardest techincal project?


    --------------------------------------------------------------------------------

    What was the most interesting thing you have ever done (technical or non technical) ?


    --------------------------------------------------------------------------------

    Mailed me this code and asked to find the mistakes in the code

    class Base {
    public:
    Base(int numElements) {
    m_baseArray = new int[numElements];
    }
    ~Base { //non-virtual
    delete [] m_baseArray;
    }
    private:
    int* m_baseArray;
    }
    class Derived : public Base {
    public:
    Derived(int numElements) : Base(numElements) {
    m_derivedArray = new int[numElements];
    }
    ~Derived() {
    delete[] m_derivedArray;
    }
    private:
    int* m_derivedArray;
    }
    int main(int argc, char** argv) {
    Base* base = new Derived(3);
    delete base;
    return 0;
    }

    What is wrong with the code ? 5


    --------------------------------------------------------------------------------

    Projects


    Ideas [more]
    If you had the entire text to 65 million books in a database, what would you do with it? 9


    Java [more]
    What is the difference between Inheritance and Interfaces? Under what conditions would you prefer one over the other? 2


    --------------------------------------------------------------------------------

    What is Garbage Collection in Java. How is it implemented? What kind of algorithms does the garbage collector use? How does it know that references can be collected? What are advantages and disadvantages of garbage collection?


    Math & Computation [more]
    You have a basket ball hoop and someone says that you can play 1 of 2 games. You get $1000 and one shot to get the hoop. Or, you get three shots and you have to make 2 of 3 shots. Which one do you choose? If p is the probability of making a particular shot, what value of p makes you switch games? 16


    --------------------------------------------------------------------------------

    Some question about random sampling and buffer read. Don't remember exactly. Had to do with calculating the probabilty and stuff.


    --------------------------------------------------------------------------------

    When i wasn't certain whether my random function generated with equal probability all permutations, the interviewer asked me to write a formal proof that it works or not and send it to him (really strange).

    Proved it with the following and he bought it:
    Probabilisticly
    card 1 has 52 positions it can fit in
    card 2 has 51
    card 3 has 50
    so on and so forth
    card 52 has 1 position to fit in

    hence its 52 x 51 x 50 x ... x 1 = 52! can be generated using this shuffle.

    Oblivious to me, aparantly this kind of shuffle is used a lot in online card games. Silly me :P


    --------------------------------------------------------------------------------

    Brainteaser: there is a bar with 25 seats in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjecent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others. So where should the first customer sit. 9


    --------------------------------------------------------------------------------

    Write a program which makes the probablity of getting the even number when a dice is thrown in 72%( some number other than 50%).


    Multiple Questions in One [more]
    Phone Screen 1: Serialize and deserialize a binary tree/graph
    General Unix questions
    C++ questions
    Design classes to represent a deck of cards


    Object Oriented Design [more]
    Design the classes and objects for a generic deck of cards that would be used in a poker game 4


    --------------------------------------------------------------------------------

    Describe the classes and data structures you would use for a file system 23


    --------------------------------------------------------------------------------

    How would you implement a map (not a map of like a city... just a set of keys which "map" to values")
    - Give two data structures you could use
    - What is average and worst case insert time, delete time, look up time
    - What are pros/cons of each 7


    --------------------------------------------------------------------------------

    Design a graph class. Write the C++ interface for it. 3


    --------------------------------------------------------------------------------

    QA engineer -

    1. say you have a calculator service running on a server. Automate the process of testing it. i.e. by one click of a buttonu should be able to test it.

    2. how would you do the same if you did not have access to the input and expected output. for example. no excel sheet that has the expected values. generate the 2 inputs on the fly. now how would you automate the testing.

    3. discuss data structures for NOTEPAD. discuss with reference to bufferer write.


    --------------------------------------------------------------------------------

    Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8


    --------------------------------------------------------------------------------

    The bigger the ratio between the size of the hash table and the number of data elements, the less chance there is for collision. What is a drawback to making the hash table big enough so the chances of collision is ignorable? 2


    --------------------------------------------------------------------------------

    Here is a graph of distribution centers and the weight to go from one to another. How would you represent this using a data structure? Code an alogrithm that allows me to check if there is a path from one node to another and what the weight of this path is. 1


    --------------------------------------------------------------------------------

    Imagine you're implementing the game of chess. Design the classes, objects and heirachies behind it.


    --------------------------------------------------------------------------------

    Design a deck of cards


    --------------------------------------------------------------------------------

    Design the data structures and algorithms for a LRU (Least Recently Used) Cache 3


    --------------------------------------------------------------------------------

    Design a Deck of Cards 1


    --------------------------------------------------------------------------------

    Asked me to take some time around 1 hour and create an API that could read names,emp ID's,phone numbers, office names in that order from a file and stores them and has the following functionality:

    1) getEmployeeById
    2) getEmployeeByName
    3) getEmployeesByName
    4) editEmployeeInfoById
    5) editEmployeeInfoByName


    --------------------------------------------------------------------------------

    Design a data structure for storing sparse arrays. Implement multiplications of such arrays. 2


    --------------------------------------------------------------------------------

    reverse linked list. Why don't you use recursion? 5


    --------------------------------------------------------------------------------

    OO design related question? How would you design a class structure for animals in a zoo


    --------------------------------------------------------------------------------

    Design the classes for Tic Tac Toe. Implement make next move method for the computer player and make sure that the computer wouldn't lose.


    --------------------------------------------------------------------------------

    Design the game Othello. Write the code to check whether someone has won the game.


    --------------------------------------------------------------------------------

    Design the classes and data structures for a parking lot


    --------------------------------------------------------------------------------

    Look within the book. Each person can look at 20% of the book at a time. Only 70% of the book can be served to all users. Design the data structures for this. 4


    --------------------------------------------------------------------------------

    How would you do a design of a monopoly game (later changed to a chess game)?


    --------------------------------------------------------------------------------

    How would you design a file system using class diagrams and what data structure would you use?


    --------------------------------------------------------------------------------

    Discuss the important features of Object Oriented Programming


    --------------------------------------------------------------------------------

    Model a chess game


    System Design [more]
    Imagine that there are 7 servers running in parallel. What happens when you need to expand to 20 live? What are issues? What could you do to fix this issue in the future? 6


    --------------------------------------------------------------------------------

    Algorithm: You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers? 14


    --------------------------------------------------------------------------------

    You have a website which has 5 reads on a database when it is loaded. Each read takes 7 seconds for a total of 35 seconds, discuss how you could improve the performance? 5


    --------------------------------------------------------------------------------

    Say you have a system. The design is good. But performance is not good. How would you find where the problem is? went on for about half an hour about it. 3


    --------------------------------------------------------------------------------

    the "logging in" feature of amazon.com has a problem. isolate the problem.


    --------------------------------------------------------------------------------

    App server+DB server, solve the querying delay problem...


    --------------------------------------------------------------------------------

    How would you design the software that runs on an ATM machine? The software should support operations such as checking balance, transfer funds from one account to another, deposits and withdrawals.


    Terminology & Trivia [more]
    Difference between class and object 16


    --------------------------------------------------------------------------------

    What's the max look up time for a binary tree 21


    --------------------------------------------------------------------------------

    What's the point of inheritance? 4


    --------------------------------------------------------------------------------

    What's the max insertion time for a hash table 8


    --------------------------------------------------------------------------------

    Why would you use an array vs linked-list 14


    --------------------------------------------------------------------------------

    What is a Pure Function? 3


    --------------------------------------------------------------------------------

    What is a linked list? What are its advantages over arrays? 7


    --------------------------------------------------------------------------------

    exception handling, C++ basics, bitwise operations


    --------------------------------------------------------------------------------

    What is an array? What is a Linked List, Map.


    --------------------------------------------------------------------------------

    Complexity of insertion and deletion for linked list.


    --------------------------------------------------------------------------------

    Unix: You want to kill a process that has been running for a long time, how to do that? 2


    --------------------------------------------------------------------------------

    XML: Differentiate between SAX and DOM. 1


    --------------------------------------------------------------------------------

    Data Structures: Time complexities for HashTable, Linked List, Binary Search, Array. 1


    --------------------------------------------------------------------------------

    Java: Differentiate between final, finally and finalize


    --------------------------------------------------------------------------------

    Java: How does the synchronized keyword work? What happens when you use it on a static method?


    --------------------------------------------------------------------------------

    Java: Talk to me about the Java Collections API


    --------------------------------------------------------------------------------

    MultiThread, Garbage Collection. Tomcat distribute request(Java Spaces), http protocal. Socket programming...


    --------------------------------------------------------------------------------

    to find a telephone number in dir and subdir (find command is the answer)


    --------------------------------------------------------------------------------

    What is Polymorphism, how do virtual functions work


    --------------------------------------------------------------------------------

    When would a program crash in a buffer overrun case. Gave me,
    buff[50];
    for( int i=0; i <100; i++ )
    buff[i] = 0;

    What will happen to first 50 bytes assigned, when would the program crash 5


    --------------------------------------------------------------------------------

    Asked me to describe the difference between final, finally and finalize in java. (The last one is tricky coz we rarely use it) 3


    --------------------------------------------------------------------------------

    Define "class" and "object."


    --------------------------------------------------------------------------------

    What does the keyword "final" do when put in front of a Collection in Java? 1


    --------------------------------------------------------------------------------

    Asked me the differnce between using Abstract class vs interface on a real world problem im working on (at one point he settled for an answer where is said "it's just intuitively wrong" - however, he tried to trick me into justifying using the wrong thing, I had to say that there is no justification for using this technique here, took a little bit of guts but he liked it)


    --------------------------------------------------------------------------------

    array vs list


    --------------------------------------------------------------------------------

    Java. final, finalize, finally


    --------------------------------------------------------------------------------

    What are thread, why are they used in programming?


    --------------------------------------------------------------------------------

    Difference between polmorphism and inheritance?


    --------------------------------------------------------------------------------

    Difference between class and object?


    --------------------------------------------------------------------------------

    Questions about C++/Java and Design Patterns.


    --------------------------------------------------------------------------------

    When would you create an interface class. 2


    --------------------------------------------------------------------------------

    How would a copy constructor behave if the class had an Object as a member Variable?


    --------------------------------------------------------------------------------

    Explain the relationship between Equals and Hashcode in Java. 1


    --------------------------------------------------------------------------------

    What is a tree? How do you traverse a tree? 1


    --------------------------------------------------------------------------------

    What's the difference between virtual methods in C++ and Java? 1


    --------------------------------------------------------------------------------

    What's the difference between == and Equals()?


    --------------------------------------------------------------------------------

    What is Perfect/Universal hashing?


    --------------------------------------------------------------------------------

    What are the advantages and disadvantages of function lining?


    --------------------------------------------------------------------------------

    How do you determine the size of an object in Java?


    --------------------------------------------------------------------------------

    What is Context Free Grammar? What is it used for?


    --------------------------------------------------------------------------------

    When does the Operating Systems do a Context Switch? 1


    Testing [more]
    3. What is black box testing?
    4. What do you include in a test plan? 1


    --------------------------------------------------------------------------------

    Say you have a system. The design is good. But performance is not good. How would you find where the problem is? went on for about half an hour about it. 3


    --------------------------------------------------------------------------------

    Suppose there is a problem with the address change feature on Amazon.com. How would you test it? What data sets would you test it against? How would you decide on such a data set?


    --------------------------------------------------------------------------------

    say u are in charge of the "login" fature of amazon.com. TEST IT.


    --------------------------------------------------------------------------------

    the "logging in" feature of amazon.com has a problem. isolate the problem.


    --------------------------------------------------------------------------------

    QA engineer -

    1. say you have a calculator service running on a server. Automate the process of testing it. i.e. by one click of a buttonu should be able to test it.

    2. how would you do the same if you did not have access to the input and expected output. for example. no excel sheet that has the expected values. generate the 2 inputs on the fly. now how would you automate the testing.

    3. discuss data structures for NOTEPAD. discuss with reference to bufferer write.


    --------------------------------------------------------------------------------

    say i give you a universal vegetable cutter which claims that it can cut any kind of vegetable. TEST IT.


    --------------------------------------------------------------------------------

    How would you test an ATM in a distributed banking system.


    --------------------------------------------------------------------------------

    How would you load test a web page without using any test tools 3


    --------------------------------------------------------------------------------

    Suppose there is a problem with calculation of taxes on the amazon.com website. How would you isolate the problem. Once isolated and fixed, how would you go ahead and test it?