Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
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
}
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.
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.
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.
Could you provide more info on swapping definition? Are we only allowed to put a car in the empty slot in each step?
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);
}
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.
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.
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.
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..
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.
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.
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);
}
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.
#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;
// }
}
}
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] + " ");
}
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] + " ");
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);
}
}
We can have a linear time run for this.
- puneet.sohi April 17, 2014First 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