Katkat
Back

Solve windowed duplicates and target expression

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

  1. 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.
  2. 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.