Solve linked list, tree, and grid problems
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
xhas no in-order successor, returnnull.
Problem C — Design an n×n tic-tac-toe checker
Implement a class for an n × n board supporting:
-
move(row, col, player)which placesplayer(1 or 2) at(row, col)(assume valid and empty). -
After each move, return:
-
0if no one has won, -
1if player 1 wins, -
2if 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
0to1. - Return the maximum possible island size after the flip.
Constraints: 1 ≤ n ≤ 500 (assume large enough that near-quadratic extra work may time out).