Han Zhu's Study Notes

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of  non-empty  words from the dictionary, where  words are sorted lexicographically by the rules of this new language . Derive the order of letters in this language. Example 1: Given the following words in dictionary, [ "wrt", "wrf", "er", "ett", "rftt" ] The correct order is:  "wertf" . Example 2: Given the following words in dictionary, [ "z", "x" ] The correct order is:  "zx" . Example 3: Given the following words in dictionary, [ "z", "x", "z" ] The order is invalid, so return  "" . Note: You may assume all letters are in lowercase. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary. If the order is invalid, return an empty string...

Implement an iterator to flatten a 2d vector. For example, Given 2d vector = [ [1,2], [3], [4,5,6] ] By calling  next  repeatedly until  hasNext  returns false, the order of elements returned by  next  should be:  [1,2,3,4,5,6] . Follow up: As an added challenge, try to code it using only  iterators in C++  or  iterators in Java . Thought process: Use two iterators. One to iterate through rows. The other to iterate through columns.  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 public class Vector2D implements Iterator < Integer > { private Iterator < List < Integer >> row ; private Iterator < Integer > column ; public Vector2D ( List < List < Integer >> vec2d ) { this . row = vec2d . iterator (); } @Override public Integer next () { this . hasNext (); ...

Implement a basic calculator to evaluate a simple expression string. The expression string contains only  non-negative  integers,  + ,  - ,  * ,  /  operators and empty spaces  . The integer division should truncate toward zero. You may assume that the given expression is always valid. Some examples: "3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5 Note:   Do not  use the  eval  built-in library function. Thought process: Iterate through the string. There are three cases: Number: keep track of number in a variable. Space: do nothing. Operand: look at previous operand. There are two cases: + or -: add / subtract current number. * or /: subtract previous number from result. Add previous * or / number to result. Set previous = previous * or / number. 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 class Solution { public int ...

Implement a basic calculator to evaluate a simple expression string. The expression string may contain open  (  and closing parentheses  ) , the plus  +  or minus sign  - ,  non-negative  integers and empty spaces  . You may assume that the given expression is always valid. Some examples: "1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23 Note:   Do not  use the  eval  built-in library function. Thought process: Iterate through string. Use a variable to store the previous operation (+ / -). If it's -, that means I need to add (-1) * number. There are six cases: Number: keep track of current number. Only perform an operation when I see + or -, because number can have more than one digit. Space: do nothing. +: add sign * number to result. Set sign to 1 and reset number. -: add sign * number to result. Set sign to -1 and reset number. (: Push previous result and sign onto stack. Reset result...

Given an array of integers, find out whether there are two distinct indices  i  and  j  in the array such that the  absolute  difference between  nums[i]  and  nums[j]  is at most  t  and the  absolute  difference between  i  and  j  is at most  k . Thought process: Iterate through the array. Use a binary search tree (TreeSet in Java) to keep track of the most recent k numbers. For each number, get the ceiling (smallest number that's greater than num) and floor (greatest number that's less than num) of it, and check if either's difference with num is at most t.  If the tree's size exceeds k, remove the least recent number. Note: there may be integer overflow when subtracting a negative number from a positive number. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class Solution { public boolean containsNearbyAlmostDuplicate ( int [] nums ,...

Given an array of integers and an integer  k , find out whether there are two distinct indices  i  and  j  in the array such that  nums[i] = nums[j]  and the  absolute  difference between  i  and  j  is at most  k . Thought process: Iterate through the array. Use a hash map to record number -> index. If duplicate numbers are found, check if the difference between their indices is <= k. If not, update the mapped index to the larger one. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution { public boolean containsNearbyDuplicate ( int [] nums , int k ) { Map < Integer , Integer > map = new HashMap <>(); for ( int i = 0 ; i < nums . length ; i ++) { if ( map . containsKey ( nums [ i ]) && i - map . get ( nums [ i ]) <= k ) { return true ; } ma...

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. Thought process: Iterate through the array. Use a set to keep track of numbers seen. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution { public boolean containsDuplicate ( int [] nums ) { Set < Integer > set = new HashSet <>(); for ( int num : nums ) { if ( set . contains ( num )) { return true ; } set . add ( num ); } return false ; } } Time complexity: O(n). And a functional Java solution just for fun (beats 0.14% of Java submissions). Solution 2: 1 2 3 4 5 public class Solution { public boolean containsDuplicate ( int [] nums ) { return nums . length != Ar...

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 4. Thought process: Dynamic programming: Sub-problem: find the length of the largest square whose bottom-right corner is at matrix[i][j]. Formula:  To get a square of length 2, all top-left, top, and left neighbors of matrix[i][j] must have a square of length 1. To get a square of length 3, all top-left, top, and left neighbors of matrix[i][j] must have a square of length 2. ... f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1])  + 1. Initialization:  f[i][0] = 1 if matrix[i][0] = 1. Otherwise 0. f[0][i] = 1 if matrix[0][i] = 1. Otherwise 0. Answer: the square of the max of f[i][j]. 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 public class Solution { p...