Katkat
Back

Implement Fibonacci generator, balanced BST, frozenset

WaymoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your understanding of Python generators for sequence generation, the mechanics of tree rotations in self-balancing data structures, and the requirements for implementing immutable, hashable collections.

Problem Statement

Design a Python-based utility that provides the following three features:

  1. Fibonacci Generator: Write a generator function fib_gen(n) that yields the first n numbers of the Fibonacci sequence, starting from 0 and 1.
  2. Balanced BST Node: Define a class Node for a Binary Search Tree that tracks its height and provides a method rotate_right() to perform a standard right rotation, maintaining the BST property.
  3. Immutable Set: Create a class FrozenSetWrapper that wraps a standard Python list. The wrapper must be hashable and immutable, allowing it to be used as a key in a dictionary. Assume the input list contains only hashable elements.

Examples

# 1. Fibonacci
gen = fib_gen(5)
print(list(gen)) # Output: [0, 1, 1, 2, 3]

# 2. Rotation
# Assuming a tree:   y
#                   / \
#                  x   T3
#                 / \
#                T1  T2
# After rotate_right(y), it becomes:
#                  x
#                 / \
#                T1  y
#                   / \
#                  T2  T3

# 3. Hashable Wrapper
s1 = FrozenSetWrapper([1, 2, 3])
s2 = FrozenSetWrapper([3, 2, 1])
my_dict = {s1: "data"}
print(my_dict[s2]) # Output: "data"

Constraints

  • n for fib_gen will be non-negative.
  • The BST rotate_right must correctly update the height attribute of affected nodes.
  • FrozenSetWrapper should be considered equal to another instance if they contain the same elements, regardless of order.

Hints

Hint 1

For the generator, remember that local variables persist between yield calls, allowing you to track the current and next values simply.

Hint 2

During a right rotation, the left child of the root becomes the new root, and the original root becomes the right child of that new root.

Hint 3

To make a custom class hashable, you must implement the __hash__ and __eq__ magic methods, ensuring the hash is consistent with equality.

Follow-up questions

  • How would you modify the Fibonacci generator to support an infinite sequence that you can stop externally?
  • What are the time and space complexity implications of using a hash-based set versus a BST for lookups as the dataset grows?
  • In the context of the immutable wrapper, what happens if the internal list is modified after being used as a dictionary key?