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 Onsite rounds at NVIDIA.

What role is this question designed for?

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

Apply sliding window techniques | NVIDIA Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Apply sliding window techniques states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Apply sliding window techniques

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Explain the sliding window technique and apply it to solve: ( 1) Given an array of positive integers and a target S, return the minimal length of a contiguous subarray with sum ≥ S (or 0 if none); ( 2) Given a string and an integer K, return the length of the longest substring containing at most K distinct characters; Analyze time and space complexity and when to use fixed vs. dynamic windows.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Apply sliding window techniques states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Minimum Size Subarray Sum

Given an array of positive integers `nums` and a positive integer `s`, return the minimal length of a contiguous subarray of which the sum is greater than or equal to `s`. If there is no such subarray, return 0. This is the classic dynamic (variable-size) sliding window: expand the right edge to grow the window sum, and as soon as the sum reaches the target, shrink from the left while it still satisfies the constraint, recording the smallest valid window length seen. Example: - nums = [2, 3, 1, 2, 4, 3], s = 7 -> 2 (the subarray [4, 3] has sum 7 with minimal length 2).

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
1 <= s <= 10^9
All integers in nums are positive (this is what makes the shrink-while-valid invariant correct).

Examples

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

Expected Output: 2

Explanation: The subarray [4, 3] has sum 7 >= 7 and length 2, which is the minimum.

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

Expected Output: 1

Explanation: A single element 4 already reaches the target, so the minimal length is 1.

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

Expected Output: 0

Explanation: The total sum is 8, which is less than 11, so no valid subarray exists; return 0.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array has no subarray reaching the target; return 0.

Input: ([5], 5)

Expected Output: 1

Explanation: The single element equals the target exactly, so the minimal length is 1.

Input: ([1, 2, 3, 4, 5], 11)

Expected Output: 3

Explanation: The subarray [3, 4, 5] sums to 12 >= 11 with length 3; no length-2 window reaches 11.

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

Expected Output: 0

Explanation: The whole array sums to 15 < 100, so no subarray qualifies; return 0.

Hints

Use two pointers forming a window. Move the right pointer to include elements and grow the running sum.
Whenever the running sum is >= s, the current window is valid: record its length, then shrink from the left to look for a shorter valid window.
Because all numbers are positive, removing from the left strictly decreases the sum, so the while-shrink loop is safe and the total pointer movement is O(n).

Longest Substring with At Most K Distinct Characters

Given a string `s` and an integer `k`, return the length of the longest substring of `s` that contains at most `k` distinct characters. This is a dynamic sliding window where the window grows greedily on the right; when the number of distinct characters exceeds `k`, shrink from the left until the constraint holds again. A hash map tracks the count of each character currently in the window so the distinct count can be maintained in O(1) per step. Example: - s = "eceba", k = 2 -> 3 (the substring "ece" has 2 distinct characters and length 3).

Constraints

0 <= s.length <= 10^5
0 <= k <= 50 (or up to the size of the character set)
s consists of arbitrary characters; an empty string or k = 0 should return 0.

Examples

Input: ("eceba", 2)

Expected Output: 3

Explanation: The substring "ece" uses exactly 2 distinct characters and has length 3, the longest possible.

Input: ("aa", 1)

Expected Output: 2

Explanation: Only one distinct character, so the whole string of length 2 qualifies.

Input: ("abcadcacacaca", 3)

Expected Output: 11

Explanation: The substring "cadcacacaca" uses the 3 distinct characters a, c, d and has length 11.

Input: ("", 2)

Expected Output: 0

Explanation: Empty string has no characters, so the answer is 0.

Input: ("abc", 0)

Expected Output: 0

Explanation: With k = 0, no character is allowed, so the longest valid substring has length 0.

Input: ("aabbcc", 1)

Expected Output: 2

Explanation: With only 1 distinct character allowed, the best windows are "aa", "bb", or "cc", each of length 2.

Input: ("a", 5)

Expected Output: 1

Explanation: k exceeds the number of distinct characters, so the entire string of length 1 qualifies.

Hints

Maintain a window [left, right] and a hash map from character to its count inside the window.
Extend the right edge each step. When the map has more than k distinct keys, shrink from the left, decrementing counts and deleting a key when its count hits zero.
After every adjustment the window is valid (at most k distinct), so update the best length with right - left + 1. Handle k = 0 and the empty string by returning 0.

Quick Overview