## Facebook Interview Question for Software Developers

• 0

Country: United States
Interview Type: Phone Interview

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

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.

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

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

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

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 static void main(String[] args) {
ArrayList<Room> roomsList = new ArrayList<Room>();

Party myParty = new Party(roomsList);

myParty.printRooms();
}
}

class Party {
ArrayList<Room> rooms;
int totalPeople;

public Party(ArrayList<Room> aRooms) {
totalPeople = 0;
rooms = aRooms;
}

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++;
}

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

people++;
}

public int getPeople() {
return people;
}

public int getPercentage() {
return percentage;
}

public float calculatePercentForTotalForExtraPerson(int total) {
return (total*percentage/100.0f) - people;
}
}``````

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

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.

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

``````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;
}``````

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

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

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

``````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``````

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

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.

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

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.

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

``````#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;

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 << " ";
}
}``````

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

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

for (int i = 0; i < 10; i++) {
}
}

Collections.sort(rooms, Comparator.comparingInt(Room::availability).thenComparingInt(Room::limit).reversed());

Room r = rooms.get(0);
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;
}

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

}``````

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

This is a problem of probability distribution.
Draw a number from 0 to 100 (or 0 to 1).

If the number between 0 -20
Send to room A
else if number between 20 - 50
Send to room B
else
Send to room C

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

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.

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

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.

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

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;
}
{
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;
list = 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);
}
{
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
{
}
}
}
}

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 = { 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;
}
}``````

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.

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