---
# System prepended metadata

title: Google Interview Challenge
tags: [INTERVIEW]

---

---
tags: INTERVIEW
---

# Google Interview Challenge
https://www.1111.com.tw/1000w/fanshome/discussTopic.asp?cat=FANS&id=301667

https://www.gushiciku.cn/pl/gyQP/zh-tw

https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed

https://docs.google.com/spreadsheets/d/1yRCOJ8KysRVkq0O9IlDriT01tC6lzPapmFO4PCmDJQA/edit#gid=126913158

https://docs.google.com/spreadsheets/d/1HV-iKgYJL4DpSOX1M-HcYG1cmz5CQxoduLOdEoTnIXo/htmlview#

https://labuladong.github.io/algo/2/

Google面試準備
刷題類型

- [ ] Arrays
- [x] Binary Search Tree
- [x] Binary Tree
- [ ] Dynamic Programming
- [ ] Greedy
- [ ] Graph – BFS、DFS
- [ ] Heap
- [ ] LinkedList
- [ ] Recursion
- [ ] Searching – Binary Search、Quick Select
- [ ] Stack
- [ ] String
- [ ] Sorting
- [ ] Topological sorting
- [x] Trie

Google面試經典題目
- [x] coin change
- [x] coin change 2
- [x] Unique path
- [x] Unique path 2
- [x] Permutation
- [x] Permutation 2
- [x] subset
- [x] subset 2
- [x] search in rotated sorted array
- [x] search in rotated sorted array 2
- [x] word break
- [x] word break 2
- [x] jump game
- [x] jump game 2
- [x] word search
- [x] word search 2
- [x] combination
- [x] combination 2
- [x] meeting room
- [x] meeting room 2
- [x] number of islands
- [x] number of islands 2
- [x] number of distinct island
- [ ] number of distinct island 2

BQ準備
Imagine you worked in a project or a team that had a problematic culture
Tell about the leading experience of a group project
Thinking about a time you were given a large amount of work to complete under the tight deadline
Tell about a time you face a problem without having clear solution
How do you solve the conflict that happen in the team

## Blind 75
### Array
- [x] [Two Sum](https://leetcode.com/problems/two-sum/)
- [x] [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
- [x] [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/)
- [x] [Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) (M)
- [x] [Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)
- [x] [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)
- [x] [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) (M)
- [x] [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)
- [x] [3 Sum](https://leetcode.com/problems/3sum/)
- [x] [Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
### Binary
- [x] [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/)
- [x] [Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/)
- [x] [Counting Bits](https://leetcode.com/problems/counting-bits/)
- [x] [Missing Number](https://leetcode.com/problems/missing-number/)
- [x] [Reverse Bits](https://leetcode.com/problems/reverse-bits/)
### Dynamic Programming
- [x] [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
- [x] [Coin Change](https://leetcode.com/problems/coin-change/)
- [x] [Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
- [x] [Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/)
- [x] [Word Break Problem](https://leetcode.com/problems/word-break/)
- [x] [Combination Sum](https://leetcode.com/problems/combination-sum-iv/)
- [x] [House Robber](https://leetcode.com/problems/house-robber/)
- [x] [House Robber II](https://leetcode.com/problems/house-robber-ii/)
- [x] [Decode Ways](https://leetcode.com/problems/decode-ways/)
- [x] [Unique Paths](https://leetcode.com/problems/unique-paths/)
- [x] [Jump Game](https://leetcode.com/problems/jump-game/)
### Graph
- [x] [Clone Graph](https://leetcode.com/problems/clone-graph/)
- [x] [Course Schedule](https://leetcode.com/problems/course-schedule/)
- [x] [Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/) (M)
- [x] [Number of Islands](https://leetcode.com/problems/number-of-islands/)
- [x] [Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/) (M)
- [x] [Alien Dictionary (Leetcode Premium)](https://leetcode.com/problems/alien-dictionary/) (H) Key: directed graph + DFS or BFS
- [x] [Graph Valid Tree (Leetcode Premium)](https://leetcode.com/problems/graph-valid-tree/) (M) Key: Check edges number first and then check unconnected component (Graph theory), Union Find!
- [x] [Number of Connected Components in an Undirected Graph (Leetcode Premium)](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/) (M)
### Interval
- [x] [Insert Interval](https://leetcode.com/problems/insert-interval/)
- [x] [Merge Intervals](https://leetcode.com/problems/merge-intervals/)
- [x] [Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/) (M) Key: greedy
- [x] [Meeting Rooms (Leetcode Premium)](https://leetcode.com/problems/meeting-rooms/)
- [x] [Meeting Rooms II (Leetcode Premium)](https://leetcode.com/problems/meeting-rooms-ii/)
### Linked List
- [x] [Reverse a Linked List](https://leetcode.com/problems/reverse-linked-list/)
- [x] [Detect Cycle in a Linked List](https://leetcode.com/problems/linked-list-cycle/)
- [x] [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
- [x] [Merge K Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
- [x] [Remove Nth Node From End Of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
- [x] [Reorder List](https://leetcode.com/problems/reorder-list/) (M)
### Matrix
- [x] [Set Matrix Zeroes](https://leetcode.com/problems/set-matrix-zeroes/)
- [x] [Spiral Matrix](https://leetcode.com/problems/spiral-matrix/)
- [x] [Rotate Image](https://leetcode.com/problems/rotate-image/)
- [x] [Word Search](https://leetcode.com/problems/word-search/)
### String
- [x] [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
- [x] [Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)
- [x] [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/) (H) Key: Optimized Sliding Windows!
- [x] [Valid Anagram](https://leetcode.com/problems/valid-anagram/)
- [x] [Group Anagrams](https://leetcode.com/problems/group-anagrams/)
- [x] [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
- [x] [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)
- [x] [Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) Key: Manacher's Algorithm
- [x] [Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/) (M) Key: Manacher's Algorithm
- [x] [Encode and Decode Strings (Leetcode Premium)](https://leetcode.com/problems/encode-and-decode-strings/) (M)
### Tree
- [x] [Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
- [x] [Same Tree](https://leetcode.com/problems/same-tree/)
- [x] [Invert/Flip Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
- [x] [Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/) (H)
- [x] [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) (M)
- [x] [Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) (H)
- [x] [Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)
- [x] [Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) (M)
- [x] [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)
- [x] [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) (M)
- [x] [Lowest Common Ancestor of BST](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
- [x] [Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/) (M)
- [x] [Add and Search Word](https://leetcode.com/problems/add-and-search-word-data-structure-design/) (M)
- [x] [Word Search II](https://leetcode.com/problems/word-search-ii/)
### Heap
- [x] [Merge K Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
- [x] [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) (M)
- [x] [Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/) (H)


## Tips
https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed

## Funny One
- [x] [Count Unique Characters of All Substrings of a Given String](https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string) Key: really special solution
- [x] [Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
- [x] [Find Leaves of Binary Tree](https://leetcode.com/problems/find-leaves-of-binary-tree/)
- [x] [Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/) Key: Binary Search!!!
- [x] [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)
- [x] [The Skyline Problem](https://leetcode.com/problems/the-skyline-problem/) Key: Select the building with heapqueue
- [x] [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/solution/) Key: tricky Apply with stack!!!
- [x] [Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/) Key: Markle Hash
- [x] [Substring with Concatenation of All Words](https://leetcode.com/problems/substring-with-concatenation-of-all-words/) Key: Sliding Window
- [x] [Longest Valid Parentheses](https://leetcode.com/problems/longest-valid-parentheses/) key: Two pointer or DP or Stack
- [x] [Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/) Key: Tricky One pass solution (DP or O(k) space)
- [x] [Design HashSet](https://leetcode.com/problems/design-hashset/discuss/?currentPage=1&orderBy=most_votes&query=&tag=python) Key: Multiplicative hashing
- [x] [Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/solution/) Key: Catalan number!
- [x] [Shortest Path in a Grid with Obstacles Elimination](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/) Key: BFS + A*
- [ ] [Student Attendance Record II](https://leetcode.com/problems/student-attendance-record-ii/) Key: hardhard DP
- [x] [Guess the Word](https://leetcode.com/problems/guess-the-word/) Key: Game theroy, compare with previous
- [x] [Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/) Key: minmun spanning tree!! (Prim's or )
- [ ] [Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) Key: Binary search space
- [ ] [132 Pattern](https://leetcode.com/problems/132-pattern/) Key: stack+min array