Walmart Labs Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Written Test
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)
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
- lx3 August 07, 2016