CareerCup

Objects
--------

Person {
int name;
int id
}

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

DoublyLinkedList {
	Person person;
	DoublyLinkedList prev;
	DoublyLinkedList next;
}

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]

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;
dictperson.Add(cp, cp1);
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;
dictcp.Add(cp, cp1);
return cp1;
}
public void init()
{
addPersonToCheckPoint(20, 1);
addPersonToCheckPoint(10, 1);
addPersonToCheckPoint(30, 1);
addPersonToCheckPoint(40, 1);
addPersonToCheckPoint(10, 2);
addPersonToCheckPoint(30, 2);

addPersonToCheckPoint(50, 1);
addPersonToCheckPoint(10, 3);
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;
c1.q.Add(p1);
}
}

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;
dictperson.Add(cp, cp1);
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;
dictcp.Add(cp, cp1);
return cp1;
}
public void init()
{
addPersonToCheckPoint(20, 1);
addPersonToCheckPoint(10, 1);
addPersonToCheckPoint(30, 1);
addPersonToCheckPoint(40, 1);
addPersonToCheckPoint(10, 2);
addPersonToCheckPoint(30, 2);

addPersonToCheckPoint(50, 1);
addPersonToCheckPoint(10, 3);
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;
c1.q.Add(p1);
}
}

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)
results.add(nameLookup[i]);

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

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

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