Solve linked list, tree, and grid problems

Quick Overview

This set evaluates mastery of core data structures and algorithmic reasoning across singly linked lists (cycle entry detection), binary search trees with parent pointers (in-order successor), constant-time state tracking for n×n game boards, and grid connectivity for maximizing component size, emphasizing pointer manipulation, traversal logic, state-design, and component analysis. Commonly asked to gauge proficiency in Coding & Algorithms and complexity analysis, these problems test both conceptual understanding of traversal and connectivity principles and practical application of space- and time-efficient implementations under typical interview constraints.

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

### Problem A — Find cycle entry in a singly linked list You are given the head of a singly linked list. The list may contain a cycle. - Return the node where the cycle begins. - If there is no cycle, return `null`. - **Constraints:** O(1) extra space. Aim for linear time. --- ### Problem B — In-order successor with parent pointers You are given a node `x` in a binary search tree (BST). Each node has pointers `left`, `right`, and `parent`. - Return the in-order successor of `x` (the next node visited in an in-order traversal). - If `x` has no in-order successor, return `null`. --- ### Problem C — Design an n×n tic-tac-toe checker Implement a class for an `n × n` board supporting: - `move(row, col, player)` which places `player` (1 or 2) at `(row, col)` (assume valid and empty). - After each move, return: - `0` if no one has won, - `1` if player 1 wins, - `2` if player 2 wins. **Goal:** Each move should be close to O(1) time. --- ### Problem D — Maximize island size by flipping one cell Given an `n × n` binary grid (`0` water, `1` land), an island is a 4-directionally connected component of `1`s. - You may flip **at most one** `0` to `1`. - Return the maximum possible island size after the flip. **Constraints:** `1 ≤ n ≤ 500` (assume large enough that near-quadratic extra work may time out).

Overview: This set evaluates mastery of core data structures and algorithmic reasoning across singly linked lists (cycle entry detection), binary search trees with parent pointers (in-order successor), constant-time state tracking for n×n game boards, and grid connectivity for maximizing component size, emphasizing pointer manipulation, traversal logic, state-design, and component analysis. Commonly asked to gauge proficiency in Coding & Algorithms and complexity analysis, these problems test both conceptual understanding of traversal and connectivity principles and practical application of space- and time-efficient implementations under typical interview constraints.

Problem A — Find cycle entry in a singly linked list

You are given the head of a singly linked list. The list may contain a cycle.

Return the node where the cycle begins.
If there is no cycle, return null .
Constraints: O(1) extra space. Aim for linear time.

Problem B — In-order successor with parent pointers

You are given a node x in a binary search tree (BST). Each node has pointers left, right, and parent.

Return the in-order successor of x (the next node visited in an in-order traversal).
If x has no in-order successor, return null .

Problem C — Design an n×n tic-tac-toe checker

Implement a class for an n × n board supporting:

move(row, col, player) which places player (1 or 2) at (row, col) (assume valid and empty).
After each move, return:
- 0 if no one has won,
- 1 if player 1 wins,
- 2 if player 2 wins.

Goal: Each move should be close to O(1) time.

Problem D — Maximize island size by flipping one cell

Given an n × n binary grid (0 water, 1 land), an island is a 4-directionally connected component of 1s.

You may flip at most one 0 to 1 .
Return the maximum possible island size after the flip.

Constraints: 1 ≤ n ≤ 500 (assume large enough that near-quadratic extra work may time out).

Solve linked list, tree, and grid problems

Quick Overview