Find the minimum eating speed for Koko to finish all bananas within h hours.

Binary search on the answer space (eating speed 1 through max pile size) rather than on the input array. For each candidate speed, greedily compute hours needed in O(n). The feasibility check is monotone — if speed k works, any speed above k also works — so binary search finds the minimum valid speed in O(n log m) time.

You are a robber. Given an array of house values, find the maximum money you can rob without robbing two adjacent houses.

At each house you make one choice: rob it (and skip the previous) or skip it (and carry forward whatever you had). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Since you only look back two steps, two variables replace the full array, giving O(n) time and O(1) space.

When should you use grid search vs random search vs Bayesian optimisation for hyperparameter tuning?

Grid search exhaustively tries every combination in a predefined grid, which is only practical for 1–2 hyperparameters. Random search samples combinations uniformly at random and finds good values faster per compute budget, especially when only a few hyperparameters actually matter. Bayesian optimisation fits a surrogate model of the objective and proposes the next trial intelligently, giving the best sample efficiency for expensive evaluations.

What is pruning in decision trees and when would you use pre-pruning versus post-pruning?

Pruning removes splits that do not improve generalisation. Pre-pruning stops growth early via hyperparameters like max_depth or min_samples_leaf. Post-pruning (cost-complexity pruning) grows the full tree then collapses nodes whose removal does not hurt held-out accuracy enough.

Adversarial Search: Minimax — GATE DA

What you'll learn

In a two-player zero-sum game, MAX maximises the score and MIN minimises it

The minimax value of a node = max of children at MAX, min of children at MIN

Compute minimax bottom-up by recursion; leaves carry utility values

Reading the root's optimal first move from the backed-up values

Two perfect players, one game tree. Each side plays the move that’s best for them, knowing the other side will do the same. Minimax just makes that idea precise on paper.

The trick is that you can’t plan only for yourself. Every plan you draft has to survive the opponent picking their best reply. So you read the tree backwards from the leaves — score in hand — and let each player choose the child that matches their goal: largest for MAX, smallest for MIN. This worst-case-aware reasoning is the backbone of every game-playing agent (chess and Go engines, poker bots) and of adversarial robustness in ML — anywhere you must act well against an opponent who answers your move.

The minimax value

Triangles point up at MAX, down at MIN. Values are backed up from the leaves.

Formally, the minimax value V(n) of a node n:

V(n) = utility(n)              if n is a leaf
V(n) = max over children c of V(c)   if n is a MAX node
V(n) = min over children c of V(c)   if n is a MIN node

That is the entire algorithm. Recurse to the leaves, then back the value up one level at a time. The root’s value is the score MAX can force against a perfectly playing MIN — the best result MAX can rationally hope for.

How GATE asks this

A typical NAT: a small game tree (often 2-3 levels, sometimes drawn as a MAX root with three strategies leading to MIN nodes with three leaves each). Compute the root’s minimax value, or state which strategy MAX should choose. Sometimes the question is an MCQ asking “which strategy is optimal for MAX” — same calculation, just read the index. This pattern appeared in GATE DA 2026.

Worked example — a real 2026 question

MAX has three strategies. Each strategy leads to a MIN node with three leaf utilities:

Strategy 1 leaves: 8, 6, -1

Strategy 2 leaves: 1, 5, 7

Strategy 3 leaves: -4, -3, -12

Which strategy should MAX play, and what is the game’s value?

Step 1 — back up MIN at each strategy node:

Strategy 1: min(8, 6, -1) = -1
Strategy 2: min(1, 5, 7) = 1
Strategy 3: min(-4, -3, -12) = -12

Step 2 — MAX picks the largest:

V(root) = max(-1, 1, -12) = 1

So MAX plays strategy 2 and secures a value of 1. This is a real GATE DA 2026 question — the answer is strategy 2.

The intuition is worth pausing on. Strategy 1 has the highest individual leaf (8), but MIN will never let you reach it — MIN steers you to the -1. Strategy 2’s worst case is 1, and MIN cannot do better than that. So the rational choice is strategy 2, even though its peak is lower.

Quick check

0/6

Q1A MAX root has two children, both MIN. Left MIN's leaves: [3, 9]; right MIN's leaves: [7, 2]. What is the minimax value of the root?numerical answer — type a number

Q2Recall the 2026 worked example with strategies giving leaves [8,6,-1], [1,5,7], [-4,-3,-12]. What is the minimax value of the root?numerical answer — type a number

Q3A 3-level tree has MAX root, then MIN, then MAX (leaves). Under the left MIN, two MAX children hold leaves [2,7] and [4,1]. Under the right MIN, two MAX children hold leaves [9,5] and [6,8]. What is the root value?numerical answer — type a number

Q4At a MIN node, three children have backed-up values 5, 12, -3. What value does MIN propagate to its parent?numerical answer — type a number

Q5Which statements about minimax are TRUE? (select all that apply)select all that apply

Q6A MAX root has three children with backed-up values -2, -5, -1. What does MAX play, and what is the root value?

Adversarial Search: Minimax

What you'll learn

Before you start

The minimax value

How GATE asks this

Worked example — a real 2026 question

Quick check

Quick check

Practice this in an interview

Sign in to track your progress

Explore further

Related lessons