New question - Google interview


  • 8
    P

    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
    R

    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 https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/
    Finally, do swap accordingly.

    The complexity is:
    [native]:
    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
    L

    @pradeepkv09 Oh, I don't know... But I think this is pretty similar to this question:
    https://leetcode.com/problems/couples-holding-hands/description/.


  • 0
    Y

    @r97922153-gmail.com 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):
        """
        Steps:
        - 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)
        visited=[False]*len(Ap)
        min_swaps=0
        for i in range(len(Ap)): # (3)
            if not visited[i] and i!=Ap[i][1]: # (5)
                cycleLength=0
                j=i
                while not visited[j]:
                    visited[j]=True
                    cycleLength += 1 # (6)
                    j=Ap[j][1]
                min_swaps += cycleLength-1 # (7)
        return min_swaps
    ``

  • 0
    L

    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.