• Misc, Python
Tags:

# Concepts

### Sliding Window

Give n element and k window size, try to get max sum.

### Bindary Search

• Only work when data is sorted

Step:

1. Use the left and right element as 2 pointers
2. Find the middle pointer between 2 pointers
3. Compare the middle element to search term
4. If middle > search term, replace left pointer with middle pointer + 1
5. If middle < search term, replace right pointer with middle pointer – 1

### Hash Table

• hash function
• collusion

collusion handling

• chaining: make each key point to a linked list, -> easy, never get full, use extra space and search O(N)
• open addressing: if key exists, probe until available -> more computation(probing), can get full, better performance

If number of keys is unknown, use chain; other wise use open addressing.

probe methods

• linear probing: probe to next slot
• double hashing

Compare to array:

• O(n) searching vs O(1) random access
• Cheaper insert/delete operation vs shift items

### Stack & Queue

• stack: LIFO, think abount dish plates
• queue: FIFO, think abount get in line for a concert

### Graph

• direct
• undirect, bi-directional

Implement with hash map

Implement with adjacency matrixes, The size is restricted.

e.g. number of nodes = 3

Set edge using `graph[v1][v2] = 1`

#### DFS

Implement with stack or recursion

#### BFS

Implement with stack or recursion

### Tree

A tree is a 1) connective, 2) acyclic, 3) undirected graph

• acyclic graph: having no cycles

Terminologies:

• root

• parent, child

• path

• leaf: no children

• tree height

• in-order: left -> root -> right

• pre-order: root -> left -> right

• post-order: left -> right -> root

Do know how to implement traversal using stack except recursion.

#### Binary Tree

• balance: height of two subtrees never differ by more than 1

#### Binary Search Tree

• left < root < right
• deletion
• leaf: direct delete
• node has one child: connect parent to child
• node has two child: replace with the minimal node which greater than the delete node

Deletion implementation:

# Math Problems

### Missing Numbers

Find the missing number for given array.

Three approachs:

1. sort the array and use 2 pointer, if current – previous > 1, the missing number is current – 1
2. hash map, first iteration to construct true/false values, second iteration to find the false one.
3. Gauss formula: sum([1,2,..n]) = n*(n+1)/2

### Count Primes

A prime is:

• Greater than 1
• Non-divisible by anything except 1 and itself

Assume the array is sorted and continuous e.g. [0, 1, 2, 3 … n], the approach:

1. Construct a boolean array with default value: true
2. Iter over array until n^2 > array size, update elements to false if the mod n is 0

### Single Number

Find the number only appear once.

The approach:

1. unique the arr items
2. 2*(a+b+c)-(a+a+b+b+c)=c

Space complexity: O(N), due to usage of set

The approach: seperate pointer for each input

# String Problems

### Move Zeros (in-place)

Move all 0’s to the end and maintain the order.

The approach: Think abount moving the non-zeros to front.

## Boats to Save People

The approach:

1. sort the array
2. group the heaviest and lightest together using 2 pointer

Time complexity: O(N*Log(N))

Space complexity: O(N), sorting

### Valid Mountain Array

Find if there is an increasing subarray followed by a decreasing subarray.

The approach: Construct a pointer start from index 1, compare to previous element.

### Container with Most Water

The approach: 2 pointer (left, right), compare the left and right height, the smaller moves.

### Longest Substring without Repeat Characters

The approach: 2 pointer start at 0 and a hash map to track character last shown position.

Move the right pointer if character does not exists, else move the left pointer to last shown position + 1.

### Find First and Last Position of Element in Sorted Array

“When you see sorted array, think abount binary search.”

“When you see sorted array, think abount binary search.”

# Hash Map Problems

### Group Anagrams

Hash function: sorted string

Time Complexity: O(N * M * Log(M)), M * Log(M) is sorting effort

• N: input array
• M: Longest word in array

### 4 Sum 2

Time complexity: O(N^2)

### LRU Cache

• move key to front for all operations: get / put

### Merge Two Sorted Lists

The approach: turtle and hare

The approach: keep tracking the previous node

### Remove Nth Node from Linked List

The approach: Use two pointer (left, right), the distance between left and right is given n.

The trick is set left pointer start from NULL.

e.g. n=2

# Backtracking / Recursion Problems

### Subset

A set contains n items has 2^n subset (each pick or not pick)

# Stack / Queue Problems

### Level Order Traversal

“When you see level by level, think abount BFS.”

# Dynamic Programming Problems

How do you know it is a DP problem?

1. if problem is recursive
2. a lot of repeated states

Two approachs:

1. top down
2. button top

### House Robber

The approach: Calculate max amount from button-top.