← Verkada Interview Insights

Verkada·Frontend Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026

Summary

Interviewed for a frontend role at Verkada and got a classic DP problem. Nothing too surprising but it's the kind of question where you either know the pattern or you're fumbling through it live.

Questions Asked (1)

Q1

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 type.

Algorithms & Data Structures
Author's notes

Went with bottom-up DP.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then explain that this is a classic dynamic programming problem (coin change) where you build up solutions for smaller amounts. Present the bottom-up DP approach with O(amount * coins) time and O(amount) space, and walk through a small example to demonstrate correctness.

Pro tip: Mention that while a greedy approach works for some coin systems, it fails for arbitrary denominations (e.g., coins [1,3,4] and amount 6), so DP is necessary. Also, discuss how you'd optimize for frontend use cases, such as memoization for repeated calls or using a Web Worker for heavy computations to avoid blocking the UI.

1. Clarify requirements and edge cases

Ask about input constraints (e.g., array size, amount range, coin denominations) and edge cases like amount=0, empty coins array, or impossible amounts. Confirm that coins can be used unlimited times.

2. Identify the algorithmic pattern

Recognize this as the coin change problem, a classic dynamic programming problem. Explain why greedy fails and why DP is needed to consider all combinations.

3. Define the DP state and recurrence

Let dp[i] be the minimum coins to make amount i. Initialize dp[0]=0 and dp[i]=Infinity for i>0. For each coin, update dp[i] = min(dp[i], dp[i-coin]+1) for i from coin to amount.

4. Implement and analyze complexity

Write clean code (e.g., in JavaScript) using a 1D array. Analyze time complexity O(amount * number of coins) and space complexity O(amount).

5. Test with examples and discuss optimizations

Walk through a small example (e.g., coins=[1,2,5], amount=11) to verify. Mention possible optimizations like early termination or using BFS for unweighted graphs, and how to handle large amounts in a frontend context.

Key Points to Mention

  • Dynamic programming approach with optimal substructure and overlapping subproblems
  • Why greedy algorithm fails for arbitrary coin denominations
  • Time and space complexity analysis (O(amount * coins) time, O(amount) space)
  • Edge cases: amount=0, empty coins array, impossible amounts (return -1)
  • Potential frontend considerations: memoization for repeated calls, Web Workers for heavy computation
  • Alternative approaches like BFS (for unweighted graph) and their trade-offs

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