Design Flashcards
LRU Cache (Medium)
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Initialize with capacity, cache (map) and doubly linked list
map maps key to list nodes
list tracks nodes with head being most recent, tail being least recent, length of capacity
get:
if key not in cache, return -1
update cache for key
return cache.get(key).value
put: create new node for key/value if cache has key, remove node from list if cache over capacity, remove tail and delete from cache insert node to head of list set node in cache with key
update:
remove node from list
set node to head of list
update node in cache
doubly linked list: sentinel head/tail insertHead(node) remove(node) removeTail(), return key (so you can remove from cache)
Read N Characters Given Read 4 (Hard)
Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.
Method read4:
The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.
The return value is the number of actual characters read.
create internalBuf outside fn let readChars = 0
while (n > 0) (still have chars to read)
if internalBuf empty, then call read4 w/ internalBuf
if read4 returns 0, return readChars
push to output buffer one character at a time from internalBuf
increment readChars
decrement n
return readChars
Implement Trie Prefix Tree (Medium)
Implement a trie with insert, search, and startsWith methods.
TrieNode class children = new Map() word = false
this.trie = new TrieNode()
insert:
set current node to trie, iterate through word, if node.children doesn’t have char, add to map (char to TrieNode), set node to matching child
at end set node.word to true
search:
iterate through word, set node to matching child, if reach end and word = true, return true
for wildcard search, if char not found and char equal wildcard, check all nodes at this level recursively, return true if any find word
startsWith:
iterate through word, set node to matching child, return if matching node regardless if word = true
Implement Stack With Queues (Easy)
Implement Queue With Stacks (Easy)
Use two stacks/queues
When adding, push to first if empty, otherwise pop/shift everything off first and push to second, then add new value to first, then pop/shift everything off second and push back to first
First Bad Version (Easy)
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Start = 1, End = n Binary Search if isBadVersio() end = mid - 1 else start = mid + 1
return start
Insert Delete GetRandom O(1) (Medium)
Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
initialize with map and list (array)
insert:
if map has value return false
map.set(val, list.length)
list.push(val)
remove:
if map does not have value return false
get index of val from map
map.delete(val)
pop last item off list
if list.length equals index, that means it was already last item, return true
otherwise map.set(last, idx) and list[idx] = last
getRandom:
calc random index
Math.floor(Math.random() * list.length)
Random Pick Index (Medium)
Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Initialize with nums
pick: If length of array is 1, return 0 let count = 0, let result = 0 iterate through array reservoir sampling if nums[i] = target & floor(random() * ++count) === 0 result = i
return result
All O(1) Data Structure (Hard)
Implement a data structure supporting the following operations:
Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) - If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string “”.
GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string “”.
Challenge: Perform all these in O(1) time complexity.
class Node, set of keys, count, prev/next pointers addKey, removeKey methods
Initialize: head = node(min_safe_integer) tail = node(max_safe_integer) keyCount (map of keys to count) countKeys (map of count to keys/nodes)
inc: get oldCount from keyCount || 0 count = oldCount + 1 keyCount.set(key, count) countKeys.set(count, new Node(count)) addKey find oldNode and remove key add new node to list (insert after oldNode) if oldNode now empty (no keys), remove
dec: if keyCount does not have key, return get oldCount from keyCount if oldCount is 1, delete from keyCount count = oldCount - 1 keyCount.set(key, count) add key to new count find oldNode and remove key add new node to list (insert before oldNode) if oldNode now empty (no keys), remove
getMaxKey:
return one of keys from tail.prev
getMinKey:
return one of keys from head.next
Random Pick With Weight (Medium)
Given an array of positive integers w. where w[i] describes the weight of ith index (0-indexed).
We need to call the function pickIndex() which randomly returns an integer in the range [0, w.length - 1]. pickIndex() should return the integer proportional to its weight in the w array. For example, for w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e 25%) while the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e 75%).
More formally, the probability of picking index i is w[i] / sum(w).
Initialize:
Track totalSum and array of prefix sums
pickIndex: target = Math.random() * totalSum Binary search start = 0 end = prefixSums.length - 1
while (low < high)
if target > prefixSums[mid] low = mid + 1
else high = mid - 1
return low
