Used to prepare for the Internship interview @ Google, Summer 2021.
Language: Python 3

Google doc files may be found in archive
List of used resources:

  1. leetcode.com
  2. stackoverflow.com
  3. geeksforgeeks.org
  4. medium.com
  5. tutorialspoint.com
  6. programiz.com
  7. goodtecher.com
  8. baihuqian.github.io
  9. zhenyu0519.github.io
  10. nikgrozev.com
  11. walkccc.me

Data structures
Hash set, map: implementation
Queues: implementation using 2 stacks, priority queue implementation collections.deque, heapq.heapify
Binary trees: implementation, BST. Max path
n-ary trees: level traversal
Trie-trees: implementation
red/black tree: implementation
splay tree,
AVL tree: implementation
min/max heaps: maxh implementation

Graphs: implementation, distance, search, connectivity, cycle-detection, BFS and DFS, deep copy
MST minimum spanning tree (Prim’s)
MST Kruskal’s
edge list: space O(e), linear search O(e)
adjacency matrices: O(v^2) space, check edge connectivity = check whole row
adjacency lists: find edge – O(d), d = degree of vertex; undir space O(2e), dir O(e)

Other algorithms
Sorting: Quick, Merge, Counting, Bucket
NP-complete problems - nondeterministic polynomial-time complete. Quick verification, hard to find solution in poly-time.
Good card shuffling algorithm (just shuffle, las vegas, monte carlo)
Random

OS Some very basic things
Processes – instance of a program which is executed by one or many threads
Threads – smallest sequence of instructions which can be executed independently
Concurrency issues, locks,
Deadlock - situation in which processes/threads block each other due to resource acquisition and none of the processes makes any progress as they wait for the resource held by the other process
conditions: mutual exclusion, hold and wait, no preemption, circular wait
Livelock - Livelock is a deadlock-like situation in which processes block each other with a repeated state change yet make no progress.
Mutexes – a key that gives access to the resource
Semaphores – generalized mutex
Monitors – process sync tools
Context switching works - the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point.
Scheduling – interrupt of a process, store state in a data structure called PCB (kernel memory, per-process stack)
Modern concurrency constructs – Green threads (emulate threads on top of JVM), protothreads (stackless threads, share same stack, ‘stack rewinding’), fibers (lightweight threads, not pre-emtied by OS kernel)

Combinatorics
n-choose-k problems and their ilk = (k!)/n!(k-n)!

**Problems

Transactions (full code **class, transactions)1146. Snapshot array (list, snapshots class)
394. Encode/decode string (string, 3[a]2[bc])
1056. Confusing number (int, 6 -> 9)
329. Longest increasing path (matrix 1->2->3…)
Robot room cleaner (matrix with obsticles)
Traveling salesman (graph/matrix, visit all nodes for min weight)
The knapsack (list, max score for limited w)
Expressive/stretchy words (string, hello - heeellloooo)
Text justification (string, cut text in blocks)
Time to notify all (list managers, list inform times)

Combination sum
39. Combination Sum (list, all combinations leading to sum) 40. Combination Sum II (list, all combinations, used once) 216. Combination Sum III (k numbers, n sum, all valid combinations) 77. Combinations (all combinations of k numbers from [1:n]) 46. Permutation (all permutations of list) 47. Permutation II (all unique permutations of list) 267. Palindrome Permutation II (string) 78. Subsets (list, all possible subsets) 90. Subsets II (list, all possible subsets, no duplicates)
Two sum3Sum 4Sum Two Sum II - Input Array Is Sorted Two Sum III - Data structure design Subarray Sum Equals K Two Sum IV - Input is a BST Two Sum Less Than K Max Number of K-Sum Pairs Count Good Meals Count Number of Pairs With Absolute Difference K Number of Pairs of Strings With Concatenation Equal to Target

Subarray, Submatrix
1074. Number of Submatrices That Sum to Target (sub matrices, sum to num) 560. Subarray Sum Equals K (list, combinations) 974. Subarray Sums Divisible by K (list, combinations) 325. Maximum Size Subarray Sum Equals k (list, subarray) 363. Max Sum of Rectangle No Larger K (matrix, rectangles)

Rectangles
84. Largest rectangle in histogram (histogram, rectangle) - Max rectangle area with 1 vs 0 (matrix, rectangle with 1s)

Word transformation / Move a box, keys, obstacles
127. Transform word (string, from one word to another) 102. Binary Tree Level Order Traversal (tree traverse, level) 127. Word Ladder (string, transformation sequence, number of words) 126. Word Ladder II (string, transformation sequence, words seqs) 301. Remove Invalid Parentheses (string, parenthesis) 317. Shortest Distance from All Buildings 773. Sliding Puzzle (game 15) 815. Bus Routes (graph, least number of buses) 854. K-Similar Strings (strings, min swaps) 864. Shortest Path to Get All Keys (matrix, path, keys) 1091. Shortest Path in Binary Matrix (matrix, clear path) 1210. Minimum Moves to Reach Target with Rotations (matrix, snake moves and rotations) 1263. Minimum Moves to Move a Box to Their Target Location (matrix, store keeper box) 1293. Shortest Path in a Grid with Obstacles Elimination (path with obstacles elimination)

**String window
**727. Minimum window subsequence (string, find window) 76. Minimum Window Substring (string, substring including duplicates) 1208. Get Equal Substrings Within Budget (string ASCII distance) 3. Longest Substring Without Repeating Characters (string, no repeat) 159. Longest Substring with At Most Two Distinct Characters (string, two distinct) 340. Longest Substring with At Most K Distinct Characters (string, k distinct) 992. Subarrays with K Different Integers (subarrays, k different) 424. Longest Repeating Character Replacement (string, replacement) 209. Minimum Size Subarray Sum (array, min subarray greater k) 713. Subarray Product Less Than K (subarray, product less) 76. Minimum Window Substring (string, substring)

Meeting rooms
253. Meeting Rooms II (find min meeting rooms num) 731. My Calendar II (list, no triple booking) 732. My Calendar III (return the intersection) 1094. Car Pooling (list, locations, passengers) 1109. Corporate Flight Bookings (list, seats numbers, ) 218. The Skyline Problem (skyline intersection)

Trie problems
208. Implement Trie (Prefix Tree) 1233. Remove Sub-Folders from the Filesystem 1032. Stream of Characters (check from char string if a suffix is in dic) 211. Add and Search Word - Data structure design (map, add, search) 676. Implement Magic Dictionary (search word in dict) 677. Map Sum Pairs (design map with prefix sum) 745. Prefix and Suffix Search (search words by prefix and suffix) 425. Word Squares (find all word squares you can build)

Buy and sell
121. Best Time to Buy and Sell Stock (list, day to buy, day to sell) 122. Best Time to Buy and Sell Stock II (list, buy and sell many times) 309. Best Time to Buy and Sell Stock with Cooldown (buy, sell, cooldown) 188. Best Time to Buy and Sell Stock IV (at most k transactions) 714. Best Time to Buy and Sell Stock with Transaction Fee (with fee)

Binary tree / path sum
257. Binary Tree Paths (all root-to leaf paths) 129. Sum Root to Leaf Numbers (sum of root-to-leaf numbers) 1022. Sum of Root To Leaf Binary Numbers (all paths sums) 988. Smallest String Starting From Leaf (smallest lexico) 112. Path Sum (find sum)
113. Path Sum II (return list of nodes sum up to sum) 437. Path Sum III (path along to the root)

378. Kth Smallest Element in a Sorted Matrix 668. Kth Smallest Number in Multiplication Table 410. Split Array Largest Sum 1011. Capacity To Ship Packages Within D Days 1231. Divide Chocolate 875. Koko Eating Bananas 774. Minimize Max Distance to Gas Station 1201. Ugly Number III 1482. Minimum Number of Days to Make m Bouquets 2141. Maximum Running Time of N Computers

Calculator
224. Basic Calculator 227. Basic Calculator II 282. Expression Add Operators 772. Basic Calculator III

Prerequisites
207. Course schedule, 210. Course schedule II. (list, graph requirements)
**
Code/Encode tree**
297. Serialize and Deserialize Binary Tree 428. Serialize and Deserialize N-ary Tree

11. Container with most water (water stayed)
245. Strobogrammatic number (number with change)
687. Longest Univalue path (tree, longest path with same value)
938. Range Sum of BST (sum of keys in binary search tree by range)
296: Best Meeting Point (matrix, distances)
2. Add two numbers in the linked list (linked list, sum)

Sliding window
Sliding window, 239. Sliding window max (list, max value), 480. Sliding Window Median (list, median), Sliding Window Average (list, avg)
715. Range Module (module)
15. 3Sum 1. TwoSum 16. 3Ssum Closest 18. 4Sum
Jump game 1 (array, first idx) Jump game 2 (array, min number of jumps) Jump game 3 (array, custom start) Jump game 4 (string, min max)

Backtracking problems: Combinations/permutations/subset/combination sum
Min cash flow
2079. Watering plants (1 worker) 2105. Watering plants II (2 workers)

Flipping matrix
Flip row or column and get all zeroes Flip binary matrix to get high score

Frequent
**Min amplitude after 3 changes (int list, change 3 times, max diff)
Ways to split string (string, split: left = right)
Max time for given digits (list, max time from it)
Server loads balancing / stone game (list, split by 2, combine)
Most booked hotel rooms (which room is booked the most?)
Min domino rotations (domino rotations)
Time to type a string (string, based on positions)
Max lvl sum of a binary tree (smallest level with the max sum)
Min Number of Chairs (lists, arrive, leave, get number of seats)
K Closest Points to Origin (list of points, k closest to origin)
Odd Even Jump (list, odd/even jumps)
License Key Formatting (string, reformat)
Unique Email Addresses (list, email filter)
Fruit Into Baskets (list, baskets)
Min Days to Bloom (list, k adjusted, l bouquets)
Fill Matrix (two diagonals and columns are equal)
Decreasing Subsequences (list, split it in decreasing subsequences)
Max Distance (binary strings, max editing distance) solution
Stores and Houses (2 lists, closest house to the store)
Pairs of integers (list, form equal pairs)
Longest substring with last == first (string, substring last = first)
Alphabet board path (matrix, alpha, UDLR)
Solve series of equations (A = B+1, B = 1)
444. Sequence reconstruction ((321) = (1,2)+(1,3)+(2,3))
221. Maximum Square (matrix, max square area)
295. Median in list (list, **class to find median)
818. Race car (speed (A*2/R-1), position)
Temperature sliding window (monotonic queue, max temperature, sliding window)
366. Find Leaves of binary tree (any tree, convert tree to list)
Jobs, max cpus, duration (list, check if job can be executed)
Calculate max ancestors (tree, Max ancestors)
Combinations of a RGBY (list, top k sum combinations)

Language
List comprehension newList = [ expression(element) for element in oldList if condition ] 
Iterators - iterator protocol: __iter__() and __next__(). Custom iterator
Lambda functions – anonymous functions, called by ‘_’ (lambda x: x + 1)(2); high level functions: high_ord_func = lambda x, func: x + func(x); high_ord_func(2, lambda x: x * x)

Prep google docs:
1. Font to consolus
2. Tools -> prefs -> turn off auto

During interview: 0. Overexplain staff
1. Ask clarification questions to make sure you understand the problem correctly
2. Discuss any assumptions you’re planning to make to solve the problem
3. Analyze various solutions and tradeoffs before starting to code
4. Plan and implement your solution
5. Test your solution, including corner and edge cases

Bonus
Here are two ref links for the f00bAr challenge from 10^100 company:
“https://f00bar.withg00gle.com/?eid=j1xPb” (replace 0 with o)
“https://f00bar.withg00gle.com/?eid=GQqyC” (replace 0 with o)