Tic Tac Toe
Entities simple hain: Board, Cell, Player, Move, Game. Galti ye hoti hai ki log sab kuch main() mein likh dete hain. Board ko apni class banao jo khud jaanta ho ki move valid hai ya nahi — validation Game class mein mat rakho.
Win check ko O(n²) mat rakho. Har move ke baad SIRF us row, column aur (agar applicable ho) diagonal ka counter update karo — ye O(1) win detection deta hai aur NxN board par bhi scale karta hai. Yahi optimization interviewer dhoondh raha hota hai.
class Board {
private final int n;
private final int[] rows, cols;
private int diag, antiDiag;
// +1 player X ke liye, -1 player O ke liye
boolean applyMove(int r, int c, int player) {
rows[r] += player; cols[c] += player;
if (r == c) diag += player;
if (r + c == n - 1) antiDiag += player;
return Math.abs(rows[r]) == n || Math.abs(cols[c]) == n
|| Math.abs(diag) == n || Math.abs(antiDiag) == n;
}
}- Board apni class ho aur khud move validate kare
- Counter-based win detection O(1) — poora board scan mat karo
- NxN generalize karo, 3x3 hardcode mat karo
3x3 hardcode karna junior signal hai. Board ko N se initialize karo — rows[N], cols[N], plus diag aur antiDiag counters. Win condition Math.abs(counter) == N ho jaata hai.
Isse "4x4 kar sakte ho?" waale follow-up ka jawab already tayyar rehta hai — code mein kuch badalna hi nahi padta. Interviewer aksar exactly yahi poochta hai.
Player ko interface banao jisme nextMove(Board) ho. HumanPlayer input se move leta hai, BotPlayer algorithm se. Isse "bot add kar sakte ho?" ka jawab bhi ready hai — nayi class, purana code untouched.
Bot ke liye minimax mention kar sakte ho, par implement karne mein time mat lagao jab tak interviewer specifically na kahe.
interface Player {
Move nextMove(Board board);
char symbol();
}
class HumanPlayer implements Player { ... }
class BotPlayer implements Player { ... } // minimax