Han Zhu's Study Notes

Given two arrays, write a function to compute their intersection. Example: Given  nums1  =  [1, 2, 2, 1] ,  nums2  =  [2, 2] , return  [2, 2] . Note: Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Follow up: What if the given array is already sorted? How would you optimize your algorithm? What if  nums1 's size is small compared to  nums2 's size? Which algorithm is better? What if elements of  nums2  are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once? Thought process: Iterate through both arrays. Count the number of each number and put the counts into two maps. Iterate through both maps. For numbers that appear in both maps, put min(count1, count2) of that number into result. Solution: 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 ...

Given two arrays, write a function to compute their intersection. Example: Given  nums1  =  [1, 2, 2, 1] ,  nums2  =  [2, 2] , return  [2] . Note: Each element in the result must be unique. The result can be in any order. Thought process: Iterate through nums1. Put the elements into a hash set. Iterate through nums2. The elements that the hash set contains are the intersection. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int [] intersection ( int [] nums1 , int [] nums2 ) { Set < Integer > set = new HashSet <>(); for ( int num : nums1 ) { set . add ( num ); } Set < Integer > intersection = new HashSet <>(); for ( int num : nums2 ) { if ( set . contains ( num )) { intersection . add ( num ); } } ...

Given two strings  s  and  t , write a function to determine if  t  is an anagram of  s . For example, s  = "anagram",  t  = "nagaram", return true. s  = "rat",  t  = "car", return false. Note: You may assume the string contains only lowercase alphabets. Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case? Thought process: Iterate through both strings, count the number of each character, and compare the counts. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean isAnagram ( String s , String t ) { int [] count = new int [ 26 ]; for ( char c : s . toCharArray ()) { count [ c - 'a' ]++; } for ( char c : t . toCharArray ()) { count [ c - 'a' ]--; } for ( int i : count ) { if ( i !=...

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index. According to the  definition of h-index on Wikipedia : "A scientist has index  h  if  h  of his/her  N  papers have  at least   h  citations each, and the other  N − h  papers have  no more than   h  citations each." For example, given  citations = [3, 0, 6, 1, 5] , which means the researcher has  5  papers in total and each of them had received  3, 0, 6, 1, 5  citations respectively. Since the researcher has  3  papers with  at least   3  citations each and the remaining two with  no more than   3  citations each, his h-index is  3 . Note : If there are several possible values for  h , the maximum one is taken as the h-index. Thought process: The definition of h-index in the problem is c...

Given an array with  n  objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for this problem. click to show follow up. Follow up: A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. Could you come up with an one-pass algorithm using only constant space? Thought process: Counting sort, as described in the follow up. In this case, the sorting does not need to be stable, so we can skip the intermediate step of counting sort. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class Solution { ...

Sort a linked list in  O ( n  log  n ) time using constant space complexity. Thought process: In this case, merge sort does not take extra space because we are sorting a linked list. We can break the original list into pieces and merge them. Pay attention to the base case and the initialization of fast and slow pointers in findMiddle function. Make sure to eliminate all possibilities of infinite loop. Solution: 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 54 55 56 57 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList ( ListNode head ) { if ( head == null || head . next == null ) { return head ; } ListNode middle = findMiddle ( h...

Given an unsorted array  nums , reorder it  in-place  such that  nums[0] <= nums[1] >= nums[2] <= nums[3]... . For example, given  nums = [3, 5, 2, 1, 6, 4] , one possible answer is  [1, 6, 2, 5, 3, 4] . Thought process: The result needs to guarantee that when i is odd, nums[i] >= nums[i - 1]; when i is even, nums[i] <= nums[i - 1]. The idea is that, whenever we see a nums[i] that violates this rule, we swap it with nums[i - 1]. This will work because if i is odd and nums[i] < nums[i - 1], nums[i] is also always less than nums[i - 2]; if i is even and nums[i] > nums[i - 1], nums[i] is also always larger than nums[i - 2]. So swapping will not violate the relationship between nums[i - 1] and nums[i - 2]. Solution: 1 2 3 4 5 6 7 8 9 10 class Solution { public: void wiggleSort(vector < int >& nums) { for ( int i = 1 ; i < nums.size(); i ++ ) { if (((i & 1 ) &...

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...

Given an array of meeting time intervals consisting of start and end times  [[s1,e1],[s2,e2],...]  (s i  < e i ), determine if a person could attend all meetings. For example, Given  [[0, 30],[5, 10],[15, 20]] , return  false . Thought process: If a meeting's end time is larger than another's start time, a person cannot attend both meetings. So the idea is to sort the array based on start time. Then we can iterate through the array to check if any two consecutive meetings overlap. Solution (C++): 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 /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: bool canAttendMeetings(vector < Interval >& intervals) { sort(intervals.begin(), intervals.end(), []( const Interval & i...

Given a set of  non-overlapping  intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals  [1,3],[6,9] , insert and merge  [2,5]  in as  [1,5],[6,9] . Example 2: Given  [1,2],[3,5],[6,7],[8,10],[12,16] , insert and merge  [4,9]  in as  [1,2],[3,10],[12,16] . This is because the new interval  [4,9]  overlaps with  [3,5],[6,7],[8,10] . Thought process: This is a follow-up to problem 56 . A naive solution is to add the new interval to the list. And the rest is the same as 56. Solution 1: 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 /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { st...