Microsoft Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

java:
class 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

- Anonymous August 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- dubai_data_science July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)...

- veeru August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Pankaj August 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BlockingQueue of Size x .
Create M thread for input and N thread to exit.
Rash Condition need to handle.

- nandkumar90 July 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}
}

- Anonymous May 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}
}

- Nishikant Sahu May 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

    }
}

- Nishikant Sahu May 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

    }
}

- Nishikant Sahu May 16, 2020 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More