Katkat
Back

Solve max-subarray, min-unique, and grid-jump

CiscoSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

  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(
  2. extra space, and explain how your algorithm handles all-negative arrays.
  3. 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).
  4. On an m×n grid indexed from (1,
  5. 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.