Algo Solution Approaches

Question 1

Make Array Zero by Subtracting Equal Amounts

Answer 1

Count number of distinct non zero values and return that number since each operation removes the current smallest positive element from all.

let set = new Set(nums)
return set.has(0) ? set.size - 1 : set.size

Question 2

Copy list with random pointer

Answer 2

Use hashmap to map original nodes to new nodes in first pass, then set next and random pointers on second pass.

while (current)
nodeMap.get(current).next = nodeMap.get(current.next) || null
nodeMap.get(current).random = nodeMap.get(current.random) || null

Question 3

Reorganize string

Answer 3

Count character frequencies. If any character freq exceeds (n+1)/2 then return “” because not possible.

maxCount = Math.max(…freq.values()
if (maxCount > Math.ceil(s.length / 2) return “”

Push all [character, count] into heap (heapify up after each one) then while the heap has elements pop off two at a time, push both in result, then if freq - 1 is more than 0, push them back on the heap [character, count - 1)

When one char left, push to result, return result.join

Question 4

Word Break II

Answer 4

Use backtracking and memoization/DP.

Iterate over string and when prefix matched a dictionary word recursively process the remainder and cache results.

Memo is Map() and also keep a word Set()

DFS method takes index. Base case is when index === string length return empty string. Second base case when memo has the index as a key return that value.

Otherwise initialize result array. For loop from start idx + 1 and go for length of string. Prefix variable is s.slice(start, end). If word set has that prefix then make a suffixes variable = to recursive call passing in end idx. Loop through suffixes and push to results

results.push(suffix === “” ? prefix : prefix + “ “ + suffix)

Outside of loop memo.set(start idx, results)
Return results

Outside dfs return dfs(0)

Question 5

All nodes K distance in binary tree

Answer 5

Find target node and create parent map (map that store parents for each node) {node: parent}

const buildParentMap = (node, parent, map) => if !node return
if parent != null map.set(node, parent)
//recursive call
buildParentMap(node.left, parent, map)
buildParentMap(node.right, parent, map)

Preorder traversal

Set distance variable, queue = [target], visited set()

While queue length. If distance === k return queue.map(node => node.val (each new level is one more distance, so each loop adds one)

Set queue size and iterate through. Shift off a node and push children to visited and queue, if parent from parent map isn’t in visited, add to visited and queue. Increment distance

Question 6

Rotting oranges

Answer 6

Multi source BFS on each rotten orange. Keep track of time and fresh as we spread rotten.

so make directions and queue, count time and number of fresh oranges. Nested loop through grid increment fresh for 1s and push rotten to queue with 2s

While fresh exist and queue has elements, set queue size and iterate through. Pop off a square [row, col] then iterate through directions and get new row and new col. if that square is 1 (fresh) then push to queue, set it to 2, decrement fresh. Outside of the for loop, increment time before next queue loop.

Return fresh === 0 ? time : -1

Question 7

Integer to English Words

Answer 7

String formatting / divide and conquer. Keep an array of words and then break up n by groups of three

<20 [“”, “one”, “two”…”nineteen”
10s [“”, “”, “twenty”, “thirty”…”ninety”
thousands [“”, “thousand”, “million”, “billion”

Helper function with long if/else (if n < 20 do index of <20 list, if n < 100 do 10s[Math.floor n/10 + “ “ + helper(n%10), else below20[math floor n/100 + “Hundred” + helper(n%100)

Under helper function i = 0, while num>0 if num%1000 != 0 res = heloer(num%1000 + thousands[i] + “ “ + res
Num = math floor num/1000
i++

Return res.trim()

Question 8

LRU Cache

Answer 8

See other card for Map() version. In doubly linked list version it’s the same except we use linked list methods to add and remove nodes

Question 9

Max Robots within budget

Answer 9

Sliding window + monotonic queue (orders elements ascending or non). Use prefix sum to make prefix sum array from running costs. Then use sliding window to calculate the cost of the whole array.

First keep track of longest charge time in the window with the monotonic queue and a while loop (so only the longest charge time stays in the queue at any given time)

Set k/window size to r-l+1
Total running cost is prefix formula prefix[r+1] - prefix[l]
Cost = charge time (dequeue[0]) + k * total running

While cost > budget
If dequeue[0] < left then shift
Left++
Recalculate window size, total running cost, and cost

Still in for loop res= math max of res, left - right + 1

Outside loop return res

Question 10

Find triangular sum of array

Answer 10

Basically while loop through creating new and smaller arrays. Can use for loop, map, or reduce

while array length > 1

newArr = []
For loop
newArr.push(arr [i] + arr[i +1])
arr = newArr

OR

arr = arr.slice(1).map((val, i) => (val + arr[i]) % 10) this removes the first element from the array each loop

OR

arr = arr.reduce((newArr, cur, i, a) => {
If i < a.length
newArr.push((cur + a[i+1]) % 10)
Return newArr }, [])

THEN return arr[0] last element