PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This set evaluates algorithmic problem-solving across arrays, immutable linked-list interfaces, parent-pointer tree traversal, string validity via minimal edits, and grid-based pathfinding including an AI-assisted maze search, testing data-structure knowledge, complexity reasoning, and handling of constrained APIs.

  • medium
  • Meta
  • Coding & Algorithms
  • Backend Engineer

Solve coding and AI-assisted tasks

Company: Meta

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

This interview included several algorithm problems across a phone screen, onsite coding, and an AI-assisted coding round. Solve the following tasks: 1. **Right-side visibility in a skyline**: Given an integer array `heights`, where `heights[i]` is the height of the `i`-th building from left to right, return the indices of buildings that can see the ocean on the right. A building can see the ocean if every building to its right is strictly shorter. Return the indices in increasing order, and be prepared to discuss edge cases. 2. **Print an immutable linked list in reverse**: You are given the head of a singly linked list whose nodes expose only `getNext()` and `printValue()` methods. You may not modify the list. Print the values from tail to head. First discuss multiple approaches, then implement the simplest correct approach. 3. **Find a common ancestor with parent pointers**: You are given two nodes in a tree. Each node has a pointer to its parent. Return their lowest common ancestor. 4. **Remove the fewest invalid parentheses**: Given a string containing lowercase letters and parentheses, remove the minimum number of parentheses so that the result is valid. Return any valid result. 5. **AI-assisted maze search**: In a separate AI-enabled coding round, solve a grid-maze problem. Given a 2D grid containing a start cell `S`, an end cell `E`, open cells `.`, and walls `#`, determine whether `E` is reachable from `S` using 4-directional movement. Be ready for common follow-ups such as returning the shortest path length or reconstructing one valid path.

Quick Answer: This set evaluates algorithmic problem-solving across arrays, immutable linked-list interfaces, parent-pointer tree traversal, string validity via minimal edits, and grid-based pathfinding including an AI-assisted maze search, testing data-structure knowledge, complexity reasoning, and handling of constrained APIs.

Part 1: Right-side visibility in a skyline

Given an integer array heights, where heights[i] is the height of the i-th building from left to right, return the indices of all buildings that can see the ocean on the right. A building can see the ocean if every building to its right is strictly shorter. Return the indices in increasing order.

Constraints

  • 0 <= len(heights) <= 10^5
  • -10^9 <= heights[i] <= 10^9
  • If two buildings have the same height, the one on the left cannot see past the one on the right.

Examples

Input: [4, 2, 3, 1]

Expected Output: [0, 2, 3]

Explanation: Building 0 is taller than all buildings to its right, building 2 is taller than building 3, and building 3 is the rightmost building.

Input: [1, 2, 3, 4]

Expected Output: [3]

Explanation: Only the last building can see the ocean because every earlier building has a taller building to its right.

Input: [4, 3, 2, 1]

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

Explanation: Each building is taller than all buildings to its right.

Input: [2, 2, 2]

Expected Output: [2]

Explanation: Visibility requires strictly shorter buildings to the right, so equal heights block the view.

Input: []

Expected Output: []

Explanation: Edge case: no buildings means no visible indices.

Hints

  1. Scan from right to left instead of checking every building against all buildings to its right.
  2. A building is visible exactly when it is taller than every building seen so far from the right.

Part 2: Print an immutable linked list in reverse

You are given an immutable singly linked list, but for testability it is represented by three inputs: values, next_index, and head. values[i] is the value stored in node i, next_index[i] is the index of the next node or -1 if it is the tail, and head is the index of the first node or -1 for an empty list. You may not modify the structure. Return the values in the order they would be printed from tail to head.

Constraints

  • 0 <= n <= 10^5, where n == len(values) == len(next_index)
  • head is -1 for an empty list; otherwise 0 <= head < n
  • Starting from head, next_index describes a valid acyclic singly linked list
  • You must not mutate values or next_index

Examples

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

Expected Output: [3, 2, 1]

Explanation: Traverse 1 -> 2 -> 3, then output in reverse.

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

Expected Output: []

Explanation: Edge case: empty immutable list.

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

Expected Output: [42]

Explanation: A single-node list prints the same value in reverse.

Input: ([5, 7, 7, 9], [1, 2, 3, -1], 0)

Expected Output: [9, 7, 7, 5]

Explanation: The linked list order is 5 -> 7 -> 7 -> 9, so reverse printing is 9, 7, 7, 5.

Hints

  1. Since you can only move forward through the list, store what you see as you traverse.
  2. A stack is a simple way to reverse the order without modifying the list.

Part 3: Find a common ancestor with parent pointers

Nodes in a tree are numbered from 0 to n - 1. You are given a parent array where parent[i] is the parent of node i, and the root has parent -1. Given two node indices a and b, return their lowest common ancestor (LCA): the deepest node that is an ancestor of both. This models the classic interview problem where each node has a direct pointer to its parent.

Constraints

  • 1 <= n <= 10^5, where n == len(parent)
  • Exactly one node has parent -1, and every other node has exactly one valid parent index
  • 0 <= a, b < n
  • a and b are in the same tree

Examples

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

Expected Output: 1

Explanation: Nodes 3 and 4 share parent 1, so the LCA is 1.

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

Expected Output: 0

Explanation: The paths are 3 -> 1 -> 0 and 5 -> 2 -> 0, so the first common ancestor is 0.

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

Expected Output: 2

Explanation: A node is allowed to be its own ancestor, so the LCA of 2 and 5 is 2.

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

Expected Output: 0

Explanation: The root is an ancestor of every node in the tree.

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

Expected Output: 0

Explanation: Edge case: a single-node tree.

Hints

  1. If one node is deeper than the other, move it upward first until both nodes are at the same depth.
  2. Once the depths match, move both nodes upward together until they meet.

Part 4: Remove the fewest invalid parentheses

Given a string s containing lowercase letters and parentheses, remove the minimum number of parentheses so that the resulting string is valid. A valid parentheses string has balanced, properly ordered parentheses. Return any valid result with the minimum number of removals. The expected outputs below match the reference solution shown here.

Constraints

  • 0 <= len(s) <= 10^5
  • s contains only lowercase English letters and the characters '(' and ')'

Examples

Input: "lee(t(c)o)de)"

Expected Output: "lee(t(c)o)de"

Explanation: Removing the final unmatched ')' produces a valid string with one deletion.

Input: "()())()"

Expected Output: "()()()"

Explanation: One unmatched closing parenthesis must be removed.

Input: "a)b(c)d"

Expected Output: "ab(c)d"

Explanation: Remove the unmatched ')' after 'a'.

Input: "))( ("

Expected Output: ""

Explanation: This case is intentionally not used because it contains a space, which is outside the stated constraints.

Input: "))( ("

Expected Output: ""

Explanation: Placeholder removed.

Hints

  1. As you scan left to right, unmatched closing parentheses can be identified immediately.
  2. Any opening parentheses left unmatched after the scan must also be removed.

Part 5: AI-assisted maze search

You are given a rectangular 2D grid containing one start cell 'S', one end cell 'E', open cells '.', and walls '#'. Determine whether E is reachable from S using only 4-directional movement: up, down, left, and right. This is the core version of a maze-search problem; a common follow-up is to return the shortest path length or reconstruct one valid path.

Constraints

  • 1 <= rows, cols <= 200
  • grid is rectangular
  • Each cell is one of 'S', 'E', '.', '#'
  • There is exactly one 'S' and exactly one 'E'

Examples

Input: ["S..", "##.", "..E"]

Expected Output: True

Explanation: There is a path across the top row and then down to E.

Input: ["S#.", "##.", "..E"]

Expected Output: False

Explanation: The start is blocked and cannot reach the lower rows.

Input: ["SE"]

Expected Output: True

Explanation: Edge case: the end is immediately adjacent to the start.

Input: ["S#E"]

Expected Output: False

Explanation: A wall directly blocks the only possible route.

Hints

  1. Treat each non-wall cell as a node in a graph connected to its four neighbors.
  2. BFS is especially useful because it also supports the shortest-path follow-up.
Last updated: May 7, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ 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

  • Find Shortest Unique Prefixes - Meta (medium)
  • Compute Exclusive Execution Times - Meta (medium)
  • Solve Tree Columns And Maze Variants - Meta (medium)
  • Solve Tree Diameter and Palindromic Counts - Meta (medium)
  • Simulate Monster Team Battles - Meta (hard)