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.
New question  Google interview


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/minimumnumberswapsrequiredsortarray/
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?

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

@r97922153gmail.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 cycleLength1 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 += cycleLength1 # (7) return min_swaps ``