IT Interview Questions

(From Microsoft) Assume I have a linked list contains all of the alphabets from ‘A’ to ‘Z’. I want to find the letter ‘Q’ in the list, how does you perform the search to find the ‘Q’?Answer: In a linked list, we only know about the header and other elements are invisible unless we go through the node one by one. Since we have go through every single node to find ‘Q’, the search time for a linked list is linear which is O (N).

1. How do you write a function that can reverse a linked-list? (Cisco System)

void reverselist(void)
{
  if(head==0)
    return;
        if(head->next==0)
    return;
  if(head->next==tail)
  {
    head->next = 0;
    tail->next = head;
  }
   else
  {
    node* pre = head;
    node* cur = head->next;
    node* curnext = cur->next;
    head->next = 0;
    cur->next = head;

    for(; curnext!=0; )
    {
      cur->next = pre;
      pre = cur;
      cur = curnext;
      curnext = curnext->next;
    }

    curnext->next = cur;
  }
}

2. What is polymorphism?

Polymorphism is the idea that a base class can be inherited by several classes. A base class pointer can point to its child class and a base class array can store different child class objects.

Q: What is the difference between Stack and Queue? A: Stack is a Last In First Out (LIFO) data structure.

Queue is a First In First Out (FIFO) data structure

Q: Write a fucntion that will reverse a string. (Microsoft)

A: char *strrev(char *s)

{

int i = 0, len = strlen(s);

char *str;

if ((str = (char *)malloc(len+1)) == NULL) /*cannot allocate memory */

err_num = 2;

return (str);

}

while(len)

str[i++]=s[–len];

str[i] = NULL;

return (str);

}

Q: What is the software Life-Cycle?

Q1 What are the advantages and disadvantages of B-star trees over Binary trees? (Asked by Motorola people)A1 B-star trees have better data structure and are faster in search than Binary trees, but it’s harder to write codes for B-start trees.

Q2 Write the psuedo code for the Depth first Search.(Asked by Microsoft)

A2

dfs(G, v) //OUTLINE
Mark v as “discovered”
For each vertex w such that edge vw is in G:
If w is undiscovered:
dfs(G, w); that is, explore vw, visit w, explore from there
as much as possible, and backtrack from w to v.
Otherwise:
“Check” vw without visiting w.
Mark v as “finished”.

1.Question: Suppose that data is an array of 1000 integers. Write a single function call that will sort the 100 elements data [222] through data [321].
Answer: quicksort ((data + 222), 100);

2.Question: Which recursive sorting technique always makes recursive calls to sort subarrays that are about half size of the original array?
Answer: Mergesort always makes recursive calls to sort subarrays that are about half size of the original array, resulting in O(n log n) time.