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 Software Engineer candidates at Meta during technical interviews.

Optimize flight costs and find grid path

Quick Overview

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.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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, 0) 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.

Quick Answer: 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.

Optimize Flight Costs (Depart Then Return)

You are given two integer arrays `D` and `R` of equal length `n`. `D[i]` is the cost to depart on day `i`, and `R[j]` is the cost to return on day `j`. You must pick a departure day `i` and a return day `j` with `0 <= i < j < n` (the return must be strictly after the departure), minimizing the total trip cost `C = D[i] + R[j]`. Return a list `[minCost, i, j]` where `minCost` is the minimal achievable total cost and `i`, `j` are the chosen departure and return days. If no valid pair exists (i.e. `n < 2`), return `[-1, -1, -1]`. This is a variant of the single buy-then-sell stock problem: scan left to right while remembering the cheapest departure cost seen so far, and at each candidate return day combine it with that minimum. Example: `D = [5, 2, 8, 1]`, `R = [10, 3, 6, 4]` -> `[6, 1, 3]` (depart day 1 at cost 2, return day 3 at cost 4, total 6).

Constraints

1 <= n <= 10^5 (length of D equals length of R)
Costs may be any 32-bit integers, including negatives
Return must be strictly after departure: i < j
If n < 2 there is no valid (i, j) pair; return [-1, -1, -1]
On ties, the earliest return day j (and the cheapest departure index recorded before it) is reported

Examples

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

Expected Output: [6, 1, 3]

Explanation: Cheapest departure before day 3 is day 1 (cost 2). Combined with return cost R[3]=4 gives total 6, the minimum.

Input: ([1], [1])

Expected Output: [-1, -1, -1]

Explanation: n = 1 < 2, so no valid (i, j) with i < j exists.

Input: ([3, 1], [4, 2])

Expected Output: [5, 0, 1]

Explanation: Only valid pair is i=0, j=1: D[0]+R[1] = 3+2 = 5.

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

Expected Output: [9, 2, 3]

Explanation: Departure costs strictly decrease, so the latest allowed departure (day 2, cost 8) paired with the only later return (day 3) gives 8+1=9.

Input: ([-5, -2, -3], [-1, -4, -6])

Expected Output: [-11, 0, 2]

Explanation: Negative costs are allowed. Cheapest departure is day 0 (-5); the best return after it is day 2 (-6), total -11.

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

Expected Output: [7, 0, 1]

Explanation: All totals are 7; the earliest return day j=1 (with departure j=0) is reported on ties.

Hints

You do not need to try all O(n^2) pairs. Fix the return day j and ask: what is the cheapest departure on any day before j?
Scan left to right keeping `minDepCost` and its index among days 0..j-1. At day j, the best total ending here is minDepCost + R[j].
Update the running best total before updating minDepCost with D[j], so day j is never used as its own departure-and-return.
Handle n < 2 up front by returning [-1, -1, -1].

Find a Path Through a Binary Grid

You are given an `m x n` binary grid where `0` marks a walkable cell and `1` marks a blocked cell. Starting at the top-left cell `(0, 0)` and ending at the bottom-right cell `(m-1, n-1)`, return any valid path as a list of `[row, col]` coordinates. You may move only up, down, left, or right, and must stay within the grid bounds. Cells on the path must all be walkable (value `0`). If no path exists (including the case where the start or the destination is blocked), return an empty list `[]`. Use a breadth-first search from the start, recording each cell's parent as it is first discovered, then reconstruct the path by walking parent pointers back from the destination. BFS additionally guarantees the returned path is a shortest one. Example: for `[[0,0,0],[0,1,0],[0,0,0]]` a valid path is `[[0,0],[1,0],[2,0],[2,1],[2,2]]`.

Constraints

1 <= m, n (the grid has at least one cell)
Each cell is 0 (walkable) or 1 (blocked)
Moves are 4-directional: up, down, left, right; no diagonals
Start (0,0) and destination (m-1,n-1) may themselves be blocked, in which case return []
When a path exists, BFS returns a shortest path; with neighbor order down, right, up, left the path is deterministic

Examples

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

Expected Output: [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]]

Explanation: The center cell (1,1) is blocked, so BFS routes down the left column then across the bottom row to reach (2,2).

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

Expected Output: []

Explanation: From (0,0) both the right cell (0,1) and the down cell (1,0) are blocked, so the destination is unreachable.

Input: ([[0]],)

Expected Output: [[0, 0]]

Explanation: A 1x1 walkable grid: start equals destination, so the path is just the single cell.

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

Expected Output: []

Explanation: The start cell (0,0) is blocked, so no path can begin; return [].

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

Expected Output: []

Explanation: The destination cell (1,1) is blocked, so no path can end there; return [].

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

Expected Output: [[0, 0], [0, 1], [0, 2], [0, 3], [1, 3], [2, 3]]

Explanation: Row 1 is walled except its last column, so the only crossing is at column 3: across the top row, down through (1,3), to the destination (2,3).

Hints

Both BFS and DFS work. BFS additionally gives you a shortest path and avoids deep recursion on large grids.
Mark a cell visited at the moment you enqueue it (not when you dequeue it) to avoid enqueuing the same cell twice.
Store a parent pointer for every cell when you first discover it, then rebuild the path by following parents from the destination back to the start and reversing.
Check the start and destination cells for being blocked before searching, and handle the 1x1 grid as its own answer.

Quick Overview