Han Zhu's Study Notes

You are given two integer arrays  nums1  and  nums2  sorted in ascending order and an integer  k . Define a pair  (u,v)  which consists of one element from the first array and one element from the second array. Find the k pairs  (u 1 ,v 1 ),(u 2 ,v 2 ) ...(u k ,v k )  with the smallest sums. Example 1: Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] Example 2: Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Return: [1,1],[1,1] The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3] Example 3: Given nums1 = [1,2], nums2 = [3], k = 3 Return: [1,3],[2,3] All possible pairs are returned from the sequence: [1,3],[2,3] Thought process: Maintain a min heap of size k. At first, offer all (nums1[i], nums2[0]) to the heap. Do k iterations. For eac...

Find the  k th largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given  [3,2,1,5,6,4]  and k = 2, return 5. Note:  You may assume k is always valid, 1 <= k <= array's length. Thought process: Divide and conquer. Quick select. Use the partition algorithm from quick sort to sort the array in descending order. After partitioning, there are three cases for the pivot: Pivot == k: found the kth largest element. Pivot < k: keep searching on the right side. Pivot > k: keep searching on the left side. Solution 1 (quick select): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { private Random random = new Random (); public int findKthLargest ( int [] nums , int k ) { return partition ( nums , k , 0 , nums . length - 1 ); } ...

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are  given the locations and height of all the buildings  as shown on a cityscape photo (Figure A), write a program to  output the skyline  formed by these buildings collectively (Figure B).   The geometric information of each building is represented by a triplet of integers  [Li, Ri, Hi] , where  Li  and  Ri  are the x coordinates of the left and right edge of the ith building, respectively, and  Hi  is its height. It is guaranteed that  0 ? Li, Ri ? INT_MAX ,  0 < Hi ? INT_MAX , and  Ri - Li > 0 . You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. For instance, the dimensions of all buildings in Figure A are recorded as:  [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] . The output is a list ...

Merge  k  sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Thought process: Algorithm 1: Divide and conquer. Break k lists into pairs and merge a pair at a time. Algorithm 2: Use a heap. At the start, offer the first element of each list into the heap. While the heap is not empty, poll the first element from it, and offer first.next into the heap. Solution 1 (Divide and conquer): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists ( ListNode [] lists ) { if ( lists . length == 0 ) { return null ; } return mergeKLists ( lists , 0 , lists . l...

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples:  [2,3,4]  , the median is  3 [2,3] , the median is  (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far. For example: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 Thought process: Use a max heap to maintain the smaller half of the numbers, and a min heap to maintain the larger half of the numbers. Designate one of the heap's top to be the median, or smaller of the middle values if total number is even. To maintain two heaps' balance, we need to make sure that one of the heap's size is always equal to or 1 larger than the other's. We can designate the heap that keeps...

Given an array of meeting time intervals consisting of start and end times  [[s1,e1],[s2,e2],...]  (s i  < e i ), find the minimum number of conference rooms required. For example, Given  [[0, 30],[5, 10],[15, 20]] , return  2 . Thought process: The idea is to first sort the array based on start time, so we can examine the meetings as they take place in order (and be greedy).  Suppose we have three meetings: [0, 30], [5, 10], and [15, 20] in sorted order. When we see the second meeting, we check if its start time is later than the first meeting's end time. It's not, so we need another room. We then compare the third meeting's start time with the minimum of first two meetings' end times. If there is a meeting that ends before the third meeting starts, then we don't need another room. So as we iterate through the array, we need to store each meeting's end time and get the minimum quickly. Min heap is a natural choice. Solution (C++): 1...