New question - Google interview

  • 8

    N different couple goes to a cinema with 2N different seats. They take their place randomly. You could make swap operation. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

  • 0

    Only leave the idea here.

    For example, couples are a, b, c, d, e & 1, 2, 3, 4, 5. a->1, b->2 and so on.
    Then fix the alphabets & try matching numbers with alphabets..
    Make an Boolean array to represent if a number has been visited.
    Initially all numbers have not been visited.
    Find the circles recursively as this
    Finally, do swap accordingly.

    The complexity is:
    time: O(n) in finding all circle, O(n) in swapping (or you can do both simutaneously)
    space: O(n) in Boolean array.

    Any better idea?

  • 0

    @pradeepkv09 Oh, I don't know... But I think this is pretty similar to this question:

  • 0
    Y sorting requires O(n.log(n)) .. rest is O(n)

    BTW here is the Python code I wrote based on awesome article you shared.

    def minSwaps(A):
        - create new list of (value,index) tuples, call it Ap   ... (1)
        - sort Ap using value                                   ... (2)
          Initialize min_swaps=0
        - now go over Ap sequentially.                          ... (3)
          say, index i is current node
          - cycleLength=0
          - if i is not visited yet and i'th element is not at correct position ... (5)
            - tag i as visited
            - count number of nodes in cycle starting from i. Assign as cycleLength ... (6)
              - see from where i came from.
                There is some node there. tag the node visited.
                see where that came from ... and so on ...
                terminate this when we loop back to i
            Add cycleLength-1 to min_swaps                       ... (7)
          go to (3)
        Ap=[(A[i],i) for i in range(len(A))] # (1)
        Ap=sorted(Ap, key=lambda pair: pair[0]) # (2)
        for i in range(len(Ap)): # (3)
            if not visited[i] and i!=Ap[i][1]: # (5)
                while not visited[j]:
                    cycleLength += 1 # (6)
                min_swaps += cycleLength-1 # (7)
        return min_swaps

  • 0

    I think that is a good question

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.