#### 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:

#### Practice Problems

**EASY**

**MEDIUM**

○ Design an Underground System

**HARD**