CareerCup

A recursive solution.

#include <iostream>
using namespace std;

int min_time(int h_left, int m_left, int h_num, 
             int m_num, int holes[], int mice[]) {
  while(h_left <= 216 && holes[h_left] == 0) h_left++;
  if (h_left > 216) return 0;
  while(m_left <= 216 && mice[m_left] == 0) m_left++;
  if (m_left > 216) return 0;

  //not skip
  int curr = abs(h_left - m_left);
  mice[m_left]--;
  int rest = min_time(h_left + 1, m_left, h_num - 1, 
                      m_num - 1, holes, mice);
  mice[m_left]++;
  int no_skip = max(curr, rest);
  if (m_left <= h_left || h_num == m_num) {
    return no_skip;
  }
  else {
    //skip
    int skip = min_time(h_left + 1, m_left, h_num - 1,
                        m_num, holes, mice);
    return min(no_skip, skip);
  }
}

void get_min_time(void) {
  int n, m;
  cin>>n>>m;
  int mice[217], holes[217];
  memset(mice, 0, 217*sizeof(int));
  memset(holes, 0, 217*sizeof(int));

  for (int i = 0; i < n; i++) {
    int temp;
    cin>>temp;
    mice[108+temp]++;
  }
  for (int i = 0; i < m; i++) {
    int temp;
    cin>>temp;
    holes[108+temp]++;
  }

  cout<<"Min time: "<<min_time(0, 0, m, n, holes, mice)<<endl;
}

int main() {
  int T;
  cin>>T;
  for (int i = 0; i < T; i++) get_min_time();
  return 0;
}

DP will be more effective.

Well, it seems to be a binary search problem.

f(t) - discrete function, which says FALSE if it is impossible to move mice to the holes in t minutes, and TRUE if possible.

Obviously, this function is monotone. So we need to find the border between FALSE and TRUE. So binary search for t seems to work fine.

For an exact amount of minutes t it's easy to check whether it is possible or not: just try to put mice to the left free hole(if this path is less then t), else to the right(if less). mice's paths won't intersect(but can overlap).

So, if this solution is right, its complexity is O(NlogP) P - the longest distance between mouse and the hole.

import java.util.Scanner;

public class Mice {

public static void main(String[] args) {
Scanner input = new Scanner(System.in);

int T = Integer.parseInt(input.nextLine());

String[] nm;

int n;
int m;

int[] mices;
int[] holes;

int[] distances;
int[] differences;

String[] miceStr;
String[] holesStr;

for(int i = 0; i < T; i++) {

nm = input.nextLine().split(" ");

n = Integer.parseInt(nm[0]);
m = Integer.parseInt(nm[1]);

mices = new int[n];
holes = new int[m];

distances = new int[n];
differences = new int[m];

miceStr = input.nextLine().split(" ");

for(int j = 0; j < miceStr.length; j++) {
mices[j] = Integer.parseInt(miceStr[j]);
}

holesStr = input.nextLine().split(" ");

for(int j = 0; j < holesStr.length; j++) {
holes[j] = Integer.parseInt(holesStr[j]);
}

for(int mice = 0; mice < mices.length; mice++) {
for(int hole = 0; hole < holes.length; hole++) {
differences[hole] = getDifference(mices[mice], holes[hole]);
}

distances[mice] = getMin(differences);
}

System.out.println(getMax(distances));
}
}

private static int getDifference(int i, int j) {
if(i < j) {
return j - i;
} else
return i - j;
}

private static int getMin(int[] num) {
int min = 0;

if(num.length > 0)
min = num[0];

if(num.length > 1)
for(int i = 1; i < num.length; i++) {
if(num[i] < min)
min = num[i];
}

return min;
}

private static int getMax(int[] num) {
int max = 0;

if(num.length > 0)
max = num[0];

if(num.length > 1)
for(int i = 1; i < num.length; i++) {
if(num[i] > max)
max = num[i];
}

return max;
}
}

1. convert the input strings into int vectors that represent the positions of the holes and mice;
2. sort the vectors;
3. find the min time using dynamic programming.

My elegant java solution:

public class MouseHole {
	
	public static void main(String[] args){
		
		int[] m={2, 0, -4};
		int[] h={3, 1, 2, -1 };
		
		int x=MouseHole.assignHoles(m, h);
		System.out.println(x);
		
	}

		public static int assignHoles(int[] mouseP, int[] holes){
		
		HashMap<Integer, Integer> hm=new HashMap<>();
		for(int i : holes){
			hm.put(i, 0);
		}
		
		int MaxTime=0;
		for(int i: mouseP){
			int minDis=Integer.MAX_VALUE;
			int selectedHole=0;
			for(int j: holes){
				
			    int dis=Math.abs(i-j);
			    if(minDis>dis && hm.get(j)==0){
			    	minDis=dis;
			    	selectedHole=j;
			    }
			 
			}
			hm.put(selectedHole, 1);
			MaxTime=Math.max(MaxTime, minDis);
		}
		
		return MaxTime;
		
	}
}

#include <iostream>
#include <limits>

int solve(int *mice , int *holes , int M , int H , int m_from , int h_from , int max){  
    if (m_from == M)
       return max;
    int bestDistance = std::numeric_limits<int>::max();
    for (int i = m_from ; i < M ; ++i){
        for (int j = h_from; j < H ; ++j){
            int distance = std::abs(mice[i]-holes[j]);
            std::swap( mice[m_from] , mice[i] );
            std::swap( holes[h_from] , holes[j]);
            int result = solve(mice , holes , M , H , m_from + 1 , h_from +1 , std::max(max , distance));
            if (result < bestDistance)
                bestDistance = result;
            std::swap( holes[j] , holes[h_from]);
            std::swap(mice[i] , mice[m_from]);
        }
    }
    return bestDistance;
 }

int mice[3] = {2,0,-4};
int holes[4] = {3,1,2,-1};

int main(){
    std::cout<<solve(mice , holes , 3 , 4 , 0 , 0 , 0)<<std::endl;
}

At an abstract level, this is an assignment problem for Bi-partite graph.
I think Hungarian algorithm would do here.

At an abstract level, this is an assignment problem for Bi-partite graph.
I think Hungarian algorithm would do here.

At an abstract level, this is an assignment problem for Bi-partite graph.
I think Hungarian algorithm would do here.

How about this one?

public static int findShortestTime(int[] mouses, int[] holes) {
        Arrays.sort(mouses);
        Arrays.sort(holes);
        int maxTime = -1;
        if(holes.length >= mouses.length) {
            int visitedHoles = 0;

            for(int i = 0; i < mouses.length; i++) {
                int j = i + visitedHoles;
                int timeToRun = abs(holes[j] - mouses[i]);

                while(j + 1 < holes.length && timeToRun > abs(holes[j + 1] - mouses[i])){
                    j = i + ++visitedHoles;
                    timeToRun = abs(holes[j] - mouses[i]);
                }
                if(maxTime < 0 || maxTime < timeToRun) {
                    maxTime = timeToRun;
                }
            }
        }
        return maxTime;
    }

You can check out the editorial at the problem's page. It was available after the CodeSprint Elimination Round 1ended. It's not Amazon's interview question, it is the second problem of the above mentioned competition on hackerRank.
hackerrank->archivedcontests-> CodeSprint India 2014 Elimination Round1->Mice V2->Editorial

DP can solve it.
public int min2(int[] mouse, int[] holes) {
if (mouse == null || holes == null)
return -1;
int lenM = mouse.length;
int lenH = holes.length;
if (lenM > lenH)
return -1;
Arrays.sort(mouse);
Arrays.sort(holes);
int[][] DP = new int[lenM][lenH];
DP[0][0] = Math.abs(mouse[0] - holes[0]);
int min = DP[0][0];
for (int i = 0; i < lenH; i++) {
DP[0][i] = min = Math.min(min, Math.abs(mouse[0] - holes[i]));
}
for (int i = 1; i < lenM; i++) {
DP[i][i] = Math.max(DP[i - 1][i - 1], Math.abs(mouse[i] - holes[i]));
}
for (int i = 1; i < lenM; i++) {
for (int j = i + 1; j < lenH; j++) {
DP[i][j] = Math.min(DP[i][j - 1],
Math.max(DP[i - 1][j - 1], Math.abs(mouse[i] - holes[j])));
}
}
return DP[lenM - 1][lenH - 1];
}

What about this?

import java.util.*;

public class Mice {
    public int getSmallestTime(List<Integer> micePosition,
            List<Integer> holePosition) {
        Collections.sort(micePosition);
        Collections.sort(holePosition);
        List<Integer> positions = new ArrayList<Integer>();
        List<Integer> miceLocations = new ArrayList<Integer>();
        int distance = -1;
        for (int i = 0; i < micePosition.size(); i ++) {
            int prev = 0, next = 0;
            if (holePosition.size() > 1) {
                next = 1;
            }
            int mp = micePosition.get(i);
            int hpminus = holePosition.get(prev);
            int hpplus = holePosition.get(next);
            int distminus = Math.abs(mp - hpminus);
            int distplus = Math.abs(mp- hpplus);
            int index = prev;
            index = hpplus > hpminus ? prev : next;
            int newdist = distplus > distminus ? distminus : distplus;
            distance =  Math.max(distance, newdist);
            positions.add(holePosition.get(index));
            holePosition.remove(index);
            miceLocations.add(mp);
        }
        System.out.println("mice are at: " + miceLocations);
        System.out.println("and they occupy: " + positions);
        return distance;
    }

    public static void main(String[] argv) {
        Mice m = new Mice();
        List<Integer> ml = toList(new int[]{2, 0, -4});
        List<Integer> hl = toList(new int[]{3, 1, 2, -1});
        System.out.println("mice positions: " + ml);
        System.out.println("holes: " + hl);
        System.out.println("fastest time: " + m.getSmallestTime(ml, hl));
    }

    private static List<Integer> toList(int[] numbers) {
        List<Integer> l = new ArrayList<Integer>();
        for (int n : numbers) {
            l.add(n);
        }
        return l;
    }
}