Microsoft Interview Question
Web:
www.microsoft.com
|
HQ:
Redmond, WA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,272 Interview Reviews |
Back to all Microsoft Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Development Engineer at Microsoft:
Dec 30, 2011
Pancakes, size varies, and are put in a stack with random order. You have one operation called Flip(int[] pancakes, int k) to flip all pancakes from the top one to kth pancake, write a sort(int[] pancakes]) method
Add Tags
[?]
See more for this Microsoft Software Development Engineer Interview
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (6)
Jan 4, 2012
Never mind the previous comment, misread the description of the Flip operation
Helpful Answer?
Yes |
No
Inappropriate?
Feb 3, 2012
Could you make a more clear description the operation of Flip functon? Thanks!
Helpful Answer?
Yes |
No
Inappropriate?
Feb 4, 2012
For example, if pancakes are {1,2,4,3}, (number means pancake sizes), and if we flip(pancakes, 2), then the first two pancakes are flipped and result will be {2,1,4,3}
Helpful Answer?
Yes |
No
Inappropriate?
Mar 6, 2012
Well, selection sort would work, but it's slow. Find position j of the minimum between [i,n-1], starting with i = 0. If j != i, then use Flip(pancakes,n-j) to get it to the top, then flip to its subsequent minimum position i, therefore Flip(pancakes,n-i). Keep repeating until increasing i reaches n.
Helpful Answer?
Yes |
No
Inappropriate?
Mar 6, 2012
Hmm, if indirect sorting is allowed (via pointers in extra space), then one could use quicksort,
and place into target positions by flipping. But if that flipping is the only operation available, then even finding the minimum value AND it's current position for the selection sort above gets nontrivial (but doable).
and place into target positions by flipping. But if that flipping is the only operation available, then even finding the minimum value AND it's current position for the selection sort above gets nontrivial (but doable).
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Development Engineer Interview Questions, Microsoft Interview
0 of 0 people found this helpful
by Anonymous: