Solve common interview coding problems
Quick Overview
This set evaluates algorithmic problem-solving, data structure selection, and time/space complexity analysis across common patterns such as maximum subarray (linear and circular variants), nested string decoding, BST validation, task scheduling with cooldowns, sliding-window max-min constraints, and BFS shortest-paths; domain: Coding & Algorithms.
You are given several independent coding tasks (typical of SWE/MLE interview rounds). For each task, design an algorithm and describe the time/space complexity.
1) Maximum subarray sum (Kadane-style)
Input: an integer array nums of length n (may contain negatives).
Task: return the maximum possible sum of any non-empty contiguous subarray.
Constraints (typical): 1 <= n <= 2e5, -1e9 <= nums[i] <= 1e9.
2) Maximum subarray sum in a circular array
Input: an integer array nums of length n, interpreted as circular (after index n-1 comes index 0).
Task: return the maximum possible sum of any non-empty contiguous subarray where the subarray may wrap around the end to the beginning.
Constraints (typical): 1 <= n <= 2e5.
3) Decode an encoded string with nesting
Input: a string s consisting of lowercase letters, digits, and brackets, e.g. "3[a2[c]]".
Encoding rule: k[encoded_string] means encoded_string repeated k times. Encodings may be nested.
Task: return the decoded string.
Constraints (typical): decoded length can be large; avoid quadratic behavior.
4) Validate whether a binary tree is a BST
Input: the root of a binary tree.
Task: return true if it is a valid binary search tree (BST), otherwise false.
BST definition: for every node, all keys in the left subtree are strictly less than the node’s key, and all keys in the right subtree are strictly greater; both subtrees must also be BSTs.
5) Task scheduling with cooldown
Input:
-
a list of tasks
taskswhere each task is an uppercase letterA–Z -
an integer cooldown
n >= 0
Each task takes 1 unit time. The same task type must be separated by at least n time units (idle time allowed).
Task: return the minimum total time units to finish all tasks.
6) Longest subarray under max-min constraint (sliding window)
Input: an integer array nums and an integer limit.
Task: return the length of the longest contiguous subarray such that:
Follow-ups often compare approaches:
- brute force
- maintaining min/max with heaps
- optimizing to linear time
7) BFS shortest path follow-up: 1D to 2D
7a) 1D
Input: a 1D line of N positions (0..N-1), with some blocked positions, a start s, and a target t. From position i, you may move to i-1 or i+1 if in bounds and not blocked.
Task: find the minimum number of moves from s to t (or report unreachable).
7b) 2D follow-up
Input: an R x C grid with blocked cells, start cell, and target cell. Moves are 4-directional.
Task: find the minimum number of moves from start to target (or report unreachable).