## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

We can have a linear time run for this.

First consider number of steps needed to swap two element using empty space e, it would take 3 steps

A = e 1 2 3 7 6 4 5
If we swap 2 and 5, steps would be:
1. Swap 2 and e i.e 2 1 e 3 7 6 4 5
2. Swap 5 and e i.e. 2 1 5 3 7 6 4 e
3. Swap 2 and e i.e. e 1 5 3 7 6 4 2

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

Now for the algo:

``````Walk the array A,
1. Compare each element with its position in the original array O
(this can be optimized, so that we don’t need to lookup entire array O every time)
2. If element is not in proper position, swap it with its original position using empty space
3. Do not advance further yet
If (current element not in proper pos){
goto step 2
}
else {
goto next pos
}``````

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

How does your approach differ from swapping every element with each other (not with the empty one)?
1) Say we are at position 'i'.
2) The original position of a[i] is p. So swap a[i] with a[p].
3) Now the a[i] contains new element. Repeat the process till a[i] contains the correct element.
4) Move to a[i+1]
The only difference is that the empty element is handled as any other element in the array.
Moreover I don't get what does it mean 'with least number of swaps'. Did you reduce the number of swaps in your algo?
I think the number of swaps which is required to revert the modified array to the original form depends on the element distribution in the modified array.
Simple example:
Original array: {1,2,3,4}
Modified version 1: {3,4,1,2} - 2 swaps, because new elements already matches the position after swap.
Modified version 2: {2,3,4,1} - 3 swaps.

Comment hidden because of low score. Click to expand.
2
of 2 votes

It does not differ from swapping element with each other. If anything, it add more complexity.
The point here is that we're simulating a parking lot, so if its full, to exchange the positions of two cars, we'll need an empty space. That is why we must use the empty slot within the array.

I think with min # of swaps, the interviewer actually means least run time complexity. That's what I was shooting for in my solution.

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

Just move the car to be parked in the empty positon.Then move the car that needs to be placed in the new empty postion. By this way you'll move only those cars need to be moved only once.

Comment hidden because of low score. Click to expand.
0
of 0 votes

this makes sense to me

7 swaps
state: e1237645
desired: 4651732e
4->e
412376e5
2->e
41e37625
5->e
4153762e
1->e
4e537621
6->e
46537e21
3->e
465e7321
1->e
4651732e

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

Could you provide more info on swapping definition? Are we only allowed to put a car in the empty slot in each step?

Comment hidden because of low score. Click to expand.
0
of 0 votes

The position of two cars can only be swapped using the empty space.

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

Can this be done using backtracking algorithm?

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

How can we optimize the trivial solution for this problem? I mean, how can we bring the constraint of minimum swaps bring into picture?

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

``````private static final int NO_CAR = -1;

public ParkingInstructions getParkingInstructions(int[] startingParkingLot, int[] desiredParkingLot) {
final int parkingLotSize = startingParkingLot.length;
int[] currentParkingLot = Arrays.copyOf(startingParkingLot, parkingLotSize);

List<int[]> intermediateParkingLotPhases = new ArrayList<int[]>(parkingLotSize);
int numberOfSteps = 0;

while (areAllCarsInDesiredSpots(currentParkingLot, desiredParkingLot) == false) {
int currentEmptySpotPosition = getPositionOfCar(currentParkingLot, NO_CAR);

int spotToSwapEmptyPositionWith = currentEmptySpotPosition;
if (isCarInDesiredSpot(currentParkingLot[currentEmptySpotPosition], desiredParkingLot[currentEmptySpotPosition])) {
spotToSwapEmptyPositionWith = findPositionOfFirstAvailableCarToSwap(currentParkingLot, desiredParkingLot);
swapCarsInSpots(currentParkingLot, currentEmptySpotPosition, spotToSwapEmptyPositionWith);
currentEmptySpotPosition = spotToSwapEmptyPositionWith;
}

spotToSwapEmptyPositionWith = getPositionOfCarDesiredInCurrentEmptySpot(currentParkingLot, desiredParkingLot, currentEmptySpotPosition);
swapCarsInSpots(currentParkingLot, currentEmptySpotPosition, spotToSwapEmptyPositionWith);

intermediateParkingLotPhases.add(Arrays.copyOf(currentParkingLot, parkingLotSize));
numberOfSteps++;
}

return new ParkingInstructions(intermediateParkingLotPhases, numberOfSteps);
}

private boolean areAllCarsInDesiredSpots(int[] currentParkingLot, int[] desiredParkingLot) {
final int parkingLotSize = currentParkingLot.length;
boolean areAllCarsInDesiredSpots = true;

int spotPosition = 0;

while (areAllCarsInDesiredSpots == true && spotPosition < parkingLotSize) {
areAllCarsInDesiredSpots = isCarInDesiredSpot(currentParkingLot[spotPosition], desiredParkingLot[spotPosition]);
spotPosition++;
}

return areAllCarsInDesiredSpots;
}

private boolean isCarInDesiredSpot(int currentSpot, int desiredSpot) {
return currentSpot == desiredSpot;
}

private int getPositionOfCar(int[] parkingLot, int carToFind) {
int spotThatCarIsIn = 0;
for (int currentParkingSpot : parkingLot) {
if (carToFind == currentParkingSpot) {
break;
}

spotThatCarIsIn++;
}

return spotThatCarIsIn;
}

private int findPositionOfFirstAvailableCarToSwap(int[] parkingLot, int[] desiredLot) {

final int parkingLotSize = parkingLot.length;
int spotPosition = 0;

while (spotPosition < parkingLotSize) {
if (isCarInDesiredSpot(parkingLot[spotPosition], desiredLot[spotPosition]) == false) {
break;
}

spotPosition++;
}

return spotPosition;
}

private void swapCarsInSpots(int[] parkingLot, int firstSpot, int secondSpot) {
final int tempSpot = parkingLot[firstSpot];
parkingLot[firstSpot] = parkingLot[secondSpot];
parkingLot[secondSpot] = tempSpot;
}

private int getPositionOfCarDesiredInCurrentEmptySpot(int[] currentParkingLot, int[] desiredParkingLot, int positionOfCurrentEmptySpot) {
final int desiredCarForCurrentEmptySpot = desiredParkingLot[positionOfCurrentEmptySpot];

return getPositionOfCar(currentParkingLot, desiredCarForCurrentEmptySpot);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please add some explanation for your code?

Comment hidden because of low score. Click to expand.
2
of 2 votes

Sure thing. I first check whether all cars are in their desired positions. If so, I don't have any work to do.

If that's not the case. I first locate where the empty spot is. There is a boundary case for this, where the empty spot happens to be where it should be. If that's the case, my approach was to find the first non-sorted car and swap the empty spot with that. I did some by-hand runs of this and determined that it didn't matter which one I picked, the number of steps was the same.

No matter what, I then figure out what car should be in the spot where the empty spot currently is. It's then just a matter of swapping the two.

The class is rather verbose, I know, but I figured it's slightly more readable that way.

I didn't come up with a scientific method to prove this, but the number of intermediate steps between the initial parking lot and the desired parking lot tends to be about equals to how many cars are unsorted. But then there's also the matter of arbitrary spots with the empty space, so that could potentially skew it.

Finally, a rough (possibly inaccurate, I just woke up) complexity analysis says that it should run in linear time, and creating a list of intermediate values to return cause it to use linear space.

Comment hidden because of low score. Click to expand.
0
of 0 votes

what language is the code written

Comment hidden because of low score. Click to expand.
0
of 0 votes

What language is the code written

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

I think we need to move the right car to the empty pos, in this way, we can move with min swap.
if in some case, empty pos is in right pos, but there still some car in wrong pos, we need to move this wrong car to empty pos, then still with this rule, move right car to the empty pos.
for example:
expected pos:
1 4 5 2 3 6 9 _ 7 8
but init car pos:
1 5 7 3 9 _ 2 4 6 8
==>> move 6 to the empty pos:
1 5 7 3 9 6 2 4 _ 8
=>> move 7 to empty pos:
1 5 _ 3 9 6 2 4 7 8
1 _ 5 3 9 6 2 4 7 8
1 4 5 3 9 6 2 _ 7 8
==> in this case empty pos is in right pos. but there are still some car in wrong place.
1 4 5 _ 9 6 2 3 7 8
1 4 5 2 9 6 _ 3 7 8
1 4 5 2 _ 6 9 3 7 8
1 4 5 2 3 6 9 _ 7 8

10 swaps.

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

It's nothing but "Selection Sort" from My understanding,

Maximum number of swaps = No. of the Slots.

Time Complexity : O(n^2).

If the Value is bigger than the key, Then in such cases Time complexity has the lesser priority than the Swaps.

Please correct me if anything wrong.

Comment hidden because of low score. Click to expand.
0
of 0 votes

We can do it in O(n) time, if we just pre process the original array, instead of finding the correct position by going over the array every time..

Comment hidden because of low score. Click to expand.
0
of 0 votes

Please Elaborate How it's possible in O(n) time..

Comment hidden because of low score. Click to expand.
2
of 2 votes

If, A: Changed array, O: Original array
O(N^2) run time: For each element in A, we'll find its original position in O( O(N) time operation). We'll swap it with its original position. Do this N times and we get O(N^2) run time.

O(N) run time: Instead of walking the array O every time to find the original position of an element, pre process it, so that we can get the original position of an element in O(1) run time. We could maintain a hashtable, or another sorted array etc.

So, now putting an element in its correct position in A would be a constant time operation, O(1) lookup and O(3) to swap to original position.

Run time = O(N) to preprocess + O(4*N) to rearrange array in proper time = linear time.

I hope my algo comes across clearly, its hard to explain your thinking in writing.

Comment hidden because of low score. Click to expand.
0
of 0 votes

selection sort will not work.
take example:
given array [1,2,3,4,5,_ ]

final array [5,2,3,1,_,4]

the answer is 3, but with selection sort method it is giving 5.

Comment hidden because of low score. Click to expand.
0
of 0 votes

selection sort will not work.
take example:
given array [1,2,3,4,5,_ ]

final array [5,2,3,1,_,4]

the answer is 3, but with selection sort method it is giving 5.

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

``````void swaps(int a[],int b[],int n)
{
int i=1;
int hash[100];
for(i=1;i<=n;i++)
hash[a[i]]=i;
for(i=1;i<=n;i++)
printf("%d--->%d\n",i,hash[i]);
int count=0;
i=1;
while(i<=n)
{
if(b[i]==a[i])
i++;
else
{
int temp = hash[b[i]];
b[i]=b[i]^b[temp];
b[temp]=b[i]^b[temp];
b[i]=b[i]^b[temp];
count++;
}
}
printf("Count is %d\n",count);
}``````

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

This problem is basically expecting to sort the cars based on their expected position. So if example order is 4,6,5,1,7,3,2,empty. Map these numbers to f (A) = 1 2 3 4 5 6 7 8(the expected positions). So f[car 4] =1 , f[car 6] = 2..... . Now use f to convert the current order of cars to these mapped array. So if current order is empty,1,2,3,7,6,4,2 then using f we can map this to B = 8, 4, 7, 6, 5, 2, 1, 7.

So this problem is equivalent to in-place sorting of B. The only constraint is that we have only 1 temp variable(the empty location) that can be used for swapping. In this case B[0]= 8 is the empty location that can be treated as a temp variable. So use quick sort here to do the sorting using temp(B[0]) as the temp variable for all the swapping operations involved in quicksort.

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

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
/*Minimum number of swaps required to sort array algo with slight modification*/
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<pair<int,int> >v;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
v.push_back(make_pair(a,i));
}
sort(v.begin(), v.end());
std::vector<int> vis(n,0);
int ans=0;
for(int i=0;i<n;i++)
{
if(vis[i] || v[i].second==i)
continue;
int cyc_size = 0;
int j=i;
while(!vis[j])
{
vis[j]=1;
cyc_size++;
j=v[j].second;
}
cyc_size++;
ans=ans+cyc_size;
}
cout<<ans<<endl;
// for(int i=0;i<n;i++)
// {
// 	cout<<v[i].first<<" "<<v[i].second<<endl;
// }
}
}``````

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

int len = cars.length-1;

char [] updated = new char[cars.length];

int count = 0;

int carPosition = 0;

for(int i = 0; i < cars.length; i++) {

char movedCar = 0;

updated[i] = cars[i];

if(cars[i] == '0') {

if(count == 0) {
// Find Empty spat moved to End move
// moved End Empty spat
movedCar = cars[i];
cars[i] = cars[len];
carPosition = i;

cars[len] = movedCar;

count++;

}else {

while(count == carPosition) {

}

char currentCar = cars[carPosition];
movedCar = cars[carPosition-2];

cars[carPosition] = movedCar;

cars[carPosition-2] = currentCar;

currentCar = cars[carPosition-2];
movedCar = cars[carPosition-1];

cars[carPosition-1] = currentCar;
cars[carPosition-2] = movedCar;

currentCar = cars[carPosition-2];

currentCar = cars[carPosition-4] ;

movedCar = cars[carPosition-2];

cars[carPosition-2]= currentCar;

cars[carPosition-4]= movedCar;

movedCar = cars[0];

currentCar = cars[carPosition-3] ;

cars[0]= currentCar;

cars[carPosition-3] = movedCar;

}
}

}

for (int j = 0; j < cars.length; j++) {

System.out.print(cars[j] + " ");
}﻿

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

int len = cars.length-1;

char [] updated = new char[cars.length];

int count = 0;

int carPosition = 0;

for(int i = 0; i < cars.length; i++) {

char movedCar = 0;

updated[i] = cars[i];

if(cars[i] == '0') {

if(count == 0) {
// Find Empty spat moved to End move
// moved End Empty spat
movedCar = cars[i];
cars[i] = cars[len];
carPosition = i;

cars[len] = movedCar;

count++;

}else {

while(count == carPosition) {

}

char currentCar = cars[carPosition];
movedCar = cars[carPosition-2];

cars[carPosition] = movedCar;

cars[carPosition-2] = currentCar;

currentCar = cars[carPosition-2];
movedCar = cars[carPosition-1];

cars[carPosition-1] = currentCar;
cars[carPosition-2] = movedCar;

currentCar = cars[carPosition-2];

currentCar = cars[carPosition-4] ;

movedCar = cars[carPosition-2];

cars[carPosition-2]= currentCar;

cars[carPosition-4]= movedCar;

movedCar = cars[0];

currentCar = cars[carPosition-3] ;

cars[0]= currentCar;

cars[carPosition-3] = movedCar;

}
}

for (int j = 0; j < cars.length; j++) {

System.out.print(cars[j] + " ");

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

``````public class CarMovingProblem {
Hashtable<Character, Integer> idealMap = new Hashtable<>();
Hashtable<Character, Integer> givenMap = new Hashtable<>();
static int changes = 0;

public void getMiniumSwaps(List<Character> ideal, List<Character> given) {
for (int i = 0; i < given.size(); i++) {
idealMap.put(ideal.get(i), i);
givenMap.put(given.get(i), i);
}

int blankIndex = getBlankIndex(given);
while (true) {
if (!isIndexCorrectlyParked(blankIndex, ideal, given)) {
//blank is not correctly parked, get what car should be here at this index
char ch = ideal.get(blankIndex);
//find out where is it parked now
final Integer idealIndex = givenMap.get(ch);
swapCarsAtIndex(blankIndex, idealIndex, given);
blankIndex = getBlankIndex(given);
} else {
//getFirstIncorrectlyParkedIndex
int firstIncorrectlyParkedCarIndex = getFirstIncorrectlyParkedCarIndex(ideal, given);
if (firstIncorrectlyParkedCarIndex == -1) {
break;
} else {
swapCarsAtIndex(firstIncorrectlyParkedCarIndex, blankIndex, given);
blankIndex  = firstIncorrectlyParkedCarIndex;
}
}
}
}

public void swapCarsAtIndex(int x, int y, List<Character> given) {
final Character temp = given.get(x);
given.set(x, given.get(y));
given.set(y, temp);
changes++;
givenMap.put(given.get(x), x);
givenMap.put(given.get(y), y);
System.out.println(given);
}

public int getBlankIndex(List<Character> given) {

return given.indexOf('_');
}

public boolean isIndexCorrectlyParked(int i, List<Character> ideal, List<Character> given) {
if (i <= ideal.size() - 1 && i <= given.size() - 1)
return ideal.get(i) == given.get(i);
return false;
}

public int getFirstIncorrectlyParkedCarIndex(List<Character> ideal, List<Character> given) {
for (int i = 0; i < ideal.size(); i++) {
if (ideal.get(i) != given.get(i)) {
return i;
}
}
return -1;
}

public static void main(String[] args) {
// new CarMovingProblem().getMiniumSwaps(Arrays.asList('A', 'B', 'C', 'D', 'E', 'F', 'G', '_'), Arrays.asList('A', '_', 'D', 'E', 'B', 'F', 'G', 'C'));
final List<Character> given = Arrays.asList('D', 'F', 'E', 'A', 'G', 'C', 'B', '_');
final List<Character> ideal = Arrays.asList('_','A','B','C','G','F','D','E');

System.out.println(given);
System.out.println("||");
System.out.println(ideal);
System.out.println("==================");
new CarMovingProblem().getMiniumSwaps(ideal,given );
System.out.println("swaps required: " + changes);
}
}``````

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