Duolingo Intern Software Engineer Interview Experience — Karat Screen With Three Verbal Q&As and a Grid DFS Problem

I just finished the Duolingo Karat SWE Intern interview, so here is my writeup.

Format: the first 10 minutes are 3 Q&A questions on algorithms and complexity analysis. No code to write, you just answer out loud. The remaining 45 minutes are one coding problem in Karat Studio, and you can pick your own language. You get one redo. It was basically the exact same problem that had already been posted on the forum.

Q&A (3 questions):

1. Reverse Array In-place: you loop over the whole array and swap each position with its mirror position. Does this reverse the array correctly? The answer is no, because every pair gets swapped twice and the array ends up back as it started. You only need to loop over the first half. Time O(n), Space O(1).
2. Top N Matches: a dating app has P users, and you are given an O(1) get_match function. Find the N best matches for a given person, where N is much smaller than P. Use a min heap of size N. Time O(P log N), Space O(N).
3. Binary Tree Sum: recursively compute the sum of all node values in a binary tree, then give the time and space complexity. Time O(n), Space O(h). For a balanced tree that is O(log n), and in the worst case it degenerates into a linked list and becomes O(n).

Coding (DFS):

You are given a 2D height matrix. You can start from any cell. At each step you look at the 8 surrounding directions, and you may only move to a cell that is strictly higher than the current one, and you must pick the highest one among them. If several neighbors tie for highest, prefer the smaller row, then the smaller column. If there is no higher neighbor, you stop.

You need to return how many starting positions end up reaching the global highest point of the whole matrix. If there are several global highest points, reaching any one of them counts.

The solution is to first scan the matrix to find the global maximum, then run a DFS from every cell that simulates the movement rule. Use memoization to cache whether each cell eventually reaches the global highest point, so nothing is computed twice. Since the heights are strictly increasing along a path, there can't be any cycles. Time O(R x C), Space O(R x C).