Implement three whiteboard coding tasks
Company: Palo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
The interview report described several coding questions in the same category:
1. **Binary search**: Given a sorted array of integers and a target value, return the index of the target if it exists, otherwise return `-1`. The expected time complexity is `O(log n)`.
2. **Randomized set data structure**: Design a data structure that supports the following operations in average `O(1)` time:
- `insert(x)`: add `x` if it is not already present
- `remove(x)`: delete `x` if it is present
- `getRandom()`: return a uniformly random element from the current set
3. **Expression evaluator**: Given a string containing non-negative integers, spaces, and the operators `+`, `-`, `*`, and `/`, evaluate the expression while respecting normal operator precedence. As a follow-up, extend the evaluator to support nested parentheses.
Quick Answer: This set of whiteboard coding tasks evaluates proficiency in algorithmic problem-solving, data structure design, and parsing techniques by covering binary search, randomized set operations with average O(1) complexity, and operator-precedence expression evaluation including nested parentheses.