Days ago, I took an online interview from Microsoft Shanghai. After some quick
questions, I was asked to solve a simple question, sorting a linked list, in a
online editor, whose content was shared between me and the interviewer in real-time.
Iterate from the head of list to the end. For an element, if it’s larger than the
next one, swap them. Therefore, after the first pass, the largest one goes to the
last position of the list. After the second pass, the second largest one gets to
the second last position. Keep iterating until the list is sorted.
Obviously, the complexity is O(n^2).
Solution 2
Solution 2 solves the problem recursively. The problem of size N can be solved by
solving problem of size N-1 firstly and then inserting the first element into the
sorted list.
The code is cleaner, and the complexity is also O(n^2).
Solution 3
This solution does it in a “divide-and-conquer” way. It divides the problem into
small ones, sorts them, and merges small sorted list into larger ones till the
whole list is sorted.
The inner loop takes O(n) time. The outer loop runs O(lgn) times. So this
soluton is O(nlgn).
The Interview
It sounded rather easy at first glance, and it really is. Within seconds, I told
the interviewer it could be solved by “insertion sorting” since a linked list cannot
be accessed randomly. I started coding immediately and was losted in implementaion
details soon. Minutes later, it become unable to continue. I told the interviewer
I was stuck. With more minutes, I come up with a draft version of solution 1. It
finally took around 30 minutes to solve this easy question. And next 15 minutes
interview to pick out mistakes from my draft solution.
It made me awkward. An eligible candidate is supposed to solve it much more quickly!
And the result of interview confirms it - no further call from Microsoft.
I usually feel nervous during interview, maybe due to the personality. In an interview,
the interviewees are expected to respond quickly, which gives more pressures.
Putting my bad feelings alone, there are still somethings to keep in mind when
solving a problem:
think about it first before implement. Do some drawings or scratch on paper
if needed.
try to describe a soluton in a few steps without thinking about details of each
step. For example, solution 1 is easy to describe in a few simple steps. It’s just
like programming in C - implementing a function by some small ones, which makes
code clean. Thinking/solving this way makes people think more easily and not lost
in great details.
recursion also helps people think. Like the above one, recursion breaks the
problem down. A big problem usually becomes a smaller one plus some extra steps.
You don’t need to think about solving the problem(N-1) (at last it becomes to
problem(1) and easy to solve).
just like design patter to OO, there are “patterns” to algorithm design, like
“divide-and-conquer”, dynamic programming and greedy algorithm. Thinking about them,
then maybe an (efficient) solution come out.
2015-09-2423:24
如果你觉得这篇文章对你有用,可以微信扫一扫表示🙏 / If you find this post is useful to you, buy me 🍶 via Wechat
Sort A Linked List
Days ago, I took an online interview from Microsoft Shanghai. After some quick questions, I was asked to solve a simple question, sorting a linked list, in a online editor, whose content was shared between me and the interviewer in real-time.
Solutions
Below are three solutions. Source is here.
Solution 1
Iterate from the head of list to the end. For an element, if it’s larger than the next one, swap them. Therefore, after the first pass, the largest one goes to the last position of the list. After the second pass, the second largest one gets to the second last position. Keep iterating until the list is sorted.
Obviously, the complexity is
O(n^2)
.Solution 2
Solution 2 solves the problem recursively. The problem of size
N
can be solved by solving problem of sizeN-1
firstly and then inserting the first element into the sorted list.The code is cleaner, and the complexity is also
O(n^2)
.Solution 3
This solution does it in a “divide-and-conquer” way. It divides the problem into small ones, sorts them, and merges small sorted list into larger ones till the whole list is sorted.
The inner loop takes
O(n)
time. The outer loop runsO(lgn)
times. So this soluton isO(nlgn)
.The Interview
It sounded rather easy at first glance, and it really is. Within seconds, I told the interviewer it could be solved by “insertion sorting” since a linked list cannot be accessed randomly. I started coding immediately and was losted in implementaion details soon. Minutes later, it become unable to continue. I told the interviewer I was stuck. With more minutes, I come up with a draft version of solution 1. It finally took around 30 minutes to solve this easy question. And next 15 minutes interview to pick out mistakes from my draft solution.
It made me awkward. An eligible candidate is supposed to solve it much more quickly! And the result of interview confirms it - no further call from Microsoft.
I usually feel nervous during interview, maybe due to the personality. In an interview, the interviewees are expected to respond quickly, which gives more pressures. Putting my bad feelings alone, there are still somethings to keep in mind when solving a problem:
如果你觉得这篇文章对你有用,可以微信扫一扫表示🙏 / If you find this post is useful to you, buy me 🍶 via Wechat