Introduction
It is the sort algorithm and I cannot use heap since C# does not have class. I write a function to find the minimum index in K + 1 contiguous subarray.
Algorithm practice
Here is my C# practice.
Showing posts with label Sort k-messed array. Show all posts
Showing posts with label Sort k-messed array. Show all posts
Tuesday, March 27, 2018
Sort k shifted array
March 27, 2018
It is the sort algorithm and I cannot use heap since C# does not have class. I write a function to find the minimum index in K + 1 contiguous subarray.
Here is my C# practice.
It is the sort algorithm and I cannot use heap since C# does not have class. I write a function to find the minimum index in K + 1 contiguous subarray.
Here is my C# practice.
Saturday, April 15, 2017
Messed array k step away small talk
April 15, 2017
Julia was busy with Hackerrank week code #31 this morning starting from 8:00 am and she had some issues about her attitude to test cases, last night she stayed up to 1 am to work on coding with test cases. She failed 50% test case of minimum spanning tree, and she thought that this Saturday morning time is the wonderful time to learn how to strength her test skills, she tried to fix those failed test cases today.
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.
The 30 minutes mocking experience is here with transcript, thought process, hint given and C# code.
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."
June 28, 2017 8:00 pm - 8:30 pm
C# practice code is here.
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.
Subscribe to:
Posts (Atom)