Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Basic logic is:
currentCar[i] - input.
desiredCar[i] - output.
1) Map car to position based on the input order (umap) and remember empty index.
2) Now loop through the input order cars.
For each entry check desiredCar[i] and if it is not same as currentCar[i] and
currentCar[i] is not "-1" then we need to keep swaping empty index with currentCar
until empty index reaches to its desired position.
If empty index is found to be at desired position and we still have cars which are not
at the appropriate position then first swap the empty car position with current position
to allow us to move the current car to its appropriate slots.
My (probably naive) O(n^2) solution:
Loop through the spots:
if desired car:
continue
if not empty:
loop through the spots again, looking for the empty spot
put the current car in the empty spot
loop through the spots again, looking for the desired car
put the desired car in the current spot
if empty:
loop through the desired spots again, looking for the desired car
put the desired car in the current spot
Trying this again so it will look right:
My (probably naive) O(n^2) solution:
Loop through the spots:
if desired car:
continue
if not empty:
loop through the spots again, looking for the empty spot
put the current car in the empty spot
loop through the spots again, looking for the desired car
put the desired car in the current spot
if empty:
loop through the desired spots again, looking for the desired car
put the desired car in the current spot
General idea: keep track of the empty spot, and move the car that belongs there in the final order.* somehow the empty spot is in its final location before the rest of the cars are in the right position, move a car that is not already in its final location into the empty spot **
Example
start = [1, 2, 3, -1, 4, 5]
end = [5, 1, -1, 3, 2, 4]
* first move -> [1, 2, -1, 3, 4, 5] -> 3 is now in the correct final spot
** second move -> [-1, 2, 1, 3, 4, 5]
def parkCars(start, end):
current = start
empty = findInCurrent(-1, current)
output = []
while current != end: # n
# if empty spot in correct location
if current[empty] == end[empty]:
newEmpty = findWrongParking(current, end)
else:
newEmpty = findInCurrent(end[empty], current)
current[empty] = current[newEmpty]
output.append(current[newEmpty])
current[newEmpty] = -1
empty = newEmpty
return output
def findInCurrent(value, current):
for i in range(len(current)):
if current[i] == value:
return i
else:
continue
def findWrongParking(current, end):
for i in range(len(current)):
if current[i] != end[i]:
return i
else:
continue
public List<Integer> reArrange(int input[], int output[]) {
List<Integer> carsMoved = new ArrayList<>();
// Find current empty slot
int emptySlot = findEmptySlot(input);
// Create a car to slot map
// In case car is already at correct position, exclude it
Map<Integer, Integer> carSlotMap = getCarSlotMap(input, output);
while(carSlotMap.size() != 0) {
if(output[emptySlot] != -1) {
int newEmptySlot = carSlotMap.get(output[emptySlot]);
carSlotMap.remove(output[emptySlot]);
carsMoved.add(output[emptySlot]);
emptySlot = newEmptySlot;
} else {
int carToMove = carSlotMap.keySet().iterator().next();
carsMoved.add(carToMove);
int newEmptySlot = carSlotMap.get(carToMove);
carSlotMap.put(carToMove, emptySlot);
emptySlot = newEmptySlot;
}
}
return carsMoved;
}
private int findEmptySlot(int[] input) {
for(int i = 0; i < input.length; i++) {
if(input[i] == -1) {
return i;
}
}
return -1;
}
private Map<Integer, Integer> getCarSlotMap(int[] input, int[] output) {
Map<Integer, Integer> carSlotMap = new HashMap<>();
for(int i = 0; i < input.length; i++) {
if(input[i] != -1) {
if(input[i] != output[i]) {
carSlotMap.put(input[i], i);
}
}
}
return carSlotMap;
}
In the beginning : create a map with key value pair.. where key is desired index and value is current index.. in this example for "3" --> current index is 2 and desired index is 3.. so map will have 3 --> 2
Now figure out the location of empty index.. In this example empty index is 3. We look up the map for 3 and it returns 2 (which means we can swap index 3 and 2)
for the empty index, perform lookup in map
case 1. lookup succeeds --> then swap and then delete the entry from map and remember index of new empty index e'
case 2. lookup fails --> read first value from map (d' --> c') perform swap of e', c', then update entry d' --> c' to d' --> e'
exit case : Map is empty
current status
a b -1 c
final status
c -1 b a
Create hashmap with key as desired index and value as current index..
0 3
2 1
3 0
Step 1
Now in current array find out index of blank.. In this case it is 2
lookup map for desired location
(i.e 2 and value 1)
swap value from index 1 to 2
a -1 b c
Delete entry for 2 1 from map..
now map has following entry
0 3
3 0
Step 2
position of blank index = 1. Lookup 1 in the map
Result : entry not found
then read first entry from map (0 3)
then move value from position 3 to position 1
a c b -1
and update the map from 0 3 to 0 1
map entry looks like this
0 1
3 0
iterate the steps as long as map is not empty. when map is empty you will get the desired arrangement.
I did it with BFS.
def move arr, idx
loc = arr.index(-1)
return false if idx == loc
arr = arr.dup
arr[loc], arr[idx] = arr[idx], arr[loc]
arr
end
def moves arr
res = []
arr.length.times do |idx|
if move(arr, idx)
res << move(arr, idx)
end
end
res
end
def solved_arr arr
i = 1
solved = [-1]
while i < arr.length
solved << i
i += 1
end
solved
end
def bfs arr
hash = {}
hash[arr] = [0, arr]
solved = solved_arr(arr)
break_loop = false
queue = [arr]
until break_loop
past = queue.shift
moves = moves(past)
moves.each do |el|
queue << el unless hash[el]
hash[el] = past unless hash[el]
break_loop = true if el == solved
end
end
res = []
while hash[solved] != arr
res << solved
solved = hash[solved]
end
res << solved
res << arr
res.reverse
end
I used BFS.
def move arr, idx
loc = arr.index(-1)
return false if idx == loc
arr = arr.dup
arr[loc], arr[idx] = arr[idx], arr[loc]
arr
end
def moves arr
res = []
arr.length.times do |idx|
if move(arr, idx)
res << move(arr, idx)
end
end
res
end
def solved_arr arr
i = 1
solved = [-1]
while i < arr.length
solved << i
i += 1
end
solved
end
def bfs arr
hash = {}
hash[arr] = [0, arr]
solved = solved_arr(arr)
break_loop = false
queue = [arr]
until break_loop
past = queue.shift
moves = moves(past)
moves.each do |el|
queue << el unless hash[el]
hash[el] = past unless hash[el]
break_loop = true if el == solved
end
end
res = []
while hash[solved] != arr
res << solved
solved = hash[solved]
end
res << solved
res << arr
res.reverse
end
def min_moves(parking, desired):
cars = dict()
free_spot = None
for i in xrange(len(parking)):
if parking[i] == -1:
free_spot = i
elif parking[i] is not desired[i]:
cars[parking[i]] = (i, None)
for i in xrange(len(parking)):
if desired[i] in cars:
cars[desired[i]] = (cars[desired[i]][0], i)
swaps = dict()
for car in cars:
swaps[cars[car][1]] = cars[car][0]
num_swaps = 0
while swaps:
if free_spot in swaps:
temp = free_spot
free_spot = swaps[free_spot]
del swaps[temp]
else:
first = swaps.items()[0]
swaps[first[0]] = free_spot
free_spot = first[1]
num_swaps += 1
return num_swaps
p = [1, 2, 3, -1, 4, 5]
d = [5, -1, 2, 3, 1, 4]
print min_moves(p, d)
I got a naive solution, and I don't know if it's the minimize steps.
The strategy is to loop through the desired order, if desire[i] is empty(-1) or it's just equal to current[i], continue; or else if the current[i] is not empty, we move current[i] to empty slot first, and then move desire[i] to slot i. The following is runnable C++ code:
void dump(vector<int> a){
for(int i =0;i<a.size();i++){
cout << a[i] << ",";
}
cout << endl;
}
void move(vector<int> & current, vector<int>& desire){
unordered_map<int,int> car_pos;
int empty;
for(int i=0;i<current.size();i++){
if(current[i] == -1)
empty = i;
else
car_pos[current[i]] = i;
}
for(int i =0;i<desire.size();i++){
if(desire[i] == -1)
continue;
if(car_pos[desire[i]] == i)
continue;
int move_car;
if(i!=empty){
move_car = current[i];
current[empty] = move_car;
car_pos[move_car] = empty;
empty = i;
current[empty] = -1;
cout << "move " <<move_car << ", current pos is ";
dump(current);
}
move_car = desire[i];
current[i] = move_car;
empty = car_pos[move_car];
car_pos[move_car] = i;
current[empty] = -1;
cout << "move " <<move_car << ", current pos is ";
dump(current);
}
}
Cause the algorithm travel the desire oder once, ant the operation of each loop body is constant time, the time complexity is O(n)
I derived following solution ::
private static int calculate(int[] arrInitial, int[] arrFinal) {
int totalsteps = 0, position = 0, blankSpot = 0, placeholder = 0, finalBlankSpot = 0, tempValue = 0,
tempIndex = 0;
blankSpot = findIndex(arrInitial, -1);
finalBlankSpot = findIndex(arrFinal, -1);
while (finalSet.size() != arrInitial.length - 1) {
if (arrInitial[position] == arrFinal[position]) {
if (arrInitial[position] != -1)
finalSet.add(arrInitial[position]);
position++;
totalsteps++;
continue;
}
tempValue = arrFinal[position];
// for tempValue in arr1, find its index
tempIndex = findIndex(arrInitial, tempValue);
// swap value of arrInital[position] with blankSpot
arrInitial[blankSpot] = arrInitial[position];
arrInitial[position] = -1;
blankSpot = position;
// now swap value of tempIndex in arrInitial with new blankspot and
// update blankspot value
arrInitial[position] = arrInitial[tempIndex];
arrInitial[tempIndex] = -1;
blankSpot = tempIndex;
if (arrInitial[position] != -1)
finalSet.add(arrInitial[position]);
position++;
totalsteps++;
}
return totalsteps;
}
private static int findIndex(int[] arr, int value) {
int index = 0;
for (int i : arr) {
if (i == value)
return index;
index++;
}
return index;
}
int flipToB(int curr[], int exp[]) {
int space = -1;
int spaceIdx = 0;
int swap = 0;
Map<Integer, Integer> ktv = new HashMap<>();
for (int i = 0; i < curr.length; i++) {
ktv.put(curr[i], i);
if (exp[i] == space) {
spaceIdx = i;
}
}
for (int i = 0; i < curr.length; i++) {
if (exp[i] == curr[i])
continue;
int pos = i;
move(i, ktv.get(space), ktv, curr);
swap = swap + 1;
while (pos != spaceIdx) {
int newpos = ktv.get(exp[pos]);
move(newpos, pos, ktv, curr);
pos = newpos;
swap = swap + 1;
}
}
return swap;
}
void move(int fromIdx, int toIdx, Map<Integer, Integer> ktv, int input[]) {
int val = input[fromIdx];
input[fromIdx] = input[toIdx];
ktv.put(input[toIdx], fromIdx);
input[toIdx] = val;
ktv.put(val, toIdx);
}
I am trying to approach this as a sorting question. Basically, assign a sorted key array to the final position, and now try to "sort" the initial array using the empty space as temp variable for each swap (in quick sort or bubble sort). Make required adjustments to move the empty spot to required place.
var src = [1,2,3,-1,4,5];
var dest = [5,1,2,-1,3,4];
var procCount = 0;
function replaceElement(arr, num1, num2) {
var num1Idx = arr.indexOf(num1);
var num2Idx = arr.indexOf(num2);
arr[num2Idx] = num1;
arr[num1Idx] = num2;
procCount++;
}
function go() {
while(true) {
if(procCount > 15) {
return;
}
console.log(src);
var targetIdx = src.indexOf(-1);
var destVal = dest[targetIdx];
if(src.toString() === dest.toString()) {
break;
}
if(destVal === -1) {
for(var i in src) {
if(src[i] !== -1) {
if(src[i] !== dest[i]) {
replaceElement(src, -1, src[i]);
break;
}
}
}
} else {
replaceElement(src, -1, destVal);
}
}
}
I applied a modified quick sort routine (avg. runtime O(nlogn)...
public static void solveProblem2()
{
int[] arr1 = new int[] {1, 2, 3, -1, 4, 5};
int[] arr2 = new int[] {5, 1,-1, 3, 2, 4};
List<Integer> lResults = new ArrayList<Integer>();
Map<Integer, Integer> mOrdering = new HashMap<Integer, Integer> ();
int k = -1;
for(int j=0;j<arr2.length;j++)
{
mOrdering.put(arr2[j], j);
}
for(int j=0;j<arr1.length;j++)
{
if(arr1[j]==-1)
{
k = j;
}
}
List<Integer> lTempIndex = new ArrayList<Integer>();
lTempIndex.add(k);
modifiedQuickSort(lResults, mOrdering, arr1, 0, arr1.length-1, lTempIndex);
for(int m : lResults)
System.out.println("move car at "+m+" into empty spot...");
}
private static void modifiedQuickSort(List<Integer> _lResults, Map<Integer, Integer> _mOrder, int[] _arr, int _start, int _end, List<Integer> _tempIndex)
{
if(_start>=_end)
{
return;
}
int pivot = _arr[_start];
int lo = _start-1;
int hi = _end+1;
while(true)
{
do {
lo++;
}
while(_mOrder.get(_arr[lo])<_mOrder.get(pivot));
do {
hi--;
}
while(_mOrder.get(_arr[hi])>_mOrder.get(pivot));
if(lo>=hi)
{
break;
}
else
{
// swap (using _tempIndex as the temp swap location)
if (_arr[lo] != -1 && _arr[hi] != -1)
{
_lResults.add(lo);
_arr[_tempIndex.get(0)] = _arr[lo];
_arr[lo] = -1;
_lResults.add(hi);
_arr[lo] = _arr[hi];
_arr[hi] = -1;
_lResults.add(_tempIndex.get(0));
_arr[hi] = _arr[_tempIndex.get(0)];
_arr[_tempIndex.get(0)] = -1;
}
else if (_arr[lo] == -1)
{
_lResults.add(hi);
_arr[lo] = _arr[hi];
_arr[hi] = -1;
_tempIndex.set(0,hi);
}
else if (_arr[hi] == -1)
{
_lResults.add(lo);
_arr[hi] = _arr[lo];
_arr[lo] = -1;
_tempIndex.set(0,lo);
}
}
}
modifiedQuickSort(_lResults, _mOrder, _arr, _start, hi, _tempIndex);
modifiedQuickSort(_lResults, _mOrder, _arr, hi+1, _end, _tempIndex);
}
I applied a modified quick sort...
public static void solveProblem2()
{
int[] arr1 = new int[] {1, 2, 3, -1, 4, 5};
int[] arr2 = new int[] {5, 1,-1, 3, 2, 4};
List<Integer> lResults = new ArrayList<Integer>();
Map<Integer, Integer> mOrdering = new HashMap<Integer, Integer> ();
int k = -1;
for(int j=0;j<arr2.length;j++)
{
mOrdering.put(arr2[j], j);
}
for(int j=0;j<arr1.length;j++)
{
if(arr1[j]==-1)
{
k = j;
}
}
List<Integer> lTempIndex = new ArrayList<Integer>();
lTempIndex.add(k);
modifiedQuickSort(lResults, mOrdering, arr1, 0, arr1.length-1, lTempIndex);
for(int m : lResults)
System.out.println("move car at "+m+" into empty spot...");
}
private static void modifiedQuickSort(List<Integer> _lResults, Map<Integer, Integer> _mOrder, int[] _arr, int _start, int _end, List<Integer> _tempIndex)
{
if(_start>=_end)
{
return;
}
int pivot = _arr[_start];
int lo = _start-1;
int hi = _end+1;
while(true)
{
do {
lo++;
}
while(_mOrder.get(_arr[lo])<_mOrder.get(pivot));
do {
hi--;
}
while(_mOrder.get(_arr[hi])>_mOrder.get(pivot));
if(lo>=hi)
{
break;
}
else
{
// swap (using _tempIndex as the temp swap location)
if (_arr[lo] != -1 && _arr[hi] != -1)
{
_lResults.add(lo);
_arr[_tempIndex.get(0)] = _arr[lo];
_arr[lo] = -1;
_lResults.add(hi);
_arr[lo] = _arr[hi];
_arr[hi] = -1;
_lResults.add(_tempIndex.get(0));
_arr[hi] = _arr[_tempIndex.get(0)];
_arr[_tempIndex.get(0)] = -1;
}
else if (_arr[lo] == -1)
{
_lResults.add(hi);
_arr[lo] = _arr[hi];
_arr[hi] = -1;
_tempIndex.set(0,hi);
}
else if (_arr[hi] == -1)
{
_lResults.add(lo);
_arr[hi] = _arr[lo];
_arr[lo] = -1;
_tempIndex.set(0,lo);
}
}
}
modifiedQuickSort(_lResults, _mOrder, _arr, _start, hi, _tempIndex);
modifiedQuickSort(_lResults, _mOrder, _arr, hi+1, _end, _tempIndex);
}
1. Remove all the cars at the same position between initial position and desired position
2. N as the all cars and M as after removing the cars at the same positions
- return M if -1 is not at the same position
- return M + 1 if -1 is at the same position
Details: cpluspluslearning-petert.blogspot.co.uk/2017/01/dsa-minimum-swap-to-reach-desired.html
My solution with O(n)
import java.util.*;
public class timet {
public static void moves(ArrayList<Integer> init,ArrayList<Integer> finl){
boolean no_swap = false;
for(int i=0;i<init.size();i++){
int moving_element = finl.get(i);
int indx = init.indexOf(moving_element);
int curr_empty_space = init.indexOf(-1);
if(curr_empty_space == indx){
continue;
}else{
System.out.println("Moving index "+i+" to index "+ curr_empty_space);
init = swap(init,i,curr_empty_space);
System.out.println("Moving index "+indx+" to index "+ i);
init = swap(init,indx,i);
}
}
System.out.println(init);
}
public static ArrayList<Integer> swap(ArrayList<Integer> list,int pos_a, int pos_b){
int tmp = list.get(pos_a);
list.set(pos_a,list.get(pos_b));
list.set(pos_b,tmp);
return list;
}
public static void main(String[] args){
Integer[] pos = new Integer[] {1,2,3,-1,4,5};
ArrayList<Integer> init = new ArrayList<Integer>();
ArrayList<Integer> finl = new ArrayList<Integer>();
init.addAll(Arrays.asList(pos));
pos = null;
pos = new Integer[] {5,1,-1,3,2,4};
finl.addAll(Arrays.asList(pos));
System.out.println(init);
System.out.print(finl);
moves(init,finl);
}
}
My solution with O(n)
import java.util.*;
public class timet {
public static void moves(ArrayList<Integer> init,ArrayList<Integer> finl){
boolean no_swap = false;
for(int i=0;i<init.size();i++){
int moving_element = finl.get(i);
int indx = init.indexOf(moving_element);
int curr_empty_space = init.indexOf(-1);
if(curr_empty_space == indx){
continue;
}else{
System.out.println("Moving index "+i+" to index "+ curr_empty_space);
init = swap(init,i,curr_empty_space);
System.out.println("Moving index "+indx+" to index "+ i);
init = swap(init,indx,i);
}
}
System.out.println(init);
}
public static ArrayList<Integer> swap(ArrayList<Integer> list,int pos_a, int pos_b){
int tmp = list.get(pos_a);
list.set(pos_a,list.get(pos_b));
list.set(pos_b,tmp);
return list;
}
public static void main(String[] args){
Integer[] pos = new Integer[] {1,2,3,-1,4,5};
ArrayList<Integer> init = new ArrayList<Integer>();
ArrayList<Integer> finl = new ArrayList<Integer>();
init.addAll(Arrays.asList(pos));
pos = null;
pos = new Integer[] {5,1,-1,3,2,4};
finl.addAll(Arrays.asList(pos));
System.out.println(init);
System.out.print(finl);
moves(init,finl);
}
}
def parking_arranger(order, target_order):
reverse_map = {k: i for (i, k) in enumerate(order)}
not_in_place = {i: i for i in xrange(len(order)) if order[i] != target_order[i]}
while len(not_in_place) > 0:
if reverse_map[-1] in not_in_place:
i = not_in_place.pop(reverse_map[-1])
else:
i = not_in_place.popitem()[0]
parking_swap(order, reverse_map, order[i], target_order[i])
def parking_swap(order, reverse_map, j, k):
if j == k:
return
if j == -1 or k == -1:
tmp = list(order)
order[reverse_map[j]], order[reverse_map[k]] = k, j
reverse_map[j], reverse_map[k] = reverse_map[k], reverse_map[j]
print str(tmp) + " -> " + str(order)
else:
parking_swap(order, reverse_map, j, -1)
parking_swap(order, reverse_map, -1, k)
parking_swap(order, reverse_map, j, -1)
parking_arranger([1, 2, 3, -1, 4, 5], [5, 1, -1, 3, 2, 4])
parking_arranger([-1, 1, 2, 3], [1, 2, 3, -1])
My O(n) solution in C++14
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
const int EMPTY_SPACE = 0;
unordered_map<int, int> vectorToMap(const vector<int>& v)
{
unordered_map<int, int> map;
for (int i = 0; i < v.size(); i++)
map[v[i]] = i;
return map;
}
void displayVector(const vector<int>& v)
{
for (int i : v)
cout << i << " ";
cout << endl;
}
int swapCars(vector<int> currentOrder, const vector<int>& desiredOrder)
{
unordered_map<int, int> carIndex = vectorToMap(currentOrder);
int empty = carIndex[EMPTY_SPACE],
steps = 0;
for(int i = desiredOrder.size() - 1; i >= 0; i--)
{
//if current index isn't empty and the current car isn't already in the correct position
if (desiredOrder[i] != EMPTY_SPACE && carIndex[desiredOrder[i]] != i)
{
//if we are not on the same index as empty, the current car needs to move to the empty position
//in order to make an empty space for the correct car to fill its position
if (i != empty)
{
//updates the car's location index
carIndex[currentOrder[i]] = empty;
//move the current car into the empty position
swap(currentOrder[i], currentOrder[empty]);
displayVector(currentOrder);
steps++;
}
empty = carIndex[desiredOrder[i]];
//updates the car's location index
carIndex[desiredOrder[i]] = i;
//move the correct car into the empty space
currentOrder[empty] = EMPTY_SPACE;
currentOrder[i] = desiredOrder[i];
displayVector(currentOrder);
steps++;
}
}
return steps;
}
int main(void)
{
vector<int> original = { 1, 2, EMPTY_SPACE, 3, 4, 5 };
vector<int> desired = { EMPTY_SPACE, 3, 5, 1, 2, 4 };
cout << swapCars(original, desired) << endl;
system("Pause");
return 0;
}
public static void main(String[] args) {
int[] start = {1,2,3,-1,4,5};
int[] target = {5,1,-1,3,2,4};
int n = start.length;
int index = -1;
for(int i = 0; i < n; i++){
if(start[i] == -1){
index = i;
break;
}
}
move(start, target, n, false, index);
}
//123-145, 51-1324
public static boolean move(int[] start, int[] target, int n, boolean achieved, int index){
boolean alligned = true;
for(int i = 0; i < n; i++){
if(start[i] != target[i]){
alligned = false;
break;
}
}
if(alligned)
return true;
else{
int car = target[index];
if(car == -1){
swap(start, index, 0);
System.out.print(start[index] + " ");
achieved = move(start, target, n, achieved, 0);
}else{
int carInd = -1;
for(int i = 0; i < n; i++){
if(start[i] == car){
carInd = i;
break;
}
}
swap(start, index, carInd);
System.out.print(start[index] + " ");
achieved = move(start, target, n, achieved, carInd);
}
return achieved;
}
}
public static void swap(int[] start, int i, int j){
int t = start[i];
start[i] = start[j];
start[j] = t;
}
- be.dhaval December 28, 2016void car_parking_order(vector<char> currentOrder, vector<char> desiredOrder) { unordered_map<char, int> umap; int eindex = -1; for (int i = 0; i < currentOrder.size(); i++) { // maps car to index position for current order umap.insert(make_pair(currentOrder[i], i)); if (currentOrder[i] == 'e') { eindex = i; // remember the index where empty element in current order } } for (int i = 0; i < currentOrder.size(); i++) { cout << currentOrder[i] << " "; } cout << "\n"; int numSwap = 0; for (int i = 0; i < currentOrder.size(); i++) { char desiredCar = desiredOrder[i]; if (desiredCar != currentOrder[i] && currentOrder[i] != 'e') { // if we find eindex at its desired position then first swap the current // eindex ('e') with current unordered element and update current eindex as // current position. // when we update current element we need to update umap to reflect that. if (desiredOrder[eindex] == 'e') { char temp = currentOrder[i]; currentOrder[i] = 'e'; umap[currentOrder[i]] = i; currentOrder[eindex] = temp; cout << "\n"; } // move around empty positions until empty position moves to its correct // place, get the corresponding desired element for the empty index and // look for its index in current element to swap it.. while (desiredOrder[eindex] != 'e') { char desired = desiredOrder[eindex]; // 6 int swapPos = umap[desired]; // position of 6 in current order currentOrder[swapPos] = 'e'; // position of 6 made empty umap[currentOrder[swapPos]] = swapPos; currentOrder[eindex] = desired; // position of empty made 6 umap[currentOrder[eindex]] = eindex; eindex = swapPos; for (int j = 0; j < currentOrder.size(); j++) { cout << currentOrder[j] << " "; } numSwap++; cout << "\n"; } } } cout << "number of swaps:" << numSwap << "\n"; }