7.1
Design the data structures for a generic deck of cards. Explain how you would subclass it to implement particular card games.
SOLUTION
Assume that we’re building a blackjack game, so we need to know the value of the cards.
Face cards are ten and an ace is 11 (most of the time, but that’s the job of the Hand class, not
the following class).
public class BlackJackCard extends Card { public BlackJackCard(int r, Suit s) { super(r, s); } public int value() { int r = super.value(); if (r == 1) return 11; // aces are 11 if (r < 10) return r; return 10; } boolean isAce() { return super.value() == 1; } } public class Card { public enum Suit { CLUBS (1), SPADES (2), HEARTS (3), DIAMONDS (4); int value; private Suit(int v) { value = v; } }; private int card; private Suit suit; public Card(int r, Suit s) { card = r; suit = s; } public int value() { return card; } public Suit suit() { return suit; } }
7.2
Imagine you have a call center with three levels of employees: fresher, technical lead (TL), product manager (PM). There can be multiple employees, but only one TL or PM. An incoming telephone call must be allocated to a fresher who is free. If a fresher can’t handle the call, he or she must escalate the call to technical lead. If the TL is not free or not able to handle it, then the call should be escalated to PM. Design the classes and data structures for this problem. Implement a method getCallHandler().
SOLUTION
All three ranks of employees have different work to be done, so those specific functions are profile specific. We should keep these specific things within their respective class.
There are a few things which are common to them, like address, name, job title, age, etc. These things can be kept in one class and can be extended / inherited by others.
Finally, there should be one CallHandler class which would route the calls to the concerned person.
NOTE: On any object oriented design question, there are many ways to design the objects. Discuss the trade-offs of different solutions with your interviewer. You should usually design for long term code flexibility and maintenance.
class Call { int rank = 0; // minimal rank of employee who can handle this call public void reply(String message) { // play recorded message to the customer } public void disconnect() { reply("Thank you for calling"); } } class Employee { CallHandler callHandler; int rank; // 0- fresher, 1 - technical lead, 2 - product manager boolean free; public Employee(int rank) { this.rank = rank; } // start the conversation void ReceiveCall(Call call) { free = false; } // the issue is resolved, finish the call void CallHandled(Call call) { call.disconnect(); free = true; // look if there is a call waiting in queue callHandler.getNextCall(this); } // the issue is not resolved, escalate the call void CannotHandle(Call call) { call.rank = rank + 1; callHandler.dispatchCall(call); free = true; // look if there is a call waiting in queue callHandler.getNextCall(this); } } class Fresher extends Employee { public Fresher() { super(0); } } class ProductManager extends Employee { public ProductManager() { super(2); } } class TechLead extends Employee { public TechLead() { super(1); } } public class CallHandler { static final int LEVELS = 3; // we have 3 levels of employees static final int NUM_FRESHERS = 5; // we have 5 freshers ArrayList<Employee>[] employeeLevels = new ArrayList[LEVELS]; // queues for each call抯 rank Queue<Call>[] callQueues = new LinkedList[LEVELS]; public CallHandler() { // create freshers ArrayList<Employee> freshers = new ArrayList(NUM_FRESHERS); for (int k = 0; k < NUM_FRESHERS - 1; k++) { freshers.add(new Fresher()); } employeeLevels[0] = freshers; // create technical lead ArrayList<Employee> tls = new ArrayList(1); tls.add(new TechLead()); // we have 1 technical lead employeeLevels[1] = tls; // create product manager ArrayList<Employee> pms = new ArrayList(1); pms.add(new ProductManager()); // we have 1 product manager employeeLevels[1] = pms; } Employee getCallHandler(Call call) { for (int level = call.rank; level < LEVELS - 1; level++) { ArrayList<Employee> employeeLevel = employeeLevels[level]; for (Employee emp : employeeLevel) { if (emp.free) { return emp; } } } return null; } // routes the call to an available employee, or saves in a queue // if no employee available void dispatchCall(Call call) { // try to route the call to an employee with minimal rank Employee emp = getCallHandler(call); if (emp != null) { emp.ReceiveCall(call); } else { // place the call into corresponding call queue according to // its rank call.reply("Please wait for free employee to reply"); callQueues[call.rank].add(call); } } // employee got free, look for a waiting call he/she can serve void getNextCall(Employee emp) { // check the queues, starting from the highest rank this // employee can serve for (int rank = emp.rank; rank >= 0; rank--) { Queue<Call> que = callQueues[rank]; Call call = que.poll(); // remove the first call, if any if (call != null) { emp.ReceiveCall(call); return; } } } }
7.3
Design a musical juke box using object oriented principles.
SOLUTION
Let’s first understand the basic system components:
»» CD player
»» CD
»» Display () (displays length of song, remaining time and playlist)
Now, let’s break this down further:
»» Playlist creation (includes add, delete, shuffle etc sub functionalities)
»» CD selector
»» Track selector
»» Queueing up a song
»» Get next song from playlist
A user also can be introduced:
»» Adding
»» Deleting
»» Credit information
How do we group this functionality based on Objects (data + functions which go together)?
Object oriented design suggests wrapping up data with their operating functions in a single entity class.
public class CD { } public class CDPlayer { private Playlist p; private CD c; public Playlist getPlaylist() { return p; } public void setPlaylist(Playlist p) { this.p = p; } public CD getCD() { return c; } public void setCD(CD c) { this.c = c; } public CDPlayer(Playlist p) { this.p = p; } public CDPlayer(CD c, Playlist p) { this.p = p; this.c = c; } public CDPlayer(CD c){ this.c = c; } public void playTrack(Song s) { } } public class JukeBox { private CDPlayer cdPlayer; private User user; private Set<CD> cdCollection; private TrackSelector ts; public JukeBox(CDPlayer cdPlayer, User user, Set<CD> cdCollection, TrackSelector ts) { super(); this.cdPlayer = cdPlayer; this.user = user; this.cdCollection = cdCollection; this.ts = ts; } public Song getCurrentTrack() { return ts.getCurrentSong(); } public void processOneUser(User u) { this.user = u; } } public class Playlist { private Song track; private Queue<Song> queue; public Playlist(Song track, Queue<Song> queue) { super(); this.track = track; this.queue = queue; } public Song getNextTrackToPlay(){ return queue.peek(); } public void queueUpTrack(Song s){ queue.add(s); } } public class Song { private String songName; public String toString() { return songName; } } public class TrackSelector { private Song currentSong; public TrackSelector(Song s) { currentSong=s; } public void setTrack(Song s) { currentSong = s; } public Song getCurrentSong() { return currentSong; } } public class User { private String name; public String getName() { return name; } public void setName(String name) { this.name = name; } public long getID() { return ID; } public void setID(long iD) { ID = iD; } private long ID; public User(String name, long iD) { this.name = name; ID = iD; } public User getUser() { return this; } public static User addUser(String name, long iD){ return new User(name, iD); } }
7.4
Design a chess game using object oriented principles.
SOLUTION
package Question7_4; //include info about timing, etc. public class ChessFormat { } package Question7_4; public abstract class ChessPieceBase { abstract void estimationParameter0(); /* used by PositionEstimater in different circumstances */ abstract int estimationParameter1(); abstract boolean canBeChecked(); abstract boolean isSupportCastle(); // other rule-base properties } package Question7_4; public class ChessPieceTurn { }; package Question7_4; class ComputerPlayer extends PlayerBase { public ChessPieceTurn getTurn(Position p) { return null; } public void setDifficulty() { }; public PositionEstimator estimater; public PositionBackTracker backtracter; } package Question7_4; public class GameManager { // keeps track of time, end of the game, etc void processTurn(PlayerBase player) { }; boolean acceptTurn(ChessPieceTurn turn) { return true; }; Position currentPosition; ChessFormat format; public void setGameLog(String filePath) { }; } package Question7_4; public class HumanPlayer extends PlayerBase { public ChessPieceTurn getTurn(Position p) { return null; } } package Question7_4; public class King extends ChessPieceBase { void estimationParameter0() { }; int estimationParameter1() { return 0; } boolean canBeChecked() { return false; } boolean isSupportCastle() { return false; } } package Question7_4; public abstract class PlayerBase { public abstract ChessPieceTurn getTurn(Position p); } package Question7_4; public class PositionBackTracker { // get next position for estimation. public static Position getNext(Position p) { return null; } } package Question7_4; public class PositionEstimator { // calculate value of a position public static PositionPotentialValue estimate(Position p) { return null; } } package Question7_4; import java.util.ArrayList; public class Position { // represents chess positions in compact form ArrayList<ChessPieceBase> black; ArrayList<ChessPieceBase> white; } package Question7_4; public abstract class PositionPotentialValue { /* compares value of potential game position */ abstract boolean lessThan(PositionPotentialValue pv); } package Question7_4; public class Queen extends ChessPieceBase { void estimationParameter0() { }; int estimationParameter1() { return 0; } boolean canBeChecked() { return false; } boolean isSupportCastle() { return false; } }
7.5
Design the data structures for an online book reader system.
SOLUTION
Since the problem doesn’t describe much about the functionality, let’s assume we want to design a basic online reading system which provides the following functionality:
»» User membership creation and extension.
»» Searching the database of books
»» Reading the books
To implement these we may require many other functions, like get, set, update, etc. Objects required would likely include User, Book, and Library.
The following code / object oriented design describes this functionality:
This design is a very simplistic implementation of such a system. We have a class for User to keep all the information regarding the user, and an identifier to identify each user uniquely. We can add functionality like registering the user, charging a membership amount and monthly / daily quota, etc.
Next, we have book class where we will keep all the book’s information. We would also implement functions like add / delete / update books.
Finally, we have a manager class for managing the online book reader system which would have a listen function to listen for any incoming requests to log in. It also provides book search functionality and display functionality. Because the end user interacts through this class, search must be implemented here.
public class Book { private long ID; private String details; private static Set<Book> books; public Book(long iD, String details) { ID = iD; this.details = 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 long getID() { return ID; } public void setID(long iD) { ID = iD; } public String getDetails() { return details; } public void setDetails(String details) { this.details = details; } } public class OnlineReaderSystem { private Book b; private User u; public OnlineReaderSystem(Book b, User u) { this.b = b; this.u = 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() { } public Book getBook() { return b; } public void setBook(Book b) { this.b = b; } public User getUser() { return u; } public void setUser(User u) { this.u = u; } } public class User { private long ID; private String details; private int accountType; private static Set<User> users; 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) { ID = iD; this.details = details; this.accountType = accountType; } public long getID() { return ID; } public void setID(long iD) { ID = iD; } public String getDetails() { return details; } public void setDetails(String details) { this.details = details; } public int getAccountType() { return accountType; } public void setAccountType(int accountType) { this.accountType = accountType; } }
7.6
Implement a jigsaw puzzle. Design the data structures and explain an algorithm to solve the puzzle.
SOLUTION
Overview:
1.
We grouped the edges by their type. Because inners go with outers, and vice versa,
this enables us to go straight to the potential matches.
We keep track of the inner perimeter of the puzzle (exposed_edges) as we work our
way inwards. exposed_edges is initialized to be the corner’s edges.
7.7
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?
SOLUTION
What is our chat server?
This is something you should discuss with your interviewer, but let’s make a couple of assumptions: 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)?
Q1 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.
Q2 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”?
Q3 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.
Q4 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?
7.8
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.
SOLUTION
Othello has these major steps:
2. Game () which would be the main function to manage all the activity in the game:
3. Initialize the game which will be done by constructor
4. Get first user input
5. Validate the input
6. Change board configuration
7. Check if someone has won the game
8. Get second user input
9. Validate the input
10. Change the board configuration
11. Check if someone has won the game...
NOTE: The full code for Othello is contained in the code attachment.
package Question7_8; import java.io.*; import java.util.*; import java.awt.Point; public class Question { private final int white = 1; private final int black = 2; private int[][] board; /* Sets up the board in the standard othello starting positions, * and starts the game */ public void start () { board = new int [8] [8]; board[3][3] = white; board[4][4] = white; board[3][4] = black; board[4][3] = black; game(); } /* Prints an ascii art representation of the board. */ private void printBoard () { System.out.println ("-----------------"); for (int i = 0; i < 8; i++) { System.out.print("|"); for (int j = 0; j < 8; j++) { switch (board [j] [i]) { case white: System.out.print("O|"); break; case black: System.out.print("@|"); break; default: System.out.print(" |"); break; } } System.out.println("\n-----------------"); } System.out.println(""); } /* Returns the winner, if any. If there are no winners, returns * 0 */ private int won() { if (!canGo (white) && !canGo (black)) { int count = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (board [i] [j] == white) { count++; } if (board [i] [j] == black) { count--; } } } if (count > 0) return white; if (count < 0) return black; return 3; } return 0; } /* Returns whether the player of the specified color has a valid * move in his turn. This will return false when * 1. none of his pieces are present * 2. none of his moves result in him gaining new pieces * 3. the board is filled up */ private boolean canGo(int color) { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (isValid(color, i, j)) return true; } } return false; } /* Returns if a move at coordinate (x,y) is a valid move for the * specified player */ private boolean isValid(int color, int x, int y) { int opponent = 3 - color; if (x < 0 || x > 7 || y < 0 || y > 7) { return false; } if (board [x] [y] != 0) { return false; // The space is already occupied } else { // Check in all 8 directions for (int dx = -1; dx < 2; dx++) { for (int dy = -1; dy < 2; dy++) { if (x + dx < 0 || x + dx > 7 || y + dy < 0 || y + dy > 7) { continue; } if (board [x + dx] [y + dy] == opponent) { // Found opponent piece int tempX = x; int tempY = y; while (true) { tempX += dx; tempY += dy; if (board[tempX][tempY] == 0) { break; } if (tempX < 0 || tempX > 7 || tempY < 0 || tempY > 7) { break; } if (board [tempX] [tempY] == color) { return true; } } } } } return false; } } /* Prompts the player for a move and the coordinates for the move. * Throws an exception if the input is not valid or if the entered * coordinates do not make a valid move. */ private void getMove (int color) throws Exception { BufferedReader br = new BufferedReader( new InputStreamReader (System.in)); if (canGo(color)) { System.out.println ("It抯 " + (color == 1 ? "white" : "black") + "抯 turn:"); int x, y; System.out.print ("Enter an x coordinate: "); x = Integer.parseInt (br.readLine ()); System.out.print ("Enter an y coordinate: "); y = Integer.parseInt (br.readLine ()); if (!isValid (color, x, y)) { throw new Exception (); } else { add (x, y, color); } } else { System.out.println((color== 1 ? "white": "black") + " doesn抰 have any possible moves this turn, skipping."); } } /* Adds the move onto the board, and the pieces gained from that * move. Assumes the move is valid. */ private void add (int x, int y, int color) { List<Point> endPoints = new ArrayList<Point>(); board[x][y] = color; int opponent = 3 - color; //check in all 8 directions for (int dx = -1; dx < 2; dx++) { for (int dy = -1; dy < 2; dy++) { if (x + dx < 0 || x + dx > 7 || y + dy < 0 || y + dy > 7) { continue; } if (board[x + dx][y + dy] == opponent) { // Found opponent piece int tempX = x; int tempY = y; while (true) { tempX += dx; tempY += dy; if (board[tempX][tempY] == 0) { break; } if (tempX < 0 || tempX > 7 || tempY < 0 || tempY > 7) { break; } if (board[tempX][tempY] == color) { endPoints.add(new Point(tempX, tempY)); } } } } } for (int i = 0; i < endPoints.size(); i++) { Point p = endPoints.get(i); int dx = p.x - x; int dy = p.y - y; if (dx != 0) { dx = p.x - x > 0 ? 1:- 1; } if (dy != 0) { dy = p.y - y > 0 ? 1 : -1; } int tempX = x; int tempY = y; while (!(tempX == p.x && tempY == p.y)) { tempX += dx; tempY += dy; board[tempX][tempY] = color; } } } /* The actual game: runs continuously until a player wins */ private void game() { printBoard(); while (won() == 0) { boolean valid = false; while (!valid) { try { getMove(black); valid = true; } catch (Exception e) { System.out.println ("Please enter a valid coordinate!"); } } valid = false; printBoard(); while (!valid) { try { getMove(white); valid = true; } catch (Exception e) { System.out.println ("Please enter a valid coordinate!"); } } printBoard (); } if(won()!=3) { System.out.println (won () == 1 ? "white" : "black" + " won!"); } else { System.out.println("It抯 a draw!"); } } public static void main(String[] args) { Question o = new Question(); o.start (); } }
7.9
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.
SOLUTION
For data block allocation, we can use bitmask vector and linear search (see “Practical File System Design”) or B+ trees (see Wikipedia).
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) { ... } };
7.10 Describe the data structures and algorithms that you would use to implement a garbage collector in C++.
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; }