#recursion

69 recursion interview questions, asked at Google, Amazon, Meta and 21 more companies. Last asked Oct 2026.

Merge two config trees with per-node merge rulesCodingTwo configuration files have been parsed from YAML into trees of dicts, lists and plain values: a base and an overlay. Merge the overlay into the base. Each node can carry its own…
Last asked Oct 2026
+3
In-memory file system with files and foldersCodingImplement an in-memory file system with path-based file and folder access, plus follow-ups on per-directory limits, duplicate names and identical contents. Covers the bank's vault…
Last asked Oct 2026
Parse message definitions and compute their sizesCodingParse text definitions of message types made of typed fields, where a field can be another message type. Report each field's type and each message's total size from given…
Last asked Sep 2026
Binary search tree keys within a rangeCodingGiven a binary search tree (as a level-order list with nulls for missing children) and an inclusive range low, high, return every key in the range in ascending order. Skip the…
Last asked Sep 2026
Toy language type inference with generics and tuplesCodingA small typed language has three kinds of type: - Primitives: int, float, char. - Generics: placeholders named T followed by a number (T1, T2, ...). A generic can stand for any…
Last asked Sep 2026
Delete leaves with a target value, repeatedlyCodingGiven a binary tree and a target value, delete every leaf that holds the target. If that turns its parent into a leaf holding the target, delete the parent as well, and keep going…
Last asked Sep 2026
Render nested JSON in a code-style viewerCodingBuild a React component that displays a given JSON object the way a code editor would: indentation, braces and brackets, keys and values styled by type, and nested objects and…
Last asked Sep 2026
Range sum of a binary search treeCodingGiven a binary search tree and two bounds low and high, return the sum of the values within the inclusive range, skipping subtrees that cannot contain any. Follow-up: answer many…
Last asked Sep 2026
+1
Lowest common ancestor of a binary treeCodingGiven a binary tree (no ordering on the values) and two of its nodes, return their lowest common ancestor: the deepest node that has both in its subtree.
Last asked Sep 2026
Path between two nodes of an implicit Fibonacci treeCodingA Fibonacci tree of order k is a binary tree defined recursively: - Orders 0 and 1 are a single node. - For k = 2, the root's left subtree is a Fibonacci tree of order k - 2 and…
Last asked Sep 2026
Parse a custom record format with mapped fieldsCodingParse records written in a custom text format: a few fixed comma-separated fields first (for example a machine code, a timestamp and two coded fields), then a free-form section of…
Last asked Sep 2026
Filter an n-ary tree by substring and render it indentedCodingEach node of an n-ary tree has a string value and a list of children. 1. Given a search string, return the filtered tree: keep every node whose value contains the substring, plus…
Last asked Sep 2026
+2
Insert plus, times and parentheses to reach a targetCodingYou are given an equation whose left side is a sequence of non-negative integers with no operators between them, and whose right side is a target. For example: 2 3 4 = 20. Insert…
Last asked Sep 2026
Flatten a linked list with side branches into one doubly linked listCodingEach node of a singly linked list has a forward link and may also have one side branch: a link to the head of another list, whose nodes may have side branches of their own…
Last asked Sep 2026
Expand placeholders from a variable storeCodingImplement a small store of variables, like the export NAME="Tom" lines of a shell startup file. Any string can refer to a variable as %NAME%; expanding the string replaces each…
Last asked Sep 2026
Simplify an arithmetic expression treeCodingYou get the root of an expression tree: every internal node is a binary operator with two children, and every leaf is an integer constant or a variable name. Return a simplified…
Last asked Sep 2026
Compute entity sizes and validate a hierarchical file systemCodingFiles and folders form a hierarchy. Compute the size of any entity, where a folder's size is the total of everything inside it, and validate the hierarchy: check that it really is…
Last asked Aug 2026
Format a forest of nested commentsCodingGiven comments where each one may reply to another, format the whole forest of threads so that every reply appears nested under its parent.
Last asked Aug 2026
Print each tree node's level and whether it is balancedCodingGiven a tree, walk it with a depth-first search and report, for every node, its level and whether the subtree under it is balanced (by the definition the interviewer gives, such…
Last asked Aug 2026
Nested list weight sum, parsed from a stringCodingA nested list holds integers and other lists. Return the sum of every integer multiplied by its depth, where the outermost list is depth 1. One version hands you the nested list…
Last asked Aug 2026
One-pass S-expression parser with error reportingCodingWrite a parser for a small S-expression language that reads the input character by character in a single left-to-right pass; splitting the whole string up front is not allowed. It…
Last asked Aug 2026
+1
Minimum root-to-leaf path sumCodingGiven the root of a binary tree whose nodes hold integers (values may be negative), find the root-to-leaf path with the smallest sum. A leaf is a node with no children. A…
Last asked Aug 2026
Serialize and deserialize an N-ary treeCodingDesign a string format for a rooted tree in which each node has any number of children in a fixed order. Implement serialize(root) and deserialize(data) so that decoding gives…
Last asked Jul 2026
Accessible expand-and-collapse tree in ReactCodingBuild a React component that renders nested data as a tree where each node can be expanded or collapsed, to any depth. Render it recursively, keep the expanded state sensibly, and…
Last asked Jul 2026
Regular expression matchingCodingDecide whether a whole string matches a pattern where . matches any single character and matches zero or more of the element before it.
Last asked Jul 2026
Build a quadtreeCodingA quadtree splits a 2D region into four quadrants, recursively: every node is either a leaf or has exactly four children. Build one yourself. One version builds it from a square…
Last asked Jun 2026
Deep equality of two recordsCodingWrite a function that decides whether two records are deeply equal: the same keys, with values that are equal all the way down through nested maps and lists. Agree with the…
Last asked Jun 2026
Lowest common ancestor in a BST and in a binary treeCodingGiven two nodes, return their lowest common ancestor first in a binary search tree, using the ordering, and then in a plain binary tree where you cannot rely on it. Explain both…
Last asked Jun 2026
Kth largest perfect binary subtreeCodingIn a binary tree, find every subtree that is a perfect binary tree and return the size of the kth largest.
Last asked Jun 2026
Every ordered sum of 1s and 2s that makes nCodingGiven n, list every ordered sequence of 1s and 2s that adds up to n (so 1+2 and 2+1 are different), and say how many there are.
Last asked Jun 2026
Implement a JSON parserCodingWrite a parser that turns a JSON string into native values: objects, arrays, strings with escapes, numbers, true, false and null. Use a recursive-descent design, skip whitespace…
Last asked Jun 2026
+1
Evaluate nested add and sub expressionsCodingImplement evaluate(expression: str) - int, which evaluates a string written in a small function-call language. An expression is either: - an integer literal, possibly negative…
Last asked Jun 2026
+1
Diameter of a binary treeCodingReturn the number of edges on the longest path between any two nodes of a binary tree. The path need not pass through the root. Solve it in one pass.
Last asked May 2026
Merge two named treesCodingEach tree node is a dictionary with a name, an integer value and an ordered list of children. Given two such trees t1 and t2, build a new merged tree that follows t1's nodes and…
Last asked May 2026
Knockout tournament by rank, then build the bracketCodingPlayers are listed by rank, where a smaller number is a better player. Neighbours play each other (index 0 against 1, 2 against 3, and so on) and the better rank advances, round…
Last asked May 2026
Validate a parsed config against field descriptorsCodingGiven a parsed YAML or JSON document and a set of message descriptors that list each field's type and whether it is required or repeated, report every invalid field with the…
Last asked Apr 2026
Flatten a nested list iteratorCodingA list holds integers and other lists, nested to any depth. Write an iterator with next() and hasnext() that returns the integers in order. Do it lazily with a stack of positions…
Last asked Apr 2026
Validate a binary search treeCodingDecide whether a binary tree is a valid binary search tree.
Last asked Apr 2026
Implement pow(x, n)CodingCompute x raised to an integer power n (which may be negative) in O(log n) multiplications by squaring, rather than multiplying n times. Handle n = 0, negative exponents and…
Last asked Apr 2026
Is every 3+ letter piece of a string a dictionary word?Coding1. Given a string and a dictionary, return true when every piece of the string of length 3 or more is a valid word. (The report says subsequences; confirm with the interviewer…
Last asked Mar 2026
Tower of Hanoi movesCodingPrint or return every move that transfers n disks from the first peg to the third, using the middle peg, never placing a larger disk on a smaller one. Write the recursive solution…
Last asked Mar 2026
Generate all permutationsCodingReturn every ordering of a list of distinct numbers using backtracking. Follow-ups may include input with duplicates (skip repeats) and the time cost. In the reported round a…
Last asked Mar 2026
Flatten and rebuild nested Python containersCodingGiven an arbitrarily nested mix of lists, tuples and dicts with integer leaves, produce a flat list of the integers in order. Then, given the original structure and a new flat…
Last asked Mar 2026
Serialize an expression tree with the fewest parenthesesCodingGiven a binary expression tree of numbers and operators, print it as an infix expression using only the parentheses that precedence and associativity require (for example, keep…
Last asked Feb 2026
Nested list weight sumCodingA nested list holds integers and other nested lists. Return the sum of every integer multiplied by its depth (integers in the outer list have depth 1).
Last asked Feb 2026
Decode a string with nested repeat countsCodingAn encoded string uses k... to mean the bracketed part repeated k times, and brackets may nest, for example 3a2c decodes to accaccacc. Return the decoded string. Use a stack or…
Last asked Feb 2026
Settle group debts with the fewest transfersCodingA group of people owe each other money, given as transfers (from, to, amount). Return the smallest number of transfers that brings every person's balance to zero.
Last asked Feb 2026
Maximum path sum in an N-ary treeCodingEach node of an N-ary tree holds an integer. A path joins any two nodes through parent and child links and visits each node at most once. Return the largest path sum. Unlike the…
Last asked Jan 2026
Winner of a stack-merging gameCodingTwo players take turns merging stacks according to the game's rules until no move is left. Given the starting stacks, decide which player wins if both play optimally. Start with a…
Last asked Jan 2026
All subsets of a list with duplicatesCodingReturn every distinct subset of an integer list that may contain duplicate values, with no subset repeated. Sort first and skip duplicates during backtracking, and give the output…
Last asked Jan 2026
Build a binary tree from a parenthesized stringCodingA string encodes a binary tree as an integer followed by zero, one or two parenthesized subtrees, the left one first, for example 4(2(3)(1))(6(5)). Parse it into a tree and return…
Last asked Jan 2026
Lowest common ancestor in an N-ary treeCodingGiven the root of an N-ary tree and two of its nodes, return their lowest common ancestor. Use one depth-first pass in which each subtree reports whether it contains each of the…
Last asked Dec 2025
Look up a value in a nested object by pathCodingGiven a nested object (maps and lists inside each other) and a path string such as a.b.0.c, return the value at that path, or a default when any step is missing. Handle list…
Last asked Oct 2025
Print a directory tree with indentationCodingGiven a root directory, print it and everything under it, one entry per line, with each entry indented one step more than its parent directory.
Last asked Oct 2025
Fill a second tree with subtree sums of the firstCodingYou get the roots of two complete binary trees with exactly the same shape. For every node of the second tree, set its value to the sum of the subtree rooted at the matching node…
Last asked Sep 2025
Permutations of a list with duplicatesCodingReturn every distinct ordering of a list that may contain repeated values, with no duplicate orderings in the output. Sort first and skip a value at a position when an equal value…
Last asked Sep 2025
Deep clone an objectCodingWrite a function that makes a deep copy of a value that can contain nested objects and arrays, so changing the copy never changes the original. Talk through which types need…
Last asked Sep 2025
Turn dotted keys into a nested dictionaryCodingA model's weights come as a flat mapping from dotted names such as layer1.attention.query.weight to values. Convert it into a nested dictionary ({"layer1": {"attention": {"query":…
Last asked Aug 2025
Expression add operatorsCodingGiven a string of digits and a target, insert +, - or between digits so that the expression evaluates to the target, and return every such expression. Handle multiplication…
Last asked Aug 2025
Target sumCodingPut a + or - in front of every number in an array and count how many ways the expression adds up to a target. Write the recursive solution, then turn it into a dynamic program…
Last asked Aug 2025
Parse and evaluate a Lisp-like expression with error handlingCodingEvaluate expressions such as (add 1 2), (mult 3 (add 2 3)) and (let x 2 (mult x 5)), where let binds variables in nested scopes. Unlike the classic version, the input may be…
Last asked Aug 2025
Construct binary tree from inorder and postorder traversalCodingGiven the inorder and postorder traversals of a binary tree with distinct values, rebuild the tree. The last postorder value is the root; its position in the inorder list splits…
Last asked Aug 2025
Collapsible JSON viewer in ReactCodingIn an hour of React, pretty-print a JSON value (objects, arrays, strings, numbers) with indentation, and give every nested object and array a toggle that collapses it to a…
Last asked Jul 2025
Nested todo list with subtasksCodingModel a todo list whose items can nest subtasks to any depth: add, complete and list tasks while keeping the hierarchy. Reported on 1point3acres' Notion bank; reconstructed in our…
Template formatter with plural blocksCodingImplement formattemplate(text: str, keys: liststr, values: liststr) - str. keysi maps to valuesi; all values are strings. text can contain two kinds of expressions in braces: 1…
Merge two n-ary trees by child positionCodingImplement mergetrees(root1, root2). It takes the roots of two n-ary trees and returns the root of a new tree that merges them. Each node has an integer val and an ordered list…
Integer to English words, built up by rangeCodingWrite a function that spells out an integer in English words. The interviewer adds the ranges in parts, and later parts should reuse earlier ones, so design for extension from the…
Merge neighbor sums from many binary trees into the lastCodingYou are given a list trees of binary trees (each given by its root, possibly empty). The neighbor sum of a node is its own value plus the values of its left and right children…
+2
Compress an n-ary tree by promoting childrenCodingEach node of an n-ary tree holds a unique integer value and an ordered list of children. You are given the root and a list compressednodes of values. Implement compress(root…