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 Technical Screen rounds at Waymo.

What role is this question designed for?

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

Implement Fibonacci generator, balanced BST, frozenset

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are coding in **Python**. Implement the following three tasks. Unless explicitly allowed, **do not use Python built-in container types** (`list`, `dict`, `set`, `tuple`) or library data structures to store your core data; instead use your own node/linked structures and primitive fields (e.g., `int`, `bool`, references). ## 1) Fibonacci generator Implement a generator function: ```python def fib(): """Yield the infinite Fibonacci sequence: 0, 1, 1, 2, 3, 5, ...""" ... ``` Requirements: - Must be a generator (use `yield`). - Must run in O(1) extra space. ## 2) Balanced binary search tree (BST) without built-in data structures Implement a self-balancing BST (e.g., AVL or Red-Black) to store **integers**. Define an API similar to: ```python class BalancedBST: def insert(self, x: int) -> None: ... def remove(self, x: int) -> None: ... # no-op if not present def contains(self, x: int) -> bool: ... def min(self) -> int | None: ... def max(self) -> int | None: ... ``` Requirements: - `insert`, `remove`, `contains` should be **O(log n)** worst-case. - You must maintain balance via rotations and any metadata needed (height / color, etc.). - You may implement your own `Node` class. ## 3) Implement an immutable set ("frozenset") Implement an immutable, hashable set type supporting at least: ```python class FrozenSet: def __init__(self, iterable=None): ... def __contains__(self, x) -> bool: ... def __len__(self) -> int: ... def __iter__(self): ... def __hash__(self) -> int: ... def union(self, other: "FrozenSet") -> "FrozenSet": ... def intersection(self, other: "FrozenSet") -> "FrozenSet": ... ``` Requirements: - Instances are immutable after construction. - Equal sets must have equal hashes. - `union` / `intersection` must return new `FrozenSet` instances. Clarify any assumptions you need (e.g., whether elements must be hashable, how to handle duplicates in input, and expected behavior for empty sets).

Quick Answer: This question evaluates proficiency in core data structures and algorithms with a focus on Python-specific features, testing generator semantics (yield), self‑balancing binary search tree invariants and rotations, and immutable/hashable set design.

Part 1: Fibonacci Generator

Given a non-negative integer `n`, return the first `n` Fibonacci numbers. Inside `solution`, implement an infinite generator `fib()` that uses `yield` and keeps only O(1) auxiliary state. Using a list for the final returned result is allowed.

Constraints

`0 <= n <= 50`
The generator itself must keep only constant extra state.
The returned list must contain exactly `n` numbers.

Examples

Input: 0

Expected Output: []

Explanation: Edge case: requesting zero values should return an empty list.

Input: 1

Expected Output: [0]

Explanation: The sequence starts with 0.

Input: 7

Expected Output: [0, 1, 1, 2, 3, 5, 8]

Explanation: The first 7 Fibonacci numbers are returned.

Input: 10

Expected Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Explanation: A larger sample confirms the recurrence continues correctly.

Hints

A Fibonacci generator only needs to remember the previous two values.
A generator keeps its local variables between `yield` calls, so you do not need extra storage.

Part 2: Self-Balancing BST Operations

Process a sequence of operations on a self-balancing binary search tree that stores integers. You must build the tree from your own node objects and maintain balance with rotations. Duplicate inserts are ignored, and removing a value that is not present is a no-op. For simpler grading, each numeric argument is provided as a string.

Constraints

`1 <= len(operations) <= 100000`
Each numeric argument fits in the range `[-10^9, 10^9]`.
`insert`, `remove`, and `contains` should be O(log n) worst-case by keeping the tree balanced.
Use custom node-based storage for the tree; built-in lists are allowed only for the input and returned output.

Examples

Input: [['insert', '5'], ['insert', '2'], ['insert', '8'], ['contains', '2'], ['min'], ['max']]

Expected Output: ['true', '2', '8']

Explanation: Basic insertions followed by membership and boundary queries.

Input: [['insert', '10'], ['insert', '10'], ['remove', '7'], ['contains', '10'], ['remove', '10'], ['contains', '10'], ['min'], ['max']]

Expected Output: ['true', 'false', 'None', 'None']

Explanation: Tests duplicate insertion, removing a missing value, and queries after the tree becomes empty.

Input: [['min'], ['max'], ['contains', '1']]

Expected Output: ['None', 'None', 'false']

Explanation: Edge case: all queries are on an empty tree.

Input: [['insert', '30'], ['insert', '20'], ['insert', '10'], ['insert', '25'], ['remove', '20'], ['contains', '20'], ['min'], ['max']]

Expected Output: ['false', '10', '30']

Explanation: This sequence forces balancing and then deletes a node with two children.

Hints

AVL trees are a good fit here: store each node's height and rebalance after inserts and deletes.
Deletion in a BST is easiest if you replace a node with two children by its in-order successor.

Part 3: Immutable Set with Hashing

Implement an immutable set of integers using your own node-based storage, not Python's built-in `set` or `dict` as the core container. Duplicate input values are ignored. To make testing deterministic, iteration should yield values in increasing order. Equal sets must have equal hash values, but the exact numeric hash does not need to match Python's built-in `frozenset`. The `union` and `intersection` operations must return new set objects rather than modifying existing ones.

Constraints

`0 <= len(a), len(b) <= 10000`
All elements and `probe` are integers in `[-10^9, 10^9]`.
Duplicate values in the input lists should be ignored.
Use custom node-based storage for the set contents; lists are allowed only for input, output, and simple formatting.

Examples

Input: ([1, 2, 2, 3], [3, 4], 2)

Expected Output: ['3', 'true', '[1,2,3]', '[1,2,3,4]', '[3]', 'true']

Explanation: Duplicates are removed, membership works, and union and intersection return new sets.

Input: ([], [], 5)

Expected Output: ['0', 'false', '[]', '[]', '[]', 'true']

Explanation: Edge case: empty sets should behave correctly.

Input: ([5, 5, 5], [1, 5, 7], 1)

Expected Output: ['1', 'false', '[5]', '[1,5,7]', '[5]', 'true']

Explanation: A single unique element remains after removing duplicates.

Input: ([10, -1, 3], [-1, 3, 8, 10], -1)

Expected Output: ['3', 'true', '[-1,3,10]', '[-1,3,8,10]', '[-1,3,10]', 'true']

Explanation: Negative numbers and a non-trivial full intersection are handled correctly.

Hints

A balanced BST lets you support membership, insertion during construction, and sorted iteration without using built-in hash tables.
For hashing, combine the hashes of the stored values in a deterministic way so that building the same set from a different order gives the same result.

Quick Overview

This question evaluates proficiency in core data structures and algorithms with a focus on Python-specific features, testing generator semantics (yield), self‑balancing binary search tree invariants and rotations, and immutable/hashable set design.