Cisco Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
W=Initial no of plates
e= time to eat by single person
Devide the time interval into n parts
Create two arrays with the size n.
P[n]:Used to store current no of plates empty. Intially P[0]=W(i.e all plates are empty)
R[n]:Recycled plates . R[0]=0
Xi:no of guests come at ith interval
Z:Maximum no of allowed waiting list
(At time of waiting p will be negative number)
Repeat loop from i to n
1)if Ri>0 -> Notify host
2) Pi=Pi-Xi+Ri
if(Pi<0)
R(i+e)=Xi+Pi(with sign ..means Pi is negative)
if (-Pi)>Z.->Notify Host
for this we can have a flag for each person when there is an empty plate for person we can just flip the flag so when ever the flag is fliped(0 to 1 or 1 to 0) accordingly the super_counter(Stroing sum of flags is updated) so when the counter increases the maximum limit the alarm will be on. and when the flag flip from 1 to 0 alarm will be on..and super_counter will be decreased ..s like this at each increment of counter we have to check for maximum limit and super_counter
On notification of plate
if(flag_i is flipped){
if(flag_i==0){
w--;
alarm on;
}
else{
w++
if(w>limit)
alarm on;
}
}
/*
One way to implement this is using asynchronous thread communications.
Poller (thread) keeps polling Guests on regular interval to see if they have any empty plate.
On each run, it lists the Guests which have empty plate. and notifies the Host using appropriate Event object.
I havent tried below code.. just wrote it on Notepad and pasting it here. Just a sample code..
more complex code can be created using Locking APIs..
*/
public class Guest {
boolean isPlateFull = true;
int id;
Guest() {
//or pass Poller instance to each Guest so guests can register them selfs
Poller.register(this);
}
public void eat() {
isPlateFull = false;
}
public void serve() {
isPlateFull = true;
}
public boolean checkPlate() {
return isPlateFull;
}
@PreDestroy
public void myFinalize() {
Poller.unregister(this);
}
//equals and hashCode
//evil getters and setters
}
class Poller implements Runnable {
private Thread t;
private static List<Guest> guestsToPoll = new ArrayList<>();
public static final int pollIntervalSeconds = 5;
public static volatile boolean keepRunning = true;
public Host host;
public static final int maxGuestWaiting = 5;
public static final Poller instance;
private Poller(){}
//making an assumption only 1 poller thread needs to be creted.
//you may need to crete multiple Pollers for each Host.
//or single Poller can handle multiple hosts using a map of Host and Guests
public static final Poller getInstance(Host host){
if(instance == null) {
synchronized(Poller.class) {
if(instance == null) {
instance = new Poller();
instance.host = host;
instance.t = new Thread(this);
instance.t.start();
}
}
}
return instance;
}
@Override
public void run() {
while(keepRunning) {
synchronized(guestsToPoll) {
List<Guest> guestsWaiting = new ArrayList<>();
for(Guest guest : guestsToPoll) {
if(!guest.checkPlate()) { //plate is not full
guestsWaiting.add(guest);
host.notify(new GuestWaitingEvent(guest));
}
}
if(hosts.size()>=maxGuestWaiting) {
host.notify(new MaxHostWaitingEvent(hosts.size()/*, hosts*/));
}
guestsToPoll.wait(pollIntervalSeconds * 1000); //release the lock for a while and wait.
}
}
}
public static void register(Guest g) {
guestsToPoll.add(g);
}
public static void unregister(Guest g) {
guestsToPoll.remove(g); //uses equals
}
public static void stopPoller() {
keepRunning = false;
}
}
public enum EventType{
MAX_GUEST_WAITING,
GUEST_WAITING;
}
public abstract class Event {
EventType type;
Event(EventType type) {
this.type = type;
}
}
public class GuestWaitingEvent extends Event {
private Guest guest;
public HostWaitingEvent(Guest guest) {
super(EventType.GUEST_WAITING);
this.guest = guest;
}
//accessor methods
}
public class MaxGuestWaitingEvent extends Event {
private int num;
//private List<Guest> guestsWaiting; //you can notify who is waiting as well
public MaxGuestWaiting(int n/*, List<Guest> guests*/) {
super(EventType.MAX_GUEST_WAITING);
num = n;
//guestsWaiting = guests;
}
//accessor methods
}
//for truly asynchronous behavior
public class Host implements Runnable {
int servingsRemaining = 5;
Set<Guest> guestsToServe = new HashSet<>();
private Thread t;
private static final instance;
private static final int sleepTime = 200; //millis
private volatile boolean keepRunning = true;
private Host(){}
public static final Host getInstance() {
if(instance == null) {
synchronized(Host.class) {
if(instance == null) {
instance = new Host();
instance.t = new Thread(instance);
instance.t.start();
}
}
}
}
public void stop() {
keepRunning = false;
}
@Override
public void run() {
while(keepRunning) {
synchronized(guestsToServe) {
if(guestsToServe.size()==0) {
try {
guestsToServe.wait(sleepTime); //release the locks for a while
} catch (IllegalMonitorStateException | InterruptedException e) {
e.printStackTrace(System.out);
throw e;
}
} else {
for(Guest guest : guestsToServe) {
while(servingsRemaining==0) {
cook(); //imagine this is asynchronous as well!
guestsToServe.wait(sleepTime*5);
}
serve(guest);
}
}
}
}
}
public void cook() {
//get items from pantry and cook!!
servingsRemaining = 5;
}
public void serve(Guest guest) {
guest.serve();
servingsRemaining--;
}
public void notify(Event event) {
if(GuestWaitingEvent.class.equals(event.getClass())) {
synchronized(guestsToServe) {
guestsToServe.add(((GuestWaitingEvent)event).getGuest());
}
} else (MaxGuestWaitingEvent.class.equals(event.getClass())) {
//do some other thing..
}
}
}
I think we can have an observer pattern here with a slight difference. Whenver there is an update from the client (like EmptyPlate) it notifies the host about it. The host which has a counter for the number of client objects, reduces the count
- DashDash February 26, 2013