Amazon Interview Question for SDE1s


Country: -
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

def mouse_assignment(holes, unassigned_mice)
    max_time = 0
    holes.sort!
    unassigned_mice.sort!
    holes.each do |hole|
      mouse = unassigned_mice.shift
      travel_time = (hole - mouse)
      max_time = [max_time,travel_time, travel_time*-1].max
    end
    return max_time
  end

- Anonymous September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For given input
holes = [4,0,5]
unassigned_mice = [4,-4,2]

mouse_assignment(holes, unassigned_mice)

- Anonymous September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I read the problem as being one where the number of holes are greater than or equal to the number of mice. In that regard, this would align well with a bipartite graph of mice to holes. To solve:
1. sort the array of mice based on position
2. sort the array of holes based on position
3. create graph. The edges should be relative to the size difference between the mice and hole arrays. (if |mice| == |holes|, then it would only be m1 -> h1. But if |holes| - |mice| = 1, then there would be 2 edges for each mouse, m1 -> h1, h2; m2 -> h2, h3; etc)
4. solve using a bipartite graph matching algorithm.

Solution complexity would be O( mice * (|holes| - |mice| + 1) ).

- Zortlord October 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, this is the correct answer. But we can optimize it. if |holes| - |mice| = 1,
and if mn stick to hn, but not hn+1, mn-i would stick to the original one

- samprasyork October 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public int getMin(int[] mouse, int[] holes) {
if (mouse == null || holes == null) {
return -1;
}
int lenM = mouse.length;
int lenH = holes.length;
if (lenM == 0 || lenH == 0 || lenM > lenH) {
return -1;
}
int result = 0;
int[] position = new int[lenM];
for (int i = 0; i < lenM; i++) {
position[i] = i;
}

for (int i = lenM; i < lenH; i++) {
if (!adjust(mouse, holes, position, i, lenM - 1)) {
break;
}
}

for (int i = 0; i < lenM; i++) {
result = Math.max(result, Math.abs(mouse[i] - holes[position[i]]));
}
return result;
}

private boolean adjust(int[] mouse, int[] holes, int[] position,
int holeIndex, int lastMouse) {
if (lastMouse < 0) {
return false;
}
if (Math.abs(mouse[lastMouse] - holes[position[lastMouse]]) > Math
.abs(mouse[lastMouse] - holes[holeIndex])) {
position[lastMouse] = holeIndex;
adjust(mouse, holes, position, holeIndex - 1, lastMouse - 1);
return true;
}

return false;
}

- samprasyork October 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

##python##
print('mice')
mice=input().split(' ')
mice1=[]
for m in mice:mice1.append(int(m))
mice1.sort()
print('hole')
hole=input().split(' ')
hole1=[]
for h in hole:hole1.append(int(h))
hole1.sort()
temp=0
for a in range(len(mice1)):
k=abs(mice1[a]-hole1[a])
if temp<k:
temp=k
print(temp)

- Hy_kor September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh.....

,

preserve indent???

- Hy_kor September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone explain me the solution?

- ABC September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I will explain xlshi's solution.

Let the arrays be M and H for mice and hole respectively. Sort the arrays in ascending order
M : -4 2 4
H : 0 4 5
For any mice at position i all holes with position <i (in the array) will be further away when compared to hole at i (because the array is sorted in ascending order). Thus applying this logic recursively from the bottom of the array you will be able to get the final hole for each mouse and max time taken.

- kr.neerav September 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

My solutions:
1) sort holes and mice
2) get the max difference between holes[i] and mice[i] 0<=i<holes.length

public int mouseAssignment(int[] holes, int[] mice){
		if(holes==null || mice==null || holes.length==0 || mice.length==0 || holes.length!=mice.length){
			return 0;
		}
		Arrays.sort(holes);
		Arrays.sort(mice);
		int maxTime = 0;
		for(int i=0; i<holes.length; i++){
			maxTime = Math.max(Math.abs(holes[i]-mice[i]), maxTime);
		}
		return maxTime;
	}

- xlshi September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I read the question as having a number of holes equal to or greater than the number of mice. If this were the case, then your approach would not be optimal.

- Zortlord September 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Zortlord its right... lets say we have 3 mouses: -1 2 3
and these positions: -40 -20 0 1 4 5
His algorithm would return 39; the answer should be 2

- Fernando September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Fernando

If there are 3 mouse : -1 2 3
and holes are : -40 -20 0 1 4 5

Then the answer should be 1 not 2 as
(-1, 0) = 1
(2, 1) = 1
(3, 4) = 1

So ans = 1

Please correct if I am wrong.

Also we can approach like -

1) sort both the mouse and holes array
2) pick the first mouse and find the point where the absolute diff between mouse and hole is minimum
3) Now perform the diff operation from this point in holes array.

- shailendra September 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int HolesMice(vector<int> &mice, vector<int> &holes, map<int,int> &assignment)
{
    //DO pre-checks.
    const int invalidInput = -1;
    if(mice.size() == 0 || holes.size() != mice.size())
        return invalidInput;

    int maxTime = INT_MIN;
    sort(mice.begin(), mice.end());
    sort(holes.begin(), holes.end());

    transform(mice.begin(), mice.end(), holes.begin(), inserter(assignment,assignment.end()), [&](int a,int b)
    {
        maxTime=max(maxTime,abs(abs(a)-abs(b)));
        return make_pair(a,b);
    }
    );
    return maxTime;
}

BOOST_AUTO_TEST_CASE(TestHolesMice)
{
    int _mice[] = {2,3,5,7,10};
    int _holes[] = {7,11,14,12,15};
    vector<int> mice;
    mice.assign(_mice,_mice+5);
    vector<int> holes;
    holes.assign(_holes,_holes+5);
    map<int,int> assignment;
    BOOST_CHECK(HolesMice(mice, holes, assignment) == 8);
    BOOST_CHECK(assignment[_mice[0]] == 7);
    BOOST_CHECK(assignment[_mice[4]] == 15);
}

- Anonymous September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

maxTime=max(maxTime,abs(a-b));

- Anonymous September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class MouseHole {
	
	public static void main(String[] args) {
		
		int[] Mouse = {4,-4,2};
		int[] Hole = {4,0,5};
		getMax(Hole,Mouse);
	}
	static void getMax(int[] Hole , int[] Mouse) {
		
		Arrays.sort(Hole);
		Arrays.sort(Mouse);
		
		int max = Integer.MIN_VALUE;
		for(int i=0;i<Hole.length;i++) {
			
			max = Math.max(Math.abs(Hole[i]-Mouse[i]), max);
			
		}
		
		System.out.println(max);
	}

}

- shukad333 September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) store mice & holes positions in two different array
2)sort both arrays
3)Remove common elements
4)now iterate through each index,subtract elements on same index and store the sum.
Ex :
sorted array will be :
0 4 5
-4 2 4
after removing common elements arrays will be
0 5
-4 2
so sum would be
|(-4-0) |+ |(2-5)| = 7

- Gaurav Goyal September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not provide the optimal answer. If the holes are {1, 2, 3} and the mice are {2, 3, 4}, then it will report the best time as 3 minutes when the best time could be 1 minute.

- Zortlord September 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question is not asking the "sum" of the time. All the mice run into the holes at the same time in the most optimal way so that the last mouse takes least time to reach his hole.

For the input:
M: 4 -4 2
H: 4 0 5

The answer is: 4

- Qiusheng September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use graphic search algorithm Dijsta algorithm to the find the shortest path between vertrexs.

- Anonymous September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not sure if this has been posted but what you could do is sort holes and mice, then store each distance of the mice to holes in a nxn matrix, then get the diagonal. It will yield the most optimal solution

- Anonymous September 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is this not similar to job assignment problem? What could be the mot effective algo for it since its NP-hard? Branch and bound approach seems to be my guess. Let me know if i'm thinking on right line

- CodeSlave October 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you translate this code in python please??????????

- Anonymous November 25, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More