Find best position to host the party based on Manhattan distance

Feb. 12, 2018

Introduction

I do not expect that I will learn the algorithm from the peer after the mock interview. Actually it is very good experience to learn that the peer can solve the problem using very good reasoning skills, related to quick select algorithm.

For my understanding, it is like applying counting sort or bucket sort, you decide where to place the position, count how many increments and decrements for each move.

Algorithm discussion

Here is the algorithm.

Follow up 

May 8, 2018

The peer got Google full time job starting this May. I am so excited to get connected to him.

June 19, 2018
Here is Leetcode 296.

One of his blogs:
https://blog.csdn.net/xudli/article/details/49420623

Here is blog about geeksforgeeks.com.
https://www.geeksforgeeks.org/sum-manhattan-distances-pairs-points/

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

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)