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 Technical Screen rounds at Expedia.

What role is this question designed for?

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

Solve three interview coding problems | Expedia Coding Question

Solve three interview coding problems

Company: Expedia

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

This interview report described three coding tasks: 1. **Generate a run-length spoken sequence** Start with `s1 = "1"`. To build the next term, read the current string from left to right, group consecutive identical digits, and write each group as `<count><digit>`. For example, `"1" -> "11" -> "21" -> "1211"`. Given an integer `n`, return the `n`th term of the sequence. 2. **Count substrings that can be rearranged into a palindrome** Given a list of lowercase strings, compute the answer for each string independently. For a single string `s`, count how many non-empty contiguous substrings can be rearranged, by swapping characters, into a palindrome. Example: for `s = "aabb"`, the answer is `9`. 3. **Replace wildcards to satisfy a digit-sum constraint** You are given a numeric string such as `"08??840"`, a target sum `24`, and the rule that each `?` must be replaced by a digit from `0` to `8` inclusive. Return all possible completed strings whose digits sum to the target. For example, valid outputs for `"08??840"` with target sum `24` are: - `"0804840"` - `"0813840"` - `"0822840"` - `"0840840"` Return the complete set of valid strings in any order.

Quick Answer: This multi-part question evaluates string manipulation, combinatorial counting, and constrained enumeration skills through sequence generation, palindromic-anagram substring counting, and wildcard digit-sum completion tasks.

Part 1: Generate a Run-Length Spoken Sequence

Start with s1 = "1". To create the next term, scan the current term from left to right, group consecutive equal digits, and write each group as <count><digit>. For example, "1" -> "11" -> "21" -> "1211". Given an integer n, return the nth term of this sequence.

Constraints

1 <= n <= 25
The answer fits in memory.

Examples

Input: 1

Expected Output: "1"

Explanation: Edge case: the first term is the starting value itself.

Input: 2

Expected Output: "11"

Explanation: Read "1" as one 1.

Input: 4

Expected Output: "1211"

Explanation: "1" -> "11" -> "21" -> "1211".

Input: 6

Expected Output: "312211"

Explanation: Continuing the sequence gives the sixth term as "312211".

Hints

Build the sequence iteratively from term 1 up to term n.
When converting one term into the next, count consecutive equal digits with a loop or two pointers.

Part 2: Count Substrings That Can Be Rearranged Into a Palindrome

You are given a list of lowercase strings. For each string independently, count how many non-empty contiguous substrings can be rearranged into a palindrome. A substring can be rearranged into a palindrome if and only if at most one character appears an odd number of times. Return the counts in the same order as the input strings.

Constraints

0 <= len(strings) <= 10^4
0 <= len(s) for each s in strings
Sum of lengths of all strings <= 2 * 10^5
Each string contains only characters 'a' to 'z'

Examples

Input: ["aabb"]

Expected Output: [9]

Explanation: There are 9 non-empty substrings of "aabb" that can be rearranged into a palindrome.

Input: ["abc", "aaaa"]

Expected Output: [3, 10]

Explanation: "abc" contributes only its three single-character substrings. Every non-empty substring of "aaaa" works, so its count is 10.

Input: [""]

Expected Output: [0]

Explanation: Edge case: an empty string has no non-empty substrings.

Input: []

Expected Output: []

Explanation: Edge case: no input strings means no answers.

Hints

A multiset of characters can form a palindrome if at most one character has odd frequency.
Use a prefix parity bitmask: two prefixes define a valid substring when their masks are equal or differ by exactly one bit.

Part 3: Replace Wildcards to Match a Digit Sum

You are given a string pattern containing digits and the character '?'. Each '?' must be replaced by a digit from 0 to 8 inclusive. Return all completed strings whose total digit sum equals target. For deterministic testing, return the valid strings sorted in lexicographic order.

Constraints

0 <= len(pattern) <= 15
pattern contains only characters '0' to '9' and '?'
0 <= target <= 9 * len(pattern)
Each '?' may only be replaced with a digit from 0 to 8

Examples

Input: ("08??840", 24)

Expected Output: ["0804840", "0813840", "0822840", "0831840", "0840840"]

Explanation: The fixed digits sum to 20, so the two wildcards must add up to 4.

Input: ("5?1", 7)

Expected Output: ["511"]

Explanation: The fixed digits already sum to 6, so the wildcard must be 1.

Input: ("123", 6)

Expected Output: ["123"]

Explanation: Edge case: there are no wildcards, and the existing digit sum already matches the target.

Input: ("??", 0)

Expected Output: ["00"]

Explanation: Edge case: the minimum possible sum is 0, achieved only by replacing both wildcards with 0.

Input: ("??", 20)

Expected Output: []

Explanation: Edge case: with two wildcards limited to 0..8, the maximum possible sum is 16, so no solution exists.

Hints

First compute the sum of the fixed digits, then only distribute the remaining sum across the '?' positions.
Use backtracking, but prune branches when the remaining sum is too small or too large for the remaining wildcard slots.

Quick Overview

This multi-part question evaluates string manipulation, combinatorial counting, and constrained enumeration skills through sequence generation, palindromic-anagram substring counting, and wildcard digit-sum completion tasks.