Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Implement distinct islands and sliding maxima states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement distinct islands and sliding maxima

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

1) Given a binary grid where 1 represents land and 0 represents water, count how many distinct island shapes exist. Two islands are considered the same if one can be translated (shifted) to match the other; rotations and reflections should be treated as different. Implement an algorithm that returns the count and analyze its time and space complexity. Then discuss how you would extend the method if rotations and reflections were also considered equivalent. 2) Given an integer array and a window size k, return the maximum value for every contiguous subarray of length k. Implement an O(n) solution and explain why it is linear. Compare this approach to a heap-based method and discuss trade-offs.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Implement distinct islands and sliding maxima states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Count Distinct Island Shapes

Given a binary grid where `1` represents land and `0` represents water, count how many **distinct** island shapes exist. An island is a maximal group of `1`s connected 4-directionally (up/down/left/right). Two islands are considered the **same** if one can be **translated** (shifted) to exactly overlap the other; rotations and reflections are treated as **different** shapes. Return the number of distinct island shapes. **Approach:** Flood-fill each island with DFS/BFS, recording each cell's coordinates **relative to the island's first-visited cell**. This relative-coordinate signature is translation-invariant, so two islands with the same shape produce the same signature. Insert each signature into a hash set; the answer is the set's size. **Extension (rotations + reflections):** If rotations and reflections should also be considered equivalent, generate all 8 transformations (4 rotations × 2 reflections) of each shape's coordinate set, normalize each (translate so the min coordinate is the origin), and use the lexicographically smallest canonical form as the signature.

Constraints

  • 1 <= number of rows, columns (grid may also be empty -> return 0)
  • grid[i][j] is 0 (water) or 1 (land)
  • Connectivity is 4-directional (no diagonals)
  • Translation-equivalent islands count as one shape; rotations/reflections are distinct

Examples

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

Expected Output: 1

Explanation: Two 2x2 square islands have the same shape after translation, so there is 1 distinct shape.

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

Expected Output: 3

Explanation: An L-shape (top-left), a single-cell island plus an L (right side), and a horizontal domino — three distinct shapes after deduping translation-equivalent ones.

Hints

  1. Anchor each island's shape to the coordinates of its first-visited cell by storing (r - base_r, c - base_c) for every land cell. This makes the signature translation-invariant.
  2. Always traverse the island in a deterministic order (e.g., fixed DFS direction order) so identical shapes yield identical coordinate sequences.
  3. Store each shape signature (a tuple of relative coordinates) in a hash set; the count of distinct shapes is the set size.
  4. For the rotation/reflection extension, compute all 8 dihedral transformations of the coordinate set, normalize each to the origin, and key on the lexicographically smallest one.

Sliding Window Maximum

Given an integer array `nums` and a window size `k`, return an array containing the **maximum** of every contiguous subarray (window) of length `k`, in order from left to right. Implement an **O(n)** solution using a **monotonic deque**: maintain a deque of indices whose corresponding values are in decreasing order. For each new element, pop smaller-or-equal values from the back (they can never be the max while the new element is in the window), append the current index, drop the front index if it has slid out of the window, and once the first full window is formed record `nums[deque.front]` as that window's maximum. **Why O(n):** each index is pushed and popped from the deque at most once, so the total amount of deque work across the whole scan is linear. **Heap comparison:** A max-heap of (value, index) yields O(n log k) because each insertion/lazy-deletion costs O(log k); it uses more memory for stale entries and is slower in practice, but generalizes more easily when you need order statistics beyond just the maximum.

Constraints

  • 1 <= k <= nums.length (this solution also clamps k > len(nums) and returns [] for empty input)
  • nums may contain negative numbers, zeros, and duplicates
  • Return one maximum per window, in left-to-right order

Examples

Input: ([1,3,-1,-3,5,3,6,7], 3)

Expected Output: [3, 3, 5, 5, 6, 7]

Explanation: Windows [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7.

Input: ([1], 1)

Expected Output: [1]

Explanation: A single-element window returns that element.

Hints

  1. Maintain a deque of indices (not values) so you can tell when the front element has slid out of the current window.
  2. Keep the deque values in decreasing order: before pushing index i, pop every back index whose value is <= nums[i], since they can never be a future window maximum.
  3. The front of the deque is always the index of the current window's maximum — emit nums[deque.front] once you have seen at least k elements.
  4. Each index enters and leaves the deque at most once, which is the key to the overall O(n) time bound versus a heap's O(n log k).

Loading coding console...