← Nebius Interview Insights

Nebius·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Interviewed at Nebius for a Software Engineer role and got a string/combinatorics problem that looked deceptively simple but had a neat bitmask trick at its core. The coding round was focused and technical, no fluff.

Questions Asked (1)

Q1

Given a list of lowercase strings, count the number of unordered pairs (i, j) where the combined characters of the two strings can be rearranged into a palindrome.

Algorithms & Data Structures
Author's notes

My first instinct was brute force: check every pair, count character frequencies, see if at most one char has odd count.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the combined characters of two strings can form a palindrome if and only if the XOR of their character parity bitmasks has at most one bit set. Represent each string as a 26-bit mask of character parities, then count pairs of masks whose XOR has popcount ≤ 1 using a hash map for O(n) time.

Pro tip: Mention that the palindrome condition reduces to a parity check, and that using a 26-bit integer mask makes the solution both elegant and efficient. Also, clarify that unordered pairs mean (i, j) with i < j, so you avoid double-counting.

1. Understand the palindrome condition

A string can be rearranged into a palindrome if at most one character has an odd frequency. For two strings combined, this means the XOR of their parity masks has at most one bit set.

2. Encode each string as a bitmask

For each string, compute a 26-bit integer where the i-th bit is 1 if the i-th lowercase letter appears an odd number of times. This captures the parity of character counts.

3. Count pairs with XOR popcount ≤ 1

Use a hash map to store the frequency of each mask seen so far. For each mask, count how many previous masks differ by 0 bits (same mask) or exactly 1 bit (flip each of the 26 bits).

4. Handle unordered pairs and avoid double-counting

Since we process strings in order and only look at previous masks, each unordered pair (i, j) with i < j is counted exactly once. Add the counts to a running total.

5. Analyze complexity and edge cases

Time complexity is O(26 * n) = O(n) and space O(n). Discuss edge cases: empty strings, single-character strings, and strings with all even counts.

Key Points to Mention

  • Palindrome rearrangement condition: at most one character with odd frequency.
  • Bitmask representation: 26 bits for lowercase letters, using XOR to combine parities.
  • XOR of two masks has popcount ≤ 1 if and only if the combined strings can form a palindrome.
  • Hash map to count frequencies of masks for O(n) time.
  • Iterate over 26 possible bit flips (or 27 including zero flips) to find valid pairs.
  • Time complexity O(n) and space O(n), with n as the number of strings.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.