Question

GoldMan Sachs | Recent Interview Experiences | Coderpad | SDE | Set-15

Answer 1

Question:

Given a jumbled collection of segments, each of which is represented as a Pair(startPoint, endPoint), this function sorts the segments to make a continuous path.
A few assumptions you can make:
Each particular segment goes in one direction only, i.e.: if you see (1, 2), you will not see (2, 1).
Each starting point only have one way to the end point, i.e.: if you see (6, 5), you will not see (6, 10), (6, 3), etc.
For example, if you've passed a list containing the following int arrays:
[(4, 5), (9, 4), (5, 1), (11, 9)]

Then your implementation should sort it such:
[(11, 9), (9, 4), (4, 5), (5, 1)]

@param segments collection of segments, each represented by a Pair(startPoint, endPoint).
@return The sorted segments such that they form a continuous path.
@throws Exception if there is no way to create one continuous path from

all the segments passed into this function. Feel free to change the Exception type as you think appropriate.

I thought about use hashmap or topological sort but I don't know how to finish it. And I have checked the Chegg before unfortunately the answer is not completed.

Can someone show me how to solve this problem in Python? Thank you.

Answer 2

Here is my solution, I leveraged the fact that the start and end value will only have one occurrence, e.g. 11 and 1. I put all of the starts and ends in a key:value dict and I select either 11 or 1 to be my starting point depending on if they are a key in my dict indicating they are a start. I only tested on your example, I'm sure there could be some tidying up in my code.

 

example = [(4, 5), (9, 4), (5, 1), (11, 9)]

def continuousSort(arr):
    m = {}
    values = []
    output = []
    
    startAndEnd = []
    for i in range(len(arr)):
        start = arr[i][0]
        end = arr[i][1]
        m[start] = end
        values.extend([start, end])
    
    occur = Counter(values)
    for i in occur:
        if occur[i] == 1:
            startAndEnd.append(i)

    if len(startAndEnd) > 2:
        return []

    curr = startAndEnd[0] if startAndEnd[0] in m.keys() else startAndEnd[1]

    for _ in range(len(m)):
        output.append((curr, m[curr]))
        curr = m[curr]
    return output
    

continuous = continuousSort(example)
print(continuous)
    
# [(11, 9), (9, 4), (4, 5), (5, 1)]

 

Condensed down

 

example = [(4, 5), (9, 4), (5, 1), (11, 9)]

def continuousSort(arr):
    m, output = dict(arr), []
    values = [i for i_arr in arr for i in i_arr]
    occur = Counter(values)
    startAndEnd = [x for x in occur if occur[x] == 1]

    if len(startAndEnd) > 2:
        return []
    
    curr = startAndEnd[0] if startAndEnd[0] in m.keys() else startAndEnd[1]
    
    for _ in range(len(m)):
        output.append((curr, m[curr]))
        curr = m[curr]
    return output
    
continuous = continuousSort(example)
print(continuous)
    
# [(11, 9), (9, 4), (4, 5), (5, 1)]