← Fuse Energy Interview Insights

Fuse Energy·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Fuse Energy had me extend a previous mini-spreadsheet problem by adding cycle detection to SUM formula assignments. Pretty focused technical session, no fluff.

Questions Asked (1)

Q1

You have a spreadsheet that supports Set, Get, and SUM operations. Now extend it so that assigning a SUM formula to a cell raises an error if it would create a circular dependency, either direct or through a chain of references.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

This is a follow-up to the base spreadsheet problem so if you haven't already built the dependency graph in the first part, you're starting behind.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the spreadsheet as a directed graph where cells are nodes and formula references are edges. To detect cycles, perform a depth-first search (DFS) from the target cell before adding the new dependency, checking if it can reach itself. If a cycle is found, reject the assignment; otherwise, update the graph and recompute values as needed.

Pro tip: Mention that cycle detection should be efficient and not block the UI; consider incremental checks or caching to avoid full graph traversals on every edit. Also, discuss how to handle error propagation and recovery when a cycle is detected.

1. Clarify requirements and assumptions

Confirm the scope: only SUM formulas, direct and indirect cycles, and whether other operations (Set, Get) need modification. Ask about performance expectations and error handling.

2. Model dependencies as a graph

Represent each cell as a node and each reference in a formula as a directed edge. For SUM, the cell depends on all cells in the range.

3. Detect cycles before assignment

Use DFS or topological sort to check if adding the new edges would create a cycle. If a cycle is detected, raise an error and do not update the cell.

4. Update and recompute

If no cycle, update the graph and recompute the affected cells' values, ensuring consistency and propagating changes efficiently.

5. Discuss trade-offs and optimizations

Talk about time/space complexity, incremental vs. full recomputation, and potential optimizations like memoization or lazy evaluation.

Key Points to Mention

  • Directed graph representation of cell dependencies
  • Cycle detection algorithms: DFS with recursion stack, topological sort (Kahn's algorithm)
  • Handling ranges in SUM: dependencies on multiple cells
  • Error handling: raising exceptions, rolling back changes, user feedback
  • Performance considerations: incremental updates, caching, avoiding full graph scans
  • Testing edge cases: self-reference, indirect cycles, large ranges

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