Author |
Topic: some interview questions (Read 1176 times) |
|
Sam
Newbie
Posts: 30
|
 |
some interview questions
« on: May 7th, 2006, 9:07pm » |
 Quote  Modify
|
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 .
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: some interview questions
« Reply #1 on: May 8th, 2006, 2:55am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sam
Newbie
Posts: 30
|
|
Re: some interview questions
« Reply #2 on: May 8th, 2006, 7:51am » |
Quote Modify
|
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) .
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: some interview questions
« Reply #3 on: May 9th, 2006, 2:58am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
techie
Newbie
Posts: 4
|
|
Re: some interview questions
« Reply #4 on: May 15th, 2006, 11:28pm » |
Quote Modify
|
Towr
i was n't able to understand as tro how will u apply hash in first ques...can u elaborate a bit..plz??
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: some interview questions
« Reply #5 on: May 16th, 2006, 2:16am » |
Quote Modify
|
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.
|
| « Last Edit: May 16th, 2006, 2:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sam
Newbie
Posts: 30
|
|
Re: some interview questions
« Reply #6 on: Jun 12th, 2006, 9:48pm » |
Quote Modify
|
Hi all ,
Please tell me some good book or online material on processes and thread,synchronization and other OS concepts.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print