Katkat
Back

Optimize Travel Costs and Generate Rotational Symmetric Numbers

MetaData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

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.

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