Katkat
Back

Solve three interview coding problems

ExpediaSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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