Twitter
4.3 of 5 159 reviews
www.twitter.com San Francisco, CA 1000 to 5000 Employees

Twitter Software Engineer Interview Question

I interviewed in San Francisco, CA and was asked:
"Given an array with all elements sorted on each individual row and column find the K-th smallest one"
Add Tags [?]
Answer Flag Question

Part of a Software Engineer Interview Review - one of 225 Twitter Interview Reviews

Answers & Comments

1
of 1
vote
Top left is the smallest one, obviously. Insert that, along with (0, 0), into a min heap.
while less than k elements have been popped:
   pop the smallest element. Say it's coordinates are (i, j)
   Insert (i+1, j), (i, j+1) into the min heap. These are the possible next smallest numbers.

The element at the root of the min-heap is the k-th smallest element now.
- Jigsaw on Feb 2, 2013 Flag Response
2
of 2
votes
Treat every row in the matrix as a separate stream of numbers.
Merge the streams in an ordered way while decrementing k. When k is zero, your current element is the one in question.
- bg on Mar 4, 2013 Flag Response
1
of 4
votes
Walk through the matrix starting (0, 0).
The comparisons happen between bottom and right values.
If the right value is smaller than bottom, go to the bottom.
If bottom is smaller than right, go right.
Count every time you make a move.
Do this until counter == K or you reach end of matrix.
- deveffort on Jul 5, 2013 Flag Response
0
of 0
votes
The key feature of such a matrix is: The element at (m,n) should be the largest one in the sub matrix (0,0,m,n). So, the search should start from (0,N), then do zig-zag search based on the above feature.
- Jun on Jan 8, 2014 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Twitter – Why Work for Us?

Twitter helps you create and share ideas and information instantly, without barriers. An information network Twitter is a real-time information network that connects you to the latest stories, ideas, opinions and… Full Overview

Provided by employer [?]

Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Twitter interview questions and advice. All interview reviews posted anonymously by Twitter employees and interview candidates.