1)Given two sorted linked lists list1,list2. Combine the two list into a new sorted list with our creating new nodes.-All give the test case for testing the same2)You have to count the occurances of all words in a document. You are given a method chat * GetNextWord, that returns the next word from the document.- Which datastructure can be userd to achieve this- Write a algorithm for the same- What is the order of the above algorithm

Interview Candidate
Oct 12th, 2006
12
9960

Showing Answers 1 - 12 of 12 Answers

sumit

Nov 15th, 2006

use BST to store the words along with their count . insertion and search will have a complexiety of O(log n)

Suman Deb Roy

Jun 29th, 2007

use merge sort ..well modified merge sort

Zirammem
Profile Answers by Zirammem

Feb 24th, 2008

1=> Merge-Sort.
2=>simple 'while' loop; take next word using GetNextWord, read until EOF, increment count; ans is the count.

Udit Agarwal
Profile Answers by Udit Agarwal

Dec 10th, 2010

ASSUMPTIONS: 'list' is a class with head as public data member and 'getlist()' & 'print()' are it's member functions.
'struct node' has node() constructor.

node* merge(list l1, list l2)
{
   node* p =l1.head ;
   node* q= l2.head;
   node* r= NULL ;
   node* tmp;
   while (p != NULL && q != NULL)
   {
   if (p->a < q->a )
   {
   tmp = p->next ;
   p->next = q;
   if (r != NULL)
   {
   r->next = p;
   }
   r = p;
   p = tmp;
   }
   else
   {
   if (r == NULL)
   l1.head = q;
   tmp = q->next;
   q->next = p;
   if (r != NULL)
   {
   r->next = q;
   }
   r = q;

   q = tmp;
   }
   }
   l1.print();
}