Thursday, January 5, 2012

Interview Questions: 3. Stack, Queue, List


Stack

Problem - 1: Reverse a Stack in place:void PercolateUp()
{
       Element a,b;
       if(IsEmpty())
               return;

       a = Pop();
       if(IsEmpty())
       {
               Push(a);
               return;
       }

       Percolate();
       b = Pop();
       Push(a);
       Push(b);
}

void Reverse()
{
       Element a;
       if(IsEmpty())
               return;
       PercolateUp();
       a = Pop();
       Reverse();
       Push(a);
}

Queue

Problem - 1: Implement circular queues
 /*class Queue {
    public:
        Queue() {
            cout << "Inside Queue()" << endl;
            _front = 0;
            _rear = 0;
        }
        int push(int data);
        int pop();
        bool isEmpty();
        bool isFull();
        ~Queue() {
            cout << "Inside ~Queue()" << endl;
        }
    private:
        static const int _size = 10;
        int _data[_size];
        int _front;
        int _rear;
};
int Queue::push(int data){
    if(!isFull()) {
        _rear = (_rear + 1) % _size;
        _data[_rear] = data;
        cout << "Queue::pushed: "<< _data[_rear] << endl;
        return 0;
    } else {
        cout << "Over Flow!" << endl;
        return -1;
    }
}

int Queue::pop() {
    if(!isEmpty()) {
          _front = (_front + 1) % _size;
          cout << "Queue::poped: "<< _data[_front] << endl;
          return _data[_front];
    } else {
        cout << "Under Flow!" << endl;
        return -1;
    }
}


bool Queue::isEmpty() {
    if (_front == _rear)
        return 1;
    else
        return 0;
    
}
bool Queue::isFull() {
    if ((_rear+1) % _size == _front)
        return 1;
    else
        return 0;
}

Link-List

Problem - 1: Return Nth the node from the end of the linked list in one pass.
Node * GetNthNode ( Node* Head , int NthNode )
{
      Node * pNthNode = NULL;
      Node * pTempNode = NULL;
      int nCurrentElement = 0;
     
for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )
      {
            nCurrentElement++;                 
            if ( nCurrentElement - NthNode == 0 )
            {
                  pNthNode = Head;
            }
            else
            if ( nCurrentElement - NthNode > 0)
            {
                  pNthNode = pNthNode ->pNext;
            }                            
      }
      if (pNthNode )
      {
            return pNthNode;
      }
      else
            return NULL;
}
Time complexity : O( n  )
Space complexity : O(1), constant
Problem - 2: Reverse a singly linked list

Approach 1 -  Iterative version with three variable
Node* ReverseList( Node ** List )      
{

   Node *temp1 = *List;
   Node * temp2 = NULL;
   Node * temp3 = NULL;

   while ( temp1 )
   {
         *List = temp1; //set the head to last node           
temp2= temp1->pNext; // save the next ptr in temp2
         temp1->pNext = temp3; // change next to privous
         temp3 = temp1;
         temp1 = temp2;
   }

   return *List;
}
Time complexity : O( n  )
Space complexity : O(1), constant


Approach 2 Recursive reverse 
List recursiveReverse(List L)
{
    List first, rest;
    if(!L)
        return NULL;
    first = L;
    rest = L->next;
    if(!rest)
        return NULL;
    rest = recursiveReverse(rest);
    first->next->next = first;
    first->next = NULL;
    L=rest;
    return L;

Time complexity : O( n  )
Space complexity : O(1), constant


Approach 3 Iterative version with only one variable
Swap (Node* A, Node* B)
{
        A = (node *) ((unsigned long) A ^(unsigned long) B);
        B= (node *) ((unsigned long)  A ^(unsigned long) B);
        A =(node *) ((unsigned long) A ^ (unsigned long) B);

}

void reverse (node* head)
{
    node *temp=NULL;
    while(true)
    {
        if(head->next==NULL)
        {
            head->next=temp;
            break;
        }
        Swap(head->next, temp);
        Swap(head, temp);
    }
}
Time complexity : O( n  )
Space complexity : O(1), constant



Problem - 3: Delete a node in single non circular  linked list
void deleteNode(node *n)
{
if(n == NULL)
    return;
p = NULL;
if(n->next == NULL)
    {
    while(n->next != NULL)
        {
         p = n;
         n = n->next;
        }
    }
else
    {
    p = n->next
    n->data = p->data;
    n->next = p->next;
    }
    delete p;
}
Time complexity : Avg O(1  ), worst case O(n)
Space complexity : O(1), constant


Problem - 4: Implement "Merge Sort" for "Link List"?
line merge_sort (line list1) 
    {
    if (list1 == NULL || list1.next == NULL)
        return list1;
    line list2 = split (list1);
    list1 = merge_sort (list1);
    list2 = merge_sort (list2);
    return merge (list1, list2);
    }
line split (line list1)
    {
    if (list1 == NULL)
        return list1;
    if (list1.next == NULL)
        return list1.next;
    line list2 = list1.next;
    list1.next = list2.next;
    list2.next = split (list2.next);
    return list2;
    }

line merge (line list1, line list2) 
    {
    if (&list1 == NULL) 
        return list2;
    if (list2 == NULL) 
        return list1;
    if (list1.data < list2.data) 
        {
        list1.next = merge (list1.next, list2);
        return list1;
        }
    else 
        {
        list2.next = merge (list1, list2.next);
        return list2;
        } 
    }
Time complexity : O(n log n  )
Space complexity : O(1), constant



Problem - 5:  There are two singly linked lists l1 and l2 representing polynomials in X. we have to find difference b/w lists l1-l2. lists are in orders of descending powers.
constraints: no extra space i.e. O(1) space O(m+n) time complexity m and n and nodes in the lists.

struct node{
int coeff;
int power;
node *next;
};

Subtract (Poly* A, Poly* B)

{
while (A && B)
    {
    poly * r = new poly ();
    if (A->C > B->C)
        {
        r->c = A->C;
        r->P = A->P;
        AddLL(r);
        A = A->Next;
        }
   else if (A->C < B->C)
        {
        r->c = B->C;
        r->P = B->P;
        AddLL(r);
        B = B->Next;
        }
    else
        {
        r->c = A->C - B->C;
        r->P = A->P;
        AddLL(r);
        B = B->Next;
        A = A->Next;
        }
    }
while (A || B)
    {
    poly * r = new poly ();
    if(A != NULL)
        {
        r->c = B->C;
        r->P = B->P;
        AddLL(r);
        B = B->Next;
        }
    else
        {
        r->c = A->C;
        r->P = A->P;
        AddLL(r);
        A = A->Next;
        }
    }
}

Problem -  6: Evaluate a polynomial
typedef struct node
    {
  float cf;
  float px;
  float py;
  struct node *next;
    }mynode;
float evaluate(mynode *head, float x, float y)
    {
   float x,y,sum;
   sum = 0;
   mynode *poly;

   for(poly = head->next; poly != head; poly = poly->next)
       {
     sum = sum + poly->cf * pow(x, poly->px) * pow(y, poly->py);
       }

   return(sum);
    } 

Problem - 7: There are two link list...having a common tail...i.e they are in a Y shape...find the point of intersection in O(n) time and constant extra space.
1) Take 2 pointers. ptr1 and ptr2
2) Start moving towards tail.
3) As soon as one of pointer reaches last node, start counter.
4) When the next pointer also reaches last node, stop counter.
5) Now you know, what is difference in length of two list.
6) Initialize the two pointers again with the two linked lists heads.
7) move the pointer with longer linked list by counter number of nodes, so that now the lengths are equal for both.
8) start moving both pointers now and as soon as they hit the same node, it is the intersection.

Problem - 8: Detect and remove loop in link list
1. Loop Detection: Take two pointers Fast and Slow (Slow jumps one step at a time while Fast two step)
    While (Fast != NULL)
        if(Fast == Slow)
              return true;
        else
             fast = fast->next->next
             slow = slow->next
     return false;
2. Loop Length: After detecting loop stop one pointer and increment other pointer by 1 step untill
Loop
    if (fast == slow)
    break;
else
    slow++
    LoopLength++
EndLoop

3. Loop Position: You can find out loop start position also.
     Fast = Slow = Start
     Fast += LoopLenght
    Loop
        If Fast != Slow
        Fast++;
        Slow++
    EndLoop
4. Loop Removal:Fast and Slow Both are pointing to the start of loop position.
    Loop
        if(Slow == Fast->next)
            break;
        Fast = Fast->next;
     Fast->next = NULL;

Problem - 9: Return Nth the node from the end of the linked list in one pass.

Node * GetNthNode ( Node* Head , int NthNode )
{
      Node * pNthNode = NULL;
      Node * pTempNode = NULL;
      int nCurrentElement = 0;
      for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )
      {
            nCurrentElement++;                 
            if ( nCurrentElement - NthNode == 0 )
            {
                  pNthNode = Head;
            }
            else
            if ( nCurrentElement - NthNode > 0)
            {
                  pNthNode = pNthNode ->pNext;
            }                            
      }
      if (pNthNode )
      {
            return pNthNode;
      }
      else
            return NULL;
}

No comments:

Post a Comment