Medium Flashcards
- LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
use OrderedDict or Hash Map + Doubly Linked List
OrderedDict:
Any time a key is used (get/put), move it to the end of the ordered dict. Then the first element is the LRU.
Hash Map + Doubly Linked List:
Store nodes in the hash map by key. When you retrieve the node, you can use it to remove itself from the linked list (regardless of its position) and add it back at the end. This allows you to maintain a unique queue of keys.
- Number of Islands
Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
DFS works but is slowish O(4^nm). BFS is O(nm).
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
self.ROWS = len(grid)
self.COLS = len(grid[0])
visits = set()
count = 0
for r in range(self.ROWS):
for c in range(self.COLS):
count = count + self.dfs(grid, r, c, visits)
return count
def dfs(self, grid, r, c, visits) -> int:
# base case of out bounds
if min(r, c) < 0: return 0
elif r == self.ROWS: return 0
elif c == self.COLS: return 0
# base case cur val is zero, return zero
if grid[r][c] == "0": return 0
# base case already visited
if (r,c) in visits: return 0
# if one, add cur pos to visits
visits.add((r, c))
# step
self.dfs(grid, r, c+1, visits)
self.dfs(grid, r+1, c, visits)
self.dfs(grid, r, c-1, visits)
self.dfs(grid, r-1, c, visits)
# ignore all return values
# return one if cur pos is one
return 1
- Max Area of Island
You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
DFS works but is slowish
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
self.ROWS = len(grid)
self.COLS = len(grid[0])
visits = set()
maxArea = 0
for r in range(self.ROWS):
for c in range(self.COLS):
res = self.dfs(grid, r, c, visits)
maxArea = max(res, maxArea)
return maxArea
def dfs(self, grid, r, c, visits) -> int:
# base case of out bounds
if min(r, c) < 0: return 0
elif r >= self.ROWS: return 0
elif c >= self.COLS: return 0
# base case cur val is zero, return zero
if grid[r][c] == 0: return 0
# base case already visited
if (r,c) in visits: return 0
# if one, add cur pos to visits
visits.add((r, c))
# step
count = 1
count = count + self.dfs(grid, r, c+1, visits)
count = count + self.dfs(grid, r+1, c, visits)
count = count + self.dfs(grid, r, c-1, visits)
count = count + self.dfs(grid, r-1, c, visits)
# count accumulates the size of the island
return count
- Shortest Path in Binary Matrix
Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
All the visited cells of the path are 0. All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.
O(n)
BFS - Breadth First Seach of a matrix O(n)
import collections
class Solution:
# BFS. Also could use A, which uses estimates of the remaining dist to prioritize paths.
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] > 0: return -1
n = len(grid)
visits = set()
queue = collections.deque()
queue.append((0, 0))
neigh = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]
grid[0][0] = 1 # set num of previous steps
shortest = nn + 1
while queue: # O(n)
r, c = queue.popleft()
visits.add((r, c))
steps = grid[r][c]
if (r, c) == (n-1, n-1): # reached bottom right corner
if grid[r][c] < shortest:
shortest = grid[r][c]
for dr, dc in neigh: # O(8)
rNeigh = r + dr
cNeigh = c + dc
if min(rNeigh, cNeigh) < 0 or max(rNeigh, cNeigh) >= n or grid[rNeigh][cNeigh] >= 1 or (rNeigh, cNeigh) in visits:
continue
queue.append((rNeigh, cNeigh))
grid[rNeigh][cNeigh] = steps + 1
if shortest > n*n: return -1
return shortest
- Rotting Oranges
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
BFS O(nm)
def orangesRotting(self, grid: List[List[int]]) -> int:
ROWS = len(grid)
COLS = len(grid[0])
NEIGH = [[0, 1], [1, 0], [0, -1], [-1, 0]]
steps = 0
rotten = collections.deque()
fresh = set()
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
rotten.append((r, c))
elif grid[r][c] == 1:
fresh.add((r, c))
while fresh:
if len(rotten) == 0 : break
rotten.append((-1, -1)) # marker
while rotten:
r, c = rotten.popleft()
if r == -1: # we reached the marker
break
# add fresh neighbors to queue
for dr, dc in NEIGH:
rN = r + dr
cN = c + dc
if (rN, cN) in fresh:
rotten.append((rN, cN))
fresh.remove((rN, cN))
grid[rN][cN] = 2
if len(fresh) == 0: break
steps += 1
if fresh: return -1
return steps
- Search a 2D Matrix
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Binary search. Treat matrix as as sorted array, calculate index. O(log(mn))
- Koko Eating Bananas
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Binary search. Search between min/max possible time to eat the bananas to find the optimal rate.
- House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Binary decision tree with DP. At every house, skip either 1 or 2 houses. It doesn’t make sense to skip 3, because you could have skipped 1 and gotten a larger sum. Use memoization to speed up.
- Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
2-dimensional DP bottom up approach
def uniquePaths(self, m: int, n: int) -> int:
prevRow = [0] * n
prevRow[n-1] = 1 # puts 1 in the bottom right cell
for row in range(m-1, -1, -1): # iterate through row indices backward
curRow = [0] * n
for col in range(n-1, -1, -1): # iterate through col indices backward
right = curRow[col+1] if col + 1 < n else 0
down = prevRow[col]
curRow[col] = down + right
prevRow = curRow
return prevRow[0]
- Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.
Step through each cell in the board. Add its value to an array of length 9. We have arrays for each row, col, and 3x3 box. Before writing the value, check if it already exists. If so, return false.
To improve on space complexity, we could use bitmasks instead of arrays.
- Design Bounded Blocking Queue
Implement a thread-safe bounded blocking queue that has the following methods:
BoundedBlockingQueue(int capacity) The constructor initializes the queue with a maximum capacity. void enqueue(int element) Adds an element to the front of the queue. If the queue is full, the calling thread is blocked until the queue is no longer full. int dequeue() Returns the element at the rear of the queue and removes it. If the queue is empty, the calling thread is blocked until the queue is no longer empty.
Use two Lock objects, one for enqueue and one for dequeue. Lock the dequeue in init. Use a deque for storage.
- Fizz Buzz Multithreaded
You have the four functions:
printFizz that prints the word "fizz" to the console, printBuzz that prints the word "buzz" to the console, printFizzBuzz that prints the word "fizzbuzz" to the console, and printNumber that prints a given integer to the console.
You are given an instance of the class FizzBuzz that has four functions: fizz, buzz, fizzbuzz and number. The same instance of FizzBuzz will be passed to four different threads:
Thread A: calls fizz() that should output the word "fizz". Thread B: calls buzz() that should output the word "buzz". Thread C: calls fizzbuzz() that should output the word "fizzbuzz". Thread D: calls number() that should only output the integers.
Modify the given class to output the series [1, 2, “fizz”, 4, “buzz”, …] where the ith token (1-indexed) of the series is:
"fizzbuzz" if i is divisible by 3 and 5, "fizz" if i is divisible by 3 and not 5, "buzz" if i is divisible by 5 and not 3, or i if i is not divisible by 3 or 5.
Implement the FizzBuzz class:
FizzBuzz(int n) Initializes the object with the number n that represents the length of the sequence that should be printed. void fizz(printFizz) Calls printFizz to output "fizz". void buzz(printBuzz) Calls printBuzz to output "buzz". void fizzbuzz(printFizzBuzz) Calls printFizzBuzz to output "fizzbuzz". void number(printNumber) Calls printnumber to output the numbers.
Each thread only calls its function once. Use the printNumber thread as the master thread, run a for loop, and have it release the others as needed. The others have while True loops where they acquire a lock and check the done flag. Then they release the number thread. When done, the number thread acquires its lock again to make sure no other threads are running, then sets the done flag and releases the other threads.
from threading import Semaphore
class FizzBuzz:
def __init__(self, n: int):
self.n = n
self.done = False
self.fLock = Semaphore(0)
self.bLock = Semaphore(0)
self.fbLock = Semaphore(0)
self.nLock = Semaphore(1)
# printFizz() outputs "fizz"
def fizz(self, printFizz: 'Callable[[], None]') -> None:
print("fizz")
while True:
self.fLock.acquire()
if self.done: break
printFizz()
self.nLock.release()
# printBuzz() outputs "buzz"
def buzz(self, printBuzz: 'Callable[[], None]') -> None:
print("buzz")
while True:
self.bLock.acquire()
if self.done: break
printBuzz()
self.nLock.release()
# printFizzBuzz() outputs "fizzbuzz"
def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
print("fizzbuzz")
while True:
self.fbLock.acquire()
if self.done: break
printFizzBuzz()
self.nLock.release()
# printNumber(x) outputs "x", where x is an integer.
def number(self, printNumber: 'Callable[[int], None]') -> None:
print("number")
for i in range(1, self.n+1):
self.nLock.acquire()
if i % 3 == 0:
if i % 5 == 0:
self.fbLock.release()
else:
self.fLock.release()
else:
if i % 5 == 0: # and not 3
self.bLock.release()
else: # not divisible by 3 or 5
printNumber(i)
self.nLock.release()
self.nLock.acquire() # ensures no other threads are running
self.done = True
self.fLock.release()
self.bLock.release()
self.fbLock.release()
- Two Sum II - Input Array Is Sorted
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Use two pointers. Move the r pointer up until it get to target. Then move left and right pointers in until you find a match.
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l = 0
r = 1
while r < len(numbers) - 1 and numbers[r] < target:
if numbers[r] + numbers[l] == target: return [l+1, r+1]
r += 1
while l < r:
sm = numbers[r] + numbers[l]
if sm == target:
return [l+1, r+1]
elif sm < target:
l += 1
else:
r -= 1
assert("Solution not found")
return [0, 0]
- Rotate Array
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Reverse the entire array, then reverse the first k elements, then reverse the remaining elements.
Another approach is to move each number to its final position (calculated), storing the existing number in a temp variable and moving it to its final position on the next iteration.
k = 3
Original List : 1 2 3 4 5 6 7
After reversing all numbers : 7 6 5 4 3 2 1
After reversing first k numbers : 5 6 7 4 3 2 1
After revering last n-k numbers : 5 6 7 1 2 3 4
class Solution:
def reverse(self, nums: list, start: int, end: int) -> None:
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start, end = start + 1, end - 1
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
self.reverse(nums, 0, n - 1)
self.reverse(nums, 0, k - 1)
self.reverse(nums, k, n - 1)
- Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
nth from the END. Use two pointers. Make a dummy head. Start both pointers at the dummy. Advance the leading pointer to n, then advance both by one until reaching the end of the list. Use the trailing pointer to cut out the nth node from the end:
trailing.next = trailing.next.next
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
trailing = dummy
leading = dummy
for _ in range(n+1):
leading = leading.next
while leading:
trailing = trailing.next
leading = leading.next
trailing.next = trailing.next.next
return dummy.next
