Data structure and algorithms for garbage collection in C++

Describe the data structures and algorithms that you would use to implement a garbage collector in C++.

My initial thoughts:
Utilize the concept of smart pointer:

template <class T>
class SmartPtr
{
public:
	explicit SmartPtr(T* pointee) : pointee_(pointee);
	SmartPtr& operator=(const SmartPtr& other);
	~SmartPtr();
	
	T& operator*() const {
		..
		return *pointee_;
	}

	T* operator->() const {
		...
		return pointee_;
	}
	
private:
	T* pointee_;
	...
};

Solution:
In C++, garbage collection with reference counting is almost always implemented with smart pointers, which perform reference counting. The main reason for using smart pointers over raw ordinary pointers is the conceptual simplicity of implementation and usage.
With smart pointers, everything related to garbage collection is performed behind the scenes – typically in constructors/destructors/assignment operator/explicit object management functions.
There are two types of functions, both of which are very simple:

RefCountPointer::type1() {
	// implementation depends on reference counting organisation.
	// There can also be no ref. counter at all (see approach #4)
	incrementRefCounter();
}

RefCountPointer::type2() {
	// Implementation depends on reference counting organisation.
	// There can also be no ref. counter at all (see approach #4).
	
	decrementRefCounter();
	if (referenceCounterIsZero()) {
		destructObject();
	}
}

There are several approaches for reference counting implementation in C++:

  1. Simple reference counting:
    struct Object { }; 
    struct RefCount {
    	int count; 
    };
    struct RefCountPtr {
    	Object * pointee;
    	RefCount * refCount; 
    };
    
    • Advantages: performance.
    • Disadvantages: memory overhead because of two pointers.
  2. Alternative reference counting.

    struct Object { ... }; 
    struct RefCountPtrImpl {
    	int count;
    	Object * object; 
    };
    struct RefCountPtr {
    	RefCountPtrImpl * pointee; 
    };
    
    • Advantages: no memory overhead because of two pointers.
    • Disadvantages: performance penalty because of extra level of indirection.
  3. Intrusive reference counting.

    struct Object { ... };
    struct ObjectIntrusiveReferenceCounting {
    	Object object;
    	int count; 
    };
    struct RefCountPtr {
    	ObjectIntrusiveReferenceCounting * pointee; 
    };
    
    • Advantages: no previous disadvantages.
    • Disadvantages: class for intrusive reference counting should be modified.
  4. Ownership list reference counting It is an alternative for approach 1-3. For 1-3 it is only important to determine that counter is zero — its actual value is not important This is the main idea of approach # 4.
    All Smart-Pointers for given objects are stored in doubly-linked lists. The constructor of a smart pointer adds the new node to a list, and the destructor removes a node from the list and checks if the list is empty or not. If it is empty, the object is deleted.

    struct Object {  };
    struct ListNode {
    	Object * pointee;
    	ListNode * next;
    }
    
Advertisements

Design an in-memory file system

Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible.

My initial codes:

	public class File {
		String fileName = new String();
		String extension = new String();
		long size = 0;
		Calendar createdTime = Calendar.getInstance();
		Calendar modifiedTime = Calendar.getInstance();
		Calendar lastAccessTime = Calendar.getInstance();
		boolean readOnly = false;
		boolean hidden = false;
		boolean isExecutable = false;

		boolean isFolder = false;
		File upperLevel = null;
		Set<File> children = new HashSet<File>();

		public String getName() {
			if (isFolder)
				return fileName;
			else
				return fileName + "." + extension;
		}

		@Override
		public String toString() {
			// String prefix = isFolder ? "/" : "";
			String appendix = isFolder ? "/" : "." + extension;
			return fileName + appendix;
		}
	}

	public class FileSystem {
		File root = new File();
		File current = root;

		public FileSystem() {
			root.fileName = "~";
			root.isFolder = true;
		}

		public boolean create(String name, boolean isFolder) {
			if (current.isFolder) {
				File newFile = new File();
				if (isFolder) {
					newFile.fileName = name;
				} else {
					String[] names = name.split("\\.");
					newFile.fileName = names[0];
					newFile.extension = names[1];
				}
				newFile.isFolder = isFolder;
				newFile.upperLevel = current;
				current.children.add(newFile);
				return true;
			} else {
				System.out.println("Can only create a file under a directory");
				return false;
			}
		}

		public void list() {
			for (File file : current.children) {
				System.out.printf("%5d %40s\n", file.size, file);
			}
		}

		public boolean changeDirectory(String dir) {
			if (dir.equals("..") && current.upperLevel != null) {
				current = current.upperLevel;
				return true;
			}
			for (File file : current.children) {
				if (file.getName().equals(dir)) {
					current = file;
				}
				return true;
			}
			return false;
		}

		public boolean remove(String[] names) {
			List<File> filesToRemove = new LinkedList<File>();
			boolean deleted = false;
			for (File file : current.children) {
				for (String name : names) {
					if (file.getName().equals(name))
						filesToRemove.add(file);
				}
			}
			for (File file : filesToRemove) {
				current.children.remove(file);
				deleted = true;
			}
			return deleted;
		}
	}

	public static String readCommand(File current) {
		System.out.println(current + "$ ");
		String input = new String();
		InputStreamReader converter = new InputStreamReader(System.in);
		BufferedReader in = new BufferedReader(converter);
		try {
			input = in.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return input;
	}

	public static void main(String[] args) {
		System.out.println("Bruce's file system starts.");
		Q7_9 instance = new Q7_9();
		FileSystem system = instance.system;
		String input = readCommand(system.current);

		while (!input.equals("exit")) {
			if (input.contains("touch")) {
				String[] commands = input.split(" ");
				system.create(commands[1], false);
			} else if (input.contains("mkdir")) {
				String[] commands = input.split(" ");
				system.create(commands[1], true);
			} else if (input.contains("ls")) {
				system.list();
			} else if (input.contains("cd")) {
				String[] commands = input.split(" ");
				system.changeDirectory(commands[1]);
			} else if (input.contains("rm")) {
				String[] commands = input.split(" ");
				String[] names = new String[commands.length - 1];
				for (int i = 0; i < names.length; ++i)
					names[i] = commands[i + 1];
				system.remove(names);
			}
			input = readCommand(system.current);
		}
	}

Solution:

	struct DataBlock { char data[DATA_BLOCK_SIZE]; };
	DataBlock dataBlocks[NUM_DATA_BLOCKS];
	struct INode { std::vector<int> datablocks; };
	
	struct MetaData {
		int size;
		Date last_modifed, created;
		char extra_attributes;
	};
	
	std::vector<bool> dataBlockUsed(NUM_DATA_BLOCKS);
	std::map<string, INode *> mapFromName;
	struct FSBase;
	
	struct File : public FSBase {
		private:
			std::vector<INode> * nodes;
			MetaData metaData;
	};
	
	struct Directory : pubic FSBase { std::vector<FSBase* > content; };
	struct FileSystem {
		init();
		mount(FileSystem*);
		unmount(FileSystem*);
		File createFile(cosnt char* name) { ... }
		Directory createDirectory(const char* name) { ... }
		// mapFromName to find INode corresponding to file
		void openFile(File * file, FileMode mode) { ... }
		void closeFile(File * file) { ... }
		void writeToFile(File * file, void * data, int num) { ... }
		void readFromFile(File* file, void* res, int numbutes, 
				int position) { ... }
	};

Are you like, WTF?! At least I was like that. I mean, is this really what is expected during the interview…?

Design the Othello game

Othello is played as follows: Each Othello piece is white on one side and black on the other. When a piece is surrounded by its opponents on both the left and right sides, or both the top and bottom, it is said to be captured and its color is flipped. On your turn, you must capture at least one of your opponent’s pieces.
The game ends when either user has no more valid moves, and the win is assigned to the person with the most pieces. Implement the object oriented design for Othello.

My initial thoughts:
The game flow looks like this:

  • Initialize the game which will be done by constructor
  • Get first user input
  • Validate the input
  • Change board configuration
  • Check if someone has won the game Get second user input
  • Validate the input
  • Change the board configuration
  • Check if someone has won the game

My initial codes:

There are a few logical bugs in the following game but the design is clearly shown here:

	public class Player {
		private final char label;
		private Set<Pair<Integer>> pieces = new HashSet<Pair<Integer>>();

		public Player(char label) {
			this.label = label;
		}

		public void addOnePiece(Pair<Integer> piece) {
			pieces.add(piece);
		}

		public void removeOnePiece(Pair<Integer> piece) {
			pieces.remove(piece);
		}

		public Set<Pair<Integer>> getPieces() {
			return pieces;
		}

		public char getLabel() {
			return label;
		}

	}

	public class Board {
		private final char BLACK = '*';
		private final char WHITE = '^';
		private Player black;
		private Player white;

		private char[][] board = new char[8][8];

		public Board() {
			for (int i = 0; i < board.length; ++i) {
				for (int j = 0; j < board[0].length; ++j) {
					board[i][j] = '.';
				}
			}
			black = new Player(BLACK);
			black.addOnePiece(new Pair<Integer>(3, 4));
			board[3][4] = BLACK;
			black.addOnePiece(new Pair<Integer>(4, 3));
			board[4][3] = BLACK;

			white = new Player(WHITE);
			white.addOnePiece(new Pair<Integer>(3, 3));
			board[3][3] = WHITE;
			white.addOnePiece(new Pair<Integer>(4, 4));
			board[4][4] = WHITE;
		}

		public boolean checkMove(Player player, Player opponent,
				Pair<Integer> piece) {
			if (piece.getX() < 0 || piece.getX() >= 7)
				return false;
			if (piece.getY() < 0 || piece.getY() >= 7)
				return false;
			char label = player.getLabel();
			char backup = board[piece.getX()][piece.getY()];
			board[piece.getX()][piece.getY()] = label;
			for (Pair<Integer> pos : opponent.getPieces()) {
				if (capturedLeftAndRight(pos) || capturedUpAndDown(pos))
					return true;
			}
			board[piece.getX()][piece.getY()] = backup;
			return false;
		}

		public boolean capturedLeftAndRight(Pair<Integer> piece) {
			int row = piece.getX();
			int col = piece.getY();
			int leftCol = col - 1 < 0 ? col : col - 1;
			int rightCol = col + 1 >= 8 ? col : col + 1;
			char left = board[row][leftCol];
			char right = board[row][rightCol];
			return left == right && left != board[row][col] && left != '.';
		}

		public boolean capturedUpAndDown(Pair<Integer> piece) {
			int row = piece.getX();
			int col = piece.getY();
			int upRow = row - 1 < 0 ? row : row - 1;
			int downRow = row + 1 >= 8 ? row : row + 1;
			char up = board[upRow][col];
			char down = board[downRow][col];
			return up == down && up != board[row][col] && up != '.';
		}

		public void flip(Pair<Integer> piece) {
			if (board[piece.getX()][piece.getY()] == BLACK)
				board[piece.getX()][piece.getY()] = WHITE;
			else if (board[piece.getX()][piece.getY()] == WHITE)
				board[piece.getX()][piece.getY()] = BLACK;
		}

		@Override
		public String toString() {
			String result = new String();
			result += ' ';
			for (int i = 0; i < board.length; ++i) {
				result += i;
			}
			result += '\n';
			for (int i = 0; i < board.length; ++i) {
				result += i;
				for (int j = 0; j < board[0].length; ++j) {
					result += board[i][j];
				}
				result += '\n';
			}
			return result;
		}

		public void step() {
			// System.out.println(this);

			String input = new String();
			int x = 0;
			int y = 0;
			do {
				System.out.println("White's turn: ");
				InputStreamReader converter = new InputStreamReader(System.in);
				BufferedReader in = new BufferedReader(converter);
				try {
					input = in.readLine();
					char[] inputs = input.toCharArray();
					x = Integer.parseInt("" + inputs[0]);
					y = Integer.parseInt("" + inputs[1]);
				} catch (IOException e) {
					e.printStackTrace();
				}
			} while (!checkMove(white, black, new Pair<Integer>(x, y)));
			board[x][y] = WHITE;
			white.addOnePiece(new Pair<Integer>(x, y));

			boolean blackWin = true;
			List<Pair<Integer>> posToBeRemoved = new LinkedList<Pair<Integer>>();
			for (Pair<Integer> pos : black.getPieces()) {
				if (capturedLeftAndRight(pos) || capturedUpAndDown(pos)) {
					flip(pos);
					// black.removeOnePiece(pos);
					posToBeRemoved.add(pos);
					white.addOnePiece(pos);
					blackWin = false;
				}
			}
			for (Pair<Integer> pos : posToBeRemoved) {
				black.removeOnePiece(pos);
			}
			posToBeRemoved.clear();
			System.out.println(this);
			if (blackWin) {
				System.out.println("Black has won!");
				System.exit(0);
			}

			do {
				System.out.println("Black's turn: ");
				InputStreamReader converter = new InputStreamReader(System.in);
				BufferedReader in = new BufferedReader(converter);
				try {
					input = in.readLine();
					char[] inputs = input.toCharArray();
					x = Integer.parseInt("" + inputs[0]);
					y = Integer.parseInt("" + inputs[1]);
				} catch (IOException e) {
					e.printStackTrace();
				}
			} while (!checkMove(black, white, new Pair<Integer>(x, y)));
			board[x][y] = BLACK;
			black.addOnePiece(new Pair<Integer>(x, y));

			boolean whiteWin = true;
			for (Pair<Integer> pos : white.getPieces()) {
				if (capturedLeftAndRight(pos) || capturedUpAndDown(pos)) {
					flip(pos);
					// white.removeOnePiece(pos);
					posToBeRemoved.add(pos);
					black.addOnePiece(pos);
					whiteWin = false;
				}
			}
			for (Pair<Integer> pos : posToBeRemoved) {
				white.removeOnePiece(pos);
			}
			posToBeRemoved.clear();
			System.out.println(this);
			if (whiteWin) {
				System.out.println("White has won!");
				System.exit(0);
			}
		}
	}

Design an online chat server

Explain how you would design a chat server. In particular, provide details about the various backend components, classes, and methods. What would be the hardest problems to solve?

My initial thoughts:
We certainly need a user class. We need to handle concurrency. That is the hardest problem.

My initial codes:

	public class MyUser {
		private long ID;
		private String username;
		private String password;

		public void speak() {

		}
	}

	public class MySession {
		Set users;

		public void handleEvent() {
			// hitting 'Enter' by any user
			// will trigger an event.
			// We need to handle them in turns
			// Need a queue here, perhaps
		}

		public void display(MyUser user) {
			// display user's chat
		}
	}

	public class MyChatServer {
		MySession currentSession;
		Set registeredUsers;

		public void register() {
			// register a user
		}

		public void login() {
			// ask for username and password,
			// retrieve the user
			MyUser user = null;
			currentSession.users.add(user);
		}

		public void run() {

		}

	}

Solution:
Apparently, I am too naive and I think too few. Here’s the detailed solution.

What is our chat server?
This is something you should discuss with your interviewer, but let’s make a couple of as- sumptions: imagine we’re designing a basic chat server that needs to support a small number of users. People have a contact list, they see who is online vs offline, and they can send text-based messages to them. We will not worry about supporting group chat, voice chat, etc. We will also assume that contact lists are mutual: I can only talk to you if you can talk to me. Let’s keep it simple.

What specific actions does it need to support?

  • User A signs online
  • User A asks for their contact list, with each person’s current status
  • Friends of User A now see User A as online
  • User A adds User B to contact list
  • User A sends text-based message to User B
  • User A changes status message and/or status type
  • User A removes User B
  • User A signs offline

What can we learn about these requirements?
We must have a concept of users, add request status, online status, and messages.

What are the core components?
We’ll need a database to store items and an “always online” application as the server. We might recommend using XML for the communication between the chat server and the clients, as it’s easy for a person and a machine to read.

What are the key objects and methods?
We have listed the key objects and methods below. Note that we have hidden many of the details, such as how to actually push the data out to a client.

	enum StatusType {
		online, offline, away;
	}

	class Status {
		StatusType status_type;
		String status_message;
	}

	class User {
		String username;
		String display_name;
		User[] contact_list;
		AddRequest[] requests;

		boolean updateStatus(StatusType stype, 
				String message) {
		};

		boolean addUserWithUsername(String name);

		boolean approveRequest(String username);

		boolean denyRequest(String username);

		boolean removeContact(String username);

		boolean sendMessage(String username, 
				String message);
	}

	// Holds data that from_user would like to add to_user
	class AddRequest {
		User from_user;
		User to_user;
	}

	class Server {
		User getUserByUsername(String username);
	}

What problems would be the hardest to solve (or the most interesting)?

  1. How do we know if someone is online—I mean, really, really know?
    While we would like users to tell us when they sign off, we can’t know for sure. A user’s connection might have died, for example. To make sure that we know when a user has signed off, we might try regularly pinging the client to make sure it’s still there.
  2. How do we deal with conflicting information?
    We have some information stored in the computer’s memory and some in the database. What happens if they get out of sync? Which one is “right”?
  3. How do we make our server scale?
    While we designed out chat server without worrying -too much- about scalability, in real life this would be a concern. We’d need to split our data across many servers, which would increase our concern about out of sync data.
  4. How we do prevent denial of service attacks?
    Clients can push data to us—what if they try to DOS us? How do we prevent that?

Implement a jigsaw puzzle

Implement a jigsaw puzzle. Design the data structures and explain an algorithm to solve the puzzle.

My initial thoughts:
Each piece contains pointer to its four edges. We iterate through pairs of pieces to check whether they match along any edge.

My initial codes:

	public class MyPiece {
		int ID;
		MyPiece up;
		MyPiece down;
		MyPiece left;
		MyPiece right;

		int[][] pixels;

		public MyPiece(int iD, MyPiece up, MyPiece down, MyPiece left,
				MyPiece right, int[][] pixels) {
			super();
			ID = iD;
			this.up = up;
			this.down = down;
			this.left = left;
			this.right = right;
			this.pixels = pixels;
		}

		public void display() {
			// TODO display this piece
		}

		@Override
		public Object clone() {
			return new MyPiece(ID, up, down, left, right, pixels);
		}
	}

	public class MyPicture {
		Set<MyPiece> pieces;

	}

	public class MyJigsawPuzzle {
		MyPicture picture;
		int ROW;
		int COL;
		MyPiece[][] puzzle;

		public void initialize() {
			// TODO initialize the picture
		}

		public void startGame() {
			List<MyPiece> pieceList = new LinkedList<MyPiece>();
			for (MyPiece piece : picture.pieces) {
				pieceList.add(piece);
			}
			Collections.shuffle(pieceList);
			puzzle = new MyPiece[ROW][COL];
			for (int i = 0; i < ROW; ++i) {
				for (int j = 0; j < COL; ++j) {
					puzzle[i][j] = pieceList.get(pieceList.size() - 1);
					pieceList.remove(puzzle[i][j]);
				}

			}

			for (int i = 0; i < ROW; ++i) {
				for (int j = 0; j < COL; ++j) {
					puzzle[i][j].display();
				}
			}
		}

		public boolean isComplete() {
			for (int i = 0; i < ROW; ++i) {
				for (int j = 0; j < COL; ++j) {
					MyPiece piece = puzzle[i][j];
					MyPiece up = i >= 1 ? puzzle[i - 1][j] : null;
					MyPiece down = i < ROW - 1 ? puzzle[i + 1][j] : null;
					MyPiece left = j >= 1 ? puzzle[i][j - 1] : null;
					MyPiece right = j < COL - 1 ? puzzle[i][j + 1] : null;
					if (piece.up != up || piece.down != down
							|| piece.left != left || piece.right != right)
						return false;
				}
			}
			return true;
		}

		public void solve() {
			for (int i = 0; i < ROW; ++i) {
				for (int j = 0; j < COL; ++j) {
					MyPiece A = puzzle[i][j];
					for (int m = 0; m < ROW; ++m) {
						for (int n = 0; j < COL; ++n) {
							MyPiece B = puzzle[m][n];
							if (A.up == B)
								swap(i - 1, j, m, n);
							else if (A.down == B)
								swap(i + 1, j, m, n);
							else if (A.left == B)
								swap(i, j - 1, m, n);
							else if (A.right == B)
								swap(i, j + 1, m, n);
						}
					}
				}
			}
		}

		public void swap(int i, int j, int m, int n) {
			MyPiece temp = puzzle[i][j];
			puzzle[i][j] = puzzle[m][n];
			puzzle[m][n] = temp;
		}
	}

Solution:

	class Edge {
		enum Type {
			inner, outer, flat
		}

		Piece parent;
		Type type;

		boolean fitsWith(Edge type) {
		}; // Inners & outer fit together.
	}

	class Piece {
		Edge left, right, top, bottom;

		// 90, 180, etc
		Orientation solvedOrientation = 90;
	}

	class Puzzle {
		// Remaining pieces left to put away.
		Piece[][] pieces;
		Piece[][] solution;
		Edge[] inners, outers, flats;

		// We're going to solve this by working our way
		// in-wards, starting with the corners.
		// This is a list of the inside edges.
		Edge[] exposed_edges;

		void sort() {

			// Iterate through all edges,
			// adding each to inners, outers, etc,
			// as appropriate.
			// Look for the corners—add those to solution.
			// Add each non-flat edge of the corner
			// to exposed_edges.

		}

		void solve() {
			for (Edge edge1 : exposed_edges) {
				// Look for a match to edge1
				if (edge1.type == Edge.Type.inner) {
					for (Edge edge2 : outers) {
						if (edge1.fitsWith(edge2)) {
							// We found a match!
							// Remove edge1 from
							// exposed_edges.
							// Add edge2's piece
							// to solution.
							// Check which edges of edge2
							// are exposed, and add
							// those to exposed_edges.
						}
					}
					// Do the same thing,
					// swapping inner & outer.
				}
			}
		}
	}

Design data structures for an online book reader system

Design the data structures for an online book reader system.

My initial thoughts:
I design this book reader system based on iBooks from Apple: you can search for books, add bookmarks and so on.

	public class MyBook {
		private final String author;
		private final String title;
		private final int number_pages;
		private final List<String> content;
		private final List<Integer> chapterIndex;

		private List<Integer> bookmarks;

		public MyBook(String author, String title, int number_pages,
				ArrayList<String> content, List<Integer> chapterIndex) {
			super();
			this.author = author;
			this.title = title;
			this.number_pages = number_pages;
			this.content = content;
			this.chapterIndex = chapterIndex;
		}

		public void addBookMark(int pageNumber) {
			bookmarks.add(pageNumber);
		}

		public List<Integer> getBookmarks() {
			return bookmarks;
		}

		public String getPage(int pageNumber) {
			return content.get(pageNumber);
		}
	}

	public class MyOnlineReader {
		private Map<String, Map<String, MyBook>> bookMap;
		private MyBook currentBook;
		private int currentPage;

		public void openBook(String author, String title) {
			currentBook = bookMap.get(author).get(title);
			List<Integer> bookmarks = currentBook.getBookmarks();
			if (bookmarks.isEmpty())
				bookmarks.add(0);
			currentPage = bookmarks.get(bookmarks.size() - 1);
			System.out.println(currentBook.getPage(currentPage));
		}

		private boolean finished() {
			return currentPage == currentBook.number_pages - 1;
		}

		public void addBookMark() {
			if (!currentBook.getBookmarks().contains(currentPage))
				currentBook.addBookMark(currentPage);
		}

		public void displayAllBookMark() {
			System.out.println(currentBook.getBookmarks());
		}

		public void nextPage() {
			List<Integer> bookmarks = currentBook.getBookmarks();
			bookmarks.remove(currentPage);
			currentPage = finished() ? 
					currentPage : currentPage + 1;
			bookmarks.add(currentPage);
			System.out.println(currentBook.getPage(currentPage));
		}

		public void previousPage() {
			List<Integer> bookmarks = currentBook.getBookmarks();
			bookmarks.remove(currentPage);
			currentPage = currentPage == 0 ? 
					currentPage : currentPage - 1;
			bookmarks.add(currentPage);
			System.out.println(currentBook.getPage(currentPage));
		}

		public void goToPage(int pageNumber) {
			if (pageNumber < 0 || pageNumber >= currentBook.number_pages)
				return;
			List<Integer> bookmarks = currentBook.getBookmarks();
			bookmarks.remove(currentPage);
			currentPage = pageNumber;
			bookmarks.add(currentPage);
			System.out.println(currentBook.getPage(currentPage));
		}
	}

Solution:

	public class Book {
		private long ID;
		private String details;
		private static Set<Book> books;

		public long getID() {
			return ID;
		}

		public Book(long id, String details) {
		}

		public static void addBook(long iD, String details) {
			books.add(new Book(iD, details));
		}

		public void update() {
		}

		public static void delete(Book b) {
			books.remove(b);
		}

		public static Book find(long id) {
			for (Book b : books)
				if (b.getID() == id)
					return b;
			return null;
		}
	}

	public class User {
		private long ID;
		private String details;
		private int accountType;
		private static Set<User> users;

		public long getID() {
			return ID;
		}

		public Book searchLibrary(long id) {
			return Book.find(id);
		}

		public void renewMembership() {
		}

		public static User find(long ID) {
			for (User u : users) {
				if (u.getID() == ID)
					return u;
			}
			return null;
		}

		public static void addUser(long ID, String details, 
				int accountType) {
			users.add(new User(ID, details, accountType));
		}

		public User(long iD, String details, int accountType) {
		}
	}

	public class OnlineReaderSystem {
		private Book b;
		private User u;

		public OnlineReaderSystem(Book b, User u) {
		}

		public void listenRequest() {
		}

		public Book searchBook(long ID) {
			return Book.find(ID);
		}

		public User searchUser(long ID) {
			return User.find(ID);
		}

		public void display() {
		}
	}

One thing I learnt from the solution is to put a private static set of all users in a user class. Hence all of the single user shares a copy of references to all the other users. Brilliant design.

Design a chess game using OO principles

Design a chess game using object oriented principles.

My initial thoughts(code):

	public abstract class MyChessPiece {
		private int horizontal;
		private int vertical;

		public abstract boolean moveTo(Pair<Integer> des);

		public Pair<Integer> getPos() {
			return new Pair<Integer>(horizontal, vertical);
		}
	}

	public class MyKing extends MyChessPiece {
		@Override
		public boolean moveTo(Pair<Integer> des) {
			return false;
		}
	}

	public class MyRook extends MyChessPiece {
		@Override
		public boolean moveTo(Pair<Integer> des) {
			return false;
		}
	}

	public class MyBishop extends MyChessPiece {
		@Override
		public boolean moveTo(Pair<Integer> des) {
			return false;
		}
	}

	public class MyQueen extends MyChessPiece {
		@Override
		public boolean moveTo(Pair<Integer> des) {
			return false;
		}
	}

	public class MyKnight extends MyChessPiece {
		@Override
		public boolean moveTo(Pair<Integer> des) {
			return false;
		}
	}

	public class MyPawn extends MyChessPiece {
		@Override
		public boolean moveTo(Pair<Integer> des) {
			return false;
		}
	}

	public class MyPlayer {
		private Map<Pair<Integer>, MyChessPiece> pieces;

		public boolean move(Pair<Integer> origin, Pair<Integer> des) {
			return pieces.get(origin).moveTo(des);
		}
	}

	public class MyChessGame {
		private MyPlayer black;
		private MyPlayer white;

		public void initialize() {
			// initialize the game by putting pieces for black and white
		}

		public boolean check(MyPlayer white, MyPlayer black) {
			return false;
		}

		public void handleCollision(MyPlayer white, MyPlayer black) {
			// follow the rule
		}

		public void play() {
			boolean gameOver = false;
			while (!gameOver) {
				// white moves
				white.move(new Pair<Integer>(0, 0), new Pair<Integer>(0, 0));
				black.move(new Pair<Integer>(0, 0), new Pair<Integer>(0, 0));

				gameOver = check(white, black);
			}
		}

	}

Solution:

	public class ChessPieceTurn {
	};

	public class GameManager {
		void processTurn(PlayerBase player) {
		};

		boolean acceptTurn(ChessPieceTurn turn) {
			return true;
		};

		Position currentPosition;
	}

	public abstract class PlayerBase {
		public abstract ChessPieceTurn getTurn(Position p);
	}

	class ComputerPlayer extends PlayerBase {
		@Override
		public ChessPieceTurn getTurn(Position p) {
			return null;
		}

		public void setDifficulty() {
		};

		public PositionEstimator estimater;
		public PositionBackTracker backtracter;
	}

	public class HumanPlayer extends PlayerBase {
		@Override
		public ChessPieceTurn getTurn(Position p) {
			return null;
		}
	}

	public abstract class ChessPieceBase {
		abstract boolean canBeChecked();

		abstract boolean isSupportCastle();
	}

	public class King extends ChessPieceBase {

		@Override
		boolean canBeChecked() {
			// TODO Auto-generated method stub
			return false;
		}

		@Override
		boolean isSupportCastle() {
			// TODO Auto-generated method stub
			return false;
		}
	}

	public class Queen extends ChessPieceBase {

		@Override
		boolean canBeChecked() {
			// TODO Auto-generated method stub
			return false;
		}

		@Override
		boolean isSupportCastle() {
			// TODO Auto-generated method stub
			return false;
		}
	}

	public class Position { // represents chess positions in compact form
		ArrayList<ChessPieceBase> black;

		ArrayList<ChessPieceBase> white;
	}

	public class PositionBackTracker {
		public Position getNext(Position p) {
			return null;
		}
	}

	public class PositionEstimator {
		public PositionPotentialValue estimate(Position p) {
			return null;
		}
	}

	public abstract class PositionPotentialValue {
		abstract boolean lessThan(PositionPotentialValue pv);
	}

Previous Older Entries