Han Zhu's Study Notes

Given an array  nums  containing  n  + 1 integers where each integer is between 1 and  n  (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Note: You  must not  modify the array (assume the array is read only). You must use only constant,  O (1) extra space. Your runtime complexity should be less than  O(n 2 ) . There is only one duplicate number in the array, but it could be repeated more than once. Thought process: Based on the conditions, we cannot sort the array or use hashmap. That leaves us with one less obvious solution and one even less obvious solution.  The first solution is to use binary search on the range of the numbers. Since all numbers are between 1 and n, the duplicate must be either in the range 1 to n / 2, or n / 2 to n. We can count the numbers between 1 and n / 2. If there are n / 2 + 1 numbers, then w...

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 integers, every element appears  twice  except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Thought process: Iterate through the array. Maintain a set of integers seen so far. If a number is already in the set, erase it from the set. In the end the set will have one element remaining, which is the single number. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int singleNumber(vector < int >& nums) { unordered_set < int > set; for ( int num : nums) { if ( ! set.insert(num).second) { set.erase(num); } } return * set.begin(); } }; Time complexity: O(n). Space complexity: O(n). Follow-up: This problem can be solved without using extra space using the XOR operation. A XOR A = 0. By XORing ...

Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh". Thought process: Use two pointers: one from the start of the string, the other from the end of the string. Swap the characters pointed until they collide. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public : string reverseString ( string s ) { int i = 0 ; int j = s . length () - 1 ; while ( i < j ) { swap ( s [ i ], s [ j ]); i ++; j --; } return s ; } }; Time complexity: O(n).

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap. For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend. Hint: If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner? Thought process: If n < 4, I can always win by taking all the stones. If n = 4, I will always lose. If 4 < n < 8, I can always win by leaving 4 stones in the heap. If n = 8, I can never win because no matter how many stones I take, ...

Given an array of integers, return  indices  of the two numbers such that they add up to a specific target. You may assume that each input would have  exactly  one solution, and you may not use the  same  element twice. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[ 0 ] + nums[ 1 ] = 2 + 7 = 9, return [ 0 , 1 ]. Thought process: Iterate through the array. Use a hashmap to keep track of array elements and their corresponding indices. As I come to nums[i], if the hashmap contains target - nums[i], that means we have found the pair. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public int [] twoSum ( int [] nums , int target ) { Map < Integer , Integer > map = new HashMap <>(); for ( int i = 0 ; i < nums . length ; i ++) { if ( map . containsKey ( target - nums [ i ])) { return new int []{ map . get ( target - nums [ ...

Race Condition: Race condition occurs when the result of some computation depends on the exact timing of multiple threads of execution, i.e., the order in which the instructions are executed. Code that updates a variable can be broken into several assembly lines. Because the code is not atomic, if multiple threads are updating a variable at the same time, the result is undetermined. Consistency: Ideally, it shouldn't make a difference whether the requests are executed concurrently or not. We need a consistency model that specifies how the system should behave in the presence of consistency. The strictest model is sequential consistency, which states that the result of any execution is the same as if the operations of all the processors had been executed in a sequential order. Mutual Exclusion: Code has a critical section where accesses from other threads to the same shared resources will cause problems. To solve this problem, we need mutual exclusion. The idea ...