Tech Interview

Question 1

Alg. complexity of (Hash)Set - Add/Remove/Contains/Size operations

Answer 1

O(1)

Question 2

Write an optimized Disjoint Set Class in Python with Path Compression and Union-by-Rank

Answer 2

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)

Question 3

Time Complexity for Find, Union, Connected operations of Disjoint Set with Path Compression and Union-by-Rank

Answer 3

O(1) on average

Question 4

Write a Binary Search function in Python for a list (array)

Answer 4

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

Question 5

Every time you ‘union’ two nodes in a disjoint set that aren’t already connected, what happens to the number of distinct sets?

Answer 5

Decreases by 1

Question 6

How to sort a list of lists in Python by the first element of each inner list

Answer 6

Call sort() on the list of lists

Question 7

How to clear a set in Python

Answer 7

set.clear()

Question 8

How to determine if a graph is a valid tree?

Answer 8

• All nodes should be connected in some way

- Only one path connecting any 2 nodes (no cycles)

Question 9

How to get union of a set

Ex. get {1,4,6,7} from {1,4} + {6,7}

Answer 9

A | B

Question 10

How to get absolute value in Python

Answer 10

abs()

Question 11

Give a high-level description of Kruskal’s algorithm to get the minimum spanning tree

Answer 11

1. Create a new UnionFind() for all points
2. Get the list of all possible edges for the points, and sort by weight of an edge ascending.
3. For each edge, check if connected points are already connected in UF. Skip if so.
4. If not, that edge (weight) is included, and connect the points

Question 12

How to construct a heap in Python

Answer 12

import heapq

heapWithValues = [3,1,2]
heapq.heapify(heapWithValues)

Question 13

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?

Answer 13

A heap

Question 14

Time complexity of insertion, deletion, getMax/getMin of a heap?

Answer 14

O(log N), O(log N), O(1)

Question 15

Time complexity to convert data to a heap using Heapify

Answer 15

O(N)

Question 16

How to get the K largest/smallest elements from a collection of data?

Answer 16

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)

Question 17

How to find the Kth largest/smallest element in a collection of data?

Answer 17

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)

Question 18

Python code for finding Kth largest element in array

Answer 18

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]

Question 19

What needs to be done to create and use a max heap in Python (heapq) ?

Answer 19

Every value added or removed (popped) needs to be multiplied by -1

Question 20

What’s the sort mechanism when sorting a list of lists/tuples in Python?

Answer 20

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

Question 21

How to remove an element from a Python list by index?

Answer 21

a = [1, 2, 3, 4]
del a[1]
# a = [1, 3, 4]

Question 22

How to insert a value at beginning of List in Python

Answer 22

arr = [2, 3, 4]
arr.insert(0, 5)
// arr = [5, 2, 3, 4]

Question 23

How to sum two positive numbers using bitwise operations?

Answer 23

x ^ y is the answer without the “carry”
(x & y) &laquo_space;1 is the carry
Keep summing the above two in a loop until carry = 0

Question 24

How to find difference of two positive numbers using bitwise operations?

Answer 24

x ^ y Is the answer without the “borrow”
((~x) & y) &laquo_space;1 is the borrow
Keep summing the above two in a loop until borrow = 0

Question 25

How to zero out the least significant ‘1’ bit of an int?

Answer 25

x & (x - 1)

Question 26

How to find index of substring in string?

Answer 26

str.index(substr)

Question 27

What’s the built-in Python tool for memoization?

Answer 27

from functors import lru_cache

@lru_cache
def myFunc(…):
…

Question 28

What’s the problem with using @lru_cache with a function with lists as input?

Answer 28

Lists are unhashable, so this will fail.

Need to use tuples instead as a potential option

Question 29

How to create a list with first n numbers in Python?

Answer 29

list(range(1, n))

Question 30

How to initialize 2D array of zeros in Python?

Answer 30

zeros = [ [0] * cols for _ in range(rows)]

Question 31

How to join strings in Python with separator

Answer 31

strs = [“hello”,”world”]
separator = “.”
separator.join(x for x in strs)

Question 32

What can happen to mutable objects (sets, lists, dicts, etc.) when passed as an arg to a function in Python?

Answer 32

The original reference is passed as argument, and can be changed by the function