

Title: Any yahoo interview questions Post by dav on Nov 8^{th}, 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 10^{th}, 2005, 10:52pm Any updates ??? :o 

Title: Re: Any yahoo interview questions Post by towr on Nov 11^{th}, 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 12^{th}, 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 13^{th}, 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 14^{th}, 2005, 12:18am on 11/13/05 at 19:44:34, dav wrote:


Title: Re: Any yahoo interview questions Post by dav on Dec 2^{nd}, 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 2^{nd}, 2005, 2:39am the easiest way, [hideb] Find the columnindex 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 columnindex back until you encounter a 1. Repeat for every row. [/hideb] code: [hideb] max_row=0; int col=0; while (col < n1 && 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 2^{nd}, 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 2^{nd}, 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 12^{th}, 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 13^{th}, 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 10^{th}, 2011, 1:03am If you want to get more materials that related to this topic, you can visit: http://interviewquestionsandanswers.biz/yahoointerviewquestionsandanswers Best regards. 

Title: Re: Any yahoo interview questions Post by Hippo on Oct 10^{th}, 2011, 2:04am on 11/12/05 at 01:44:05, algo_wrencher 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. 

Title: Re: Any yahoo interview questions Post by birbal on Dec 25^{th}, 2011, 5:32am on 10/10/11 at 02:04:11, Hippo wrote:
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 25^{th}, 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 26^{th}, 2011, 9:58am on 12/25/11 at 11:45:23, krishnav wrote:
Nice solution. 

Title: Re: Any yahoo interview questions Post by Grimbal on Dec 28^{th}, 2011, 8:28am on 12/25/11 at 05:32:36, birbal wrote:
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 7^{th}, 2012, 10:53am on 12/28/11 at 08:28:23, Grimbal wrote:
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 26^{th}, 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 © 20002004 Yet another Bulletin Board 