How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve windowed duplicates and target expression

Quick 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.

Solve windowed duplicates and target expression

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

Windowed Duplicate Check with Minimum Index Gap

Given an integer array `nums` and an integer `k`, determine whether there exist indices `i` and `j` (i != j) such that `nums[i] == nums[j]` and `|i - j| <= k`. Return a result describing two things: whether such a pair exists, and the minimum index gap among all qualifying pairs. Return `[found, gap]` where `found` is a boolean and `gap` is the smallest `|i - j|` over all valid duplicate pairs, or `-1` if no qualifying pair exists. The target is an O(n) time solution that uses at most O(k) extra space. While scanning left to right, keep only entries that are still within distance `k` of the current index (evict stale entries using a sliding window — e.g. a hash map plus a moving front pointer, or a hash set of the last k elements). Because two equal values that are closer together always produce a smaller gap than ones farther apart, tracking the most recent previous index of each value is sufficient to find the minimum gap. Examples: - nums = [1, 2, 3, 1], k = 3 -> [true, 3] - nums = [1, 0, 1, 1], k = 1 -> [true, 1] (indices 2 and 3) - nums = [1, 2, 3, 1, 2, 3], k = 2 -> [false, -1] (nearest duplicate is 3 apart, exceeds k)

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= len(nums)
When no qualifying pair exists, return [False, -1]
The minimum index gap is always >= 1 when a pair exists

Examples

Input: ([1, 2, 3, 1], 3)

Expected Output: [True, 3]

Explanation: nums[0]==nums[3]==1 with gap 3 <= 3, so a pair exists and the minimum gap is 3.

Input: ([1, 0, 1, 1], 1)

Expected Output: [True, 1]

Explanation: Indices 2 and 3 both hold 1 with gap 1 <= 1; that is the smallest possible gap.

Input: ([1, 2, 3, 1, 2, 3], 2)

Expected Output: [False, -1]

Explanation: Every duplicate (the 1s, 2s, 3s) is exactly 3 apart, which exceeds k=2, so no qualifying pair exists.

Input: ([], 0)

Expected Output: [False, -1]

Explanation: Empty array has no elements and therefore no pairs.

Input: ([5], 3)

Expected Output: [False, -1]

Explanation: A single element cannot form a pair.

Input: ([1, 1, 1, 1], 2)

Expected Output: [True, 1]

Explanation: Adjacent equal elements give gap 1, the minimum possible.

Input: ([-2, -2, 4, -2], 3)

Expected Output: [True, 1]

Explanation: Indices 0 and 1 hold -2 with gap 1; negatives are handled the same as any other value.

Input: ([4, 5, 6, 4], 0)

Expected Output: [False, -1]

Explanation: The only duplicate (4 at indices 0 and 3) is gap 3, but k=0 requires gap <= 0, so no pair qualifies.

Hints

Storing the most recent index of each value is enough: for any value, the closest pair of equal entries is always the two consecutive occurrences, so comparing each element only against its previous occurrence finds the global minimum gap.
To bound space to O(k), keep a sliding window — drop the entry for the element that falls out of range as the index advances (a hash set of the last k values, or a hash map plus a front pointer). Scanning the whole map to evict on every step would push time to O(n*k); the front pointer keeps it O(n).
Track the best (smallest) gap seen so far; you can stop early only if you find a gap of 1, which is the minimum possible.

Target Expression from Digits 1 to 9

Given the fixed digit string "123456789" (the digits 1 through 9 in order) and a target integer `target`, insert between consecutive digits one of: `'+'`, `'-'`, or nothing (concatenation, which fuses adjacent digits into a multi-digit number). You may also place a leading `'+'` or `'-'` before the first digit. Determine whether any resulting expression evaluates to `target`, and if so return one valid expression string; otherwise return the empty string `""`. Use DFS / backtracking that consumes the digits left to right and evaluates the running total on the fly (without reparsing the string at the end). For each digit after the first, branch three ways: concatenate it onto the current trailing operand, or start a new operand preceded by `'+'`, or start a new operand preceded by `'-'`. Because the source digits are 1..9 there are never any zeros, so leading-zero numbers cannot occur here — but the general technique must guard against operands like `0X`. This solution returns the first expression found under a fixed branch order (concatenation first, then `'+'`, then `'-'`; the first digit is tried as implicit-plus, then leading `'+'`, then leading `'-'`), so its output is deterministic. Examples: - target = 100 -> "123+45-67+8-9" - target = 0 -> "12+34-56-7+8+9" - target = 99999 -> "" (unreachable)

Constraints

The digit string is fixed as "123456789"
-10^9 <= target <= 10^9
Allowed inserts between digits: '+', '-', or nothing (concatenation)
A leading '+' or '-' may precede the first digit
Return the empty string "" when no expression evaluates to target
The returned expression, when evaluated, must equal target exactly

Examples

Input: (100,)

Expected Output: '123+45-67+8-9'

Explanation: 123 + 45 - 67 + 8 - 9 = 100; this is the first expression found under the concat-first branch order.

Input: (45,)

Expected Output: '12+34-5-6-7+8+9'

Explanation: 12 + 34 - 5 - 6 - 7 + 8 + 9 = 45.

Input: (0,)

Expected Output: '12+34-56-7+8+9'

Explanation: 12 + 34 - 56 - 7 + 8 + 9 = 0; a target of zero is reachable.

Input: (1,)

Expected Output: '12+34+5-67+8+9'

Explanation: 12 + 34 + 5 - 67 + 8 + 9 = 1.

Input: (-45,)

Expected Output: '12+3+4-56-7+8-9'

Explanation: 12 + 3 + 4 - 56 - 7 + 8 - 9 = -45; negative targets are reachable using subtraction.

Input: (363,)

Expected Output: '-12+345+6+7+8+9'

Explanation: -12 + 345 + 6 + 7 + 8 + 9 = 363; here a leading '-' is required because no implicit-plus arrangement reaches 363 first.

Input: (123456789,)

Expected Output: '123456789'

Explanation: Concatenating every digit with no operators yields the maximum value 123456789.

Input: (99999,)

Expected Output: ''

Explanation: No insertion of +, -, or concatenation over 1..9 evaluates to 99999, so the empty string is returned.

Input: (7,)

Expected Output: '1+23+4-5-6+7-8-9'

Explanation: 1 + 23 + 4 - 5 - 6 + 7 - 8 - 9 = 7.

Hints

Carry the running total through the recursion instead of building then re-parsing. To support concatenation you must remember the signed value of the operand currently being built, so that fusing a new digit means subtracting the old operand from the total and adding back the operand grown by one digit (last_sign * (last_num*10 + d)).
Branch order makes the result deterministic: at each gap try concatenation, then '+', then '-'. For the very first digit, try it as a plain positive operand first, and only fall back to an explicit leading '+' or leading '-' if nothing else reaches the target.
Pruning: this input is small, but in general you can bound the reachable range — once the partial total plus the maximum positive contribution of the remaining digits is below target (or partial minus the maximum negative contribution is above target), that branch can be abandoned. Watch for integer overflow when concatenating many digits in lower-level languages (use 64-bit accumulators).

Quick Overview

Solve windowed duplicates and target expression

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Windowed Duplicate Check with Minimum Index Gap

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= len(nums)
When no qualifying pair exists, return [False, -1]
The minimum index gap is always >= 1 when a pair exists

Examples

Input: ([1, 2, 3, 1], 3)

Expected Output: [True, 3]

Explanation: nums[0]==nums[3]==1 with gap 3 <= 3, so a pair exists and the minimum gap is 3.

Input: ([1, 0, 1, 1], 1)

Expected Output: [True, 1]

Explanation: Indices 2 and 3 both hold 1 with gap 1 <= 1; that is the smallest possible gap.

Input: ([1, 2, 3, 1, 2, 3], 2)

Expected Output: [False, -1]

Explanation: Every duplicate (the 1s, 2s, 3s) is exactly 3 apart, which exceeds k=2, so no qualifying pair exists.

Input: ([], 0)

Expected Output: [False, -1]

Explanation: Empty array has no elements and therefore no pairs.

Input: ([5], 3)

Expected Output: [False, -1]

Explanation: A single element cannot form a pair.

Input: ([1, 1, 1, 1], 2)

Expected Output: [True, 1]

Explanation: Adjacent equal elements give gap 1, the minimum possible.

Input: ([-2, -2, 4, -2], 3)

Expected Output: [True, 1]

Explanation: Indices 0 and 1 hold -2 with gap 1; negatives are handled the same as any other value.

Input: ([4, 5, 6, 4], 0)

Expected Output: [False, -1]

Explanation: The only duplicate (4 at indices 0 and 3) is gap 3, but k=0 requires gap <= 0, so no pair qualifies.

Hints

Storing the most recent index of each value is enough: for any value, the closest pair of equal entries is always the two consecutive occurrences, so comparing each element only against its previous occurrence finds the global minimum gap.
To bound space to O(k), keep a sliding window — drop the entry for the element that falls out of range as the index advances (a hash set of the last k values, or a hash map plus a front pointer). Scanning the whole map to evict on every step would push time to O(n*k); the front pointer keeps it O(n).
Track the best (smallest) gap seen so far; you can stop early only if you find a gap of 1, which is the minimum possible.

Target Expression from Digits 1 to 9

Constraints

The digit string is fixed as "123456789"
-10^9 <= target <= 10^9
Allowed inserts between digits: '+', '-', or nothing (concatenation)
A leading '+' or '-' may precede the first digit
Return the empty string "" when no expression evaluates to target
The returned expression, when evaluated, must equal target exactly

Examples

Input: (100,)

Expected Output: '123+45-67+8-9'

Explanation: 123 + 45 - 67 + 8 - 9 = 100; this is the first expression found under the concat-first branch order.

Input: (45,)

Expected Output: '12+34-5-6-7+8+9'

Explanation: 12 + 34 - 5 - 6 - 7 + 8 + 9 = 45.

Input: (0,)

Expected Output: '12+34-56-7+8+9'

Explanation: 12 + 34 - 56 - 7 + 8 + 9 = 0; a target of zero is reachable.

Input: (1,)

Expected Output: '12+34+5-67+8+9'

Explanation: 12 + 34 + 5 - 67 + 8 + 9 = 1.

Input: (-45,)

Expected Output: '12+3+4-56-7+8-9'

Explanation: 12 + 3 + 4 - 56 - 7 + 8 - 9 = -45; negative targets are reachable using subtraction.

Input: (363,)

Expected Output: '-12+345+6+7+8+9'

Explanation: -12 + 345 + 6 + 7 + 8 + 9 = 363; here a leading '-' is required because no implicit-plus arrangement reaches 363 first.

Input: (123456789,)

Expected Output: '123456789'

Explanation: Concatenating every digit with no operators yields the maximum value 123456789.

Input: (99999,)

Expected Output: ''

Explanation: No insertion of +, -, or concatenation over 1..9 evaluates to 99999, so the empty string is returned.

Input: (7,)

Expected Output: '1+23+4-5-6+7-8-9'

Explanation: 1 + 23 + 4 - 5 - 6 + 7 - 8 - 9 = 7.

Hints

Carry the running total through the recursion instead of building then re-parsing. To support concatenation you must remember the signed value of the operand currently being built, so that fusing a new digit means subtracting the old operand from the total and adding back the operand grown by one digit (last_sign * (last_num*10 + d)).
Branch order makes the result deterministic: at each gap try concatenation, then '+', then '-'. For the very first digit, try it as a plain positive operand first, and only fall back to an explicit leading '+' or leading '-' if nothing else reaches the target.
Pruning: this input is small, but in general you can bound the reachable range — once the partial total plus the maximum positive contribution of the remaining digits is below target (or partial minus the maximum negative contribution is above target), that branch can be abandoned. Watch for integer overflow when concatenating many digits in lower-level languages (use 64-bit accumulators).