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

        riddles >> cs >> Any yahoo interview questions
        
(Message started by: dav on Nov 8th, 2005, 3:20am)
Title: Any yahoo interview questions
Post by dav on Nov 8th, 2005, 3:20am
hi,
    If any body knows yahoo interview questions, please post them
Title: Re: Any yahoo interview questions
Post by dav on Nov 10th, 2005, 10:52pm
Any updates ??? :o
Title: Re: Any yahoo interview questions
Post by towr on Nov 11th, 2005, 12:39pm
I think the answer is that nobody here knows any Yahoo interview questions.
Title: Re: Any yahoo interview questions
Post by algo_wrencher on Nov 12th, 2005, 1:44am
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. 8)
Title: Re: Any yahoo interview questions
Post by dav on Nov 13th, 2005, 7:44pm
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.
Title: Re: Any yahoo interview questions
Post by towr on Nov 14th, 2005, 12:18am

on 11/13/05 at 19:44:34, 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. ;)
Title: Re: Any yahoo interview questions
Post by dav on Dec 2nd, 2005, 2:20am
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 ???
Title: Re: Any yahoo interview questions
Post by towr on Dec 2nd, 2005, 2:39am
the easiest way,
[hideb]
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.
[/hideb]

code:
[hideb]
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.
[/hideb]
Title: Re: Any yahoo interview questions
Post by dav on Dec 2nd, 2005, 4:22am
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
Title: Re: Any yahoo interview questions
Post by towr on Dec 2nd, 2005, 5:33am
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).
Title: Re: Any yahoo interview questions
Post by Gautam on Dec 12th, 2005, 3:22pm




#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);
}
Title: Re: Any yahoo interview questions
Post by Grimbal on Dec 13th, 2005, 2:01am
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);
}
Title: Re: Any yahoo interview questions
Post by hamburg113 on Oct 10th, 2011, 1:03am
If you want to get more materials that related to this topic, you can visit: http://interviewquestionsandanswers.biz/yahoo-interview-questions-and-answers

Best regards.
Title: Re: Any yahoo interview questions
Post by Hippo on Oct 10th, 2011, 2:04am

on 11/12/05 at 01:44:05, 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.
Title: Re: Any yahoo interview questions
Post by birbal on Dec 25th, 2011, 5:32am

on 10/10/11 at 02:04:11, 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?
Title: Re: Any yahoo interview questions
Post by krishnav on Dec 25th, 2011, 11:45am
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).
Title: Re: Any yahoo interview questions
Post by birbal on Dec 26th, 2011, 9:58am

on 12/25/11 at 11:45:23, 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.
Title: Re: Any yahoo interview questions
Post by Grimbal on Dec 28th, 2011, 8:28am

on 12/25/11 at 05:32:36, 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.
Title: Re: Any yahoo interview questions
Post by birbal on Jan 7th, 2012, 10:53am

on 12/28/11 at 08:28:23, 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
Title: Re: Any yahoo interview questions
Post by jordan on Feb 26th, 2015, 7:09am
Questions depends on the positions you want to apply. I googled and find many examples on the web.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board