Design X

May 12, 2021

Introduction

There are a class of problems in technical interviews that will ask you to design a typically known game or data structure using object oriented principles. You may be asked to design a data structure like a Hash Map or an LRU cache or simulate a game like Tic Tac Toe or a system like a Browser's history functionality.

An Example

Design Tic Tac Toe. You have to implement a class named TicTacToe which will take an integer n representing an nxn grid and you need to implement a method called move that will take a row, column and player that will place an item. The player id is either 1 or 2 and the move method will return the winner everytime it's called. If there is no winner it returns 0 otherwise it will return either player 1 or 2.

The key insight to realize for this problem is that a tic tac toe game can only be won if a player places an item entirely in a row, column or one of the two diagonals. So we only need to keep track of the number of placements by each player for each row, column, diagonal, and antidiagonal. One clever way to do this is to keep for arrays of size N and if player 1 places an item add 1 to the respective row,column,diagonal, or antidiagonal or if player 2 places an item add -1. If at anypoint any of these four arrays contains total value of size N for a row,column, diagonal or antidiagonal, then the player that just placed the item is the winner. The code follows below: