Verkada Inc.·Frontend Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Verkada frontend interview had at least one algorithmic problem, which surprised me a bit for a frontend role. The coin change problem is a classic but it still requires you to actually know your DP fundamentals cold.

Questions Asked (1)

Given an array of coin denominations and a target amount, return the minimum number of coins needed to reach that amount. Return -1 if it's not possible. You have unlimited coins of each denomination.

Algorithms & Data Structures

Author's notes

Knew this one but still fumbled the initialization step for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints (e.g., coin denominations positive, target non-negative) and discuss the dynamic programming approach. Explain that you'll use a DP array where dp[i] represents the minimum coins to make amount i, initialized to infinity except dp[0]=0, and iterate through amounts and coins to fill it. Finally, analyze time and space complexity and consider edge cases.

Pro tip: Mention that while the DP solution is standard, you can optimize space by using a 1D array and that for certain coin systems a greedy approach works, but it's not guaranteed for all denominations. This shows depth of understanding.

1. Clarify the problem

Ask about constraints: coin denominations (positive integers?), target amount (non-negative?), and whether the order of coins matters. Confirm that unlimited coins of each denomination are available.

2. Discuss approaches

Mention brute force (exponential), greedy (not always optimal), and dynamic programming (optimal). Explain why DP is suitable: overlapping subproblems and optimal substructure.

3. Define DP state and transition

Define dp[i] as the minimum coins to make amount i. Initialize dp[0]=0 and others to infinity. For each amount i from 1 to target, and for each coin c, if i>=c, dp[i] = min(dp[i], dp[i-c]+1).

4. Implement and handle edge cases

Code the DP iteratively. After filling, return dp[target] if it's not infinity, else -1. Handle edge cases: target=0 returns 0, empty coins array returns -1 for target>0.

5. Analyze complexity and test

Time complexity O(target * number of coins), space O(target). Walk through a small example to verify. Mention potential optimizations like early termination if dp[target] is found.

Key Points to Mention

Dynamic programming approach with optimal substructure and overlapping subproblems
State definition: dp[i] = min coins for amount i
Transition: dp[i] = min(dp[i], dp[i - coin] + 1) for each coin
Initialization: dp[0] = 0, others = infinity
Return -1 if dp[target] remains infinity
Time and space complexity analysis: O(target * coins) time, O(target) space

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.