Katkat
Back

Solve linked list, tree, and grid problems

MetaMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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