wu :: forums
« wu :: forums - Any yahoo interview questions »

Welcome, Guest. Please Login or Register.
Nov 4th, 2024, 11:42pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Icarus, william wu, Eigenray, Grimbal, towr, SMQ, ThudnBlunder)
   Any yahoo interview questions
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Any yahoo interview questions  (Read 5132 times)
dav
Newbie
*





   


Gender: male
Posts: 47
Any yahoo interview questions  
« on: Nov 8th, 2005, 3:20am »
Quote Quote Modify Modify

hi,
     If any body knows yahoo interview questions, please post them
IP Logged
dav
Newbie
*





   


Gender: male
Posts: 47
Re: Any yahoo interview questions  
« Reply #1 on: Nov 10th, 2005, 10:52pm »
Quote Quote Modify Modify

Any updates Huh Shocked
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Any yahoo interview questions  
« Reply #2 on: Nov 11th, 2005, 12:39pm »
Quote Quote Modify 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 Quote Modify Modify

Sorry for being lazy to reply. Just gathered courage to move out of bed to write this Wink  
 
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. Cool
 
IP Logged
dav
Newbie
*





   


Gender: male
Posts: 47
Re: Any yahoo interview questions  
« Reply #4 on: Nov 13th, 2005, 7:44pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Any yahoo interview questions  
« Reply #5 on: Nov 14th, 2005, 12:18am »
Quote Quote Modify 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. Wink
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
dav
Newbie
*





   


Gender: male
Posts: 47
Re: Any yahoo interview questions  
« Reply #6 on: Dec 2nd, 2005, 2:20am »
Quote Quote Modify 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 Huh
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Any yahoo interview questions  
« Reply #7 on: Dec 2nd, 2005, 2:39am »
Quote Quote Modify 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: male
Posts: 47
Re: Any yahoo interview questions  
« Reply #8 on: Dec 2nd, 2005, 4:22am »
Quote Quote Modify 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: male
Posts: 13730
Re: Any yahoo interview questions  
« Reply #9 on: Dec 2nd, 2005, 5:33am »
Quote Quote Modify 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

Email

Re: Any yahoo interview questions  
« Reply #10 on: Dec 12th, 2005, 3:22pm »
Quote Quote Modify Modify Remove 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: male
Posts: 7527
Re: Any yahoo interview questions  
« Reply #11 on: Dec 13th, 2005, 2:01am »
Quote Quote Modify 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
hamburg113
Newbie
*





   


Posts: 1
Re: Any yahoo interview questions  
« Reply #12 on: Oct 10th, 2011, 1:03am »
Quote Quote Modify Modify

If you want to get more materials that related to this topic, you can visit: http://interviewquestionsandanswers.biz/yahoo-interview-questions-and-an swers
 
Best regards.
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: Any yahoo interview questions  
« Reply #13 on: Oct 10th, 2011, 2:04am »
Quote Quote Modify 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 Smiley.
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: male
Posts: 250
Re: Any yahoo interview questions  
« Reply #14 on: Dec 25th, 2011, 5:32am »
Quote Quote Modify Modify

on Oct 10th, 2011, 2:04am, Hippo wrote:

That one is easy ... insert the n elements to heap, perform Findmin, DeleteMin, FindMin Smiley.
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 Quote Modify 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: male
Posts: 250
Re: Any yahoo interview questions  
« Reply #16 on: Dec 26th, 2011, 9:58am »
Quote Quote Modify 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: male
Posts: 7527
Re: Any yahoo interview questions  
« Reply #17 on: Dec 28th, 2011, 8:28am »
Quote Quote Modify 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: male
Posts: 250
Re: Any yahoo interview questions  
« Reply #18 on: Jan 7th, 2012, 10:53am »
Quote Quote Modify 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: male
Posts: 63
Re: Any yahoo interview questions  
« Reply #19 on: Feb 26th, 2015, 7:09am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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