Solve Several Algorithm Problems
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
The interview included several coding tasks:
1. **Longest symmetric substring**: Given a string `s`, return the longest contiguous substring that reads the same forward and backward.
2. **Point connectivity on a 2D plane**: You are given many points `(x, y)` and a threshold `d`. Two points are directly connected if they are in the same row (`y` is equal) or the same column (`x` is equal), and their distance along that row or column is strictly less than `d`. Connectivity is transitive. Return the number of connected components.
3. **Dynamic land additions**: Start with an `m x n` grid of water. Land cells are added one at a time. After each addition, report the current number of connected land masses using 4-directional adjacency. Follow-up: discuss how you would support deleting existing land cells as well.
4. **Square root by binary search**: Implement a function that computes the square root of a non-negative number using binary search. Clarify whether the expected result is the integer floor or a floating-point approximation within a chosen precision.
5. **Evaluate nested arithmetic expressions**: Given an expression string such as `sub(1,add(2,3))`, evaluate its integer result. Supported operations are `add(a,b)` and `sub(a,b)`, and expressions may be nested arbitrarily. Example: `sub(1,add(2,3)) = -4`.
Quick Answer: This collection evaluates proficiency in string processing (longest palindromic substrings), graph connectivity and union‑find style concepts for 2D point clustering, dynamic connectivity for incremental grid updates, numeric methods using binary search for roots, and recursive parsing/evaluation of nested arithmetic expressions.