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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Solve Three Algorithmic Problems | Meta Coding Question

Solve Three Algorithmic Problems

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Three coding questions were mentioned: 1. **Second-largest distinct permutation** Given an array of integers that may contain duplicates, consider all distinct permutations of the array ordered from largest to smallest in lexicographic order. Return the second-largest distinct permutation. Examples: - `[1, 2, 3, 4, 5] -> [5, 4, 3, 1, 2]` - `[1, 1, 5] -> [1, 5, 1]` You may assume there are at least two distinct permutations. 2. **Merge m sorted arrays and return first k values** You are given `m` integer arrays, each already sorted in non-decreasing order. Return the first `k` values in globally sorted order across all arrays. Preserve duplicates. 3. **Choose a subset of words with no repeated characters** Given a list of words, choose a subset whose concatenation contains no repeated characters. Maximize the total number of unique characters in the concatenated result. A word that contains duplicate characters internally cannot be part of any valid solution unless those duplicates are allowed by the rules; assume the final concatenation must contain each character at most once. Discuss an algorithm that still works when the input contains thousands of words.

Quick Answer: This set of problems evaluates algorithmic problem-solving skills such as reasoning about permutations and duplicate handling, efficiently merging multiple sorted arrays, and combinatorial selection under character-uniqueness constraints.

Part 1: Second-Largest Distinct Permutation

Given an integer array nums that may contain duplicates, consider all distinct permutations of nums ordered from largest to smallest in lexicographic order. Return the second permutation in that ordering. You may assume there are at least two distinct permutations.

Constraints

2 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
There are at least two distinct permutations of nums, so not all elements are identical.

Examples

Input: [1, 2, 3, 4, 5]

Expected Output: [5, 4, 3, 1, 2]

Explanation: The largest permutation is [5, 4, 3, 2, 1], and the next distinct one below it is [5, 4, 3, 1, 2].

Input: [1, 1, 5]

Expected Output: [1, 5, 1]

Explanation: Distinct permutations in descending lexicographic order are [5, 1, 1], [1, 5, 1], [1, 1, 5].

Input: [2, 2, 1]

Expected Output: [2, 1, 2]

Explanation: This checks that duplicates are handled correctly and only distinct permutations matter.

Input: [7, 3]

Expected Output: [3, 7]

Explanation: Edge case with only two elements. There are exactly two distinct permutations.

Hints

What is the largest lexicographic permutation you can build from the multiset of values?
After building the largest one, apply the previous-permutation idea exactly once.

Part 2: Merge M Sorted Arrays and Return First K Values

You are given m integer arrays, each already sorted in non-decreasing order. Return the first k values in globally sorted order across all arrays. Preserve duplicates. If the total number of available values is less than k, return all of them.

Constraints

0 <= len(arrays) <= 100000
Each inner array is sorted in non-decreasing order
0 <= total number of elements across all arrays <= 200000
0 <= k <= 200000

Examples

Input: ([[1, 4, 7], [2, 5], [3, 6, 8]], 5)

Expected Output: [1, 2, 3, 4, 5]

Explanation: The global sorted order begins 1, 2, 3, 4, 5, 6, 7, 8.

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

Expected Output: [1, 1, 1, 2]

Explanation: Duplicates must be preserved, and empty arrays should be ignored.

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

Expected Output: []

Explanation: Edge case: all arrays are empty.

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

Expected Output: [-3, -2, 0, 2, 2, 5]

Explanation: If k exceeds the total number of elements, return everything in sorted order.

Hints

You do not need to merge every value if you only need the first k answers.
Keep one candidate from each non-empty array in a min-heap.

Part 3: Maximum Unique-Character Concatenation

Given a list of lowercase words, choose a subset whose concatenation contains no repeated characters. Return the maximum possible number of characters in such a concatenation. Any word that repeats a character inside itself cannot be part of a valid answer. Your algorithm should remain practical even when the input contains thousands of words.

Constraints

0 <= len(words) <= 5000
0 <= len(word) <= 26
Each word contains only lowercase English letters a-z

Examples

Input: ["un", "iq", "ue"]

Expected Output: 4

Explanation: One optimal choice is ["un", "iq"], which gives 4 unique characters.

Input: ["ab", "cd", "aef", "gh"]

Expected Output: 7

Explanation: Choosing ["cd", "aef", "gh"] yields 7 unique characters.

Input: []

Expected Output: 0

Explanation: Edge case: with no words, the best length is 0.

Input: ["aa", "bb", "abc"]

Expected Output: 3

Explanation: Words "aa" and "bb" are invalid because they repeat characters internally, so only "abc" can be used.

Input: ["abcdefghijklmnopqrstuvwxyz", "a", "bc"]

Expected Output: 26

Explanation: The full alphabet word is already a valid optimal solution.

Hints

Convert each valid word into a 26-bit mask. If a word contains the same letter twice, discard it immediately.
Because there are only 26 possible letters, memoizing by a letter-mask state can be far more scalable than naive subset enumeration over all words.

Quick Overview

This set of problems evaluates algorithmic problem-solving skills such as reasoning about permutations and duplicate handling, efficiently merging multiple sorted arrays, and combinatorial selection under character-uniqueness constraints.