Implement stacks, median, and tree path sum
Company: Bytedance
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Implement or discuss the following coding tasks.
1. Design a MinStack data structure that supports push, pop, top, and getMin in O(1) time.
2. Design a MaxStack that supports push, pop, top, peekMax, and popMax. Aim for constant-time top and efficient maximum operations.
3. Given a stream of numbers, design a data structure that can return the current median after each insertion. If helpful, explain whether ideas from the MaxStack design can or cannot be adapted.
4. Given a binary tree with integer values and a target sum, determine whether there exists a path whose endpoints are a node and one of its ancestors, so the path moves only upward from child to parent, and the sum of the values on that path equals the target. A single node counts as a valid path. You may preprocess parent pointers if needed.
Quick Answer: This question evaluates skills in designing and implementing efficient data structures and online algorithms, covering stack variants with constant-time operations, median maintenance for data streams, and ancestor-path sum reasoning in binary trees.