Tech Interview Flashcards
Alg. complexity of (Hash)Set - Add/Remove/Contains/Size operations
O(1)
Write an optimized Disjoint Set Class in Python with Path Compression and Union-by-Rank
class UnionFind:
def \_\_init\_\_(self, size):
self.root = [i for i in range(size)]
self.rank = [1] * size
def find(self, x):
if x == self.root[x]: return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.root[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.root[rootX] = rootY
else:
self.root[rootY] = rootX
self.rank[rootX] += 1
def connected(self, x, y):
return self.find(x) == self.find(y)
Time Complexity for Find, Union, Connected operations of Disjoint Set with Path Compression and Union-by-Rank
O(1) on average
Write a Binary Search function in Python for a list (array)
def BS(arr, val):
if len(arr) == 0: return -1
low = 0
high = len(arr) - 1
mid = 0
while low < high:
mid = (low + high) // 2
if arr[mid] == val:
return mid
elif arr[mid] > val:
high = mid - 1
else:
low = mid + 1
return -1
Every time you ‘union’ two nodes in a disjoint set that aren’t already connected, what happens to the number of distinct sets?
Decreases by 1
How to sort a list of lists in Python by the first element of each inner list
Call sort() on the list of lists
How to clear a set in Python
set.clear()
How to determine if a graph is a valid tree?
- All nodes should be connected in some way
- Only one path connecting any 2 nodes (no cycles)
How to get union of a set
Ex. get {1,4,6,7} from {1,4} + {6,7}
A | B
How to get absolute value in Python
abs()
Give a high-level description of Kruskal’s algorithm to get the minimum spanning tree
- Create a new UnionFind() for all points
- Get the list of all possible edges for the points, and sort by weight of an edge ascending.
- For each edge, check if connected points are already connected in UF. Skip if so.
- If not, that edge (weight) is included, and connect the points
How to construct a heap in Python
import heapq
heapWithValues = [3,1,2]
heapq.heapify(heapWithValues)
What data structure to use when you care about getting the max/min value of a set of data, but don’t care about the order of the rest of the data?
A heap
Time complexity of insertion, deletion, getMax/getMin of a heap?
O(log N), O(log N), O(1)
Time complexity to convert data to a heap using Heapify
O(N)
How to get the K largest/smallest elements from a collection of data?
Add K elements to a heap
For every next element in data, delete top of the heap if larger/smaller, add current element to top of heap (keep only K in heap)
At the end of iteration, will have K smallest/largest
Time complexity: O(N log K)
How to find the Kth largest/smallest element in a collection of data?
Add K elements to min/max heap, respectively
Iterate over remaining data. For current element, if larger/smaller than current element, remove top of heap and add current value
At the end, the top of heap is the Kth largest/smallest element.
Time complexity: O(N log K)
Python code for finding Kth largest element in array
import heapq
def findKthLargest(self, nums: List[int], k: int) -> int:
minHeap = []
for i in range(k):
minHeap.append(nums[i])
heapq.heapify(minHeap)
for i in range(k,len(nums)):
if nums[i] > minHeap[0]:
heapq.heappop(minHeap)
heapq.heappush(minHeap, nums[i])
return minHeap[0]
What needs to be done to create and use a max heap in Python (heapq) ?
Every value added or removed (popped) needs to be multiplied by -1
What’s the sort mechanism when sorting a list of lists/tuples in Python?
Calling list.sort() will sort ascending by first element in each list/tuple. If first element is equal, it will sort on the second element
How to remove an element from a Python list by index?
a = [1, 2, 3, 4] del a[1] # a = [1, 3, 4]
How to insert a value at beginning of List in Python
arr = [2, 3, 4]
arr.insert(0, 5)
// arr = [5, 2, 3, 4]
How to sum two positive numbers using bitwise operations?
x ^ y is the answer without the “carry”
(x & y) «_space;1 is the carry
Keep summing the above two in a loop until carry = 0
How to find difference of two positive numbers using bitwise operations?
x ^ y Is the answer without the “borrow”
((~x) & y) «_space;1 is the borrow
Keep summing the above two in a loop until borrow = 0
How to zero out the least significant ‘1’ bit of an int?
x & (x - 1)
How to find index of substring in string?
str.index(substr)
What’s the built-in Python tool for memoization?
from functors import lru_cache
@lru_cache
def myFunc(…):
…
What’s the problem with using @lru_cache with a function with lists as input?
Lists are unhashable, so this will fail.
Need to use tuples instead as a potential option
How to create a list with first n numbers in Python?
list(range(1, n))
How to initialize 2D array of zeros in Python?
zeros = [ [0] * cols for _ in range(rows)]
How to join strings in Python with separator
strs = [“hello”,”world”]
separator = “.”
separator.join(x for x in strs)
What can happen to mutable objects (sets, lists, dicts, etc.) when passed as an arg to a function in Python?
The original reference is passed as argument, and can be changed by the function
