登录
  • #刷题
  • #工作信息
  • #求职
  • #leetcode
  • #攻略

做题思路总结【Google/FB 面试】

swu56
6053
31
之前面 Google/FB, 做题思路总结:

1. 思路

2. 划重点: input/output e.g need to know the length, so that we need use var start and end in order to get length

3. 举蛇形例, 多举例子, 举例举例举例, clarify clarify clarify

4. common sense 走不通就换个方向

5.

6. loop —> outermost condition, like while(!queue.isEmpty()) , inner condition,recursion的 base condition —> 模块化

7. ifelse —> 1. 排除法 先排除 确定的, 简单的, group 行为类似的条件 2. check if the it’s null before call its method

8. trade off + complexity analysis = recursion —> easier to understand, iterative way is less easier to understand, sort or extra space

9.

1. Corner case

2. cases(dup, visited, cannot reach, even or odd, char case sensitive,

4. char —> 大小写,特殊字符,whitespace等等怎么处理

int --> int stack overflow, 0 or negative, num starting with 0 )

5. 求 max or min —> initialize Integer.MIN_VALUE or Integer.MAX_VALUE —> Integer.MAX_VALUE + 1 == -2147483648

6. calculate int —> avoid stackoverflow —> change to use long

7. 注意 所有 refernce 的 reference,是不是null

8. while loop 中 注意, cur = cur.next

#########################################################################################################################

1. 算法

2. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

3. sort —> regular sort, pq, bucket frequency sort, 3 colors sort,topological sort —> top 1/2 no need sort

5. topological sort: a. many to one . one to many. many to many b. HashMap<Item, Count> edges - how many times this item has been hit c. Queue<Item> q -put the non-hit items to the queue 有环 不会被放进 d. we need item’s children -> Map<Item, Set<Item>> - map because usually you need cur --> next relationship, cur is polled from queue. once the --cnt[next] == 0, next is pushed into queue

8. quick select/sort —> complexity= n+n/2+n/4+…=2n —> Median_of_Two_Sorted_Arrays (sort —> leave out the all smaller part, k = k - k/2)

9.

10.

11. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

12. two pointers —> from one side Or from cur to both side OR from both sides or sliding window use Arrays.fill(cnt, 0); —> three pointers

13. Sliding window —> Map<char, count > map, int counter = map.size() or counter = target.size(), outer loop is end < len , inner loop is while(counter == 0), map.remove(key)

14. 非连续 subsequence —> Need counter, crux is where do we update the max/min,

15. 连续 substring —> 567. Permutation in String, if(i - substring_len >= 0) count[s2.charAt(i - substring_len) - 'a']++; allZero helper function

16.

17. 求返回 一个string —> 只需 start index 与 length

18. String toLowerCase

19. paragraph.replaceAll(reg_str, str) paragraph.match(reg_str)

20. palindrome —> from inner to outer OR from outer to inner , parenthesis palindrome —> one count var is enough, if negative return false then.

21. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

22.

23.

24. 分类问题 —> bfs/dfs 涂色 + Union find + mts

25. union find —> 1. 本质是 分类, Map<child, parent> parents or int[] parent , 用find() method 来recursively找 parent, find(String s, Map<String, String> parents) → return p.get(s) == s ? s : find(p.get(s), p) ,assign it to itself as parent 但要 2. 需要 iterate input twice, 因为 [a,b] [c, b] —> [c, a] 3. union 其实 就是 Map<String, TreeSet<String>> unions 4. 可以用一个单独的 class 来包括 unionfind, see below

26. MST= Kruskal+Union Find。 Union Find 如果只有一个 group,可以 Map<item, group number> parent = new HashMap<>();

27. ctolib.com

28. 经典的 kruskal算法 求解最小生成树:

29. 方式就是当前图只有点,然后我们把边从小到大排序,一条一条放进去,只要不形成环,那么这条边就是属于最小生成树上的。大致思路就是这样。

30. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

31.

32.

33. Path —> shortest path —> bfs —> 没有path —> use hashmap<str, List<str>> to record neighbors —> use hashmap<str, distance> to record distance. —> hashmap<str, distance> not only a local dedepulicate but also decide path direction

34. all path — > backtrack —> dup? sort? for loop? remove —> 22. Generate Parentheses —> dfs/recursion —> backtrack (because pass a data structure NOT String)

35. 212. Word Search II —> 212. Word Search II —> 一个char 自己只能用一次, 但其他单词可以重复用

36. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

37.

38.

39. Subset, combination, permutation

40. backtrack —> // backtracking map.remove(c); set.remove(p); 1. Wanna get all the possible solutions → backtrack

41. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

42.

43.

44. binary search

45. while(left < right) right = mid or left = mid +1. 然后 三种情况 ><= —>

45. use left+ 1 < right avoid the case of size 2, also pay attention to target >= nums[mid] && target <= nums


binary search, 没有用 left mid right 的 binary serarch 的套路, 但仍然是排除法 (240. Search a 2D Matrix II)

46. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

47.

48.

49. bit manipulation

50. & , ^, ~, >>>, << —> both squrt and division

51.

52. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

53.

54. Array

55. dp —> 1+1+1+1+1 + 1 + 1 +1 —> count each to get 8 —> add one more at left —> get 9 directly, 难点在于 —> dp need set up the first value. dp[0] = ? && conversion function —> 当需要从小积累大时, 求max min, 考虑 DP —> 如何使用 array —> cnt[] ? … 1. board[y][x] ^= 256;; All 1111111 is 255

56. change coins 1, change coins 2

57. mod —> -1 % -2 ==-1 1 % -1 ==0 -2 % -1 ==0 -4 % -3 ==-1 -2 % -3 == -2 -3 % 4 == -3 —> begin-end linked array. (622. Design Circular Queue)

58. accumulative sum —> HashMap<Integer, cnt> or HashMap<Integer, index>

59. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

60.

61.

62. Probability/Math

63. Reservoir Sampling —>unlimited streaming data —> for(int i=1;c.next != null;i++){ c = c.next; if(random.nextInt(i + 1) == i) r = c.val; }

64. Random: Random rand = new Random(); // Obtain a number between [0 - 49] —> int n = rand.nextInt(50);

65. int random = (int )(Math.random() * 50 + 1); This will give you value from 1 to 50 in case of int or 1.0 (inclusive) to 50.0 (exclusive) in case of double. random() method returns a random number between 0.0 and 0.9..., you multiply it by 50, so upper limit becomes 0.0 to 49.999... when you add 1, it becomes 1.0 to 50.999..., 1. java.util.Random rand = new java.util.Random();

66. Math.pow —> double pow(double a, double b) 返回 double 类型

67. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

68.

69.

70.

72. Point/segment/square/interval

73. square overlap —> (l1, r1) (l2, r2) —> geeksforgeeks.org

74. 求 2 intervals overlap 剩余 —> 可以用stack 和 res[], 先减后加[br]
75. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

76.

77.

78. Compare

79. comparator (str.compareTo(str), return a - b)

80. a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

81. alpbetic oder compare --> a. need to compare all the char b. need compare length

82. min heap -> PriorityQueue<int[]> pq = new PriorityQueue<int[]>((p1, p2) -> p1 - p2); // if wanna get p1 first, need get negative integer

83. max heap -> PriorityQueue<int[]> pq = new PriorityQueue<int[]>((p1, p2) -> p2 - p1);

84. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1. 遍历

2. Collections traversal —> linear —> Iterator —> Iterator<List<Integer>> i; Iterator<Integer> j; i= list.iterator(); 利口,而把以

3.

4. 2d traverse —> linear ? dfs: static int[][] dirs = {{0,1}, {0, -1}, {1, 0}, {-1, 0}}; 每次换一方向 dir = (dir + 1) % 4; 一次走到底用 while loop

5. 2d traverse —> bfs ? for (int[] dir : dirs) [br]
6. PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]); int[0] is row, int[1] is col, int[2] is used to store other val. 没必要 int[][][][br]
7. boolean[][] visited = new boolean[m][n]; —> no modify original input

8. Queue<int[]> queue = new LinkedList<>(); —> bfs, int[] is used to store row and col

9. Queue: not only used to do bfs, but also only enqueue the next valid position

10.

11. graph(tree) traversal —> no matter if it’s directional —> need check visit(set or array) —> circle or 去而复返

12. single direction to double direction —> use HashMap —> goUp(use a hashmap 863)

13. iterative way to traverse the tree —> pre, in, post order, —> why does recursion cost more ?

14.

15.

16. 遍历的方法无非 bfs dfs. 遍历的结束 可以是 queue.isEmpty() or stack.isEmpty(). 也可以是 counter == 0

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

17. recursive vs queue —> recursive 能存更多的信息, queue 只能存一个element,若不能向element 中添加field, 则可以 用两个queue

18. recursion —> 1. all recursion can convert to iterative 2. recursion —> intuitive, relatively easy to understand . but more cost because all function calls must be stored inside stack 3. function calls is up to bottom 一串 not parallel,so you can pass a global variable by using array 4. function should have base case, children iteration, and actions. 6. pre/in/post/any vs go which direction first 7. go which way (left or right )first matters ! first is right, means only go left cannot go right further , this matters when we need connect left largest to the right smallest (leetcode 114) , 8 每一个 method call 画出 自己的空间 (24. Swap Nodes in Pairs)

20. global variable in recursion —> pass a int[1] array into a recursion method or return int[2]

84. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
31条回复
热度排序

发表回复