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.

Hints

  1. Expand the window with a right pointer; shrink from the left whenever the distinct-character count exceeds k.
  2. Maintain a hash map of character counts and a running distinct counter to update the window in O(1) per step.
  3. 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.

Hints

  1. Each undirected edge contributes to BOTH of its endpoints, so process u and v separately for each edge.
  2. For each node keep a min-heap capped at size k of its largest positive weights; replace the smallest when a larger one arrives.
  3. 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.

Hints

  1. 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.
  2. Scan left to right, keep a running count of 1s seen so far.
  3. When you hit a 0, add the current count of 1s to the total — no nested loop needed.

Loading coding console...