## Bloomberg LP Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

``````Objects
--------

Person {
int name;
int id
}

CheckPoint {
Map<String, DoublyLinkedList> personToDLL; // person id to node
public CheckPoint() {
personToDLL = new HashMap<>();
}
}

Person person;
}

Variables
-----------

Map<String, CheckPoint> map; // checkPoint name to Object map
String HighestCheckPointReported; // to store the highest checkPoint that is reported;``````

Logic :

Everytime a person crosses the checkPoint(CP2)
1. Go to previous check point(CP1) if exists, get the node and delete from the list and map;
update the first and last node in checkPoint accordingly;
add the node to the current checkPoint based on the last node;
add to the map as well;

else
if previous check point doesnt exists, create the person the insert into the list; add this to the map; in current checkPoint

finally
Everytime update the HighestCheckPointReported if it is higher

To get the rank

Iterate from the HighestCheckPointReported to the lowestCheckPoint[first node in each CheckPoint object would help to find the order]

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

public class person
{
public int id;
public string name;
public int checkpointid;
}
public class checkpoint
{
public int id; //checkpoint id
public List<person> q = new List<person>();

public void removeIfExist(person pe)
{
if (pe.checkpointid == 0) return;
if (q.Find(x => x.id == pe.id) != null)
{
q.RemoveAll(x => x.id == pe.id);
}
}
};
class RaceAndCheckPoint
{
Dictionary<int, checkpoint> dictcp = new Dictionary<int, checkpoint>();
Dictionary<int, person> dictperson = new Dictionary<int, person>();
public person getperson(int cp)
{
if (cp == 0) return null;
if (dictperson.ContainsKey(cp))
{
return dictperson[cp];
}
person cp1 = new person();
cp1.id = cp;
return cp1;
}
public checkpoint getCheckpoint(int cp)
{
if (cp == 0) return null;
if (dictcp.ContainsKey(cp))
{
return dictcp[cp];
}
checkpoint cp1 = new checkpoint();
cp1.id = cp;
return cp1;
}
public void init()
{

foreach (var item in dictcp.Reverse())
{
foreach (var i in item.Value.q)
{
Console.WriteLine("P" + i.id);
}
}
}
public void addPersonToCheckPoint(int person, int checkpoint)
{
person p1 = getperson(person);
checkpoint c1 = getCheckpoint(checkpoint);
checkpoint oldcheckpoint = getCheckpoint(p1.checkpointid);
if (oldcheckpoint != null)oldcheckpoint.removeIfExist(p1);
p1.checkpointid = c1.id;
}
}

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

public class person
{
public int id;
public string name;
public int checkpointid;
}
public class checkpoint
{
public int id; //checkpoint id
public List<person> q = new List<person>();

public void removeIfExist(person pe)
{
if (pe.checkpointid == 0) return;
if (q.Find(x => x.id == pe.id) != null)
{
q.RemoveAll(x => x.id == pe.id);
}
}
};
class RaceAndCheckPoint
{
Dictionary<int, checkpoint> dictcp = new Dictionary<int, checkpoint>();
Dictionary<int, person> dictperson = new Dictionary<int, person>();
public person getperson(int cp)
{
if (cp == 0) return null;
if (dictperson.ContainsKey(cp))
{
return dictperson[cp];
}
person cp1 = new person();
cp1.id = cp;
return cp1;
}
public checkpoint getCheckpoint(int cp)
{
if (cp == 0) return null;
if (dictcp.ContainsKey(cp))
{
return dictcp[cp];
}
checkpoint cp1 = new checkpoint();
cp1.id = cp;
return cp1;
}
public void init()
{

foreach (var item in dictcp.Reverse())
{
foreach (var i in item.Value.q)
{
Console.WriteLine("P" + i.id);
}
}
}
public void addPersonToCheckPoint(int person, int checkpoint)
{
person p1 = getperson(person);
checkpoint c1 = getCheckpoint(checkpoint);
checkpoint oldcheckpoint = getCheckpoint(p1.checkpointid);
if (oldcheckpoint != null)oldcheckpoint.removeIfExist(p1);
p1.checkpointid = c1.id;
}
}

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

class race
{
private String[] nameLookup; // Maps racer number to name starting from 0
private HashMap<String, Integer> racerMap = new HashMap<>(); // Maps name to racer number (starting from 0)
private int[] currentOrder; // Could use linked list instead to save insertion time but only if implemented properly by container
private int[] lastCheckIn; // Racer number that last passed this checkpoint (or -1 if none)

race(int numCheckPoints, ArrayList<String> racerNames)
{
nameLookup = racerNames.toArray(); // Map racer numbers to names

// Now map racer names to numbers for use in update() function
for (int racerIndex = 0; racerIndex < racersNames.size(); racerIndex++)
racerMap.put(nameLookup[racerIndex], racerIndex);

// Initialize checkpoint and racer data to -1 to denote no info yet
lastCheckIn = new int[numCheckPoints];
for (int i = 0; i < numCheckPoints; i++)
lastCheckIn[i] = -1;

currentOrder = new int[numRacers];
for (int i = 0; i < numRacers; i++)
currentOrder[i] = -1;
}

public void update(String name, int checkpoint)
{
int racerNumber = racerMap.get(name); // Should check for name validity but assume OK here

// Move racer behind previous person to pass checkpoint if there was one
if (lastCheckIn[checkPoint] >= 0)
moveRacer(racerNumber, getPosition(lastCheckIn[checkPoint] + 1);
else // Otherwise this racer is in the lead so move to position 0
moveRacer(racerNumber, 0);

// Set checkpoint to this racer's number
lastCheckIn[checkPoint] = racerNumber;
}

public ArrayList<String> getCurrentOrder()
{
ArrayList<String> results = new ArrayList<>();

for (int i = 0; i < currentOrder.length(); i++)
if (currentOrder[i] >= 0)

return results;
}

public int getPosition(racerNumber)
{
return currentPosition.indexOf(racerNumber);
}

private void moveRacer(int racerNumber, int newPosition)
{
int oldPosition = getPosition(racerNumber);

if (newPosition < oldPosition) // Racer has moved up in the list so move everyone behind him/her back by one unless unaffected
{
for (int i = newPosition + 1; i <= oldPosition; i++)
currentOrder[i] = currentOrder[i-1];
}
else if (oldPosition > newPosition) // Racer has fallen back so move everyone else forward
{
for (int i = newPosition - 1; i >= oldPosition; i--)
currentOrder[i] = currentOrder[i + 1];
}

// Put racer in his/her new position
currentOrder[newPosition] = racerNumber;
}
}
};

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

#define M 5
#define N 5

int arr[M*N];

int update(int p, int c){
if(c<1 || p<1) return 0;

int pos = ((M-c)*N);

while (arr[pos] != 0)
pos++;
arr[pos] = p;
}

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

i see a lot of answers used lists to insert and look up items in their algorithm. That is not in constant ordered as asked in the question. Using ordered sets we can achieve constant O for this problem. We keep track of:
* players current position for updating queues
* a set of players who crossed each checkpoint Q
and the result is just the list from each checkpoint in backward order. For example if we have 5 checkpoints the ordered result will be: Q5, Q4, ..., Q1.
Here is the Python 3 implementation. Since there is no OrderedSet in Python, OrderedDictionary is used instead.

``````from collections import OrderedDict

class racers_checkpoint:
def __init__(self, num_players, num_checkpoints):
self.n = num_players
self.m = num_checkpoints
self.player_current_position = {x: 0 for x in range(1, self.n + 1)}
self.check_point_queues = {x:OrderedDict() for x in range(1, self.m + 1)}
self.ordered_players = [self.check_point_queues[i].keys() for i in list(range(self.m, 0, -1))]

def update_and_retrieve(self, player, checkpoint):
try:
del self.check_point_queues[self.player_current_position[player]][player]  # remove player from old queue
except KeyError:
print("no player in the queue")
self.check_point_queues[checkpoint][player] = None  # add to the new queue
self.player_current_position[player] = checkpoint  # update current position
return self.ordered_players

if __name__ == '__main__':
my_race = racers_checkpoint(10, 5)
print(my_race.update_and_retrieve(5, 1))
print(my_race.update_and_retrieve(1, 1))
print(my_race.update_and_retrieve(2, 1))
print(my_race.update_and_retrieve(5, 2))
print(my_race.update_and_retrieve(3, 1))
print(my_race.update_and_retrieve(5, 3))
print(my_race.update_and_retrieve(4, 1))``````

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.