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 Take-home Project rounds at Akuna Capital.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Akuna Capital during technical interviews.

Solve sliding window, graph top-k, and greedy tasks

Quick Overview

This multi-part question evaluates proficiency in algorithm design and data-structure use across sliding-window string processing, top-k aggregation on weighted graphs, and greedy counting on binary arrays within the Coding & Algorithms domain, emphasizing string and graph algorithms, top-k/heap techniques, and greedy pattern recognition.

Solve sliding window, graph top-k, and greedy tasks

Company: Akuna Capital

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

You have three coding tasks. Task 1 — Sliding window on strings: Given a string s and an integer k, find one longest substring of s that contains at most k distinct characters. Return the start index and length of such a substring (return the earliest start if multiple solutions have the same length). Aim for O(n) time and O(k) extra space using a sliding window. Task 2 — Top-k positive neighbors in a weighted graph: Given an undirected weighted graph with n nodes labeled 0..n-1 and an edge list edges where each edge is (u, v, w) with integer weight w (possibly negative), compute for every node v the sum of the weights of up to k incident edges with the largest positive weights. If a node has no incident edges with positive weight, its sum is 0. Return an array sums of length n where sums[v] is that sum. Target complexity O(m log k) time and O(n + m) space, where m = |edges|. Task 3 — Greedy counting on a binary array: Given an array A of length n consisting only of 0s and 1s, compute the total number of pairs (i, j) such that i < j, A[i] = 1, and A[j] = 0. Interpret this value as the minimum number of adjacent swaps needed to move all 1s to the end of the array. Aim for O(n) time and O( 1) extra space by maintaining a running count of 1s encountered.

Quick Answer: This multi-part question evaluates proficiency in algorithm design and data-structure use across sliding-window string processing, top-k aggregation on weighted graphs, and greedy counting on binary arrays within the Coding & Algorithms domain, emphasizing string and graph algorithms, top-k/heap techniques, and greedy pattern recognition.

Longest Substring with At Most K Distinct Characters

Given a string `s` and an integer `k`, find one longest substring of `s` that contains at most `k` distinct characters. Return the start index and length of such a substring as `[start, length]`. If multiple substrings share the maximum length, return the one with the earliest start index. If `k <= 0` or `s` is empty, return `[0, 0]`. Aim for O(n) time and O(k) extra space using a sliding window.

Constraints

0 <= len(s) <= 10^5
s consists of lowercase/uppercase English letters
0 <= k <= 26
Return the earliest start index when lengths tie

Examples

Input: ("eceba", 2)

Expected Output: [0, 3]

Explanation: 'ece' (indices 0..2) has distinct {e,c}=2; it is the longest window with at most 2 distinct characters.

Input: ("aa", 1)

Expected Output: [0, 2]

Explanation: The whole string has 1 distinct character, satisfying k=1.

Input: ("abcabcbb", 2)

Expected Output: [4, 4]

Explanation: 'bcbb' (indices 4..7) has distinct {b,c}=2 and length 4, the longest valid window.

Input: ("", 3)

Expected Output: [0, 0]

Explanation: Empty string yields an empty result.

Input: ("abc", 0)

Expected Output: [0, 0]

Explanation: k=0 admits no non-empty substring, so length is 0.

Input: ("aaaa", 5)

Expected Output: [0, 4]

Explanation: Only 1 distinct character; the whole string fits within k=5.

Input: ("abaccc", 2)

Expected Output: [2, 4]

Explanation: 'accc' (indices 2..5) has distinct {a,c}=2 and length 4, the earliest longest valid window.

Hints

Expand the window with a right pointer; shrink from the left whenever the distinct-character count exceeds k.
Maintain a hash map of character counts and a running distinct counter to update the window in O(1) per step.
Track the best (start, length) only when a strictly longer window is found, which preserves the earliest start on ties.

Top-K Positive Incident Edge Weight Sum per Node

Given an undirected weighted graph with `n` nodes labeled `0..n-1` and an edge list `edges` where each edge is `[u, v, w]` with integer weight `w` (possibly negative), compute for every node `v` the sum of the weights of up to `k` incident edges with the largest positive weights. If a node has no incident edges with positive weight, its sum is 0. Return an array `sums` of length `n` where `sums[v]` is that sum. Target complexity O(m log k) time and O(n + m) space, where m = |edges|.

Constraints

1 <= n <= 10^5
0 <= |edges| <= 2*10^5
each edge is [u, v, w] with 0 <= u, v < n and -10^9 <= w <= 10^9
0 <= k <= n
Only edges with strictly positive weight count toward a node's sum

Examples

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

Expected Output: [8, 9, 7, 0]

Explanation: Node 0: positives {5,3} -> 8. Node 1: {5,4} -> 9. Node 2: {3,4} -> 7. Node 3: only -2 -> 0.

Input: (3, [[0,1,-1],[1,2,-5]], 2)

Expected Output: [0, 0, 0]

Explanation: No edge has positive weight, so every node sums to 0.

Input: (1, [], 3)

Expected Output: [0]

Explanation: A single isolated node has no incident edges.

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

Expected Output: [10, 10]

Explanation: The single positive edge contributes to both endpoints.

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

Expected Output: [7, 7, 0]

Explanation: Parallel edges: top 2 positive weights for nodes 0 and 1 are {4,3} -> 7; node 2 isolated -> 0.

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

Expected Output: [0, 0]

Explanation: k=0 means no edges may be counted, so both sums are 0.

Hints

Each undirected edge contributes to BOTH of its endpoints, so process u and v separately for each edge.
For each node keep a min-heap capped at size k of its largest positive weights; replace the smallest when a larger one arrives.
Ignore non-positive weights entirely; a node's answer is the sum of whatever remains in its capped heap (0 if empty).

Minimum Adjacent Swaps to Move All 1s to the End

Given an array `A` of length `n` consisting only of 0s and 1s, compute the total number of pairs (i, j) such that i < j, A[i] = 1, and A[j] = 0. This value equals the minimum number of adjacent swaps needed to move all 1s to the end of the array. Aim for O(n) time and O(1) extra space by maintaining a running count of the 1s encountered so far and adding it to the answer each time a 0 is seen.

Constraints

0 <= n <= 10^5
A[i] is 0 or 1
The answer can be as large as ~n^2/4, so use a 64-bit accumulator in Java/C++

Examples

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

Expected Output: 3

Explanation: 1 at index 0 precedes 0s at indices 1,3 (2 pairs); 1 at index 2 precedes 0 at index 3 (1 pair); total 3.

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

Expected Output: 0

Explanation: No 1s, so no pairs.

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

Expected Output: 0

Explanation: No 0s, so no pairs.

Input: ([1,0],)

Expected Output: 1

Explanation: One 1 before one 0 -> a single swap.

Input: ([0,1],)

Expected Output: 0

Explanation: The 1 comes after the 0, forming no qualifying pair.

Input: ([],)

Expected Output: 0

Explanation: Empty array has no pairs.

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

Expected Output: 4

Explanation: Two 1s each precede two 0s: 2*2 = 4 pairs.

Hints

Every 1 that appears before a given 0 forms one valid pair, which is exactly one adjacent swap to move that 1 past the 0.
Scan left to right, keep a running count of 1s seen so far.
When you hit a 0, add the current count of 1s to the total — no nested loop needed.

Quick Overview

Solve sliding window, graph top-k, and greedy tasks

Company: Akuna Capital

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Longest Substring with At Most K Distinct Characters

Constraints

0 <= len(s) <= 10^5
s consists of lowercase/uppercase English letters
0 <= k <= 26
Return the earliest start index when lengths tie

Examples

Input: ("eceba", 2)

Expected Output: [0, 3]

Explanation: 'ece' (indices 0..2) has distinct {e,c}=2; it is the longest window with at most 2 distinct characters.

Input: ("aa", 1)

Expected Output: [0, 2]

Explanation: The whole string has 1 distinct character, satisfying k=1.

Input: ("abcabcbb", 2)

Expected Output: [4, 4]

Explanation: 'bcbb' (indices 4..7) has distinct {b,c}=2 and length 4, the longest valid window.

Input: ("", 3)

Expected Output: [0, 0]

Explanation: Empty string yields an empty result.

Input: ("abc", 0)

Expected Output: [0, 0]

Explanation: k=0 admits no non-empty substring, so length is 0.

Input: ("aaaa", 5)

Expected Output: [0, 4]

Explanation: Only 1 distinct character; the whole string fits within k=5.

Input: ("abaccc", 2)

Expected Output: [2, 4]

Explanation: 'accc' (indices 2..5) has distinct {a,c}=2 and length 4, the earliest longest valid window.

Hints

Expand the window with a right pointer; shrink from the left whenever the distinct-character count exceeds k.
Maintain a hash map of character counts and a running distinct counter to update the window in O(1) per step.
Track the best (start, length) only when a strictly longer window is found, which preserves the earliest start on ties.

Top-K Positive Incident Edge Weight Sum per Node

Constraints

1 <= n <= 10^5
0 <= |edges| <= 2*10^5
each edge is [u, v, w] with 0 <= u, v < n and -10^9 <= w <= 10^9
0 <= k <= n
Only edges with strictly positive weight count toward a node's sum

Examples

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

Expected Output: [8, 9, 7, 0]

Explanation: Node 0: positives {5,3} -> 8. Node 1: {5,4} -> 9. Node 2: {3,4} -> 7. Node 3: only -2 -> 0.

Input: (3, [[0,1,-1],[1,2,-5]], 2)

Expected Output: [0, 0, 0]

Explanation: No edge has positive weight, so every node sums to 0.

Input: (1, [], 3)

Expected Output: [0]

Explanation: A single isolated node has no incident edges.

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

Expected Output: [10, 10]

Explanation: The single positive edge contributes to both endpoints.

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

Expected Output: [7, 7, 0]

Explanation: Parallel edges: top 2 positive weights for nodes 0 and 1 are {4,3} -> 7; node 2 isolated -> 0.

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

Expected Output: [0, 0]

Explanation: k=0 means no edges may be counted, so both sums are 0.

Hints

Each undirected edge contributes to BOTH of its endpoints, so process u and v separately for each edge.
For each node keep a min-heap capped at size k of its largest positive weights; replace the smallest when a larger one arrives.
Ignore non-positive weights entirely; a node's answer is the sum of whatever remains in its capped heap (0 if empty).

Minimum Adjacent Swaps to Move All 1s to the End

Constraints

0 <= n <= 10^5
A[i] is 0 or 1
The answer can be as large as ~n^2/4, so use a 64-bit accumulator in Java/C++

Examples

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

Expected Output: 3

Explanation: 1 at index 0 precedes 0s at indices 1,3 (2 pairs); 1 at index 2 precedes 0 at index 3 (1 pair); total 3.

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

Expected Output: 0

Explanation: No 1s, so no pairs.

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

Expected Output: 0

Explanation: No 0s, so no pairs.

Input: ([1,0],)

Expected Output: 1

Explanation: One 1 before one 0 -> a single swap.

Input: ([0,1],)

Expected Output: 0

Explanation: The 1 comes after the 0, forming no qualifying pair.

Input: ([],)

Expected Output: 0

Explanation: Empty array has no pairs.

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

Expected Output: 4

Explanation: Two 1s each precede two 0s: 2*2 = 4 pairs.

Hints

Every 1 that appears before a given 0 forms one valid pair, which is exactly one adjacent swap to move that 1 past the 0.
Scan left to right, keep a running count of 1s seen so far.
When you hit a 0, add the current count of 1s to the total — no nested loop needed.