wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> some interview questions
        
(Message started by: Sam on May 7^th, 2006, 9:07pm)

Title: some interview questions
Post by Sam on May 7^th, 2006, 9:07pm

I just want to share some questions which i encontered in an interview.
Sorry ,if these already exist in the forum

1)Given an array on n no.s containing random numbers .lets say

5 4 7 2 4 7 0 1 4 5 50 100

i.e the no.s may repeat .
Now the o/p should be like

5 5 4 4 4 7 7 2 0 1 50 100

i.e the no. which comes first will be printed first followed
by the no. of times it repeats .

This is to be done in O(n).
I can't find an O(n) solution to this.

2)Given 2 sorted arrays A and B . Find the third array
C=A-B i.e C contains only those elements that are in A
and not in B .

A= 1 1 2 5 7 8 length n
B= 2 4 5 7 9 10 length m
C= 1 8

O(nlgm) is what i could think
This is to be done in O(n+m).

Also can anyone tell me a good reference
for Operating System concepts like Process,
threads,synchronization .

Title: Re: some interview questions
Post by towr on May 8^th, 2006, 2:55am

The second question is rather easy. Because both arrays are sorted, you can just traverse both from front to end int he following way:

if A[i] < B[j], add A[i] to C, and increment i
if A[i] > B[j], increment j
if A[i] = B[j], increment i (don't increment both, because A[i+1] might also be equal to B[j] and thus also shouldn't be in C)

For the first question, hashtables might be a solution. But there might be a more elementary solution.

Title: Re: some interview questions
Post by Sam on May 8^th, 2006, 7:51am

Hi towr ,
For the 1st one :

the range of no.s is not fixed .So,in worst case access to hash table will become linear and the resultant complexity will be O(n2) .

Title: Re: some interview questions
Post by towr on May 9^th, 2006, 2:58am

True, but you rarely encounter the worst case when you use a good hash.

Otherwise I can't thing of anything better than O(n log n) at the moment.

Title: Re: some interview questions
Post by techie on May 15^th, 2006, 11:28pm

Towr

i was n't able to understand as tro how will u apply hash in first ques...can u elaborate a bit..plz??

Title: Re: some interview questions
Post by towr on May 16^th, 2006, 2:16am

Assuming you actually want to sort the array.
You can use the hash to make lists of items with the same number. And use another list to get the sequence of first numbers. Then put the itemlists together in the right order..

in pseudocode:

Code:

for(i=0; i < arr.length; i++)
{
if (! hash(arr[i].num)) // if not encountered before make a note so we get the order right
orderlist.append(arr[i].num);
hash(arr[i].num).append(arr[i]); // store the item with the others sharing the same number/key
}

while (orderlist)
{
result.concat(hash(*orderlist)); // concatenate all sublists in the right order
orderlist++;
}

It is simpler if the number makes up all the content of the items in your array, rather than being just a (partial) key. But as it is it would work for ordering, say, all people with the same first name, without making them identical in the process.

Title: Re: some interview questions
Post by Sam on Jun 12^th, 2006, 9:48pm

Hi all ,
Please tell me some good book or online material on processes and thread,synchronization and other OS concepts.