Introduction
Last night 10:00 pm she had a mocking experience but she felt kind of disappointed, because she liked to get more mocking comment. Last night she did not get optimal solution. She could not think freely to reach optimal solution.
But today 10:00 am mocking experience is a very good experience, best of 8 mocking experience. She spent over 10 minutes to work on time complexity analysis, O(k2) -> O(klogk) -> O(k), she stopped before she thought about O(1), she knew that it is not so good to find minimum value using O(k) time. She asked for a hint, and then she was given to think heap sort. She got it right away, O(1) to get the minimum value if minimum heap is used to store k elements. Because all k numbers does not need to be sorted, only minimum value is needed.
Using O(k) time to get minimal is not optimal, use space to trade time, use a binary tree - a data structure to store k element, minimum value is the root of binary tree, that will be O(1) time. Actually it is named minimum heap.
Small talk about messed array
The 30 minutes mocking experience is here with transcript, thought process, hint given and C# code.
Actionable Item
This is the first time in last 8 experience Julia got rate of 7 for her code. 30 minutes is long time for a conversation. Writing code was to write down what she described in the test case. Even though Julia worked on first 10 minutes without coming out using heap sort, she understood the solution and how to approach the problem by going through a simple test case [1, 2, 3, 4, 5].
"Really familiarize yourself with the sorting algorithms. You definitely understand them but get to a place where you can recall them more intuitively."
Facts
The problem is so subtle and then Julia did not come out using heap sort, even though she wrote about the algorithm of search medium using O(1) about a data structure a few days ago.
Follow up
June 28, 2017 8:00 pm - 8:30 pm
C# practice code is here.
No comments:
Post a Comment