CareerCup

Box# : Box1, Box2, Box3
Label# : Apple, Orange, Mixed
Let's pick a fruit from Box3 (Labeled as Mixed). Now, as per the problem statement this box is not actually a mixed one which means it is either an orange box or an apple box.

Case 1: if the fruit which we picked happens to be an Orange:
1. Box3 is Orange Box
2. Box2 which is labeled Orange is actually Apple box
3. Box1 is actually a mixed box.
for this case the Correct Order is written below:
Box# : Box1, Box2, Box3
Label# : Mixed, Apple, Orange


Case 2: if the fruit which we picked happens to be an Apple:
1. Box3 is Apple Box
2. Box2 which is labeled Orange is actually Mixed box
3. Box1 is actually an Orange box.
for this case the Correct Order is written below:
Box# : Box1, Box2, Box3
Label# : Orange, Mixed, Apple

int get_rand7_from_rand5()
{
	int rnd; 
	do { 
    		int x = rand5(); //generates one of 0,1,2,3,4 
    		int y = rand5(); //generates one of 0,1,2,3,4 
    		rnd = 5*x + y; // generates a number between 0 to 24 
	} while (rnd > 20)
	return rnd % 7; 
    //for numbers between 0 to 20 : if we take modulo 7 we can see that probability of picking 0 is 3/21 (for 0, 7 and 14), probability of picking 1 is 3/21 (for 1, 8, 15). Similarly for 2, 3, 4, 5 and 6. Hence any number between 0 to 6 has equal probability.
}
//probability of the while loop running n times before it returns is (4/25)^n

Let ABC be the triangle and P be any arbitrary point in 2D space.
The if P is inside the triangle ABC or not can be found by checking the signs of the following cross products:
AB X AP, BC X BP and CA X CP.
If the signs are same then it means the point is inside the triangle, o.w. it is outside the triangle.

For this question mark P as (0,0) and check for the signs of the above cross products.

two important things to consider:
1. To find out if an entry is already there in the cache or not should be fast. Linear time search will not do.
2. If the cache is full then we need to remove the oldest entry from the cache when a new entry is about to be fetched from the disk when this entry could not be found in the cache.

So, to solve these two issues we need two data structures.
1. Hash map : This will have (key, value) pair. key is some unique id associated with the actual object. While value here is reference to the corresponding entry in a doubly linked list structure. Searching for a key in hash map will be of O(log n).

2. Doubly linked list: maintain head and tail pointers. Each node will have key, data, prev_pointer and next_pointer as attributes.
Whenever an entry (key) is searched in the hashmap, following two cases can happen:
a) entry is not found:
- fetch the object from the disk
- create node structure to be inserted in the DLL
- add this node at the front of the DLL.
- add (key, reference_to_node_in_dll) pair in hashmap
b) entry is found in the hashmap
- use the reference for the key to traverse to the node containing the object in DLL
- adjust the prev and next pointers of the nodes to make it a front node of the DLL
purpose of this exercise to move the node which is not being accessed or the least recently used one to the end of the DLL.

Now, whenever the cache is full and we have to add an entry in the hashmap:
- delete the node pointed by tail in DLL ( as this is the least recently used node) and using the key value remove the entry in the hashmap as well.
- fetch the object, create a node for DLL and add it at the front
- add (key, reference_to_node_in_dll) pair in the hashmap

This way we can implement an LRU which will handle all the possible scenarios.

Queue will not work

Here is the complete code:

#include <iostream>

class CAPiece
{
public:
	CAPiece(char cColor) : mcColor(cColor) {}
	~CAPiece() {}
	virtual char GetPiece() = 0;
	char GetColor() {
		return mcColor;
	}
	bool IsLegalMove(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) {
		CAPiece* qpDest = qpaaBoard[iDestRow][iDestCol];
		if ((qpDest == 0) || (mcColor != qpDest->GetColor())) {
			return AreSquaresLegal(iSrcRow, iSrcCol, iDestRow, iDestCol, qpaaBoard);
		}
		return false;
	}
private:
	virtual bool AreSquaresLegal(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) = 0;
	char mcColor;
};

class CPawn : public CAPiece
{
public:
	CPawn(char cColor) : CAPiece(cColor) {}
	~CPawn() {}
private:
	virtual char GetPiece() {
		return 'P';
	}
	bool AreSquaresLegal(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) {
		CAPiece* qpDest = qpaaBoard[iDestRow][iDestCol];
		if (qpDest == 0) {
			// Destination square is unoccupied
			if (iSrcCol == iDestCol) {
				if (GetColor() == 'W') {
					if (iDestRow == iSrcRow + 1) {
						return true;
					}
				} else {
					if (iDestRow == iSrcRow - 1) {
						return true;
					}
				}
			}
		} else {
			// Dest holds piece of opposite color
			if ((iSrcCol == iDestCol + 1) || (iSrcCol == iDestCol - 1)) {
				if (GetColor() == 'W') {
					if (iDestRow == iSrcRow + 1) {
						return true;
					}
				} else {
					if (iDestRow == iSrcRow - 1) {
						return true;
					}
				}
			}
		}
		return false;
	}
};

class CKnight : public CAPiece
{
public:
	CKnight(char cColor) : CAPiece(cColor) {}
	~CKnight() {}
private:
	virtual char GetPiece() {
		return 'N';
	}
	bool AreSquaresLegal(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) {
		// Destination square is unoccupied or occupied by opposite color
		if ((iSrcCol == iDestCol + 1) || (iSrcCol == iDestCol - 1)) {
			if ((iSrcRow == iDestRow + 2) || (iSrcRow == iDestRow - 2)) {
				return true;
			}
		}
		if ((iSrcCol == iDestCol + 2) || (iSrcCol == iDestCol - 2)) {
			if ((iSrcRow == iDestRow + 1) || (iSrcRow == iDestRow - 1)) {
				return true;
			}
		}
		return false;
	}
};

class CBishop : public CAPiece
{
public:
	CBishop(char cColor) : CAPiece(cColor) {}
	~CBishop() {}
private:
	virtual char GetPiece() {
		return 'B';
	}
	bool AreSquaresLegal(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) {
		if ((iDestCol - iSrcCol == iDestRow - iSrcRow) || (iDestCol - iSrcCol == iSrcRow - iDestRow)) {
			// Make sure that all invervening squares are empty
			int iRowOffset = (iDestRow - iSrcRow > 0) ? 1 : -1;
			int iColOffset = (iDestCol - iSrcCol > 0) ? 1 : -1;
			int iCheckRow;
			int iCheckCol;
			for (iCheckRow = iSrcRow + iRowOffset, iCheckCol = iSrcCol + iColOffset;
				iCheckRow !=  iDestRow;
				iCheckRow = iCheckRow + iRowOffset, iCheckCol = iCheckCol + iColOffset)
			{
				if (qpaaBoard[iCheckRow][iCheckCol] != 0) {
					return false;
				}
			}
			return true;
		}
		return false;
	}
};

class CRook : public CAPiece
{
public:
	CRook(char cColor) : CAPiece(cColor) {}
	~CRook() {}
private:
	virtual char GetPiece() {
		return 'R';
	}
	bool AreSquaresLegal(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) {
		if (iSrcRow == iDestRow) {
			// Make sure that all invervening squares are empty
			int iColOffset = (iDestCol - iSrcCol > 0) ? 1 : -1;
			for (int iCheckCol = iSrcCol + iColOffset; iCheckCol !=  iDestCol; iCheckCol = iCheckCol + iColOffset) {
				if (qpaaBoard[iSrcRow][iCheckCol] != 0) {
					return false;
				}
			}
			return true;
		} else if (iDestCol == iSrcCol) {
			// Make sure that all invervening squares are empty
			int iRowOffset = (iDestRow - iSrcRow > 0) ? 1 : -1;
			for (int iCheckRow = iSrcRow + iRowOffset; iCheckRow !=  iDestRow; iCheckRow = iCheckRow + iRowOffset) {
				if (qpaaBoard[iCheckRow][iSrcCol] != 0) {
					return false;
				}
			}
			return true;
		}
		return false;
	}
};

class CQueen : public CAPiece
{
public:
	CQueen(char cColor) : CAPiece(cColor) {}
	~CQueen() {}
private:
	virtual char GetPiece() {
		return 'Q';
	}
	bool AreSquaresLegal(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) {
		if (iSrcRow == iDestRow) {
			// Make sure that all invervening squares are empty
			int iColOffset = (iDestCol - iSrcCol > 0) ? 1 : -1;
			for (int iCheckCol = iSrcCol + iColOffset; iCheckCol !=  iDestCol; iCheckCol = iCheckCol + iColOffset) {
				if (qpaaBoard[iSrcRow][iCheckCol] != 0) {
					return false;
				}
			}
			return true;
		} else if (iDestCol == iSrcCol) {
			// Make sure that all invervening squares are empty
			int iRowOffset = (iDestRow - iSrcRow > 0) ? 1 : -1;
			for (int iCheckRow = iSrcRow + iRowOffset; iCheckRow !=  iDestRow; iCheckRow = iCheckRow + iRowOffset) {
				if (qpaaBoard[iCheckRow][iSrcCol] != 0) {
					return false;
				}
			}
			return true;
		} else if ((iDestCol - iSrcCol == iDestRow - iSrcRow) || (iDestCol - iSrcCol == iSrcRow - iDestRow)) {
			// Make sure that all invervening squares are empty
			int iRowOffset = (iDestRow - iSrcRow > 0) ? 1 : -1;
			int iColOffset = (iDestCol - iSrcCol > 0) ? 1 : -1;
			int iCheckRow;
			int iCheckCol;
			for (iCheckRow = iSrcRow + iRowOffset, iCheckCol = iSrcCol + iColOffset;
				iCheckRow !=  iDestRow;
				iCheckRow = iCheckRow + iRowOffset, iCheckCol = iCheckCol + iColOffset)
			{
				if (qpaaBoard[iCheckRow][iCheckCol] != 0) {
					return false;
				}
			}
			return true;
		}
		return false;
	}
};

class CKing : public CAPiece
{
public:
	CKing(char cColor) : CAPiece(cColor) {}
	~CKing() {}
private:
	virtual char GetPiece() {
		return 'K';
	}
	bool AreSquaresLegal(int iSrcRow, int iSrcCol, int iDestRow, int iDestCol, CAPiece* qpaaBoard[8][8]) {
		int iRowDelta = iDestRow - iSrcRow;
		int iColDelta = iDestCol - iSrcCol;
		if (((iRowDelta >= -1) && (iRowDelta <= 1)) &&
			((iColDelta >= -1) && (iColDelta <= 1)))
		{
			return true;
		}
		return false;
	}
};

class CBoard
{
public:
	CBoard() {
		for (int iRow = 0; iRow < 8; ++iRow) {
			for (int iCol = 0; iCol < 8; ++iCol) {
				mqpaaBoard[iRow][iCol] = 0;
			}
		}
		// Allocate and place black pieces
		for (int iCol = 0; iCol < 8; ++iCol) {
			mqpaaBoard[6][iCol] = new CPawn('B');
		}
		mqpaaBoard[7][0] = new CRook('B');
		mqpaaBoard[7][1] = new CKnight('B');
		mqpaaBoard[7][2] = new CBishop('B');
		mqpaaBoard[7][3] = new CKing('B');
		mqpaaBoard[7][4] = new CQueen('B');
		mqpaaBoard[7][5] = new CBishop('B');
		mqpaaBoard[7][6] = new CKnight('B');
		mqpaaBoard[7][7] = new CRook('B');
		// Allocate and place white pieces
		for (int iCol = 0; iCol < 8; ++iCol) {
			mqpaaBoard[1][iCol] = new CPawn('W');
		}
		mqpaaBoard[0][0] = new CRook('W');
		mqpaaBoard[0][1] = new CKnight('W');
		mqpaaBoard[0][2] = new CBishop('W');
		mqpaaBoard[0][3] = new CKing('W');
		mqpaaBoard[0][4] = new CQueen('W');
		mqpaaBoard[0][5] = new CBishop('W');
		mqpaaBoard[0][6] = new CKnight('W');
		mqpaaBoard[0][7] = new CRook('W');
	}
	~CBoard() {
		for (int iRow = 0; iRow < 8; ++iRow) {
			for (int iCol = 0; iCol < 8; ++iCol) {
				delete mqpaaBoard[iRow][iCol];
				mqpaaBoard[iRow][iCol] = 0;
			}
		}
	}

	void Print() {
		using namespace std;
		const int kiSquareWidth = 4;
		const int kiSquareHeight = 3;
		for (int iRow = 0; iRow < 8*kiSquareHeight; ++iRow) {
			int iSquareRow = iRow/kiSquareHeight;
			// Print side border with numbering
			if (iRow % 3 == 1) {
				cout << '-' << (char)('1' + 7 - iSquareRow) << '-';
			} else {
				cout << "---";
			}
			// Print the chess board
			for (int iCol = 0; iCol < 8*kiSquareWidth; ++iCol) {
				int iSquareCol = iCol/kiSquareWidth;
				if (((iRow % 3) == 1) && ((iCol % 4) == 1 || (iCol % 4) == 2) && mqpaaBoard[7-iSquareRow][iSquareCol] != 0) {
					if ((iCol % 4) == 1) {
						cout << mqpaaBoard[7-iSquareRow][iSquareCol]->GetColor();
					} else {
						cout << mqpaaBoard[7-iSquareRow][iSquareCol]->GetPiece();
					}
				} else {
					if ((iSquareRow + iSquareCol) % 2 == 1) {
						cout << '*';
					} else {
						cout << ' ';
					}
				}
			}
			cout << endl;
		}
		// Print the bottom border with numbers
		for (int iRow = 0; iRow < kiSquareHeight; ++iRow) {
			if (iRow % 3 == 1) {
				cout << "---";
				for (int iCol = 0; iCol < 8*kiSquareWidth; ++iCol) {
					int iSquareCol = iCol/kiSquareWidth;
					if ((iCol % 4) == 1) {
						cout << (iSquareCol + 1);
					} else {
						cout << '-';
					}
				}
				cout << endl;
			} else {
				for (int iCol = 1; iCol < 9*kiSquareWidth; ++iCol) {
					cout << '-';
				}
				cout << endl;
			}
		}
	}

	bool IsInCheck(char cColor) {
		// Find the king
		int iKingRow;
		int iKingCol;
		for (int iRow = 0; iRow < 8; ++iRow) {
			for (int iCol = 0; iCol < 8; ++iCol) {
				if (mqpaaBoard[iRow][iCol] != 0) {
					if (mqpaaBoard[iRow][iCol]->GetColor() == cColor) {
						if (mqpaaBoard[iRow][iCol]->GetPiece() == 'K') {
							iKingRow = iRow;
							iKingCol = iCol;
						}
					}
				}
			}
		}
		// Run through the opponent's pieces and see if any can take the king
		for (int iRow = 0; iRow < 8; ++iRow) {
			for (int iCol = 0; iCol < 8; ++iCol) {
				if (mqpaaBoard[iRow][iCol] != 0) {
					if (mqpaaBoard[iRow][iCol]->GetColor() != cColor) {
						if (mqpaaBoard[iRow][iCol]->IsLegalMove(iRow, iCol, iKingRow, iKingCol, mqpaaBoard)) {
							return true;
						}
					}
				}
			}
		}

		return false;
	}

	bool CanMove(char cColor) {
		// Run through all pieces
		for (int iRow = 0; iRow < 8; ++iRow) {
			for (int iCol = 0; iCol < 8; ++iCol) {
				if (mqpaaBoard[iRow][iCol] != 0) {
					// If it is a piece of the current player, see if it has a legal move
					if (mqpaaBoard[iRow][iCol]->GetColor() == cColor) {
						for (int iMoveRow = 0; iMoveRow < 8; ++iMoveRow) {
							for (int iMoveCol = 0; iMoveCol < 8; ++iMoveCol) {
								if (mqpaaBoard[iRow][iCol]->IsLegalMove(iRow, iCol, iMoveRow, iMoveCol, mqpaaBoard)) {
									// Make move and check whether king is in check
									CAPiece* qpTemp					= mqpaaBoard[iMoveRow][iMoveCol];
									mqpaaBoard[iMoveRow][iMoveCol]	= mqpaaBoard[iRow][iCol];
									mqpaaBoard[iRow][iCol]			= 0;
									bool bCanMove = !IsInCheck(cColor);
									// Undo the move
									mqpaaBoard[iRow][iCol]			= mqpaaBoard[iMoveRow][iMoveCol];
									mqpaaBoard[iMoveRow][iMoveCol]	= qpTemp;
									if (bCanMove) {
										return true;
									}
								}
							}
						}
					}
				}
			}
		}
		return false;
	}

	CAPiece* mqpaaBoard[8][8];
};

class CChess
{
public:
	CChess() : mcPlayerTurn('W') {}
	~CChess() {}

	void Start() {
		do {
			GetNextMove(mqGameBoard.mqpaaBoard);
			AlternateTurn();
		} while (!IsGameOver());
		mqGameBoard.Print();
	}

	void GetNextMove(CAPiece* qpaaBoard[8][8]) {
		using namespace std;
		bool bValidMove		= false;
		do {
			mqGameBoard.Print();

			// Get input and convert to coordinates
			cout << mcPlayerTurn << "'s Move: ";
			int iStartMove;
			cin >> iStartMove;
			int iStartRow = (iStartMove / 10) - 1;
			int iStartCol = (iStartMove % 10) - 1;

			cout << "To: ";
			int iEndMove;
			cin >> iEndMove;
			int iEndRow = (iEndMove / 10) - 1;
			int iEndCol = (iEndMove % 10) - 1;

			// Check that the indices are in range
			// and that the source and destination are different
			if ((iStartRow >= 0 && iStartRow <= 7) &&
				(iStartCol >= 0 && iStartCol <= 7) &&
				(iEndRow >= 0 && iEndRow <= 7) &&
				(iEndCol >= 0 && iEndCol <= 7)) {
				// Additional checks in here
				CAPiece* qpCurrPiece = qpaaBoard[iStartRow][iStartCol];
				// Check that the piece is the correct color
				if ((qpCurrPiece != 0) && (qpCurrPiece->GetColor() == mcPlayerTurn)) {
					// Check that the destination is a valid destination
					if (qpCurrPiece->IsLegalMove(iStartRow, iStartCol, iEndRow, iEndCol, qpaaBoard)) {
						// Make the move
						CAPiece* qpTemp					= qpaaBoard[iEndRow][iEndCol];
						qpaaBoard[iEndRow][iEndCol]		= qpaaBoard[iStartRow][iStartCol];
						qpaaBoard[iStartRow][iStartCol]	= 0;
						// Make sure that the current player is not in check
						if (!mqGameBoard.IsInCheck(mcPlayerTurn)) {
							delete qpTemp;
							bValidMove = true;
						} else { // Undo the last move
							qpaaBoard[iStartRow][iStartCol] = qpaaBoard[iEndRow][iEndCol];
							qpaaBoard[iEndRow][iEndCol]		= qpTemp;
						}
					}
				}
			}
			if (!bValidMove) {
				cout << "Invalid Move!" << endl;
			}
		} while (!bValidMove);
	}

	void AlternateTurn() {
		mcPlayerTurn = (mcPlayerTurn == 'W') ? 'B' : 'W';
	}

	bool IsGameOver() {
		// Check that the current player can move
		// If not, we have a stalemate or checkmate
		bool bCanMove(false);
		bCanMove = mqGameBoard.CanMove(mcPlayerTurn);
		if (!bCanMove) {
			if (mqGameBoard.IsInCheck(mcPlayerTurn)) {
				AlternateTurn();
				std::cout << "Checkmate, " << mcPlayerTurn << " Wins!" << std::endl;
			} else {
				std::cout << "Stalemate!" << std::endl;
			}
		}
		return !bCanMove;
	}
private:
	CBoard mqGameBoard;
	char mcPlayerTurn;
};

int main() {
	CChess qGame;
	qGame.Start();
	return 0;
}