CareerCup

This problem is basically [matchine Nuts and bolts].

Solution to this problem is with help of quicksort.
1. pick any object A randomly, then compare it all B to find the exact match for it. This pivot in quicksort.
2. While searching for match divide B into two part with respect to pivot so this will make
all small object (of type B) than pivot on left side and all large object (of type B ) on right.. same as quicksort.
3. So at this point we find exact match for B as well as we aligend B. Now we can do the same thing on array of object A . Then repeat the process for on both halves.

Complexity will be (n lg n)

Note:-
We are doing this way we cant directly compare two A type of objects.

Ref:-
[http] www wisdom weizmann ac il/~naor/PUZZLES/nuts_solution.html

You can use a hashTable to solve this problem.

Push all the 'A' object's with size as their keys. Then for each 'B' object, check if size of the object exists in HashTable.
RunTime : (Number of A objects + Number of B objects)
Memory: (Number of A objects)

quick sort...

it's typical google question "nuts and bolts matching problem"

import random

def compare_question(As, Bs):
    def f(A,B):
        # A is an int, B a string
        return cmp(A, len(B))

    if len(As) == 1:
        return [(As[0],Bs[0])]
    elif not As:
        return []

    pivot_B = Bs.pop(random.choice(range(len(Bs))))

    small_As, big_As = [], []
    for j in range(len(As)):
        A = As[j]
        if f(A, pivot_B) < 0:
            small_As.append(A)
        elif f(A, pivot_B) > 0:
            big_As.append(A)
        else:
            pivot_A_index = j

    pivot_A = As.pop(pivot_A_index)
    result = [(pivot_A,pivot_B)]

    small_Bs, big_Bs = [], []
    for B in Bs:
        if f(pivot_A, B) > 0:
            small_Bs.append(B)
        else: # has to be < now
            big_Bs.append(B)

    result += compare_question(small_As, small_Bs)
    result += compare_question(big_As, big_Bs)

    return result

print compare_question([1, 2, 4, 5, 6],
                       ["55555", "666666", "22", "1", "4444"])

I will preface my answer with the fact that the above answer utilizing a Hashtable runs faster than my answer by virtue of running in O(n) time instead of O(n log n). That being said, my answer has the potential to run in O(1) space complexity instead of O(n) space which is required of the Hashtable. Demonstrating both answers will show your interviewer your complete mastery.

This question is basically taking two randomly sorted arrays containing the same elements and asking that we match both arrays so that A[i] == B[i]. We know this from the fact that:

1. Both arrays are the same size
2. Both arrays contain the same 'object' type
3. The description 'Any object A is of the same size as exactly one object B'
4. The description 'All A's have different sizes, and all B's have different sizes'

So with a firm understanding that we have 2 unsorted lists of identical objects, the solution starts to materialize in the form of sorting. If we sort both lists, then all objects will satisfy the condition A[i] == B[i]. This means that we can get a run time complexity of O(n log n), and depending on the sort algorithm you can get O(1) space complexity by doing the sort in-place.

Quick code example in Java:

public void alignArrays(Object[] A, Object[] B){
		if(A.length != B.length) { return; }  //fail fast
		
		Arrays.sort(A);
		Arrays.sort(B);
	}

Note that we could have also made this a boolean return function and added a single for loop to ensure accuracy, but this type of error checking will increase our run time by O(2n) each call. We are given the assumption in the question that size, unique, and matching objects are guaranteed, but explaining your understanding of this concept can help further cement your understanding of the problem.