Solve classic backend coding problems

Solve the following coding problems.

1. Find the missing number from a concatenated range

You are given an integer n and a string s.

The string was formed by taking every integer from 1 to n, removing exactly one number, converting the remaining numbers to decimal strings, and concatenating them together with no separators.

Return the missing number.

There are two versions:

• Part 1: the numbers were concatenated in increasing numeric order.
  • Example: n = 5 , s = "1234" → return 5 .
• Part 2: the numbers may appear in any order before concatenation, still with no separators.
  • Example: for n = 13 , a valid string could represent a shuffled sequence such as 13, 10, 9, 2, 3, ... with one number missing.

Assume the input is valid and exactly one number from 1..n is missing.

2. Determine the status of a square board game

Implement a function that takes:

• a board size size , where the board is size x size and 3 <= size <= 9
• a list of action strings moves

Return one of:

• "in progress"
• "player 1 is the winner"
• "player 2 is the winner"

Assume every action is valid and well-formed.

Board rules

Each square may be empty or owned by one player, and it stores a number of pieces.

Turn structure

Players alternate turns. A turn consists of:

1. Place exactly once.
2. Topple zero or more times.

The input is a flat list of actions, not a list of turns. The first place action belongs to player 1. After each place action, subsequent topple actions belong to that same player until the next place action, which starts the other player's turn.

Action encoding

• "pRC" means place one piece at row R , column C .
• "tRCd" means topple the square at row R , column C in direction d , where d is one of:
  • u = up
  • r = right
  • d = down
  • l = left

Place action

A player may place a piece on:

• an empty square, or
• a square already owned by that player

If the square is empty, the player claims it and places one piece there. If the square already belongs to that player, increment its piece count by one.

Topple action

A player may topple a square they own that contains at least 2 pieces.

• Pick up all pieces from that square.
• Move in the chosen direction, placing one piece per square on consecutive cells.
• Pieces that move beyond the board are lost.
• If a placed piece lands on an opponent-owned square, that square is captured: ownership changes to the current player, and all pieces on that square now belong to the current player.

Game end

The game ends as soon as one player has no pieces remaining anywhere on the board.

Examples:

• moves = ["p10", "p12", "p10", "t10r"] → "player 1 is the winner"
• moves = ["p00", "p22", "p02", "p22", "t22u", "t02l"] → "player 2 is the winner"

3. Generate word sequences for T9 input

A phone keypad uses this mapping:

• 2 -> abc
• 3 -> def
• 4 -> ghi
• 5 -> jkl
• 6 -> mno
• 7 -> pqrs
• 8 -> tuv
• 9 -> wxyz

Implement a function with inputs:

• input_digits : an array of digits, each from 2 to 9 , length up to 25
• valid_words : an array of up to 50 lowercase English words

Return a 2D array containing all word sequences whose T9 encodings concatenate exactly to input_digits.

Each inner array represents one valid translation.

• Example: input_digits = [2,2,8] , valid_words = ["act", "bat", "cat", "acd", "test"] → [["act"], ["bat"], ["cat"]]
• Example: input_digits = [7,6,6,3,8,4,6,3] , valid_words = ["some", "time", "rome", "sometime", "so", "me"] → valid outputs include [["rome", "time"], ["so", "me", "time"], ["some", "time"], ["sometime"]]

Any output order is acceptable unless otherwise specified.