CareerCup

public int CompatibilityChecker(List<int> first, List<int> second)
{
	int relativeDifference = 0;
	for (int i = 0; i < first.Count; i++)
	{
		if (first[i] != second[i])
		{
			int j = i + 1;
			while (first[i] != second[j])
			{
				j++;
			}
			while (j != i)
			{
				Swap(second, j, j - 1);
				j--;
				relativeDifference++;
			}

		}
	}
	return relativeDifference;
}

public static double computeCompatibility(LinkedList<Integer> user1Rates, LinkedList<Integer> user2Rates)
	{
		int difference = 0;
		for(int i=0; i<user1Rates.size();i++)
		{
			Integer rate = user1Rates.get(i);
			for(int j=i+1; j<user1Rates.size();j++)
			{
				Integer rateToTest = user1Rates.get(j);
				//rate>rateTotest
				if(!isSameOrder(user2Rates, rate, rateToTest))
				{
					difference++;
				}
			}
		}
		return difference;
	}
	
	private static boolean isSameOrder(LinkedList<Integer> user2Rates, Integer rate, Integer rateToTest)
	{
		return user2Rates.indexOf(rate)>user2Rates.indexOf(rateToTest);
	}

My solution is very similar to merge sort.

(in python)

def compatibility(list_one, list_two):                                              
                                                                                    
    incompatible_list = []                                                          
    index = 0                                                                       
                                                                                    
    for item in list_one:                                                           
        if item in incompatible_list:                                               
            continue                                                                
                                                                                    
        while index < len(list_two) and item != list_two[index]:                    
            if list_two[index] not in incompatible_list:                            
                incompatible_list.append(list_two[index])                           
                                                                                    
            index = index + 1                                                       
                                                                                    
        index = index + 1                                                           
                                                                                    
    return len(incompatible_list)

This is just number of inversions right? It's a well known problem with nlogn solution, can be found at geeksforgeeks.

package walmartchallenge;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class QuestionOne {

	private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	private static int counter = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		int arr[] = new int[Integer.parseInt(input)];
		
		int arrOne[] = new int[arr.length];
		int arrTwo[] = new int[arr.length];
		
		input = br.readLine();
		populateArray(arrOne, input);
		
		input = br.readLine();
		populateArray(arrTwo, input);
		
		populateMap(arrTwo);
		
		processToFindCompatibility(arrOne, arrTwo);
		System.out.println(counter);
	}

	private static void processToFindCompatibility(int[] arrOne, int[] arrTwo) {
		for (int i = 0; i < arrOne.length; i++) {
			if (arrOne[i] != arrTwo[i]) {
				int index = map.get(arrOne[i]);
				swap(i, index, arrTwo);
				counter++;
			}
		}
	}

	private static void swap(int i, int index, int[] arr) {
		map.put(arr[i], index);
		map.put(arr[index], i);
		
		int a = arr[index];
		arr[index] = arr[i];
		arr[i] = a;
	}

	private static void populateMap(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			map.put(arr[i], i);
		}
	}

	private static void populateArray(int[] arr, String input) {
		String str[] = input.split(" ");
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(str[i]);
		}
	}
}

I submitted the above solution but only three out of 8 test cases were passing on hacker earth I did try with different custom test cases as well but all of them actually passed till the end of the test I wasn't able to figure out why remaining test cases were failing, can some one help me out on it.

Perform a merge sort on the both the arrays. Count the swap required to sort. The diff is the answer. For ex: in order to sort 31245, you need 2 swaps. To sort 32415, you need 4 swaps. diff = 4-2 = 2

total_gap = 0
for rank in dhoni_str:
    kohli_rank, dhoni_rank = kohli_str.index(rank), dhoni_str.index(rank)
    if kohli_rank - dhoni_rank > 0:
        total_gap += kohli_rank - dhoni_rank
print total_gap

total_gap = 0
for rank in dhoni_str:
    kohli_rank, dhoni_rank = kohli_str.index(rank), dhoni_str.index(rank)
    if kohli_rank - dhoni_rank > 0:
        total_gap += kohli_rank - dhoni_rank
print total_gap