Software Engineer Interview Questions

Daniel Wilson - 16 Apr 2024

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 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?"

Describe a time you received feedback. How did you respond to that feedback?

Describe a time you experienced a conflict with someone. How was it resolved?

Describe a bad mistake (taking down production etc). How was it remedied? What did you do to make sure it didn't happen again.

There is an issue with a delivery system and missing items (store didn't have it, deliverer forgot it, it was never added to the order). How you would go about solving this issue?