Solve windowed duplicates and target expression
Overview
This question evaluates proficiency in windowed duplicate detection and time-space trade-offs for streaming or bounded-range scans, along with combinatorial expression generation and on-the-fly numeric evaluation using search, reflecting skills in algorithm design, data-structure selection, and numeric correctness.
Meta
Aug 13, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0
- Windowed duplicate check: Given an integer array nums and an integer k, determine whether there exist indices i and j such that nums[i] == nums[j] and |i - j| <= k. If such pairs exist, also return the minimum index gap among them. Design an O(n) time solution that uses at most O(k) extra space. Explain how to evict stale entries while scanning (e.g., hash map plus queue or a moving front pointer), and analyze the time/space trade-offs. Provide code and complexity analysis.
- Target expression from 1..9: Given the string "123456789" (digits 1 through 9 in order) and a target integer T, insert between digits either '+', '-', or nothing (concatenation). You may also place a leading '+' or '-' before the first digit. Determine if any resulting expression evaluates to T; if so, return one valid expression (or all). Implement a DFS/backtracking approach that builds expressions and evaluates them on the fly (without reparsing), handles concatenation, avoids leading-zero numbers, discusses pruning strategies and complexity, and addresses integer-overflow considerations.