# Software Engineer Interview Questions

I intend to keep this as a reference of all the interview questions I have experienced in my career.

## Coding Challenges

These challenges are often posed in a live coding environment like coderpad. Often they can be found with a large test suite on leetcode or hackerrank.

### Maximum Profit in Job Scheduling

https://leetcode.com/problems/maximum-profit-in-job-scheduling/description

**Naive Solution - Recursion**

Base Case - No more future jobs, return current profit

Recursive case - Return the max of two calls:

- Including the current job profit in the call and finding the next schedulable job
- Excluding the current job and call with the next starting job

First call this function on the first job with 0 profit.

**Better Solution - Dynamic Programming**

Keep an array of the maximum possible profit at index X of the jobs array sorted by end_time

- Sorting by end_time lets us use our DP array to track maximum possible profit at that jobs end time.

Write a loop through the 1…end of the jobs sorted by end_time and set the maximum profit at the current jobs end_time to be the max of:

- (include the job) current job profit + possible previous profit
- (exclude the job) max profit of the job before

possible previous profit is found by finding the latest job ending at or before the start time of the job we are currently looking at.

Max profit of the job before just means dp[x - 1]

```
# @param {Integer[]} start_time
# @param {Integer[]} end_time
# @param {Integer[]} profit
# @return {Integer}
def job_scheduling(start_times, end_times, profits)
# combine data and sort by end_time
jobs = start_times.map.with_index{|st, i| [st, end_times[i], profits[i]]}.sort{|a, b| a[1] <=> b[1]}
start_times = jobs.map{|x| x[0]}
end_times = jobs.map{|x| x[1]}
profits = jobs.map{|x| x[2]}
# initialize
sorted_end_times_to_inputs = end_times.map.with_index{|e, i| [e, i]}
max_profits = [0] * start_times.length
max_profits[0] = profits[0]
# dp loop
(1...(start_times.length)).to_a.each do |job_index|
previous_job_index = latest_possible_previous_job(job_index, start_times[job_index], sorted_end_times_to_inputs)
previous_max = previous_job_index != nil ? max_profits[previous_job_index] : 0
# set max profits to max of include and exclude
max_profits[job_index] = [
profits[job_index] + previous_max, # include + max before chosen
max_profits[job_index - 1] # don't include
].max
end
max_profits.last
end
def latest_possible_previous_job(index, start_time, sorted_end_times_to_inputs)
# puts sorted_end_times_to_inputs.reverse.map{|s| s[0]}.join(" ")
i = sorted_end_times_to_inputs[0, index + 1].reverse.bsearch{|end_time| end_time[0] <= start_time}
return nil if i == nil
# puts "index: #{index}, start_time: #{start_time}, output: #{i[1]}"
return i[1]
end
```

### Minimum path sum in a 2d grid

**Solution: Dynamic Programming**

min sum path of a square is the minimum of the two square to the up and left of it. Iterate through all squares computing the min sum path for each. O(squares)

```
# @param {Integer[][]} grid
# @return {Integer}
def min_path_sum(grid)
# initialize
max_sum_dp = [[0] * grid[0].length] * grid.length
max_sum_dp[0][0] = grid[0][0]
# dp loop
(1...(grid.length * grid[0].length)).to_a.each do |i|
x = i % grid[0].length
y = i / grid[0].length
up_val = y > 0 ? max_sum_dp[y - 1][x] : nil # up
left_val = x > 0 ? max_sum_dp[y][x - 1] : nil # left
max_sum_dp[y][x] = [
up_val,
left_val
].filter{|v| v != nil}.min + grid[y][x]
end
max_sum_dp.last.last
end
```

### Question 3 - Implement serialization/deserialization for a tree data structure.

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Rather Tough: BFS to serialize pushing output into array

Deserialize by doing BFS and lookups into the array

```
# TODO
```

**Followup: Do the problem with N-ary trees**

### Question 4 - Given a restaurant name, find other restaurants in the list that are k-anagrams with each other.

A name is a k-anagram with another name if both the conditions below are true: The names contain the same number of characters. The names can be turned into anagrams by changing at most k characters in the string For example: name = "grammar", k = 3 and list = ["anagram"], "grammar" is k-anagram with "anagram" since they contain the same number of characters and you can change 'r' to 'n' and 'm' to 'a'. name = "omega grill", k = 2 and list = ["jmega frill"], "omega grill" is k-anagram with "jmega frill" since they contain same number of characters and you can change 'o' to 'j' and 'g' to 'f’

**Solution:**

```
def get_char_map(str)
char_count = {}
name.chars.each{|c| char_count[c] = (char_count[c] || 0) + 1}
char_count
end
def k_anagrams_in_list(name, k, list)
# find names in list with same # of chars
same_len_names = list.filter{|n| n.length == name.length}
# process some name data
char_count = get_char_map(name)
name_set = Set(name.chars)
# find k-anagrams
same_len_names.filter{|n|
diff = 0
candidate_count = get_char_map(n)
name_set.each{|c|
diff += (char_count[c] - (candidate_count[c] || 0)
if (diff > k)
break
end
}
return diff <= k
}
end
```

### Question 5 - Binary Tree Maximum Path Sum

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Solution is to use a recursive helper function that does the following

- Base Case: Node nil? return 0
- Compute the max path at current node
- max (0, left side recursive call) + max (0, right side recursive call) + node.val

- Compare against global maximum (this might be the root node of our max path)
- Return the sum of the greatest path connecting current node to parent
- max (left_side + node.val, right_side + node.val)

Call the recursive function on the root node and your global max will be updated to the max path value.

```
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val = 0, left = nil, right = nil)
# @val = val
# @left = left
# @right = right
# end
# end
# @param {TreeNode} root
# @return {Integer}
def max_path_sum(root)
# ruby hack to pass by reference
data_hash = { 'max' => root.val }
max_path_subtree(root, data_hash)
data_hash['max']
end
def max_path_subtree(node, data_hash)
if node == nil
return 0
end
# calculate max sum at node
left_sum = [0, max_path_subtree(node.left, data_hash)].max
right_sum = [0, max_path_subtree(node.right, data_hash)].max
sum = left_sum + right_sum + node.val
# update global max
data_hash['max'] = [data_hash['max'], sum].max
# return max path that connects node to parent
return [left_sum + node.val, right_sum + node.val].max
end
```

### Min Time Path

There is an **n **x **n** map where grid[i][j] represents the number of obstacles in the position (i, j). In every unit of time, the number of obstacles in every position will be decreased by one. Every position with one or more obstacles is not accessible.

Assume you are a dasher at DoorDash. You can drive from one position to another 4-directionally adjacent position (up/down/left/right) if and only if the position is accessible. You will start at the top left position (0, 0) and your goal is to reach the bottom right position (n-1, n-1). Assuming you can drive infinite distances in zero time, what would be the least time that you can reach the destination?

```
# Example
# 0 1 2 3 4
# 24 16 22 21 5
# 12 13 14 15 23
# 11 17 18 19 20
# 10 9 8 7 6
# Input: grid = [[0,1,2,3,4],[24,16,22,21,5],[12,13,14,15,23],[11,17,18,19,20],[10,9,8,7,6]]
# Correct Path: 0, 1, 16, 13, 12, 11, 10, 9, 8, 7, 6
# Output: 16
```

Since you can instantly move along the first path that opens to the end spot on the grid, the problem can be better understood as finding the path with the smallest maximum value of the individual spaces. When this maximum value of time passes this path opens up and we can instantly move to the finish.

This is accomplished by doing priority BFS from our start node. Since our queue of spots to visit will be sorted in increasing order, we can keep one rolling maximum of the highest value seen yet along our search. Once we've hit our finish grid, this rolling maximum will be the highest value seen yet on a path from the start to the finish.

```
require 'set'
def min_time_path(grid)
seen = Set[[0, 0]]
# BFS using priority queue by value
queue = [[grid[0][0], 0, 0]]
max = grid[0][0]
while !queue.empty?
val, x, y = *queue.shift
max = [max, val].max
# Are we at the bottom right?
if grid[y][x] == grid.last.last
return max
end
# Add unseen neighbors to queue
unseen_neighbors = get_unseen_neighbors(seen, x, y, grid)
unseen_neighbors.each do |neighbor|
n_x, n_y = *neighbor
seen.add([n_x, n_y])
n_val = grid[n_x][n_y]
index = queue.bsearch_index{|item| item[0] >= n_val }
if index == nil
queue += [[n_val, n_x, n_y]]
else
queue.insert(index, [n_val, n_x, n_y])
end
end
end
end
def get_unseen_neighbors(seen, x, y, grid)
[[x - 1, y], [x + 1, y], [x, y + 1], [x, y - 1]].filter{ |x, y|
!seen.include?([x, y]) && inbounds(x, y, grid.length)
}
end
def inbounds(x, y, boundary)
x >= 0 && x < boundary && y >= 0 && y < boundary
end
```

## System Design Problems

These problems are usually discussed with an engineer. Interviewers are looking for candidates to challenge assumptions, refine system requirements, and explain tradeoffs when making system design decisions.

### Design a 3-day Promotional Event

Say if DoorDash along with other partners across US is sponsoring for 3-day charity event where huge participation of more than 3 million customers are expected to participate and simply donate money. You were responsible to design an app for this. How would you go about it?

### Design an Image File Sharing Service

Design a system where users can log in, upload photos, and create albums.

### Design a Task Scheduler system

Design a distributes scheduler-as-a-service. The schedule exposes an API to schedule tasks based on a cron format (can be one-off or periodic tasks). The tasks are described in the form of a REST call (URL, method, body) to a service endpoint that will ultimately execute the logic. The schedule will not have single points of failure and will be highly scalable (should be able to execute hundreds of millions of tasks per day).

## Behavioral Questions

These questions are often posed to get a data point on how a candidate deals with cross-functional collaboration and how they communicate. It's a good practice to memorize a few technical highlights from your career to draw on when answering these questions

### Describe a project that you think went very well...

*Follow up: "How could it have gone even better?"*