Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
If I understand the question correctly, it's not about the algorithms, but more about OOP, right?
If so, here's some sample solution in Python:
class Mall:
def __init__(self, entries=1, exits=1, max_capacity=100, name='New Mall'):
self.__max_capacity = max_capacity
self.__entries = entries
self.__exits = exits
self.__name = name
self.__visitors_inside = 0
print('Created new mall: \n name = %s \n entry gates = %d \n exit gates = %d \n maximum capability = %d \n'
% (self.__name, self.__entries, self.__exits, self.__max_capacity))
def set_entries(self, entries):
self.__entries = entries
def get_entries(self):
return self.__entries
def set_exits(self, exits):
self.__exits = exits
def get_exits(self):
return self.__exits
def set_capacity(self, max_capacity):
self.__max_capacity = max_capacity
def get_capacity(self):
return self.__max_capacity
def add_people_inside(self, visitors):
if self.__visitors_inside == self.__max_capacity:
print('Reached the maximum of %d people inside the %s!' % self.__max_capacity, self.__name)
elif self.__visitors_inside + visitors > self.__max_capacity:
print('Maximum capacity almost reached! Can\'t let %d visitors get inside the %s, only %d slots available.'
% (visitors, self.__name, self.__max_capacity - self.__visitors_inside))
else:
self.__visitors_inside += visitors
print('%d visitors entered %s. Total amount of visitors inside: %d.'
% (visitors, self.__name, self.__visitors_inside))
if __name__ == '__main__':
dubai_mall = Mall(entries=5, exits=5, max_capacity=100000, name='Dubai Mall')
dubai_mall.add_people_inside(100)
dubai_mall.add_people_inside(100000)
I guess this is more about algorithm design and probably less about OO design. But you never know.
The algorithm I get to my mind when you have to maintain only certain people(items), is a queue. Maintain a queue structure, and if the size of the queue is exceeded, bring in your eviction policy.
The problem is queue has one entry and one exit, here there are M entries and n exits. So, you could have a master that monitors the entries and exits and report to a central data-structure to update the current items in it(the mall).
so essentially this boils down to producer-consumer problem. Producer is the one of the entries (producing an item ~~ person entering the mall) and Consumer is the one of the exits (consuming an item ~~ person leaving the datastructure)...
This is probably a System Design Question. There are multiple nodes (m-Entry and n-Exit Nodes) that need to share a common queue which has size X.
If we consider this as a Distributed System, then
- X/m tokens are assigned to each of the m-Entry nodes at the beginning
- Each of the m-Entry nodes have a local queue (say of size k)
- Each of the m-Entry node sends message to n-Exit nodes when local queue changes
- Each of the n-Exit Nodes send a message to all the m-Entry Nodes when ever a person leaves the mall
- Token Distribution is required when any person leaves from one of the n-Exit nodes
- The token distribution can be done by n-Exit nodes using:
- Size of the local queue of m-Entry Nodes
- Number of available tokens on the m-Entry Nodes
- In case of a contention, the node with lower id can get the token
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.Semaphore;
class Mall {
private Integer totalCapacity = 100;
private Semaphore semaphore = new Semaphore(totalCapacity);
private Queue<Integer> mallQueue = new LinkedList<Integer>();
public void entry(int entryCount) throws InterruptedException {
while(true){
semaphore.tryAcquire(entryCount);
while (mallQueue.size() == totalCapacity)
wait();
for (int i = 0; i < entryCount; i++) {
mallQueue.offer(i);
}
totalCapacity = totalCapacity+entryCount;
notifyAll();
semaphore.release(entryCount);
}
}
public void exitfrom(int exitCount) throws InterruptedException {
while (true){
semaphore.tryAcquire(exitCount);
while (mallQueue.size() == 0)
wait();
for (int i = 0; i <exitCount ; i++) {
mallQueue.poll();
}
totalCapacity = totalCapacity - exitCount;
notifyAll();
semaphore.release(exitCount);
}
}
}
class MallEntry extends Thread {
private Mall mallService;
private Integer entryCount;
public MallEntry(Mall service, int count ){
super("Entry gate");
this.mallService = service;
this.entryCount = count;
}
@Override
public void run() {
super.run();
try {
mallService.entry(this.entryCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
class MallExit extends Thread{
private Mall mallService;
private Integer exitCount;
public MallExit(Mall service, int exitCount){
super("Exit gate");
this.exitCount = exitCount;
this.mallService = service;
}
@Override
public void run() {
super.run();
try {
mallService.exitfrom(this.exitCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public class MallEntryusingSemaphore {
public static void main(String[] args) {
Mall mallServie = new Mall();
MallEntry mallEntry = new MallEntry(mallServie, 5);
MallExit mallExit = new MallExit(mallServie, 5);
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.Semaphore;
class Mall {
private Integer totalCapacity = 100;
private Semaphore semaphore = new Semaphore(totalCapacity);
private Queue<Integer> mallQueue = new LinkedList<Integer>();
public void entry(int entryCount) throws InterruptedException {
while(true){
semaphore.tryAcquire(entryCount);
while (mallQueue.size() == totalCapacity)
wait();
for (int i = 0; i < entryCount; i++) {
mallQueue.offer(i);
}
totalCapacity = totalCapacity+entryCount;
notifyAll();
semaphore.release(entryCount);
}
}
public void exitfrom(int exitCount) throws InterruptedException {
while (true){
semaphore.tryAcquire(exitCount);
while (mallQueue.size() == 0)
wait();
for (int i = 0; i <exitCount ; i++) {
mallQueue.poll();
}
totalCapacity = totalCapacity - exitCount;
notifyAll();
semaphore.release(exitCount);
}
}
}
class MallEntry extends Thread {
private Mall mallService;
private Integer entryCount;
public MallEntry(Mall service, int count ){
super("Entry gate");
this.mallService = service;
this.entryCount = count;
}
@Override
public void run() {
super.run();
try {
mallService.entry(this.entryCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
class MallExit extends Thread{
private Mall mallService;
private Integer exitCount;
public MallExit(Mall service, int exitCount){
super("Exit gate");
this.exitCount = exitCount;
this.mallService = service;
}
@Override
public void run() {
super.run();
try {
mallService.exitfrom(this.exitCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public class MallEntryusingSemaphore {
public static void main(String[] args) {
Mall mallServie = new Mall();
MallEntry mallEntry = new MallEntry(mallServie, 5);
MallExit mallExit = new MallExit(mallServie, 5);
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.Semaphore;
class Mall {
private Integer totalCapacity = 100;
private Semaphore semaphore = new Semaphore(totalCapacity);
private Queue<Integer> mallQueue = new LinkedList<Integer>();
public void entry(int entryCount) throws InterruptedException {
while(true){
semaphore.tryAcquire(entryCount);
while (mallQueue.size() == totalCapacity)
wait();
for (int i = 0; i < entryCount; i++) {
mallQueue.offer(i);
}
totalCapacity = totalCapacity+entryCount;
notifyAll();
semaphore.release(entryCount);
}
}
public void exitfrom(int exitCount) throws InterruptedException {
while (true){
semaphore.tryAcquire(exitCount);
while (mallQueue.size() == 0)
wait();
for (int i = 0; i <exitCount ; i++) {
mallQueue.poll();
}
totalCapacity = totalCapacity - exitCount;
notifyAll();
semaphore.release(exitCount);
}
}
}
class MallEntry extends Thread {
private Mall mallService;
private Integer entryCount;
public MallEntry(Mall service, int count ){
super("Entry gate");
this.mallService = service;
this.entryCount = count;
}
@Override
public void run() {
super.run();
try {
mallService.entry(this.entryCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
class MallExit extends Thread{
private Mall mallService;
private Integer exitCount;
public MallExit(Mall service, int exitCount){
super("Exit gate");
this.exitCount = exitCount;
this.mallService = service;
}
@Override
public void run() {
super.run();
try {
mallService.exitfrom(this.exitCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public class MallEntryusingSemaphore {
public static void main(String[] args) {
Mall mallServie = new Mall();
MallEntry mallEntry = new MallEntry(mallServie, 5);
MallExit mallExit = new MallExit(mallServie, 5);
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.Semaphore;
class Mall {
private Integer totalCapacity = 100;
private Semaphore semaphore = new Semaphore(totalCapacity);
private Queue<Integer> mallQueue = new LinkedList<Integer>();
public void entry(int entryCount) throws InterruptedException {
while(true){
semaphore.tryAcquire(entryCount);
while (mallQueue.size() == totalCapacity)
wait();
for (int i = 0; i < entryCount; i++) {
mallQueue.offer(i);
}
totalCapacity = totalCapacity+entryCount;
notifyAll();
semaphore.release(entryCount);
}
}
public void exitfrom(int exitCount) throws InterruptedException {
while (true){
semaphore.tryAcquire(exitCount);
while (mallQueue.size() == 0)
wait();
for (int i = 0; i <exitCount ; i++) {
mallQueue.poll();
}
totalCapacity = totalCapacity - exitCount;
notifyAll();
semaphore.release(exitCount);
}
}
}
class MallEntry extends Thread {
private Mall mallService;
private Integer entryCount;
public MallEntry(Mall service, int count ){
super("Entry gate");
this.mallService = service;
this.entryCount = count;
}
@Override
public void run() {
super.run();
try {
mallService.entry(this.entryCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
class MallExit extends Thread{
private Mall mallService;
private Integer exitCount;
public MallExit(Mall service, int exitCount){
super("Exit gate");
this.exitCount = exitCount;
this.mallService = service;
}
@Override
public void run() {
super.run();
try {
mallService.exitfrom(this.exitCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public class MallEntryusingSemaphore {
public static void main(String[] args) {
Mall mallServie = new Mall();
MallEntry mallEntry = new MallEntry(mallServie, 5);
MallExit mallExit = new MallExit(mallServie, 5);
}
}
java:
- Anonymous August 06, 2017class Mall containing below fields/methods:
- 1 semaphor for entry gates (initialized to m)
- 1 semaphor for exit gates (initialized to n)
- Collection <Person> with capacity = X.
- Synchronized methods for add, remove Person, utilizing entry,exit semaphores respectively