Facebook Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
So we need to know the total amount of people before we add a new person to any room If we start empty party rooms this is 0 and when we add new person we produce an index for each of the rooms based on the amount of people they can take compared to the total people in the party. So if we add 1 person this means following:
A - 1*0.2 - 0 = 0,2
B - 1*0.3 - 0 = 0,3
C - 1*0.5 - 0 = 0.5
So biggest percent means this is the empties room. Next iteration we have 1 person and we add another one:
A - 2*0,2 - 0 = 0.4
B - 2*0.3 - 0 = 0.6
C - 2*0.5 - 1 = 0
And the formula is
((total+1) * percentage / 100) - people
import java.util.ArrayList;
public class RoomsTask {
public static void main(String[] args) {
ArrayList<Room> roomsList = new ArrayList<Room>();
roomsList.add(new Room(20));
roomsList.add(new Room(30));
roomsList.add(new Room(50));
Party myParty = new Party(roomsList);
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.addPerson();
myParty.printRooms();
}
}
class Party {
ArrayList<Room> rooms;
int totalPeople;
public Party(ArrayList<Room> aRooms) {
totalPeople = 0;
rooms = aRooms;
}
public void addPerson() {
int roomIndex = 0;
for (int i = 1; i < rooms.size(); i++) {
int tmpTotal = totalPeople + 1;
float roomA = rooms.get(i-1).calculatePercentForTotalForExtraPerson(tmpTotal);
float roomB = rooms.get(i).calculatePercentForTotalForExtraPerson(tmpTotal);
if (roomA < roomB) {
roomIndex = i;
}
}
totalPeople++;
rooms.get(roomIndex).addPerson();
}
public void printRooms() {
for (Room room : rooms) {
System.out.println("Room with people: " + room.getPeople() + " and % " + room.getPercentage());
}
}
}
class Room {
private int percentage;
private int people;
public Room(int aPercentage) {
percentage = aPercentage;
people = 0;
}
public Room(int aPercentage, int aPeople) {
percentage = aPercentage;
people = aPeople;
}
public void addPerson() {
people++;
}
public int getPeople() {
return people;
}
public int getPercentage() {
return percentage;
}
public float calculatePercentForTotalForExtraPerson(int total) {
return (total*percentage/100.0f) - people;
}
}
Minimum amount of people without 'splitting' a person to maintain % is 10. (5 people, 3 people and 2 people in room). Once all rooms are full, we increase room capacity by equivalent % (i.e. 5 people. 3 people and 2 people). Now for new incoming people, we need to be uniformly distributing people. For that to happen, next person that we choose should have 50% probability to goto first room, 30% to the next and 20% to the last.
class Room {
public float percentage;
public String roomID;
public int currNumPpl=0;
}
public static String addPeople(ArrayList<Room> party) {
int totalPpl = 0;
int minPpl = 0;
int minPpl_temp=0;
int minPpl_room_count = 0;
for(Room room: party) {
totalPpl += room.currNumPpl;
int m = (int)room.percentage*100;
if(m%10==0 || m<9) {
if(m%10 ==0) minPpl_temp += m/10;
else minPpl_temp += m;
minPpl_room_count ++;
}
else
minPpl += m;
}
//find out what is the minimum people needed in order
// to use percentage effectively
if(minPpl_room_count == party.size())
minPpl = minPpl_temp;
for(Room room: party) {
if(totalPpl < minPpl) {
if(((room.currNumPpl + 1)/minPpl) <= room.percentage) {
room.currNumPpl ++;
return room.roomID;
}
}else {
if(((room.currNumPpl + 1)/(totalPpl+1)) <= room.percentage) {
room.currNumPpl ++;
return room.roomID;
}
}
}
return null;
}
We can not maintain the exact percentage at any given point, if we are adding the person 1 by 1 continuously in to the room.
We can make the queue of certain size after filling the queue we will move in the persons in the respective rooms based upon the percentage.. by this method we will maintain the exact percentage at any give point.
find the size of the queue = LCM of [% of a, % of b, % of c]
once the size is full, distribute person based upon a = (% of a)/LCM
b = (% of b )/ LCM
c = (% of c ) /LCM
Given a list of ideal percentages (rooms) that can be expanded or reduced
Ideal = [20%, 30%, 50%]
Create a list of actual percentages
Room% = [(RoomCount1 / Total), (RoomCount2 / Total), ...]
Then compare ideal percentage to actual percentage and find the room with lowest difference.
Current% = 0
For each Room%
If (Room% < Current%) Then
NextRoom = room.name
End If
Next
Print "Go to " & NextRoom
We can calculate it using the formula
(0.5) A + (0.3)B + (0.2)C
For iteration 1: Let people = 6;
(0.5) 6 + (0.3) 6 + (0.2) 6 = 3.0 + 2.0 + 1.0 = 6
For iteration 2: Let people = 7;
(0.5) 7 + (0.3) 7 + (0.2) 7 = 3.5 + 2.1 + 1.4 = 4(approx) + 2 + 1 = 7
For iteration 3: Let people = 8;
(0.5) 8 + (0.3) 8 + (0.2) 8 = 4.0 + 2.4 + 1.6 = 4 + 2 + 2(approx) = 8
For iteration 4: Let people = 9;
(0.5) 9 + (0.3) 9 + (0.2) 9 = 4.5 + 2.7 + 1.8 = 5(approx) + 2 + 2 = 9 (Giving priority to max value to have minimum difference in percentage).
And so on.
A load balancing situation. Generate a random number in uniform distribution and based on the range the number falls assign the guest to correponding room.
0 - 20 = Room A
21 - 50 = Room B
51 - 100 = Room C
Would not maintain the percentage exactly but can maintain the percentage closely. It applies even if more rooms are added.
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
float rooms[] = {0.2, 0.3, 0.5};
int full[] = {0, 0, 0};
int total = 0;
// Add 100 test people
for (int i=0; i<100; ++i) {
total++;
for (int j=0; j<3; ++j) {
if (full[j]/(float)total < rooms[j]) {
full[j]++;
break;
}
}
}
for (float i : full) {
cout << i << " ";
}
}
Java implementation of Skor's algorithm. Everything's static for the sake of simplicity. Result: CBACBCACBC
public class PartyRooms {
private static List<Room> rooms = new ArrayList<>();
private static int total = 0;
public static void main(String[] args) {
rooms.add(new Room("A", 20));
rooms.add(new Room("B", 30));
rooms.add(new Room("C", 50));
for (int i = 0; i < 10; i++) {
addPerson();
}
}
public static void addPerson() {
Collections.sort(rooms, Comparator.comparingInt(Room::availability).thenComparingInt(Room::limit).reversed());
Room r = rooms.get(0);
r.addPerson();
System.out.print(r.name);
}
static class Room {
private String name;
private int limit;
private int count;
public Room(String name, int limit) {
this.name = name;
this.limit = limit;
}
public void addPerson() {
count++;
total++;
}
public int limit() {
return limit;
}
// The larger the value, the more free space there is
public int availability() {
return limit - (total == 0 ? 0 : count * 100 / total);
}
}
}
It is a ratios and least common multiple:
Formula:
Min(15* count(A), 10*count(B), 6*count(C)).
The statistical approach of using random will also work..over the long run, but it would probably not work for small numbers. Also, I would draw a number between 1 and 1 Million instead of 1-100. It would be more stable.
You can do this with a min heap (priority queue).
The queue will have a record for each room and the priority will be decided on the room that will have the least difference with its ideal percentage when 1 more person is added to that room. We do one person because the question says the guests are coming one by one.
Every time to add a person to a room, you will min heapify that node in the heap so that you have the next best room at the front of the queue.
The time complexity of added a person to a room is O(1). and time to min heapify the queue of rooms is O(log n). So you can add people to the rooms in O(log n) time, where n is the number of rooms.
This is a general data structure and algorithm that will work for any number of rooms.
I would use Max heap to store the rooms.
Each room will have following variables,
- max: max capacity
- capacity: max number of guests that the room can hold given the percent value
- limit : limit percentage that each room should maintain.
- left : number of available spots left in the room
- gap: ratio of left/capacity
left is calculated by the following formula:
left =capacity - count;
gap is calculated by the following formula
gap = left/capacity
The heap will store each room in descending order of gap value.
ExtractMax() will return the room with highest gap value.
This algorithm can handle the allocation of new quest in O(logN), where N is the number of rooms.
Initial construction of heap can by achieved in O(N) using heapifiy().
If a new room is added, addition of new room will also take O(1).
The following is c++ version of solution
#include <iostream>
#include <math.h>
using namespace std;
struct room {
int left;
double gap;
int max;
int capacity;
float limit;
room(int c, float l):left(0), max(c), limit(l)
{
capacity = max*limit;
left = capacity;
gap = (double)left/capacity;
}
void add_guest(int n)
{
left -= n;
gap = (double)left/capacity;
}
};
class Heap {
public:
Heap (bool max = true):bMax(max){}
room * extract()
{
if (last < 0)
return 0;
room* found = list[0];
list[0] = list[last];
list[last--] = 0;
heapify(0);
return found;
}
void buildHeap(room** input, int length)
{
list = new room*[length];
int i =0;
for (i = 0; i <length; i++)
list[i] = input[i];
last = length -1;
len = length;
int half = floor((double)last/2);
for (i = half; i >= 0; i--)
heapify(i);
}
bool add(room * r)
{
if (last < len -1)
{
list[++last] = r;
bubbleUp(last);
} else
return false;
return true;
}
private:
bool isChild(int parent, int child)
{
return (bMax)? list[parent]->gap > list[child]->gap : list[parent]->gap < list[child]->gap;
}
void bubbleUp(int start)
{
if(start == 0)
return;
int p = parent(start);
if (p >= 0)
{
if (!isChild(p, start))
{
swap(p, start);
bubbleUp(p);
}
}
}
void swap(int src, int dst)
{
room * tmp = list[src];
list[src] = list[dst];
list[dst] = tmp;
}
void heapify(int s)
{
int p = s;
int l = left(s);
int r = right(s);
if (l <= last && !isChild(p, l))
{
p = l;
}
if (r <= last && !isChild(p, r))
{
p = r;
}
if (p != s)
{
swap(p, s);
heapify(p);
}
}
int parent (int s) { return floor((double)s/2); }
int left (int s) { return 2*s ;}
int right (int s) { return 2*s+1;}
bool bMax;
room** list;
int len;
int last;
};
void manage_rooms(room** rooms, int length, int guest_count)
{
Heap heap;
heap.buildHeap(rooms, length);
for (int i = 0; i < guest_count; i ++)
{
room* r = 0;
while ((r = heap.extract()))
{
if (r->left == 0)
continue;
else
{
r->add_guest(1);
heap.add(r);
}
}
}
}
int main ()
{
room *a = new room(10, 0.2);
room *b = new room(20, 0.4);
room *c = new room(40, 0.5);
double i = (double)5/7;
cout<< i <<endl;
room* inputs[3] = { new room(10, 0.2), new room(20, 0.4), new room(40, 0.5)};
manage_rooms(inputs, 3, 100);
for (int i = 0; i < 3; i++)
{
int count = inputs[i]->capacity - inputs[i]->left;
cout <<" room: count = " << count << "limit = "<<inputs[i]->limit << " percent = " << (double)(count*1.0/inputs[i]->max) <<endl;
}
}
Assume that we start out with 2 people in A, 3 people in B, and 5 people in C. We are currently maintaining the ideal percentage. Now, if we decide to add a person to a room, there is no way we can maintain this ideal percentage because we will have 11 people, so we can't get the exact percentages since you can't put a fraction of a person into a room. The best place to add a person would be in the room with the highest percentage since this would lead to the smallest difference of ideal percentages over all of the rooms.
- Skor March 14, 2015So we know that in the case that we have an ideal percentage, we should add a person to the room with the highest ideal percentage (in this case, room C).
Now, we can see that the percentages of the rooms will be lower for A and B, but higher for C. Since we can't take people out of rooms, we can only add people. Adding to C would be unwise, since it is already over the ideal percentage, so we will look at A and B. whichever has a greater difference that is lower that the average, we will add a person to the room.
We continue this heuristic to get the best case percentages at any given time...
With this heuristic, we add in this order to each room:
CBACBCACBC
If you go through it, you will see how stable the percentages are throughout