Part 1
Given a json string as input which contains an array of objects, each with an id and x, y coordinates. Compute the closeness of a coordinate from another. A coordinate being close to another is defined by the close coordinate having both the x and y position being <= 10. Example: { id: 1, x: 0, y: 0}, {id: 2, x: 10, y:10 }, coord with id: 1 is close to coord with id: 2 and vice versa.

The expected output is a { id: [close id's] } -> example: { 1: [2], 2: [1] }

It took me me forever to even do the brute force. Something like 30 minutes and it made me feel like an idiot.

Brute force:

output = {}
inputString = json.loads(jsonInput)
for i in range(len(inputString)):
    for j in range(len(inputString)):
        if i == j:
            continue
        dx, dy = abs(inputString[i]["x"] - inputString[j]["x"]), abs(inputString[i]["y"] - inputString[j]["y"])
        if dx > 10 or dy > 10:
            continue
        if inputString[i]['id'] in output:
            output[inputString[i]['id']].append(inputString[j]['id'])
        else:
            output[inputString[i]['id']] = [inputString[j]['id']]

This is O(n^2) and we can do better.

Part 2
For part 2 they wanted an efficient way to calculate the close points.
I was provided with a ton of hints to the optimization but there was nothing that was coming up until after the screen was over.

I was told to preprocess the input to this form -> { (x, y): id }
I wasn't sure what I could do with this info, until it kept me up at night and figured it out.

So essentially we can reach O(n) + O(10*10) (not sure about the constant part) runtime by computing all the points in a 10 by 10 square around the point, then look up those points in the preprocessed array.

lookupTable = {}
for input in inputString:
    lookupTable[(input['x'], input['y'])] = input['id']

output = { input['id']: [] for input in inputString }

closeThreshold = 10
for input in inputString:
    for i in range(closeThreshold + 1):
        for j in range(closeThreshold + 1):

            neg_x, pos_x = input['x'] - i, input['x'] + i
            neg_y, pos_y = input['y'] - j, input['y'] + j
            bottom_left = (neg_x, neg_y)
            bottom_right = (pos_x, neg_y)
            top_left = (neg_x, pos_y)
            top_right = (pos_x, pos_y)

            for dir in [bottom_left, bottom_right, top_left, top_right]:
                if dir in lookupTable and lookupTable[dir] != input['id']:
                    output[input['id']].append(lookupTable[(dir)])

Part 3 + Part 4
I didn't make it to this part, but this is where you would refactor and make a class called Game or something and encapsulate the function. For this there would also be methods called play and insert player. The question for these parts is what kind of data structure can you use to efficiently insert and move players around without having to process the closeness again for each player?

I looked up some things and found K-D tree or grid partitioning I still need to do more research and see if this is the right approach.