Katkat
Back

Solve linked list, grid BFS, and median queries

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate linked list pointers in-place, perform a multi-source Breadth-First Search on a grid, and maintain a sorted structure to retrieve medians efficiently.

Part 1: Linked List Reversal

Given the head of a singly linked list, reverse the nodes of the list in groups of k at a time and return the modified head. If the number of nodes is not a multiple of k, the left-out nodes at the end should remain as they are.

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    # Implementation here

Part 2: Shortest Path in a Grid

You are given an m x n binary grid where 0 represents an empty cell and 1 represents a blocked cell. Find the shortest path from the top-left (0, 0) to the bottom-right (m-1, n-1). You can move in the four cardinal directions. If no path exists, return -1.

Example: Input: grid = [[0,0,0],[1,1,0],[0,0,0]] Output: 4

Part 3: Running Median

Design a data structure that supports adding an integer from a data stream and calculating the median of all elements seen so far.

Constraints:

  • Linked list length: N <= 1000
  • Grid size: m, n <= 100
  • Stream size: M <= 10^5 additions
  • Time complexity target: O(M log M) for the median structure, O(m*n) for grid BFS.

Hints

Hint 1

For the linked list, use a recursive approach or a dummy head node with a pointer tracker to reverse segments of size k.

Hint 2

For the grid, use a queue to perform a standard BFS, keeping a separate 2D array to track visited cells to avoid cycles.

Hint 3

For the median, maintain two heaps: a max-heap for the lower half of numbers and a min-heap for the upper half, balancing them so their sizes differ by at most one.

Follow-up questions

  • How would you modify the grid BFS if each cell had a non-negative weight (cost) instead of just being blocked or empty?
  • What is the space complexity of your median finding solution, and can you optimize it if the input integers are limited to a range of 1 to 1000?
  • If the linked list was doubly linked, how would your pointer manipulation logic change?