Katkat
Back

Optimize flight costs and find grid path

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates algorithm design and problem-solving skills for array-based cost optimization and grid pathfinding, including selection under ordering constraints, path existence detection and path reconstruction, together with correctness and edge-case reasoning.

  1. Given two integer arrays D and R of equal length n, where D[i] is the cost to depart on day i and R[j] is the cost to return on day j, choose indices i and j with 0 <= i < j < n (return strictly after departure) to minimize the total trip cost C = D[i] + R[j]. Return the minimal cost and the chosen days (i, j). Design an algorithm, explain its time and space complexity, justify correctness, and discuss edge cases (e.g., n < 2, ties).
  2. Given an m x n binary grid where 0 indicates a walkable cell and 1 indicates a blocked cell, starting at the top-left cell (0,
  3. and ending at the bottom-right cell (m-1,n- 1), output any valid path as a list of coordinates if one exists. You may move only up, down, left, or right within bounds. Describe the algorithm to find such a path, how you reconstruct the path, and analyze time and space complexity.