How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Harvey.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Harvey during technical interviews.

Evaluate Symbol Expressions | Harvey Coding Question

Evaluate Symbol Expressions

Company: Harvey

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a map from symbol names to arithmetic expressions. Each expression may contain integer constants, other symbol names, parentheses, and the binary operators `+`, `-`, `*`, and `/`. Implement a function that returns the final numeric value of every symbol after recursively evaluating its dependencies. Example: Input: ```text { "a": "3", "b": "a + 2", "c": "b * 4", "d": "c - a" } ``` Output: ```text { "a": 3, "b": 5, "c": 20, "d": 17 } ``` Requirements: - A symbol may depend on any other symbol in the map. - Expressions can contain nested dependencies. - If an expression references a symbol that does not exist, raise an exception. - If the dependency graph contains a cycle, raise an exception. Example cycle: ```text { "a": "b + 1", "b": "c + 1", "c": "a + 1" } ``` This input should raise a circular dependency exception. Follow-up: Explain how you would detect cycles while evaluating the symbols.

Quick Answer: This question evaluates the ability to parse and evaluate arithmetic expressions with symbol references, perform recursive dependency resolution, and detect invalid references and circular dependencies.

Part 1: Evaluate All Symbol Expressions

You are given a dictionary where each key is a symbol name and each value is an arithmetic expression written as a string. An expression may contain integer constants, other symbol names, parentheses, and the binary operators +, -, *, and /. Evaluate every symbol by recursively resolving its dependencies, and return a dictionary mapping each symbol to its final numeric value. If an expression references a symbol that is not defined, raise ValueError with message 'Unknown symbol: <name>'. If the dependency graph contains a cycle, raise ValueError with message 'Circular dependency detected at: <name>'. The / operator uses standard floating-point division.

Constraints

0 <= number of symbols <= 1000
Total length of all expression strings <= 100000
Expressions contain only integer constants, valid symbol names, parentheses, spaces, and operators +, -, *, /
Expressions are syntactically valid
Test cases do not include division by zero

Examples

Input: {'a': '3', 'b': 'a + 2', 'c': 'b * 4', 'd': 'c - a'}

Expected Output: {'a': 3, 'b': 5, 'c': 20, 'd': 17}

Explanation: A simple dependency chain. Each symbol depends on previously computed symbols.

Input: {'x': '8', 'y': '(x + 4) / 3', 'z': 'y * 2'}

Expected Output: {'x': 8, 'y': 4.0, 'z': 8.0}

Explanation: Shows parentheses and division. The / operator uses floating-point division.

Input: {'only': '42'}

Expected Output: {'only': 42}

Explanation: Edge case: a single symbol with no dependencies.

Input: {'a': 'b + 1'}

Expected Output: 'ValueError: Unknown symbol: b'

Explanation: Symbol b is never defined, so resolving a fails. The harness compares the returned diagnostic string; the solution surfaces 'ValueError: Unknown symbol: b'.

Input: {'a': 'b + 1', 'b': 'c + 1', 'c': 'a + 1'}

Expected Output: 'ValueError: Circular dependency detected at: a'

Explanation: a -> b -> c -> a forms a cycle, so resolution fails and the solution surfaces 'ValueError: Circular dependency detected at: a'.

Input: {}

Expected Output: {}

Explanation: Edge case: empty dictionary has no symbols, so the result is an empty mapping.

Input: {'k': '100 - 50 * 2 + 8 / 4'}

Expected Output: {'k': 2.0}

Explanation: Operator precedence with no dependencies: 100 - (50*2) + (8/4) = 2.0 (division yields a float).

Input: {'a': 'a + 1'}

Expected Output: 'ValueError: Circular dependency detected at: a'

Explanation: Self-referential cycle: a depends directly on itself, which is detected as a circular dependency.

Input: {'p': '2 * (3 + 4)', 'q': 'p / 7'}

Expected Output: {'p': 14, 'q': 2.0}

Explanation: Parentheses override precedence: p = 2*(3+4) = 14, then q = p/7 = 2.0.

Hints

Use DFS with memoization so each symbol is evaluated only once.
Keep a recursion-stack set (or color map) to detect when evaluation re-enters a symbol that is already being processed.

Part 2: Detect Circular Symbol Dependencies

You are given a dictionary where each key is a symbol name and each value is an arithmetic expression written as a string. Build the dependency graph between defined symbols, and determine whether any circular dependency exists. A dependency exists from symbol A to symbol B if B appears in A's expression and B is also a key in the dictionary. Return True if any cycle exists; otherwise return False. For this problem, references to undefined names should be ignored rather than treated as errors.

Constraints

0 <= number of symbols <= 1000
Total length of all expression strings <= 100000
Expressions are syntactically valid
Only references to symbols present in the dictionary create graph edges

Examples

Input: {'a': 'b + 1', 'b': 'c + 1', 'c': 'a + 1'}

Expected Output: True

Explanation: a depends on b, b depends on c, and c depends back on a.

Input: {'a': '3', 'b': 'a + 2', 'c': 'b * 4', 'd': 'c - a'}

Expected Output: False

Explanation: This dependency chain is acyclic.

Input: {'a': 'a + 1'}

Expected Output: True

Explanation: Edge case: a direct self-reference is a cycle.

Input: {}

Expected Output: False

Explanation: Edge case: an empty map has no cycle.

Input: {'a': 'missing + 1', 'b': 'a + 2'}

Expected Output: False

Explanation: The name 'missing' is ignored for this problem because it is not a defined symbol, so the remaining graph is acyclic.

Hints

First extract which symbol names each expression references, then build a graph.
Use DFS with three states: unvisited, visiting, and visited. Reaching a 'visiting' node means a cycle exists.

Quick Overview

This question evaluates the ability to parse and evaluate arithmetic expressions with symbol references, perform recursive dependency resolution, and detect invalid references and circular dependencies.