Author |
Topic: Any yahoo interview questions (Read 5134 times) |
|
dav
Newbie
Gender: 
Posts: 47
|
 |
Any yahoo interview questions
« on: Nov 8th, 2005, 3:20am » |
 Quote  Modify
|
hi,
If any body knows yahoo interview questions, please post them
|
|
 IP Logged |
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: Any yahoo interview questions
« Reply #1 on: Nov 10th, 2005, 10:52pm » |
Quote Modify
|
Any updates  
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Any yahoo interview questions
« Reply #2 on: Nov 11th, 2005, 12:39pm » |
Quote Modify
|
I think the answer is that nobody here knows any Yahoo interview questions.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
algo_wrencher
Newbie
I am not insane, I enjoy every moment of it!
Posts: 44
|
|
Re: Any yahoo interview questions
« Reply #3 on: Nov 12th, 2005, 1:44am » |
Quote Modify
|
Sorry for being lazy to reply. Just gathered courage to move out of bed to write this 
There was a question that you are given an array of numbers and you have to find the secnd largest number in N+O(logN) comparisons.
Another one was to build a doubly linked list out of a BST.
And the last one that I can recall is that :
There is a 2D nxn array of 0's and 1's. In any row, no 0 comes before a 1 i.e the array is type of sorted.
Now you have to report the row with max no. of zeros in O(n) time.
Hope you find them good. 
|
|
IP Logged |
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: Any yahoo interview questions
« Reply #4 on: Nov 13th, 2005, 7:44pm » |
Quote Modify
|
towr,
>> I think the answer is that nobody here knows any Yahoo interview questions
Iam sorry, Iam not sure whether these kind of questions can be posted or not. Could you please tell me on this.
>> algo_wrencher,
Thanks for posting the questions.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Any yahoo interview questions
« Reply #5 on: Nov 14th, 2005, 12:18am » |
Quote Modify
|
on Nov 13th, 2005, 7:44pm, dav wrote:towr,
>> I think the answer is that nobody here knows any Yahoo interview questions
Iam sorry, Iam not sure whether these kind of questions can be posted or not. Could you please tell me on this. |
|
It's ok to post them here. But, as with all questions, there's always the chance no one has an answer; or that it takes a while.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: Any yahoo interview questions
« Reply #6 on: Dec 2nd, 2005, 2:20am » |
Quote Modify
|
There is a 2D nxn array of 0's and 1's. In any row, no 0 comes before a 1 i.e the array is type of sorted.
Now you have to report the row with max no. of zeros in O(n) time.
How can we do this o(n) time ..Any ideas
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Any yahoo interview questions
« Reply #7 on: Dec 2nd, 2005, 2:39am » |
Quote Modify
|
the easiest way,
| hidden: |
Find the column-index of the last 1 in the first row.
Look at the same column index for the second row; if it is a zero, the row has more zeros. Move the column-index back until you encounter a 1.
Repeat for every row.
|
code:
| hidden: |
max_row=0;
int col=0;
while (col < n-1 && A[0][col]==1)
col++;
for(row=1; row < n; row++)
if(A[row][col]==0)
{
while(A[row][col]==0 && col>0)
col--;
max_row=row;
}
You only move the column index forward at most n times, and then back at most equally many times. So it's O(n), despite the double loop.
|
|
| « Last Edit: Dec 2nd, 2005, 2:46am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: Any yahoo interview questions
« Reply #8 on: Dec 2nd, 2005, 4:22am » |
Quote Modify
|
Towr,
do we need to really move the index back. We can also do the incremental indexing.
If do we the incremental indexing that means our algorithm is running is more than o(n).
Could you please give me the updates
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Any yahoo interview questions
« Reply #9 on: Dec 2nd, 2005, 5:33am » |
Quote Modify
|
Well, you could start at the back of each row, and increment the r_index (the index counting from back to front.)
Which actually makes the algorithm a bit neater.
But I don't see a good way to only increment the index if you start at the front; because then you only know if you can increment by first looking at all rows and see whether there isn't a zero at that index. So in the worst case, none of the rows has a zero, and you'll look at each index of each row, which is O(n^2).
|
| « Last Edit: Dec 2nd, 2005, 5:34am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Gautam
Guest
|
|
Re: Any yahoo interview questions
« Reply #10 on: Dec 12th, 2005, 3:22pm » |
Quote Modify
 Remove
|
#include<stdio.h>
main()
{
int a[5][5],n,i,j;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&a[i][j]);
i=4;
j=0;
while(i>=0)
{
if(a[j][i]!=0)
{
j++;
}
else
{
n=j;
i--;
}
}
printf("%d\n",n);
}
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Any yahoo interview questions
« Reply #11 on: Dec 13th, 2005, 2:01am » |
Quote Modify
|
It doesn't work if the 1's fill the row...
#include<stdio.h>
main()
{
int a[5][5],i,j;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&a[i][j]);
i=4;
j=0;
while(i>=0 && j<5)
{
if(a[j][i]!=0)
{
j++;
}
else
{
i--;
}
}
printf("%d\n",j);
}
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Any yahoo interview questions
« Reply #13 on: Oct 10th, 2011, 2:04am » |
Quote Modify
|
on Nov 12th, 2005, 1:44am, algo_wrencher wrote:
There was a question that you are given an array of numbers and you have to find the secnd largest number in N+O(logN) comparisons.
|
|
That one is easy ... insert the n elements to heap, perform Findmin, DeleteMin, FindMin  .
I would use Fibonacci heaps, but Binomial are sufficient for this case. It seems to me regular heaps will need at least 2N comparisons.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Any yahoo interview questions
« Reply #14 on: Dec 25th, 2011, 5:32am » |
Quote Modify
|
on Oct 10th, 2011, 2:04am, Hippo wrote:
That one is easy ... insert the n elements to heap, perform Findmin, DeleteMin, FindMin .
I would use Fibonacci heaps, but Binomial are sufficient for this case. It seems to me regular heaps will need at least 2N comparisons. |
|
How can you do it in O(n + logn ) using heaps? can you explain?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
krishnav
Newbie
Posts: 12
|
|
Re: Any yahoo interview questions
« Reply #15 on: Dec 25th, 2011, 11:45am » |
Quote Modify
|
For the second largest element:
you can do a tournament based comparison to first find the max element - This takes O(N). Then just find the max from the list of elements who lost to the max element - this will be the second largest element, takes O(log N).
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Any yahoo interview questions
« Reply #16 on: Dec 26th, 2011, 9:58am » |
Quote Modify
|
on Dec 25th, 2011, 11:45am, krishnav wrote:For the second largest element:
you can do a tournament based comparison to first find the max element - This takes O(N). Then just find the max from the list of elements who lost to the max element - this will be the second largest element, takes O(log N). |
|
Nice solution.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Any yahoo interview questions
« Reply #17 on: Dec 28th, 2011, 8:28am » |
Quote Modify
|
on Dec 25th, 2011, 5:32am, birbal wrote:| How can you do it in O(n + logn ) using heaps? can you explain? |
|
O(n + logn) actually is the same thing as O(n).
The logn part quickly becomes insignificant compared to n.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Any yahoo interview questions
« Reply #18 on: Jan 7th, 2012, 10:53am » |
Quote Modify
|
on Dec 28th, 2011, 8:28am, Grimbal wrote:
O(n + logn) actually is the same thing as O(n).
The logn part quickly becomes insignificant compared to n.
|
|
Yes, i think the original problem says in n+logn "comparisons", and not the order
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
jordan
Junior Member
Gender:
Posts: 63
|
|
Re: Any yahoo interview questions
« Reply #19 on: Feb 26th, 2015, 7:09am » |
Quote Modify
|
Questions depends on the positions you want to apply. I googled and find many examples on the web.
|
|
IP Logged |
My personal fashion blog for hippie and free women Boho and Flower
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print