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 heap sort. Show all posts
Showing posts with label heap sort. 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.
Tuesday, December 26, 2017
sliding window in the array
Dec. 26, 2017
It is the mock interview of 12:00 PM. I have to practice a solution for k-messed array sort. Since C# does not provide minimum heap class, the peer told me that I can apply sorting similar to insertion sort.
After we discussion to use linear scan k + 1 window to find the index with the minimum value, and then swap the start position with minimum index, I wrote the following code.
C# code is here.
My argument is to write the code and also the code can pass all mock interview platform test cases. Although the time complexity is O(kn), k is the size of slide window, n is the array's length. The optimal one using minimum heap is better with time complexity O(nlogk).
Introduction
It is the mock interview of 12:00 PM. I have to practice a solution for k-messed array sort. Since C# does not provide minimum heap class, the peer told me that I can apply sorting similar to insertion sort.
After we discussion to use linear scan k + 1 window to find the index with the minimum value, and then swap the start position with minimum index, I wrote the following code.
C# code is here.
My argument is to write the code and also the code can pass all mock interview platform test cases. Although the time complexity is O(kn), k is the size of slide window, n is the array's length. The optimal one using minimum heap is better with time complexity O(nlogk).
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.
Sunday, May 15, 2016
Leetcode 215: Find kth largest element in the array
May 15, 2016
Problem statement:
https://leetcode.com/problems/kth-largest-element-in-an-array/
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Read some blogs about this problem:
http://www.jianshu.com/p/f52a88550588
Julia likes to spend 10 - 20 minutes to review "Quick Select" - the idea, similar to Quick Sort, most important part is to partition.
Time complexity: O(nlogn) in quicksort, but O(n) in quick select.
1. Quick sort: Time complexity: O(nlogn)
2. Use Heap sort, O(klogN)
Java Solution, using priority queue, code to study:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/215.kth-largest-element-in-an-array.java
Spend 20 minutes to read the blog: 4:23pm - 4:43 pm
1. http://www.cnblogs.com/yuzhangcmu/p/4164807.html
2. https://en.wikipedia.org/wiki/Introselect (read 10 minutes - 4:30pm - 4:40pm)
3. http://stackoverflow.com/questions/7559608/median-of-three-values-strategy
4. http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements
Problem statement:
https://leetcode.com/problems/kth-largest-element-in-an-array/
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Read some blogs about this problem:
http://www.jianshu.com/p/f52a88550588
Julia likes to spend 10 - 20 minutes to review "Quick Select" - the idea, similar to Quick Sort, most important part is to partition.
Time complexity: O(nlogn) in quicksort, but O(n) in quick select.
1. Quick sort: Time complexity: O(nlogn)
2. Use Heap sort, O(klogN)
Java Solution, using priority queue, code to study:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/215.kth-largest-element-in-an-array.java
Spend 20 minutes to read the blog: 4:23pm - 4:43 pm
1. http://www.cnblogs.com/yuzhangcmu/p/4164807.html
2. https://en.wikipedia.org/wiki/Introselect (read 10 minutes - 4:30pm - 4:40pm)
3. http://stackoverflow.com/questions/7559608/median-of-three-values-strategy
4. http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements
5. http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/ (4:50pm - 5:20pm)
30 minutes to review the solutions, write down short notes:
6 methods:
1. Use bubble k times - O(nk)
Modify bubble sort to run the outer loop at most k times
Like bubble sort, other sorting algorithms like selection sort can also be modified to get the k largest element.
2. Use temporary array
Time complexity: O((n-k)*k)
3. Use sorting
1. Sort the elements in descending order in O(nlogn)
4. Print the first k numbers of the sorted array O(k)
Time complexity: O(nlogn)
4. Use Max Heap
1. Build a Max Heap tree in O(n)
2. Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n+klogn)
5. Use order statistics:
1) use order statistics algorithm to find the kth largest element.
Julia, take some time to review the article: see the topic selection in worst-case linear time O(n). (10 - 15 minutes)
Write down main ideas using your own words:
Use a deterministic algorithm that runs in O(n) in the worst case.
2)
30 minutes to review the solutions, write down short notes:
6 methods:
1. Use bubble k times - O(nk)
Modify bubble sort to run the outer loop at most k times
Like bubble sort, other sorting algorithms like selection sort can also be modified to get the k largest element.
2. Use temporary array
Time complexity: O((n-k)*k)
3. Use sorting
1. Sort the elements in descending order in O(nlogn)
4. Print the first k numbers of the sorted array O(k)
Time complexity: O(nlogn)
4. Use Max Heap
1. Build a Max Heap tree in O(n)
2. Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n+klogn)
5. Use order statistics:
1) use order statistics algorithm to find the kth largest element.
Julia, take some time to review the article: see the topic selection in worst-case linear time O(n). (10 - 15 minutes)
Write down main ideas using your own words:
Use a deterministic algorithm that runs in O(n) in the worst case.
2)
Subscribe to:
Posts (Atom)