My Mixed feelings about coding interview
These days, coding interviews are like security checks before getting into big companies, and they are getting more and more competitive. It is not uncommon to hear someone fail coding rounds multiple times before he/she could eventually land in a halfway decent job. Leetcode used to only have 300 questions, but now it's a whopping 2400. I actually got dinged twice as well in the beginning of 2021, which is why I am here rethinking what I should do about this trend no matter it's for good or bad.
I heard a lot of people (usually mid-senior level), of course, these are usually the losers of this coding game, argue coding interviews are not reflective of the person's actual capability. However, in the market driven economy, coding interview is a proven efficient way to screen people. As I was sitting across the table on the interview table back when I was working for Bosch, I understand the pain of not being able to select between a bunch of qualified candidates. A coding round would serve like an efficient weeder to weed out the "less proficient" candidates. Sometimes, as an interviewer, you cannot help but to feel a weird sense of achievement by crushing someone else's ego.
The real question is how should we navigate given that the market is already like this? Coding interview skills are a little different from actual coding skills, since it is all about algorithms. In my years of experience of doing ML research, I never actually needed to use heap or any fancy data structures to process my data. Whereas at a coding prep site, there's almost 1 in 5 chance that you can stumble upon on a heap question. Should I complain? Should I just keep doing research and publish papers and stay in academia? or should I get on the train and do leetcode as well?
I guess I am more of a realistic person and my answer is to tackle the leetcode questions with a clear structure of what I am doing, and try to rebuild a stronger algorithmic foundation throughout this process. ML or stats or math skills are like the 'devil fruit' power, but coding skills, at the end of the day, are still the basic combat power to rely on in this rapidly-evolving tech world.
I am taking my baby steps.P.S. updated 8-22-2021, 2-18-2022, 4-28-2022, 10-22-2022, 4-22-2023, 1-17-2024:
After doing LeetCode for 2+ year or so, I have several important epiphonies:
Array:
Array Questions are prevalent but could be combined with other categories Array questions I practiced
Stack:
Stack questions on leetcode is not very intuitive. The questions, if not thought through carefully, can easily fool you into O(n^2) solutions. The correct answers are most of times O(n). Stack questions I practiced
while loop within the for loop that goes
through the input.
Heap:
Heap questions are intrinsically more challenging. Leetcode lists almost all the heap questions above medium difficulty. But once you get used to them, everything would look very similar to you. Especially, once you are familiar with the idea of keeping priority queue in 2D heap and how to use 2 heaps to tackle a moving stream of data, all other heap questions would be similar derivative or variant questions. Heap questions I practiced
Tree:
Tree questions are mostly revolving around BST(Binary Search Trees), and to grasp BST well, I really think the best way is to go back and read CLRS thoroughly and understand every bit they say about BSTs. Tree questions I practiced
Matrix related:
Matrix questions are somehow related and they share lots of similarities. Matrix questions I practiced
Graph:
Graph questions are involved, but I feel once I know the pattern, it's a lot more within control
def isBipartite(self, graph: List[List[int]]) -> bool:
length = len(graph)
parent = [i for i in range(length)]
def find(x):
if x!=parent[x]:
parent[x]=find(parent[x]) #rank compression
return parent[x]
def union(x,y): # union by rank can balance the tree
#whichever is taller tree will dominate
px,py=find(x),find(y)
if px!=py:
parent[px]=py
for i in range(length):
pari=find(i)
for j in graph[i]:
#check connected or not
if find(j)==pari:
return False
union(graph[i][0],j)
return True
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return node
queue = [node]
seen = {}
seen[node] = Node(node.val, [])
while queue:
curr_node = queue.pop(0)
for neighbor in curr_node.neighbors:
if neighbor not in seen:
seen[neighbor] = Node(neighbor.val, [])
queue.append(neighbor)
seen[curr_node].neighbors.append(seen[neighbor])
return seen[node]
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
dfs_stack = [root]
self._add_all_left_nodes(root, dfs_stack)
prev_val = dfs_stack[-1].val - 1 # could use math.min as well
while len(dfs_stack) > 0:
node = dfs_stack.pop()
if prev_val < node.val:
prev_val = node.val
else:
return False
if node.right is not None:
dfs_stack.append(node.right)
self._add_all_left_nodes(node.right, dfs_stack)
return True
def _add_all_left_nodes(self, node, s):
while node.left is not None:
s.append(node.left)
node = node.left
Dynamic Programming:
Base Case; Transition function; How to think about breaking a problem down to subproblems. After doing quite a few of them, I found that starting with recursion is usually the easiest, then adding memoization is not difficult, and finally coming up with tabular dp will be natural. The core is to pin down the state-transition function as early as possible. DP questions I practiced
Backtrack:
Backtracking is a tricky categrory, but could be solved using a template, 1.Subsets 2. Subsets II 3.Permutations 4. Permutations II 5. Combinations 6. Combination Sum II 7. Combination Sum III 8. Palindrome Partition Backtrack questions I practiced
def backtrack(candidate):
if find_solution(candidate):
output(candidate)
return
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)
Comments
Want to leave a comment? Visit this post's issue page on GitHub (you'll need a GitHub account).