Quick Overview

This multi-part question evaluates algorithmic problem solving, data-structure selection, complexity analysis, API design, and the handling of trees, arrays, grids, circular structures, and dynamic updates.

Solve six algorithmic problems

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Answer the following independent algorithmic prompts. For each, explain your approach, justify data structures, analyze time/space complexity, and provide correct code: 1) Bulb toggling passes: You have n bulbs initially off. For pass i (1 ≤ i ≤ n), toggle every bulb whose index is a multiple of i. After n passes, return the count of bulbs that are on. Follow-up: given m ≤ n passes or a custom toggling set S of divisors, compute the result efficiently without simulating all passes. 2) Repeated word-distance queries: Preprocess an array of words to support many queries of the form shortestDistance(word1, word 2) that returns the minimum index gap between any occurrence of the two words. Design the initialization and query APIs, then optimize for both time and memory. Follow-ups: support dynamic inserts/appends; support queries over a sliding window. 3) Invert a binary tree: Given the root of a binary tree, return its mirror image. Discuss iterative vs. recursive solutions and how to handle nodes missing exactly one child. Follow-ups: verify structural equality between the original and double-inverted tree; invert only nodes at odd depths. 4) Count land clusters in a grid: Given an m×n grid of '1' (land) and '0' (water), return the number of connected land clusters using 4-directional adjacency. Follow-ups: handle dynamic updates turning cells on/off; extend to 8-directional adjacency; optimize with union–find. 5) Longest run in a circular binary array: Given a binary array treated as circular (index wraps around), compute the maximum number of consecutive 1s. Follow-ups: if you may flip up to k zeros to ones, find the new maximum and return one optimal window. 6) Peel leaves by rounds: Given a binary tree, iteratively collect and remove its leaves; output a list of lists where the i-th list contains the values removed at round i. Provide an O(n) solution and discuss how computing node heights leads to the result.

Quick Answer: This multi-part question evaluates algorithmic problem solving, data-structure selection, complexity analysis, API design, and the handling of trees, arrays, grids, circular structures, and dynamic updates.

Part 1: Bulb Toggling Passes

You have n bulbs numbered from 1 to n, and all bulbs start turned off. On pass i, you toggle every bulb whose index is a multiple of i. After performing all passes from 1 to n, return how many bulbs are on. This version asks for the final count after all n passes, without simulating every toggle one by one.

Constraints

  • 0 <= n <= 10^18
  • Bulbs are 1-indexed
  • A toggle changes off to on, or on to off

Examples

Input: (0,)

Expected Output: 0

Explanation: There are no bulbs, so the answer is 0.

Input: (1,)

Expected Output: 1

Explanation: Bulb 1 is toggled once, so it stays on.

Hints

  1. A bulb ends up on only if it is toggled an odd number of times.
  2. Most divisors come in pairs. Which numbers have an unpaired divisor?

Part 2: Repeated Word-Distance Queries

Given a list of words and many queries, answer each query shortestDistance(word1, word2): the minimum absolute difference between any occurrence of word1 and any occurrence of word2 in the list. If a queried word does not appear, return -1 for that query. If word1 == word2, return the minimum distance between two distinct occurrences of that same word, or -1 if it appears fewer than two times.

Constraints

  • 1 <= len(words) <= 10^5
  • 1 <= len(queries) <= 10^5
  • Each word is a non-empty string
  • Total processing should avoid rescanning the full words array for every query

Examples

Input: (["practice", "makes", "perfect", "coding", "makes"], [("coding", "practice"), ("makes", "coding")])

Expected Output: [3, 1]

Explanation: coding is at index 3 and practice at 0, so distance 3. makes occurs at 1 and 4; the closest makes to coding is at 4, so distance 1.

Input: (["a", "b", "a"], [("a", "c")])

Expected Output: [-1]

Explanation: Word c does not appear.

Hints

  1. Store all positions for each distinct word in sorted order as you scan the list once.
  2. To compare two sorted position lists efficiently, try a two-pointer walk.

Part 3: Invert a Binary Tree

A binary tree is given in level-order array form, using None for missing children. Return the mirror image of the tree, also in level-order array form with trailing None values removed. In the inverted tree, every node's left and right children are swapped.

Constraints

  • 0 <= number of list entries <= 10^4
  • Node values are integers
  • If level_order is empty, the tree is empty

Examples

Input: ([4, 2, 7, 1, 3, 6, 9],)

Expected Output: [4, 7, 2, 9, 6, 3, 1]

Explanation: Every left/right subtree pair is mirrored.

Input: ([2, 1, 3, None, None, 4],)

Expected Output: [2, 3, 1, None, 4]

Explanation: Node 3's single child moves from the left side to the right side after inversion.

Hints

  1. Inversion is local: at every node, swap the left and right pointers.
  2. A breadth-first traversal is an easy way to process every node iteratively.

Part 4: Count Land Clusters in a Grid

You are given a grid of '1' and '0' characters, where '1' means land and '0' means water. Two land cells belong to the same cluster if they are connected horizontally or vertically. Return the number of connected land clusters.

Constraints

  • 0 <= number of rows <= 300
  • 0 <= number of columns <= 300
  • All rows have the same length
  • Adjacency is only up, down, left, and right

Examples

Input: (["11000", "11000", "00100", "00011"],)

Expected Output: 3

Explanation: There are three separate land clusters.

Input: (["000", "000"],)

Expected Output: 0

Explanation: There is no land.

Hints

  1. When you find an unvisited land cell, explore its whole component with DFS or BFS.
  2. Mark cells as visited so you do not count the same island more than once.

Part 5: Longest Run in a Circular Binary Array

You are given a binary array nums that should be treated as circular, so index n - 1 is adjacent to index 0. You may flip at most k zeros to ones. Return a tuple (max_len, start) where max_len is the maximum number of consecutive 1s obtainable in some circular window after at most k flips, and start is the smallest starting index of one optimal window in the original array. If nums is empty, return (0, -1). For a non-empty array, if the best length is 0, return start = 0.

Constraints

  • 0 <= len(nums) <= 2 * 10^5
  • 0 <= k <= len(nums)
  • Each element of nums is either 0 or 1
  • The chosen window length cannot exceed len(nums)

Examples

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

Expected Output: (3, 3)

Explanation: The best circular run is indices 3 -> 0 -> 1, which gives three 1s.

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

Expected Output: (4, 0)

Explanation: Flipping the zero at index 1 gives a length-4 window starting at 0. Another length-4 answer starts at 2, but 0 is smaller.

Hints

  1. A standard sliding window works for 'at most k zeros', but circularity suggests looking at a doubled array.
  2. Even with doubling, do not allow a window longer than the original array length.

Part 6: Peel Leaves by Rounds

A binary tree is given in level-order array form, using None for missing children. Repeatedly collect all current leaves, remove them, and continue until the tree is empty. Return a list of lists where the ith inner list contains the node values removed during round i. Within each round, output values in the left-to-right order produced by a postorder DFS.

Constraints

  • 0 <= number of list entries <= 10^4
  • Node values are integers
  • The intended solution should run in O(n)

Examples

Input: ([1, 2, 3, 4, 5],)

Expected Output: [[4, 5, 3], [2], [1]]

Explanation: First remove leaves 4, 5, and 3; then 2 becomes a leaf; finally 1.

Input: ([1],)

Expected Output: [[1]]

Explanation: A single node is removed in the first round.

Hints

  1. Instead of physically removing leaves round by round, compute each node's height from the bottom.
  2. All nodes with the same bottom-up height are removed in the same round.

Loading coding console...