Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS > Algo > Flashcards

Algo Flashcards

1
Q
  1. Sliding Window Median
A

Remember:

  1. Calc median must check left.size() - nRemovingLeft vs. right.size() - nRemovingRight not just only left.size() and right.size()
  2. Using 2 priority queues: add to left must compare to move it to right if needed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q
  1. LRU Cache
A
  1. Using DLinkedList for the rank. When moving rank to top must keep the same instance so that we don’t need to update keyToRanks.put(key, newRank)
  2. removeElement must update prev and next to null at the end
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q
  1. Serialize and Deserialize N-ary Tree
A

Remember to add “+” at the end of the node string as a termination notation, otherwise, when reading digits it read the one of the next node string e.g.
1+0(ended)1+0: two-node with 0 children but when reading it because the first node with “01” = 1 child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q
  1. Construct Binary Tree from Inorder and Postorder Traversal
A
  1. Use inorderIndices of num -> index to split (start, end) in inorder array
  2. Only build retVal.right then retVal.left if its size > 0
  3. Using stack to store postorder
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

min & max & sum of array of ints

A

IntStream.of(ints).min().getAsInt()
IntStream.of(ints).max().getAsInt()
IntStream.of(ints).sum()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q
  1. Design Search Autocomplete System. Methods:
  2. AutocompleteSystem(String[] sentences, int[] times) {}
  3. List input(char c) {}
A

Using Trie and add times: Map to each node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
  1. Maximum Sum of 3 Non-Overlapping Subarrays

- -> must find indices of arrays, not just the sum

A
  1. DP with memorization
  2. Loop through the cache to trace back e.g. find first, second …
  3. Using dfs(nums, end,…) instead of dfs(nums, start,…) to get the first match
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q
  1. Delete Node in a BST

How to implement removeSmallest(TreeNode parent, TreeNode node): int

A

Go to left most node ultil node.left == null:

parent. left = parent.left == node ? node.right : parent.left;
parent. right = parent.right == node ? node.right : parent.right;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
  1. Stickers to Spell Word
A
  1. dfs(int[] target, int[][] stickers, cache)
  2. remember dfs can return -1. Must check. Do not do like this:
    Math.min(retVal, 1 + dfs(newTarget, stickers, cache)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q
  1. Longest Valid Parentheses

e. g. ()) -> 2

A

DP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q
  1. Best Time to Buy and Sell Stock IV

max k transactions

A
  1. Use int[][] transactions = new int[k][2]; // list of [min-price, max-profit so far]
  2. Initialize transactions[j][0] = prices[0];
  3. Start from idx = 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q
  1. Best Meeting Point
A
  1. Loop through all rows and columns to collect house rows, house columns
  2. Find the median of these sets of rows and columns separately
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
  1. Remove Invalid Parentheses

return all longest valid strings

A
  1. Two options for each open, close: keep or remove
  2. Remember to check and stop if opens < closes
  3. Remember to:
    resultBuilder.append(ch)
    call dfs
    remove last char in resultBuilder
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q
  1. Minimum Window Substring
    Input: s = “ADOBECODEBANC”, t = “ABC”
    Output: “BANC”
A
  1. Calc freqs for t

2. Move pointer idx, increase currentFreqs, try to move left pointer, decrease currentFreqs to make idx - left smallest

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
  1. Minimum Window Subsequence
    Input: s1 = “abcdebdde”, s2 = “bde”
    Output: “bcde”
    MUST maintain the order
A
  1. build closest array e.g. closest[j][0] the nearest ‘a’ to the left
  2. go from right to left of s1, find s1[idx] = s2 last char
  3. go from right to left of s2, find nextId = clostest[nextIdx - 1][ch - ‘a’]
    Important notes:
  4. use nextIdx - 1
  5. check nextIdx - 1 >= 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q
  1. Palindrome Pairs
    words[i] + words[j] is a palindrome.
    Find all (i, j)
A
  1. create suffixes and prefixes set
  2. for each word check: suffix then prefix
  3. remember the case: ab, ba will appear twice because of 2. For case word == suffix/prefix, only pick in “check suffix” ignore in “check prefix”
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
  1. Data Stream as Disjoint Intervals
    e.g. add 1, 1
    add 2, 2
    add 3, 3
    return 1,3
A

use TreeMap

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

TreeMap methods, what throws an exception if empty?

A
  1. higherKey, lowerKey, floorKey, ceilingKey: null if empty

2. firstKey, lastKey: exception if empty

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q
  1. LFU Cache
A
  1. using Rank i.e DLinkedList with prev, next, keys, freq
  2. JUST check case by case e.g. key does not exist, new freq does not exist, etc.
    do not need to do abstract here
  3. must be fast, this is very long
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q
  1. Robot Room Cleaner
A
  1. use visit(robot, row, col, direction, cache)

2. directions must be consistent e.g. {0, -1} then {1, 0} then {0, 1} then {-1, 0}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q
  1. Zigzag Conversion
A
  1. if numRows == 1: return
  2. 2 cases:
    a. first + last row
    b. normal row
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q
  1. Largest Divisible Subset
    e.g. [1,2,3,4,5,6,7,8,9]
    return [1,2,4,8]
A
  1. sort nums
  2. dp to calc largestSubsets[i]
  3. remember largestSoFar: int and largestNum in this largest so far
  4. trace back: right -> left
    finding = largestSoFar, num = largestNum
    find: nums[i] % num == 0 && largestSubsets[i] == finding then update:
    *** num = nums[i]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q
  1. Prefix and Suffix Search

i. e. search(String prefix, String suffix): return largest idx

A
  1. using prefix & suffix Trie having Trie.wordIndices
  2. in search find prefixIndices and suffixIndices
  3. remember to reverse suffix before searching
  4. must use prefixIndices.get(i).equals(…) instead of ==
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q
  1. Basic Calculator III

e. g. (1+2)/3

A
  1. 2 stacks: nums and opts
  2. remember idx++: not applied for reading operands
  3. rules:
    a. meet num: eval if top = * or /
    b. meet + or -: eval if top = + or -
    c. meet ): eval ultil seeing (
    d. after seeing (, must eval because of this case:
    2 * (1+2)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q
  1. Sliding Puzzle

e. g. [[1, 2, 3], [4,0,5]] -> 1 swap to make [[1,2,3],[4,5,0]]

A
  1. must use BFS instead of normal dfs i.e. using seen to keep track of the path. This dfs with the depth of (mn)! call stack causes 2**(mn)! time complexity
  2. using int swaps to count the number of steps
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q
  1. Swim in Rising Water

i. e. with raining, grid[i][j] is the height of the cell

A
  1. can only go from cell 1 to cell 2 if the height of 2 cells + water is the same
  2. use Math.max(top[0], maxHeight of 2 cells) for nei cell
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q
  1. Sliding Window Maximum

k window, return max in the window for each move

A
  1. using dq/queue to achieve O(N)

2. store idx in dq instead of value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q
  1. Shortest Subarray with Sum at Least K

with negative nums

A

Note: use PriorityQueue of sum also works
1. using treeMap.put(preSum, last idx)
2. find floorEntry of currentSum - k, if found
keep trying then remove all keys before this floorKey
3. key here is (for both neg and positive shortest subarray problem): if 1 start point can pair with current idx, we can remove it because the next idx2 if can pair, the length idx2 - start is already > idx - start

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q
  1. Super Egg Drop

n floors, k eggs –> how many moves

A
  1. using dp[moves][eggs] how many floors can be covered with this number of moves & eggs
  2. dp[moves][eggs] = 1 + dp[moves - 1][eggs] + dp[moves-1][eggs-1]
  3. remember to catch base case moves - 1 <= 0, eggs = 0 or 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q 
895. Maximum Frequency Stack
pop the max freq, if same freq, pop the last added one
e.g.
push: 2 1 2 1
pop: 1 2 1 2
A

Observation: pop val, freq will decrease by 1 so for sure the freq - 1 will exist

  1. freqToVals: Map>
  2. maxFreq
  3. valToFreqs: current freq
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q
  1. Number of Music Playlists
    k: before can repeat the song e.g. k = 2: 1 2 3 1
    input: k, songs, goal: playlist size
A
  1. dp: dp[songs][goal] = dp[songs - 1][goal - 1] * songs + dp[songs][goal - 1] * (songs - k)
  2. base cases: songs == goals && songs == k + 1
    for: songs == k + 1: e.g. 3 songs, k = 2: always repeat the pattern
    1 2 3 1 2 3… doesn’t matter the value of goals
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q
  1. Binary Tree Cameras

Camera can cover itself, parent and children

A
  1. int minCamera(TreeNode node, boolean withCamera, boolean covered)
  2. consider case by case e.g. if withCamera, if not withCamera but covered…
  3. remember to cache
33
Q
  1. Number of Ways to Paint N × 3 Grid

using 3 colors, no 2 cells having the same color

A
  1. long dfs(int rows, int colorsLastRow)
  2. colorsLastRow can be 2 or 3
  3. count(prevColors, colors): just use 3 for-loops
34
Q
  1. Combination Sum
    find all combinations sum up to target
    e.g. [2,3,6,7] target = 7 result = [[2,2,3],[7]]
A
  1. backtracking, no fancy algo here

2. must ask interviewer about duplication constraint

35
Q
  1. Longest Substring with At Most K Distinct Characters
A
  1. using left, right. Init = 0
  2. for each loop while right < length
    a. add new s[right]
    b. move left until unique chars <= k
    c. update retVal
    d. right++
36
Q
  1. Count subarrays with K Different Integers
A

a. read problem 340. Longest Substring with At Most K Distinct Characters
b. result = atMost(nums, k) - atMost(nums, k - 1)

37
Q
  1. Largest Component Size by Common Factor

e. g. [20,50,9,63] –> 2 groups 20, 50 and 9, 63

A
  1. for each num loop through [2, Math.sqrt(num)] as common
  2. use UF.union(num, common) and (num, num / common) if num % common == 0
  3. for each num, using UF.findParents to count items in each group
38
Q
  1. Interval List Intersections
A

when checking to move, must compare point[1] values instead of point[0] values

39
Q
  1. Number of Submatrices That Sum to Target
A
  1. calc prefixSum[row][col] must use: row Sum and prefix[row - 1][col] but NOT global sum
  2. loop with (r1, r2, c) to have N^3, not N^4
40
Q
  1. Valid Palindrome III

e. g. remove at most k letters to make a palindrome

A
  1. using check(left, right) <= k to have N^2 instead of N^3 with (left, right, removing)
41
Q
  1. Divide Chocolate
    e.g. split into n subarray, select the one with min sweetness
    ? max sweetness can have
A
  1. same as 410
42
Q
  1. Maximal Square

i. e. area of the biggest square with all 1

A
  1. N^3 solution:
    a. calc prefixOnes: how many ones in the row from right to this cell
    b. try to go down
  2. dp[row][col] = 1 + min(dp[row + 1][col], dp[row][col + 1], dp[row + 1][col + 1])
43
Q
  1. Partition List

i. e. linked list, given x. Sort nodes so that < x in left, >= x in the right but maintain the original order

A
  1. preHead, head
  2. find preRight, right
  3. move from right.next, delete node.val < x, create node before right, after preRight
44
Q
  1. Minimum Cost to Cut a Stick

range: 0 -> n, & list of cuts. cost of cut = length of the bar

A
  1. time: O(C ^ 3), C = number of cuts

2. cut(left, right, cuts)

45
Q
  1. Search in Rotated Sorted Array II

with duplications

A
  1. check case nums[mid] < nums[right] case
    a. check case to have left = mid + 1, the rest will be right = mid - 1
  2. else if nums[mid] > nums[right]
    a. remember nums[mid] < target OR: ***target <= nums[right]
  3. else: check nums[left] vs. target before left++
46
Q
  1. Minimum Number of Days to Make m Bouquets
  2. Find the Smallest Divisor Given a Threshold
  3. Divide Chocolate
  4. Capacity To Ship Packages In N Days
  5. Koko Eating Bananas
  6. Minimize Max Distance to Gas Station
  7. Split Array Largest Sum
A
  1. binary search
    a. create feasible function
    b. choose left, right
47
Q

How to detect binary search problems?

e.g. divide chocolate problem: chocolate bar, maximize the minimized sweetness pieces

A
  1. satisfy condition(k) is true then condition(k +1) is true
  2. min (max) the max(min) value
    ref: https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems
48
Q
  1. Kth Smallest Number in Multiplication Table
A

binary search:

  1. left = 1, right = m * n
  2. for each mid, loop through each row, count how many col with (row + 1) * (col + 1) <= mid
49
Q
  1. Find K-th Smallest Pair Distance [Hard]

i. e. distance = abs(nums[i] - nums[j])

A
  1. sort nums
  2. binary search
  3. problem: in a sorted array, count how many pairs having distance <= mid?
50
Q
  1. Count Different Palindromic Subsequences

i. e. s.length <= 1000, only contain letters a, b, c, d

A
  1. build prefix (nearest char to the right e.g. ‘a’) at i, suffix (nearest char to the left e.g. ‘a’)
  2. unique chars in range i, j
51
Q
  1. Shortest Path Visiting All Nodes

w/: nodes <= 12

A
  1. using mask int to store all nodes visited e.g. node.mask | 1 &laquo_space;neiId
  2. seen = Set of nei + neiMask
52
Q

*1326. Minimum Number of Taps to Open to Water a Garden

tap at [i] can cover i - ranges[i] to i + ranges[i]

A
  1. for each tap, calculate minRange, maxRange it can cover
  2. build farCanReach[minRange] = max of all maxRange
  3. use jump game way to solve: jump(start, farCanReach, memo)
53
Q
  1. Number of Ways to Arrive at Destination

w/: shortest ways only from 0 to n - 1

A
  1. dijkstra

2. in for-loop of nei: update timeByNodes and countByNodes

54
Q
  1. The Maze II

w/: shortest distance from start to destination

A
  1. dijkstra, do not do dfs, bfs

2. add isValidRoll(current, direction) function

55
Q
  1. Couples Holding Hands

w/: how many swaps to make couples sit side by side

A
  1. 2n seat –> n couches of 2 seats
  2. connect couches into cycle e.g.
    (0, 3), (1, 4), (2, 5)
    c1 -> c2 -> c3 -> c1: 3 points -> need 2 swaps
56
Q
  1. Find K Pairs with Smallest Sums
    w/: 2 sorted arrays
    w/: 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows
A
  1. same as merge sort k sorted arrays
  2. init: nums1[0], nums2[j] with max j = k - 1
  3. poll from priority-queue and increase idx1 if < nums1.length
  4. for 1439. reuse prev = kSmallestPairs(prev, mat[idx], k)
57
Q
  1. Insert Interval
A
  1. find intertionIdx by finding last interval with

interval[1] < newInterval[0]

58
Q
  1. Graph Valid Tree

w/: undirected graph

A
  1. build graph with:
    retVal.computeIfAbsent(edge[0], k -> new HashSet<>()).add(edge[1]);
    retVal.computeIfAbsent(edge[1], k -> new HashSet<>()).add(edge[0]);
  2. IMPORTANT: dfs must have both node and prev node to prevent case: 0 –> 1, 1 –> 0 because of 1.
59
Q
  1. Shortest Path in a Hidden Grid

w/: GridMaster.{canMove(direction: char), move(direction)}

A
  1. dfs to explore the grid
  2. bfs to find shortest distance. IMPORTANT: must update seen right after queue.add to avoid duplicate
    NOT: add seen after queue.removeLast()
60
Q
  1. Find Peak Element
    return index of any peak element
    imagine that nums[-1] = nums[n] = -inf
A
  1. using binary search way
  2. leftCond, rightCond
  3. if not mid && leftCond –> go right, otherwise, go left
61
Q
  1. Find a Peak Element II

Given: a matrix where no two adjacent cells are equal

A
  1. ref 162. Find a Peak Element
  2. find row with max value of mid col
  3. of nums[maxRow][midCol] < nums[maxRow][midCol - 1] –> find in left…
62
Q
  1. Game of Life
    if live: neiLives == 2 or 3 to maintain live
    if dead: neiLives == 3 to be live
    ? infinite board
A
  1. IMPORANT: directions must not contain (0, 0)
  2. O(1): store val: (prevStatus + 1) * 10 + (newStatus + 1)
  3. infinite board: keep 3 rows in memory: current, above, below
63
Q
  1. Longest Repeating Substring

e. g. “aabcaabdaab” -> 3 (“aab” repeated)

A

solution 1. dp(s, end1, end2, memo): O(N^2)

solution 2. generate all suffixes then sort. repeated substrings should be adjacent: O(NLogN)

64
Q
  1. Cheapest Flights Within K Stops
A
  1. dijkstra algo
  2. check & add in for-nei loop
  3. number of stops = Math.max(0, nFlights - 1)
  4. keep lastVisits: map of city -> [cost, flights]. Update every valid step in 2.
65
Q
  1. Longest String Chain
A
  1. remove each letter and check with words to build the graph –> L^2N where L is max length of word (otherwise buildGraph could take LN^2
  2. ? check time complexity
66
Q
  1. Rank Teams by Votes

e. g. “AB”, “AB”, “BA” -> A first, B second…

A
  1. create Map with Team.votes: int[nTeams]

2. sort by all vote in Team.votes DESC, then Team.name ASC

67
Q
  1. Open the Lock
A
  1. Graph, BFS
68
Q
  1. Longest Substring with At Least K Repeating Characters
A
  1. longest substring with n unique chars, n from 1 to AZ

2. using start, end pointers

69
Q
  1. Number of Equal Count Substrings

e. g. “aabb”, count = 2 –> 3: “aa”, “bb”, “aabb” as all substrings having number of uniq chars = 2

A
  1. nChars = 1 to AZ. Two solutions from here:
    a. using fixed window size e.g. count * nChars
    b. using start, end pointers, same as 395. Longest Substring with At Least K Repeating Characters
70
Q
  1. Longest Subsequence Repeated k Times
    n == s.length
    2 <= n, k <= 2000
    2 <= n < k * 8
A
  1. max number of chars = 7
  2. generate candidates for each length value from 1 to 7 & check if there’re k repeating times
  3. time complexity: worst case: 7 unique chars e.g. abcdef. O(N77!)
71
Q
  1. Valid Parenthesis String

with (, ) and * = empty, open or close

A
  1. solution 1: using dp(s, idx, opens, closes). O(N^3)
  2. solution 2: using dp(s, idx, balance). O(N^2)
  3. solution 2: using minBalance, maxBalance
    a. incr both if meet (
    b. decr both if meet )
    c. decr min, incr max if meet *
    d. return false if maxBalance < 0
    e. return minBalance == 0
72
Q
  1. Paths in Maze That Lead to Same Room

e. g. number of cycles with 3 nodes

A
  1. build the graph
  2. loop through all edges and check if neiRooms1 and neiRooms2 share the same nei then retVal++
  3. retVal / 3 as each cycle counted 3 times
73
Q
  1. Minimum Cost to Reach City With Discounts

Use maximum N discounts for the route to have cost / 2

A
  1. similar to 787. Cheapest Flights Within K Stops. use lastVisits to record the last cost and discount
  2. but got TLE
74
Q
  1. Split BST

given a target, split BST into 2 trees: <= target, > target

A
  1. 30 lines, dfs
75
Q
  1. Delete and Earn

pick j and delete j, nums[j] + 1, nums[j] - 1 get nums[j] point. Calc max point

A
  1. sort

2. dp

76
Q
  1. Minimum Insertions to Balance a Parentheses String
    e.g. need ‘(‘ pair with ‘))’. How many add ‘(‘ and ‘)’ needed to make the input balanced
    Similar: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
A
  1. int balance
  2. if ch == ‘)’, read all, if closes % 2 == 1, add 1. Decrease the balance while closes > 0, balance > 0
  3. before returning: retVal += balance * 2
77
Q
  1. Minimum Swaps to Make Strings Equal

e. g. “xx” and “yy” –> swap s1[0] and s2[1] to have “yx” == “yx”

A
  1. loop through all chars, ignore all s1[idx] == s2[idx]
  2. count x1, y1 and x2, y2
  3. Imposible: x1 + x2 != y1 + y2 || (x1 + x2) % 2 == 1
  4. case “xx” and “yy” need 1 swap, “xy”, “yx” need 2 swaps
    - -> x1 / 2 + y1 / 2 + (x1 % 2 == 1 ? 2 : 0)
78
Q
  1. Score of Parentheses
    (): 1
    AB: A + B
    (A): 2 * A
A
  1. using stack, add 0 if open

2. update retVal if “)” and the root level

79
Q
  1. Wildcard Matching

with ?: match 1, *: match any

A
  1. 3 cases to match * e.g. skip both, skip in s, skip in p

CS (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions