Recursive Task Worker with Memoization
Updated
Problem statement
Implement a worker that evaluates tasks with dependencies and reuses computed results.
[0, value]: a Number task returns value.[1, left, right]: an Add task returns the sum of the tasks at indices left and right.[2, n]: a Fib task returns F(n), where F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2).
Evaluate only the task at root and the dependencies it needs. Return its exact integer result as a decimal string. Results can exceed 64-bit integers; for example, F(100)=354224848179261915075.
Memoize task results. Fib dependencies should be created or evaluated only when needed, and Fibonacci results should be shared by n across distinct Fib tasks. The list above represents the task objects and references used in this exercise.
Function
evaluateTask(tasks: int[][], root: int) → StringExamples
Example 1
tasks = [[0,7],[0,8],[1,0,1]]root = 2return = "15"The Number tasks return 7 and 8. Add combines them to return the exact string "15".
Example 2
tasks = [[2,100],[2,100],[1,0,1]]root = 2return = "708449696358523830150"Both Fib tasks return 354224848179261915075. Add returns "708449696358523830150"; the Fibonacci values can be reused across both tasks.
Constraints
- 1 <= tasks.length <= 1000
- 0 <= root < tasks.length
- A Number task is [0, value], with 0 <= value <= 1000000000.
- An Add task is [1, left, right], and both referenced task indices are smaller than its own index.
- A Fib task is [2, n], with 0 <= n <= 1000.
- Each task has 2 or 3 integer fields.
More Citadel Onsite Interview questions
- Maximize Workday EarningsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Changes for Palindromic BlocksOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Removal PoolONSITE INTERVIEW · Seen Sep 2026
- Centered K-by-K Submatrix SumsONSITE INTERVIEW · Seen Aug 2026
- Search Suggestions with a Prefix TreeONSITE INTERVIEW · Seen Aug 2026
- Traverse Interior Matrix Cells in Row-Major OrderONSITE INTERVIEW · Seen Aug 2026
- Time-Based Key-Value StorePHONE SCREEN · ONSITE INTERVIEW · Seen Feb 2026
- 2048 Simulation and Board CodecONSITE INTERVIEW · Seen Jan 2026
- Cancellable Priority Task QueueONSITE INTERVIEW · Seen Jan 2026
- Dynamic Weighted SamplingONSITE INTERVIEW · Seen Jan 2026
Similar questions at other companies
- Count Complete Tic-Tac-Toe GamesDecagon · PHONE SCREEN · ONSITE INTERVIEWDecagon interview questions
- Scramble StringExpedia · ONSITE INTERVIEWExpedia interview questions
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Flatten a Multilevel Doubly Linked ListBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Wildcard Pattern MatchingMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Every Result of Grouping an ExpressionC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Binary Tree Maximum Path SumGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Fibonacci NumberJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- Fibonacci with Input ValidationMorgan Stanley · ONSITE INTERVIEWMorgan Stanley interview questions
- Maximum Subarray SumStraive · OA