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