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

What role is this question designed for?

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

Solve four coding problems | Nebius Coding Question

Q: Solve four coding problems

This set of problems evaluates algorithmic problem-solving skills focused on array and string manipulation, frequency and multiset reasoning, sliding-window and coverage concepts, and combinatorial counting for palindromability.

Solve four coding problems

Company: Nebius

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

The interview included four independent coding problems: 1. **Longest all-healthy service streak** You are given the daily health-check results for multiple microservices. Each day is considered **healthy** only if **every** microservice passed its health check on that day. Find the maximum number of consecutive healthy days. 2. **Shortest substring covering all distinct characters** You are given a string `s`. Find the length of the shortest substring that contains **every distinct character that appears anywhere in `s`** at least once. 3. **Minimize remaining product types after deletions** You are given a list of product IDs and an integer `m`. In one operation, you may delete one occurrence of any product ID. After performing exactly `m` deletions, minimize the number of distinct product IDs that remain. Return that minimum number. 4. **Count string pairs that can form a palindrome** You are given an array of strings. Count how many pairs of strings `(i, j)` with `i < j` have the property that, after combining all characters from both strings and reordering them arbitrarily, the result can form a palindrome.

Quick Answer: This set of problems evaluates algorithmic problem-solving skills focused on array and string manipulation, frequency and multiset reasoning, sliding-window and coverage concepts, and combinatorial counting for palindromability.

Part 1: Longest All-Healthy Service Streak

You are given a 2D list `results` where `results[d][s]` is `1` if microservice `s` passed its health check on day `d`, and `0` otherwise. A day is considered healthy only if every microservice passed on that day. Return the maximum number of consecutive healthy days.

Constraints

0 <= len(results) <= 100000
If `results` is non-empty, each day contains the same number of services and at least 1 service
Each value is either 0 or 1

Examples

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

Expected Output: 3

Explanation: The first two days are healthy, the third day breaks the streak, and the last three days form the longest healthy streak.

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

Expected Output: 0

Explanation: No day has all services passing.

Input: ([],)

Expected Output: 0

Explanation: With no days, there is no healthy streak.

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

Expected Output: 1

Explanation: The single day is healthy.

Hints

First decide for each day whether it is healthy or not.
Then scan the days and track the longest consecutive run of healthy ones.

Part 2: Shortest Substring Covering All Distinct Characters

You are given a string `s`. Find the length of the shortest substring that contains every distinct character that appears anywhere in `s` at least once. If `s` is empty, return `0`.

Constraints

0 <= len(s) <= 200000
Characters may repeat arbitrarily
The solution should be efficient for long strings

Examples

Input: ("aabcbcdbca",)

Expected Output: 4

Explanation: The distinct characters are a, b, c, and d. The shortest substring containing all of them is "dbca".

Input: ("aaaa",)

Expected Output: 1

Explanation: There is only one distinct character, so any single 'a' works.

Input: ("",)

Expected Output: 0

Explanation: An empty string has no required characters.

Input: ("abca",)

Expected Output: 3

Explanation: The distinct characters are a, b, and c. "abc" or "bca" has length 3.

Input: ("abcdef",)

Expected Output: 6

Explanation: Every character is distinct, so the whole string is required.

Hints

Count how many unique characters exist in the whole string first.
A sliding window can expand to satisfy the requirement and shrink to find the minimum length.

Part 3: Minimize Remaining Product Types After Deletions

You are given a list of product IDs and an integer `m`. In one operation, you may delete one occurrence of any product ID. After performing exactly `m` deletions, minimize the number of distinct product IDs that remain. Return that minimum number.

Constraints

0 <= len(product_ids) <= 200000
0 <= m <= len(product_ids)
Product IDs are integers

Examples

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

Expected Output: 1

Explanation: Delete product 3 once and product 2 twice. Only product 1 remains.

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

Expected Output: 2

Explanation: The best choice is to remove the two IDs with frequency 1, then one extra deletion cannot remove another ID completely.

Input: ([], 0)

Expected Output: 0

Explanation: There are no products to begin with.

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

Expected Output: 1

Explanation: No deletions are made, so the one existing product type remains.

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

Expected Output: 0

Explanation: All products can be deleted.

Hints

A distinct ID disappears only when all of its occurrences are deleted.
To remove the most distinct IDs, eliminate the IDs with the smallest frequencies first.

Part 4: Count String Pairs That Can Form a Palindrome

You are given an array `words` of lowercase English strings. Count how many pairs `(i, j)` with `i < j` have the property that after combining all characters from `words[i]` and `words[j]` and reordering them arbitrarily, the result can form a palindrome.

Constraints

0 <= len(words) <= 200000
0 <= sum(len(word) for word in words) <= 200000
Each string contains only lowercase English letters 'a' to 'z'

Examples

Input: (["abc","cba","xy","yx"],)

Expected Output: 2

Explanation: The valid pairs are ("abc", "cba") and ("xy", "yx").

Input: (["a","","bb","ab"],)

Expected Output: 4

Explanation: The valid pairs are ("a", ""), ("a", "bb"), ("a", "ab"), and ("", "bb").

Input: ([],)

Expected Output: 0

Explanation: There are no pairs in an empty list.

Input: (["abc","def"],)

Expected Output: 0

Explanation: The combined characters of the only pair have too many odd counts to form a palindrome.

Input: (["a","b","c","ab"],)

Expected Output: 2

Explanation: The valid pairs are ("a", "ab") and ("b", "ab").

Hints

A multiset of characters can be rearranged into a palindrome if at most one character has an odd count.
For each string, track only which letters have odd frequency, using a bitmask.

Quick Overview

This set of problems evaluates algorithmic problem-solving skills focused on array and string manipulation, frequency and multiset reasoning, sliding-window and coverage concepts, and combinatorial counting for palindromability.