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

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

This is a Coding & Algorithms interview question from Akuna Capital for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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(

extra space by maintaining a running count of 1s encountered.

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

Comments (0)