Design a Mine Sweeper Game [CCIB]

http://www.geeksforgeeks.org/cpp-implementation-minesweeper-game/

Design a WhastApp Service

Design a WhastApp Service

http://massivetechinterview.blogspot.in/2015/10/whats-up-architecture.html

https://www.quora.com/How-does-messaging-work-in-WhatsApp

https://www.interviewbit.com/problems/design-cache/
http://massivetechinterview.blogspot.in/2015/10/caching.html

Design an Elevator

Design Elevator system. And then write an algorithm for that Design such that, the user request should be completed in logN time in a N story building with M elevators,
Also discuss elevator Algorithm or data structures used for elevators.

Data Structure Design
A good structure to use for this algorithm is three priority queues:

For the current direction with entries past the current point,
For the opposite direction, and
for the current direction prior to the current point.
Your implementation would first decide the direction, then pick a queue into which to place the requested pair of {from, to} values.

http://stackoverflow.com/questions/12009556/datastructure-for-elevator-mechanism
http://www.i-programmer.info/programmer-puzzles/203-sharpen-your-coding-skills/4561-sharpen-your-coding-skills-elevator-puzzle.html?start=1

OO Design Button Class
A typical lift has buttons(Elevator buttons) inside the cabin to let the user who got in the lift to select his/her desired floor.Similarly each floor has buttons (Floor buttons) to summon the lift to go floors above and floor below respectively. The buttons illuminate indicating the request is accepted. And the lift reaches the requested floor the button stops illuminating.

Use cases: User

• presses the floor button to summon the lift
• presses the elevator button to make the lift move to the desired floor

Floor Button/Elevator Button

• illuminates when pressed
• places a elevator request when pressed

Button is abstract class defining common behavior like illuminate, doNotIlluminate. FloorButton, ElevatorButton extend Button type and define placeRequest() which is invoked when the button is pressed. Both the floor button presses and elevator button presses adds requests at a common place.

Elevator Class:

• Opens/close the door
• ElevatorState: It has a direction (up, down, stand, maintenance), 
• a current floor
• a list of floor requests sorted in the direction. 
• It receives request from elevator Controller
• Passenger it has boarded, also we need to have addPassenger function, and load it can take

ElevatorState enum: 

Each elevator has a set of states. 

• Maintenance: the elevator does not react to external signals (only to its own signals).
• Stand: the elevator is fixed on a floor. If it receives a call. And the elevator is on that floor, the doors open. If it is on another floor, it moves in that direction.
• Up: the elevator moves up. Each time it reaches a floor, it checks if it needs to stop. If so it stops and opens the doors. It waits for a certain amount of time and closes the door (unless someting is moving through them. Then it removes the floor from the request list and checks if there is another request. If so the elevator starts moving again. If not it enters the state stand.
• Down: like up but in reverse direction.

There are additional signals:

• alarm. The elevator stops. And if it is on a floor, the doors open, the request list is cleared, the requests moved back to the bank.
• door open. Opens the doors if an elevator is on a floor and not moving.
• door closes. Closed the door if they are open.

ElevatorRequests:

Each button press results in an elevator request which has to be served. Each of these requests is tracked at a global place. ElevatorRequests, the class which stores elevator requests can use different strategies to schedule the elevator requests. 

ElevatorController:

The elevator is controlled by a controller class which we call ElevatorController. The elevator controller instructs the elevator what to do and also can shutdown/start up the elevator of the building.  serves it. 

ElevatorController runs the show by reading the next request to process and instructing the elevator what to do.  The elevator controller reads the next elevator request to be processed and and schedules to all active elevators (not in maintenance) using requestSchedulingAlgoritm() method.

The scheduling will be like:

• if available pick a standing elevator for this floor.
• else pick an elevator moving to this floor.
• else pick a standing elevator on an other floor.
• else pick the elevator with the lowest load.

How can we extend this to multiple elevators in a sky scraper
In the single elevator scenario, there is an elevator and an elevator controller and a common area where the floor requests and the elevator button request are stored and processed as per the scheduling algorithm.

To extend this to multiple elevators, each elevator will have a corresponding elevator controller. Floor based requests can be served by any elevator where as elevator button requests will be served by the elevator in which the button is pressed.

FloorButton's placeRequest adds a request to the common area which is accessible to all controller. ElevatorButton's placeRequest adds a request to the controller's internal queue as only one elevator is supposed to serve it.

Each elevator controller runs as a separate thread and checks on if it can process a floor request along with processing requests made by its own elevator button presses.

http://thought-works.blogspot.in/2012/11/object-oriented-design-for-elevator-in.html
http://k2code.blogspot.in/2014/04/design-elevator-system.html

• How would you optimize an elevator system for a building with 50 floors and 4 elevators ? Optimize in terms of lowest wait times for the users.

http://www.quora.com/What-are-ways-to-optimize-the-service-algorithm-for-an-elevator
http://dan-nolan.com/how-i-would-optimize-the-elevators-in-our-office-building/

More Reading/Discussion Points:
http://www.hiringlibrary.com/object-oriented-design-interview-for-parking-lot-or-elevator/
http://codereview.stackexchange.com/questions/5723/oop-elevator-design-evaluation
http://massivetechinterview.blogspot.in/2015/07/thought-works-object-oriented-design.html

Design Patterns

Design Patterns:

http://www.geeksforgeeks.org/category/design/

0. http://www.coderanch.com/t/659856/Wiki/Singleton-Pattern
1. https://xmruibi.gitbooks.io/interview-preparation-notes/content/OOD/TypicalPattern/index.html
2. http://javarevisited.blogspot.com/2012/06/20-design-pattern-and-software-design.html
3.  https://sourcemaking.com/design-patterns-and-tips

Factory, Singleton, Prototype and Builder Patterns:

http://coding-geek.com/category/design-pattern/

[Cracking the Coding Interview]

Because interviewers are trying to test your capabilities and not your knowledge, design patterns are mostly beyond the scope of an interview. However, the Singleton and Factory Method design patterns are widely used in interviews, so we will cover them here. There are far more design patterns than this book could possibly discuss. A great way to improve your software engineering skills is to pick up a book that focuses on this area specifically. Be careful you don't fall into a trap of constantly trying to find the "right" design pattern for a particular problem. You should create the design that works for that problem. In some cases it might be an established pattern, but in many other cases it is not. 

Singleton Class The Singleton pattern ensures that a class has only one instance and ensures access to the instance through the application. It can be useful in cases where you have a "global" object with exactly one instance. For example, we may want to implement Restaurant such that it has exactly one instance of Restaurant. 

1 public class Restaurant { 

2 private static Restaurant _instance = null; 

3 protected Restaurant() { ... } 

4 public static Restaurant getlnstance() { 

5 if (_instance == null) { 

6 _instance = new Restaurant(); 

7 } 

8 return _instance; 

9 } 

10 }

 It should be noted that many people dislike the Singleton design pattern, even calling it an "anti-pattern:' One reason for this is that it can interfere with unit testing. 

Factory Method The Factory Method offers an interface for creating an instance of a class, with its subclasses deciding which class to instantiate. You might want to implement this with the creator class being abstract and not providing an implementation for the Factory method. Or, you could have the Creator class be a concrete class that provides an implementation for the Factory method. In this case, the Factory method would take a parameter representing which class to instantiate. 

1 public class CardGame { 

2 public static CardGame createCardGame(GameType type) { 

3 if (type == GameType.Poker) { 

4 return new PokerGame(); 

5 } else if (type == GameType.BlackJack) { 

6 return new BlackJackGame(); 

7 } 

8 return null; 

9 } 

10 }