Solve max-subarray, min-unique, and grid-jump
Company: Cisco
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
1) Given an integer array nums, find a contiguous subarray with the maximum possible sum. Return (maxSum, startIndex, endIndex). If multiple subarrays have the same maxSum, choose the one with the smallest length; if still tied, choose the earliest startIndex. Achieve O(n) time and O(
1) extra space, and explain how your algorithm handles all-negative arrays.
2) Given an array of integers, return the smallest value that appears exactly once. If multiple values appear exactly once, return the minimum among them; if none exist, return -1. Aim for O(n) time. Follow-up: discuss approaches under memory constraints (e.g., limited extra space or bounded integer ranges).
3) On an m×n grid indexed from (1,
1) at the top-left, you start at (1,
1). You move in a counterclockwise direction cycle [right → up → left → down → …]. At each move you skip every alternate cell by moving exactly two cells in the current direction (landing two cells away); you may only land within bounds on an unvisited cell, and the cell you jump over remains unvisited. If the next landing cell would be out of bounds or already visited, rotate 90° counterclockwise and try again. Stop when all four directions are blocked. Return the coordinates of the last cell visited, and provide an algorithm with analyzed time and space complexity.
Quick Answer: This question evaluates array algorithms and algorithmic problem-solving skills, specifically contiguous-sum optimization (greedy/DP reasoning), frequency counting and memory-constrained selection for unique minima, and grid traversal simulation with boundary and visit-state management.
You are given positive integers m and n for an m×n grid. Grid cells are indexed with 1-based coordinates (r, c), where (1,1) is the top-left. Start at (1,1) with the current direction set to right. Repeatedly perform the following:
- Attempt to move exactly two cells in the current direction (right, up, left, or down). The landing cell must be inside the grid and not yet visited.
- If the move is valid, move to the landing cell and mark it visited. The jumped-over intermediate cell is not marked visited.
- If the move is invalid (out of bounds or landing cell already visited), rotate the current direction 90° counterclockwise (right → up → left → down → right → …) and try again from the same cell.
Stop when all four directions are invalid from your current cell. Return the coordinates [r, c] of the last visited cell.
Constraints
- 1 <= m, n
- Coordinates are 1-based with (1,1) at top-left
- Only landing cells are marked visited; the jumped-over cell is not marked
- Stop when all four directions from the current cell are invalid
- Recommended: m * n <= 200000 for Python solutions
Solution
from typing import List
def last_grid_jump_cell(m: int, n: int) -> List[int]:
# Directions: right, up, left, down (counterclockwise order)
dirs = [(0, 1), (-1, 0), (0, -1), (1, 0)]
r, c = 1, 1
visited = {(r, c)} # store visited landing cells
dir_idx = 0 # start facing right
while True:
attempts = 0
moved = False
while attempts < 4:
dr, dc = dirs[dir_idx]
nr, nc = r + 2 * dr, c + 2 * dc
if 1 <= nr <= m and 1 <= nc <= n and (nr, nc) not in visited:
r, c = nr, nc
visited.add((r, c))
moved = True
break # keep the same direction after a successful move
else:
dir_idx = (dir_idx + 1) % 4 # rotate 90° counterclockwise
attempts += 1
if not moved:
return [r, c]
Explanation
Simulate the process with a visited set for landing cells. Keep a direction pointer in counterclockwise order (right, up, left, down). From the current cell, try to move two cells in the current direction; if landing is invalid (out of bounds or already visited), rotate counterclockwise and try again. If none of the four directions works, stop and return the current cell. Only landing cells are marked visited; the intermediate cell is never marked, which is why moves always change by exactly two units in one axis.
Time complexity: O(m*n) in the worst case (each cell is considered at most once as a landing, with up to four direction checks per step).. Space complexity: O(m*n) in the worst case to store visited landing cells..
Hints
- Track visited landing cells; the intermediate cell is irrelevant to validity checks.
- Maintain a direction index for [right, up, left, down] and rotate counterclockwise only when a move is invalid.
- Terminate when you have attempted (and failed) all four directions from the current position without moving.