PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

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.

  • medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

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.

Part 1: Longest Symmetric Substring

Given a string `s`, return the longest contiguous substring that reads the same forward and backward. If there are multiple longest answers, return the one that appears first in the string.

Constraints

  • 0 <= len(s) <= 2000
  • s may contain letters, digits, spaces, or symbols
  • If `s` is empty, return an empty string

Examples

Input: ("babad",)

Expected Output: "bab"

Explanation: "bab" and "aba" are both length 3, but "bab" appears first.

Input: ("cbbd",)

Expected Output: "bb"

Explanation: The longest palindromic substring is the even-length palindrome "bb".

Input: ("a",)

Expected Output: "a"

Explanation: A single character is always a palindrome.

Input: ("",)

Expected Output: ""

Explanation: The empty string has no non-empty substring, so return an empty string.

Input: ("forgeeksskeegfor",)

Expected Output: "geeksskeeg"

Explanation: "geeksskeeg" is the longest palindrome in the string.

Input: ("abacdfgdcaba",)

Expected Output: "aba"

Explanation: There are two longest palindromes of length 3: one at the start and one at the end. Return the first one.

Input: ("aaaa",)

Expected Output: "aaaa"

Explanation: The entire string is a palindrome.

Hints

  1. A palindrome can be centered on one character or between two characters.
  2. Try expanding outward from every possible center and keep track of the best substring found so far.

Part 2: Point Connectivity on a 2D Plane

You are given a list of points `(x, y)` and an integer 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 among all points.

Constraints

  • 0 <= len(points) <= 200000
  • Coordinates are integers
  • 0 <= d <= 10^9
  • Duplicate points may appear and should be treated as distinct input points

Examples

Input: ([(0, 0), (1, 0), (5, 0), (5, 2)], 2)

Expected Output: 3

Explanation: The first two points are connected because they are in the same row and |1 - 0| = 1 < 2. The points (5, 0) and (5, 2) are not directly connected because |2 - 0| = 2 is not strictly less than 2. So the components are {(0,0),(1,0)}, {(5,0)}, and {(5,2)}.

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

Expected Output: 1

Explanation: (0,0) connects to (2,0), (2,0) connects to (2,2), and (2,2) connects to (4,2). By transitivity, all four points are in one component.

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

Expected Output: 1

Explanation: Adjacent points in the row differ by 2, which is less than 3. So (0,0) connects to (2,0), and (2,0) connects to (4,0). Even though (0,0) and (4,0) are not directly connected, all three are in the same component.

Input: ([], 5)

Expected Output: 0

Explanation: There are no points, so there are no connected components.

Input: ([(1, 1), (1, 1), (1, 2)], 0)

Expected Output: 3

Explanation: Direct connections require distance to be strictly less than 0, which is impossible. Even the duplicate points are not connected, so each point is its own component.

Input: ([(-7, 4)], 10)

Expected Output: 1

Explanation: A single point always forms exactly one connected component.

Hints

  1. Within a fixed row or column, sort the points by their varying coordinate.
  2. You do not need to connect every pair in a row or column; connecting adjacent points that are close enough is sufficient.

Part 3: Dynamic Land Additions

You start with an `m x n` grid filled with water. Land cells are added one at a time. After each addition, return the current number of connected land masses (islands), where cells are connected only in the 4 main directions: up, down, left, and right. If the same cell is added more than once, the island count does not change. Follow-up for discussion only: how would you support deleting existing land cells as well?

Constraints

  • 1 <= m, n <= 10^4
  • 0 <= len(positions) <= 2 * 10^4
  • Each position is intended to be within the grid bounds
  • Repeated additions of the same cell are allowed

Examples

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

Expected Output: [1, 1, 2, 3, 1]

Explanation: The last addition at (1, 1) connects the previously separate land groups into one island.

Input: (1, 2, [(0, 0), (0, 0)])

Expected Output: [1, 1]

Explanation: Adding the same cell twice does not change the island count the second time.

Input: (2, 2, [])

Expected Output: []

Explanation: No land is added, so there are no island counts to report.

Input: (1, 1, [(0, 0)])

Expected Output: [1]

Explanation: A single land cell forms one island.

Input: (2, 2, [(0, 0), (1, 1), (0, 1), (1, 0)])

Expected Output: [1, 2, 1, 1]

Explanation: The third addition merges the two diagonal single-cell islands through (0, 1), and the fourth cell joins the same island.

Hints

  1. A disjoint set union (union-find) structure is a natural fit because each new land cell can merge with up to 4 neighbors.
  2. Be careful with duplicate additions; they should not create a new island.

Part 4: Square Root by Binary Search

Given a non-negative number `x`, compute its square root using binary search. For this problem, return a floating-point approximation rounded to 6 decimal places.

Constraints

  • 0 <= x <= 10^12
  • Your algorithm should use binary search rather than library square root functions
  • The returned value should be rounded to 6 decimal places

Examples

Input: (2,)

Expected Output: 1.414214

Explanation: The square root of 2 is approximately 1.41421356, which rounds to 1.414214.

Input: (0,)

Expected Output: 0.0

Explanation: The square root of 0 is exactly 0.

Input: (1,)

Expected Output: 1.0

Explanation: The square root of 1 is exactly 1.

Input: (0.25,)

Expected Output: 0.5

Explanation: The square root of 0.25 is exactly 0.5.

Input: (10,)

Expected Output: 3.162278

Explanation: The square root of 10 is approximately 3.16227766, which rounds to 3.162278.

Input: (1000000,)

Expected Output: 1000.0

Explanation: The square root of 1,000,000 is exactly 1000.

Input: (1e-06,)

Expected Output: 0.001

Explanation: The square root of 0.000001 is exactly 0.001.

Hints

  1. For `x >= 1`, the answer lies in `[0, x]`; for `0 < x < 1`, it lies in `[0, 1]`.
  2. Use the square of the midpoint to decide whether to move the low or high bound.

Part 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)`. Expressions may be nested arbitrarily. Integer literals may be positive or negative, and optional spaces may appear anywhere.

Constraints

  • 1 <= len(expression) <= 100000
  • The input expression is syntactically valid
  • Supported tokens are `add`, `sub`, integers, commas, parentheses, and optional spaces

Examples

Input: ('sub(1,add(2,3))',)

Expected Output: -4

Explanation: add(2,3) = 5, then sub(1,5) = -4.

Input: (' add( sub(10,5), sub(3,-2) ) ',)

Expected Output: 10

Explanation: sub(10,5) = 5 and sub(3,-2) = 5, so add(5,5) = 10.

Input: (' -42 ',)

Expected Output: -42

Explanation: A single integer literal is already a complete expression.

Input: ('sub(add(-5,8), sub(4, sub(1, 3)))',)

Expected Output: -3

Explanation: add(-5,8) = 3, sub(1,3) = -2, sub(4,-2) = 6, and sub(3,6) = -3.

Input: ('add( -7 , sub( 4 , - 6 ) )',)

Expected Output: 3

Explanation: sub(4,-6) = 10, then add(-7,10) = 3. This also checks that spaces around a negative number are handled.

Hints

  1. A stack works well because every time you see `)`, you have enough information to evaluate one subexpression.
  2. Treat `add` and `sub` as operators and push parsed integers as values.
Last updated: May 7, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement Minesweeper and Word Search - Uber (medium)
  • Implement Store Autocomplete - Uber (medium)
  • Implement Cache Eviction And Seat Assignment - Uber (medium)
  • Schedule Non-Overlapping Meetings Efficiently - Uber (hard)
  • Evaluate an Arithmetic Expression - Uber