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

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Meta during technical interviews.

Optimize Travel Costs and Generate Rotational Symmetric Numbers

Company: Meta

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Scenario You are building a travel-search engine that must 1) show customers the cheapest round-trip they can book if departure and return prices vary by day, and 2) generate all k-digit numbers that still look the same after a 180° rotation for fraud-detection image checks. ##### Question Given two arrays, dep[i] = outbound ticket price on day i and ret[j] = return ticket price on day j, design an algorithm that returns the minimum possible total cost for any valid round-trip (depart before return). Analyze time and space complexity and discuss possible optimizations or alternative solutions. Given an integer k, generate all k-digit numbers that remain identical when rotated 180°. Provide an algorithm, analyze its complexity, and explain how your code handles corner cases. ##### Hints Cheapest flight: pre-compute suffix minima or use two-pointer scan. Strobogrammatic: recurse from outer to inner, pairing digits {0,0},{1,1},{6,9},{8,8},{9,6}.

Quick Answer: This question evaluates algorithmic optimization and complexity-analysis skills by combining array-based time-dependent pricing for round-trip cost minimization with combinatorial generation of rotationally symmetric (strobogrammatic) k-digit numbers.

Cheapest Round-Trip Booking

You are building a travel-search engine. You are given two integer arrays of the same conceptual timeline: `dep`, where `dep[i]` is the outbound (departure) ticket price on day `i`, and `ret`, where `ret[j]` is the return ticket price on day `j`. A valid round-trip departs on some day `i` and returns on a strictly later day `j` (`i < j`). The total cost of that trip is `dep[i] + ret[j]`. Return the minimum possible total cost over all valid round-trips. If no valid round-trip exists (for example, when either array is empty or there is no day pair with `i < j`), return `-1`. Example: `dep = [10, 2, 8, 6]`, `ret = [4, 9, 1, 7]`. Departing on day 1 (price 2) and returning on day 2 (price 1) costs `3`, which is the minimum, so the answer is `3`.

Constraints

0 <= len(dep), len(ret)
A valid trip requires a departure day i and return day j with i < j.
Prices fit in a 32-bit signed integer; the sum of two prices fits in a 64-bit integer.
Return -1 when no valid round-trip exists.

Examples

Input: ([10, 2, 8, 6], [4, 9, 1, 7])

Expected Output: 3

Explanation: Suffix minima of ret are [1,1,1,7]. Depart day 1 (price 2), cheapest return on/after day 2 is 1, total 3 — the minimum.

Input: ([5, 20], [30, 3])

Expected Output: 8

Explanation: Only valid trip uses depart day 0 (5) and return day 1 (3) = 8.

Input: ([100, 1], [1, 100])

Expected Output: 200

Explanation: Depart day 0 (100), the only later return is day 1 (100), total 200. Day 1's cheap departure has no later return.

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

Expected Output: 6

Explanation: Every valid pair costs 3 + 3 = 6.

Input: ([5, 5], [])

Expected Output: -1

Explanation: No return prices at all, so no valid trip.

Input: ([7], [9])

Expected Output: -1

Explanation: Single day on each side; you cannot return strictly after departure.

Input: ([2, 1, 4], [10, 1, 5])

Expected Output: 3

Explanation: Depart day 0 (2), cheapest return on/after day 1 is 1, total 3.

Hints

Fix the return day and ask: what is the cheapest departure available strictly before it? Or fix the departure day and ask for the cheapest return strictly after it.
Pre-compute a suffix-minimum array over `ret` so that for each departure day i you can look up the cheapest return on or after day i+1 in O(1).
Handle the infeasible cases up front: an empty array, or a timeline where every departure has no later return day, must yield -1.

Generate Strobogrammatic Numbers of Length k

A strobogrammatic number reads the same after a 180° rotation. Only certain digits map to valid digits under rotation: 0->0, 1->1, 8->8, 6->9, and 9->6. The pairs that may sit at mirrored positions are therefore {0,0}, {1,1}, {6,9}, {8,8}, {9,6}; the digit that may sit at the exact center (for odd lengths) is one of 0, 1, 8. Given an integer `k`, return a list (sorted in ascending lexicographic order) of all `k`-digit strings that are strobogrammatic. A `k`-digit number may not have a leading zero, except in the single case `k == 1`, where `"0"` itself is a valid 1-digit strobogrammatic number. If `k <= 0`, return an empty list. Example: for `k = 2` the answer is `["11", "69", "88", "96"]` ("00" is excluded because of the leading zero).

Constraints

k may be any integer; for k <= 0 return an empty list.
Valid rotation digits: 0<->0, 1<->1, 8<->8, 6<->9, 9<->6.
Leading zeros are not allowed for k > 1; for k == 1, "0" is included.
Results are returned as strings in ascending lexicographic order.

Examples

Input: (1,)

Expected Output: ['0', '1', '8']

Explanation: Single-digit numbers that map to themselves under rotation; '0' is allowed when k == 1.

Input: (2,)

Expected Output: ['11', '69', '88', '96']

Explanation: Mirrored pairs minus '00', which is dropped for its leading zero.

Input: (3,)

Expected Output: ['101', '111', '181', '609', '619', '689', '808', '818', '888', '906', '916', '986']

Explanation: Outer pair from {(1,1),(6,9),(8,8),(9,6)} (the (0,0) outer pair is filtered as a leading zero) combined with each center digit 0/1/8.

Input: (0,)

Expected Output: []

Explanation: Zero-length request returns an empty list.

Input: (-2,)

Expected Output: []

Explanation: Non-positive k returns an empty list.

Hints

Build the number from the outside in, choosing a mirrored pair (a, b) for the outermost positions and recursing on the inner length k-2.
The base cases are length 0 (one empty string) and length 1 (the self-rotating digits 0, 1, 8).
After generation, drop any string with a leading '0' unless k == 1, then sort the survivors.

Quick Overview

This question evaluates algorithmic optimization and complexity-analysis skills by combining array-based time-dependent pricing for round-trip cost minimization with combinatorial generation of rotationally symmetric (strobogrammatic) k-digit numbers.