Interview questions · Meta

Solve linked list, tree, and grid problems

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).

Community answers

Nothing here yet.

Join in on CSWork →