Google Interview Question
Software EngineersCountry: United States
Some discussion around a similar problem: [http]://www3.cs.stonybrook.edu/~rezaul/Fall-2012/CSE642/SeatSwap2.pdf
Go left to right once and see how many swaps it takes to fix it.
Go right to left and see how many swaps it takes to fix it.
Return min of the two swap values
Taking a stab at it. Attempted to use some memoization to reduce any redoing the same work
#include <iostream>
#include <string>
#include <climits>
#include <map>
#include <vector>
#include <utility>
using namespace std;
string swapout(string str, pair<int, int> swap) {
char temp = str[swap.first];
str[swap.first] = str[swap.second];
str[swap.second] = temp;
return str;
}
void find_swaps(string couples, map<char, int>& counts, vector<pair<int, int>>* swaps) {
map<char, int> elems;
int first_idx = -1;
int second_idx = -1;
for(int i = 0; i<couples.length(); ++i) {
if(counts[couples[i]] == 2) {
if(couples[i+1] == couples[i]) {
i++;
} else {
first_idx = i;
for(int j = i+2; j<couples.length(); ++j) {
if(couples[j] == couples[i]) {
second_idx = j;
break;
}
}
if(first_idx!=0) swaps->push_back(make_pair(first_idx-1, second_idx));
swaps->push_back(make_pair(first_idx, second_idx-1));
swaps->push_back(make_pair(first_idx+1, second_idx));
if(second_idx != couples.length()-1) swaps->push_back(make_pair(first_idx, second_idx+1));
break;
}
}
}
}
void min_swaps_rec(string couples, map<char, int>& counts, map<string, int>& min_swaps, int count, int* min) {
if(min_swaps.find(couples) != min_swaps.end()) {\
int newcount = min_swaps[couples]+count;
if(newcount < *min) *min = newcount;
return;
}
vector<pair<int, int>> swaps;
find_swaps(couples, counts, &swaps);
if (swaps.size() == 0){
if(count < *min) *min = count;
return;
}
int q = INT_MAX;
if(count+1 < *min){
for (pair<int,int> swap : swaps) {
min_swaps_rec(swapout(couples, swap), counts, min_swaps, count+1, min);
}
}
}
int min_swaps(string couples) {
map<string, int> min_swaps;
map<char, int> counts;
for(int i = 0; i<couples.length(); ++i) {
counts[couples[i]]++;
}
int min = INT_MAX;
min_swaps_rec(couples, counts, min_swaps, 0, &min);
return min;
}
int main()
{
string couples = "CAABBC";
cout<<min_swaps(couples);
}
import java.util.ArrayList;
import java.util.HashMap;
public class SwapCounter {
HashMap<Character, Pair> pairs = new HashMap<>();
public int countSwaps(char[] input) {
int swaps = 0;
pairs.clear();
// Finding pairs
for (int i = 0; i < input.length; i++) {
Character c = input[i];
Pair p;
if (pairs.containsKey(c)) {
p = pairs.get(c);
p.pos1 = i;
} else {
p = new Pair(input[i]);
p.pos0 = i;
pairs.put(c, p);
}
}
ArrayList<Character> keys = new ArrayList<Character>(pairs.keySet());
// Removing not paired characters
for (Character c : keys) {
Pair p = pairs.get(c);
if (!p.isPair()) {
pairs.remove(c);
}
}
// End of pars finding
// Simple swap cases
for (Character c : pairs.keySet()) {
Pair p = pairs.get(c);
if (p.isNexEachOther())
continue;
int[] swapPositions = new int[4];
swapPositions[0] = p.pos0 - 1;
swapPositions[1] = p.pos0 + 1;
swapPositions[2] = p.pos1 - 1;
swapPositions[3] = p.pos1 + 1;
Character[] swapCandidate = new Character[4];
swapCandidate[0] = (swapPositions[0] > 0) ? input[swapPositions[0]] : null;
swapCandidate[1] = (swapPositions[1] < input.length) ? input[swapPositions[1]] : null;
swapCandidate[2] = (swapPositions[2] > 0) ? input[swapPositions[2]] : null;
swapCandidate[3] = (swapPositions[3] < input.length) ? input[swapPositions[3]] : null;
boolean simpleSwapPossible = false;
int simpleSwapPos = -1;
for (int i = 0; i < swapCandidate.length; i++) {
Character candidate = swapCandidate[i];
if (candidate != null) {
if (pairs.containsKey(candidate)) {
Pair candidatePair = pairs.get(candidate);
if (p.isSwapable(candidatePair)) {
p.swap(candidatePair, input);
swaps++;
continue;
}
} else {
simpleSwapPossible = true;
simpleSwapPos = swapPositions[i];
}
}
}
if (simpleSwapPossible) {
swaps++;
p.swap(simpleSwapPos, input, pairs);
continue;
}
}
// Complex multi-step cases
for (Character c : pairs.keySet()) {
Pair p = pairs.get(c);
if (p.isNexEachOther())
continue;
swaps += countComplexSwaps(p, input);
}
return swaps;
}
private int countComplexSwaps(Pair p, char[] input) {
int swaps = 0;
int[] swapPositions = new int[4];
Character[] swapCandidate = new Character[4];
int shift = 2;
int shorterSwapPos = -1;
while (shift < Math.abs(p.pos0 - p.pos1)) {
swapPositions[0] = p.pos0 - shift;
swapPositions[1] = p.pos0 + shift;
swapPositions[2] = p.pos1 - shift;
swapPositions[3] = p.pos1 + shift;
swapCandidate[0] = (swapPositions[0] > 0) ? input[swapPositions[0]] : null;
swapCandidate[1] = (swapPositions[1] < input.length) ? input[swapPositions[1]] : null;
swapCandidate[2] = (swapPositions[2] > 0) ? input[swapPositions[2]] : null;
swapCandidate[3] = (swapPositions[3] < input.length) ? input[swapPositions[3]] : null;
for (int i = 0; i < swapCandidate.length; i++) {
Character candidate = swapCandidate[i];
if (candidate != null) {
if (pairs.containsKey(candidate)) {
Pair candidatePair = pairs.get(candidate);
if (!candidatePair.isNexEachOther()) {
shorterSwapPos = swapPositions[i];
}
}
} else {
if (swapPositions[i] >= 0 && swapPositions[i] < input.length) {
shorterSwapPos = swapPositions[i];
}
}
}
if (shorterSwapPos >= 0) {
return p.swapWithAllBeetwinPairs(shorterSwapPos, input, pairs);
}
shift += 2;
}
return p.swapWithAllBeetwinPairs(-1, input, pairs);
}
public class Pair {
char c;
public int pos0 = -1;
public int pos1 = -1;
public Pair(char chr) {
c = chr;
}
public boolean isPair() {
return (pos1 >= 0 && pos0 >= 0);
}
public boolean isNexEachOther() {
if (isPair()) {
return Math.abs(pos0 - pos1) == 1;
}
return false;
}
public boolean isSwapable(Pair other) {
return (Math.abs(pos0 - other.pos0) == 1 && Math.abs(pos1 - other.pos1) == 1)
|| (Math.abs(pos0 - other.pos1) == 1 && Math.abs(pos1 - other.pos0) == 1);
}
public int swapWithAllBeetwinPairs(int pos, char[] arr, HashMap<Character, Pair> otherPairs) {
int swaps = 0;
if (pos >= 0) {
if (Math.abs(pos - pos0) < Math.abs(pos - pos1)) {
int step = (pos - pos0) > 0 ? 2 : -2;
while (Math.abs(pos - pos0) > 1) {
swap(pos0 + step, arr, otherPairs);
swaps++;
}
char swapChar = arr[pos];
arr[pos1] = swapChar;
pos1 = pos;
swaps++;
} else {
int step = (pos - pos1) > 0 ? 2 : -2;
while (Math.abs(pos - pos1) > 1) {
swap(pos1 + step, arr, otherPairs);
swaps++;
}
char swapChar = arr[pos];
arr[pos0] = swapChar;
pos0 = pos;
swaps++;
}
} else {
if (pos0 < pos1) {
while (Math.abs(pos0 - pos1) > 1) {
swapPos1(pos1 - 2, arr, otherPairs);
swaps++;
}
} else {
while (Math.abs(pos0 - pos1) > 1) {
swapPos1(pos0 - 2, arr, otherPairs);
swaps++;
}
}
}
if (!isNexEachOther()) {
}
return swaps;
}
public void swap(Pair other, char[] arr) {
if (!isSwapable(other))
throw new IllegalArgumentException("Pairs must be swappable");
if (Math.abs(pos0 - other.pos0) == 1) {
int pos = pos1;
pos1 = other.pos0;
other.pos0 = pos;
} else if (Math.abs(pos1 - other.pos1) == 1) {
int pos = pos0;
pos0 = other.pos1;
other.pos1 = pos;
} else if (Math.abs(pos0 - other.pos1) == 1) {
int pos = pos1;
pos1 = other.pos1;
other.pos1 = pos;
} else if (Math.abs(pos1 - other.pos0) == 1) {
int pos = pos0;
pos0 = other.pos0;
other.pos0 = pos;
}
arr[pos0] = c;
arr[pos1] = c;
arr[other.pos0] = other.c;
arr[other.pos1] = other.c;
}
public void swap(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
if (Math.abs(pos0 - swapPos) == 1) {
swapPos1(swapPos, arr, otherPairs);
} else {
swapPos0(swapPos, arr, otherPairs);
}
}
public void swapPos0(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsValue(swapChar)) {
p = otherPairs.get(swapChar);
}
otherPairs.get(swapChar);
arr[pos0] = swapChar;
int swappedPos = pos0;
pos0 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
public void swapPos1(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsValue(swapChar)) {
p = otherPairs.get(swapChar);
}
otherPairs.get(swapChar);
arr[pos1] = swapChar;
int swappedPos = pos1;
pos1 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
}
public static void main(String[] args) {
SwapCounter swapCnt = new SwapCounter();
String inpStr = "AABCCDBEFGGEHH";
// String inpStr = "caabbddc";
char[] input = inpStr.toCharArray();
int result = swapCnt.countSwaps(input);
System.out.println(" Input: " + inpStr);
System.out.println(" Result: " + new String(input) + " swaps:" + result);
System.out.println("\n====================================");
}
}
import java.util.ArrayList;
import java.util.HashMap;
public class SwapCounter {
HashMap<Character, Pair> pairs = new HashMap<>();
public int countSwaps(char[] input) {
int swaps = 0;
pairs.clear();
// Finding pairs
for (int i = 0; i < input.length; i++) {
Character c = input[i];
Pair p;
if (pairs.containsKey(c)) {
p = pairs.get(c);
p.pos1 = i;
} else {
p = new Pair(input[i]);
p.pos0 = i;
pairs.put(c, p);
}
}
ArrayList<Character> keys = new ArrayList<Character>(pairs.keySet());
// Removing not paired characters
for (Character c : keys) {
Pair p = pairs.get(c);
if (!p.isPair()) {
pairs.remove(c);
}
}
// End of pars finding
// Simple swap cases
for (Character c : pairs.keySet()) {
Pair p = pairs.get(c);
if (p.isNexEachOther())
continue;
int[] swapPositions = new int[4];
swapPositions[0] = p.pos0 - 1;
swapPositions[1] = p.pos0 + 1;
swapPositions[2] = p.pos1 - 1;
swapPositions[3] = p.pos1 + 1;
Character[] swapCandidate = new Character[4];
swapCandidate[0] = (swapPositions[0] > 0) ? input[swapPositions[0]] : null;
swapCandidate[1] = (swapPositions[1] < input.length) ? input[swapPositions[1]] : null;
swapCandidate[2] = (swapPositions[2] > 0) ? input[swapPositions[2]] : null;
swapCandidate[3] = (swapPositions[3] < input.length) ? input[swapPositions[3]] : null;
boolean simpleSwapPossible = false;
int simpleSwapPos = -1;
for (int i = 0; i < swapCandidate.length; i++) {
Character candidate = swapCandidate[i];
if (candidate != null) {
if (pairs.containsKey(candidate)) {
Pair candidatePair = pairs.get(candidate);
if (p.isSwapable(candidatePair)) {
p.swap(candidatePair, input);
swaps++;
continue;
}
} else {
simpleSwapPossible = true;
simpleSwapPos = swapPositions[i];
}
}
}
if (simpleSwapPossible) {
swaps++;
p.swap(simpleSwapPos, input, pairs);
continue;
}
}
// Complex multi-step cases
for (Character c : pairs.keySet()) {
Pair p = pairs.get(c);
if (p.isNexEachOther())
continue;
swaps += countComplexSwaps(p, input);
}
return swaps;
}
private int countComplexSwaps(Pair p, char[] input) {
int swaps = 0;
int[] swapPositions = new int[4];
Character[] swapCandidate = new Character[4];
int shift = 2;
int shorterSwapPos = -1;
while (shift < Math.abs(p.pos0 - p.pos1)) {
swapPositions[0] = p.pos0 - shift;
swapPositions[1] = p.pos0 + shift;
swapPositions[2] = p.pos1 - shift;
swapPositions[3] = p.pos1 + shift;
swapCandidate[0] = (swapPositions[0] > 0) ? input[swapPositions[0]] : null;
swapCandidate[1] = (swapPositions[1] < input.length) ? input[swapPositions[1]] : null;
swapCandidate[2] = (swapPositions[2] > 0) ? input[swapPositions[2]] : null;
swapCandidate[3] = (swapPositions[3] < input.length) ? input[swapPositions[3]] : null;
for (int i = 0; i < swapCandidate.length; i++) {
Character candidate = swapCandidate[i];
if (candidate != null) {
if (pairs.containsKey(candidate)) {
Pair candidatePair = pairs.get(candidate);
if (!candidatePair.isNexEachOther()) {
shorterSwapPos = swapPositions[i];
}
}
} else {
if (swapPositions[i] >= 0 && swapPositions[i] < input.length) {
shorterSwapPos = swapPositions[i];
}
}
}
if (shorterSwapPos >= 0) {
return p.swapWithAllBeetwinPairs(shorterSwapPos, input, pairs);
}
shift += 2;
}
return p.swapWithAllBeetwinPairs(-1, input, pairs);
}
public class Pair {
char c;
public int pos0 = -1;
public int pos1 = -1;
public Pair(char chr) {
c = chr;
}
public boolean isPair() {
return (pos1 >= 0 && pos0 >= 0);
}
public boolean isNexEachOther() {
if (isPair()) {
return Math.abs(pos0 - pos1) == 1;
}
return false;
}
public boolean isSwapable(Pair other) {
return (Math.abs(pos0 - other.pos0) == 1 && Math.abs(pos1 - other.pos1) == 1)
|| (Math.abs(pos0 - other.pos1) == 1 && Math.abs(pos1 - other.pos0) == 1);
}
public int swapWithAllBeetwinPairs(int pos, char[] arr, HashMap<Character, Pair> otherPairs) {
int swaps = 0;
if (pos >= 0) {
if (Math.abs(pos - pos0) < Math.abs(pos - pos1)) {
int step = (pos - pos0) > 0 ? 2 : -2;
while (Math.abs(pos - pos0) > 1) {
swap(pos0 + step, arr, otherPairs);
swaps++;
}
char swapChar = arr[pos];
arr[pos1] = swapChar;
pos1 = pos;
swaps++;
} else {
int step = (pos - pos1) > 0 ? 2 : -2;
while (Math.abs(pos - pos1) > 1) {
swap(pos1 + step, arr, otherPairs);
swaps++;
}
char swapChar = arr[pos];
arr[pos0] = swapChar;
pos0 = pos;
swaps++;
}
} else {
if (pos0 < pos1) {
while (Math.abs(pos0 - pos1) > 1) {
swapPos1(pos1 - 2, arr, otherPairs);
swaps++;
}
} else {
while (Math.abs(pos0 - pos1) > 1) {
swapPos1(pos0 - 2, arr, otherPairs);
swaps++;
}
}
}
if (!isNexEachOther()) {
}
return swaps;
}
public void swap(Pair other, char[] arr) {
if (!isSwapable(other))
throw new IllegalArgumentException("Pairs must be swappable");
if (Math.abs(pos0 - other.pos0) == 1) {
int pos = pos1;
pos1 = other.pos0;
other.pos0 = pos;
} else if (Math.abs(pos1 - other.pos1) == 1) {
int pos = pos0;
pos0 = other.pos1;
other.pos1 = pos;
} else if (Math.abs(pos0 - other.pos1) == 1) {
int pos = pos1;
pos1 = other.pos1;
other.pos1 = pos;
} else if (Math.abs(pos1 - other.pos0) == 1) {
int pos = pos0;
pos0 = other.pos0;
other.pos0 = pos;
}
arr[pos0] = c;
arr[pos1] = c;
arr[other.pos0] = other.c;
arr[other.pos1] = other.c;
}
public void swap(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
if (Math.abs(pos0 - swapPos) == 1) {
swapPos1(swapPos, arr, otherPairs);
} else {
swapPos0(swapPos, arr, otherPairs);
}
}
public void swapPos0(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsValue(swapChar)) {
p = otherPairs.get(swapChar);
}
otherPairs.get(swapChar);
arr[pos0] = swapChar;
int swappedPos = pos0;
pos0 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
public void swapPos1(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsValue(swapChar)) {
p = otherPairs.get(swapChar);
}
otherPairs.get(swapChar);
arr[pos1] = swapChar;
int swappedPos = pos1;
pos1 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
}
public static void main(String[] args) {
SwapCounter swapCnt = new SwapCounter();
String inpStr = "AABCCDBEFGGEHH";
// String inpStr = "caabbddc";
char[] input = inpStr.toCharArray();
int result = swapCnt.countSwaps(input);
System.out.println(" Input: " + inpStr);
System.out.println(" Result: " + new String(input) + " swaps:" + result);
System.out.println("\n====================================");
}
}
Brut force implementation:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class SwapCounter2 {
HashMap<Character, Pair> original_pairs = new HashMap<>();
HashMap<Character, Pair> pairs = new HashMap<>();
char[] original_placement;
char[] best_placement;
int minSwaps;
public int countSwaps(char[] input) {
original_placement = Arrays.copyOf(input, input.length);
minSwaps = -1;
original_pairs.clear();
// Finding pairs
for (int i = 0; i < input.length; i++) {
Character c = input[i];
Pair p;
if (original_pairs.containsKey(c)) {
p = original_pairs.get(c);
p.pos1 = i;
} else {
p = new Pair(input[i]);
p.pos0 = i;
original_pairs.put(c, p);
}
}
ArrayList<Character> keys = new ArrayList<Character>(original_pairs.keySet());
// Removing not paired characters and building inp str
StringBuilder sb = new StringBuilder();
for (Character c : keys) {
sb.append(c);
Pair p = original_pairs.get(c);
if (!p.isPair()) {
original_pairs.remove(c);
}
}
String allChars = sb.toString();
generateAndCheck("", allChars, allChars.length());
for (int i = 0; i < input.length; i++) {
input[i] = best_placement[i];
}
return minSwaps;
}
private void cloneOriginalPairs() {
pairs.clear();
for (Character c : original_pairs.keySet()) {
Pair p = original_pairs.get(c).clonePair();
pairs.put(p.c, p);
}
}
private void checkPlacement(String str) {
cloneOriginalPairs();
char[] candidatePalcement = new char[original_placement.length];
char[] strChars = str.toCharArray();
int j = 0;
for (int i = 0; i < strChars.length; i++) {
candidatePalcement[j] = strChars[i];
if (original_pairs.containsKey(strChars[i])) {
j++;
candidatePalcement[j] = strChars[i];
}
j++;
}
char[] input_clone = Arrays.copyOf(original_placement, original_placement.length);
Pair p = getNotNextPair();
int swaps = 0;
while (p != null) {
swap(p, input_clone, candidatePalcement);
swaps++;
if (minSwaps >= 0 && swaps > minSwaps)
return;
p = getNotNextPair();
}
minSwaps = swaps;
best_placement = candidatePalcement;
}
private void swap(Pair p, char[] current, char[] placement) {
for (int i = 0; i < placement.length; i++) {
if (placement[i] == p.c && (i != p.pos0 && i != p.pos1)) {
p.swap(i, current, pairs);
return;
}
}
}
private void generateAndCheck(String str, String input, int length) {
if (str.length() == length) {
checkPlacement(str);
} else
for (int i = 0; i < input.length(); i++)
generateAndCheck(str + input.charAt(i), input.substring(0, i) + input.substring(i + 1), length);
}
private Pair getNotNextPair() {
for (Character c : pairs.keySet()) {
Pair p = pairs.get(c);
if (p.isNexEachOther())
continue;
return p;
}
return null;
}
public class Pair {
char c;
public int pos0 = -1;
public int pos1 = -1;
public Pair(char chr) {
c = chr;
}
public boolean isPair() {
return (pos1 >= 0 && pos0 >= 0);
}
public boolean isNexEachOther() {
if (isPair()) {
return Math.abs(pos0 - pos1) == 1;
}
return false;
}
public Pair clonePair() {
Pair p = new Pair(this.c);
p.pos0 = this.pos0;
p.pos1 = this.pos1;
return p;
}
/*
* public boolean isSwapable(Pair other) { return (Math.abs(pos0 -
* other.pos0) == 1 && Math.abs(pos1 - other.pos1) == 1) ||
* (Math.abs(pos0 - other.pos1) == 1 && Math.abs(pos1 - other.pos0) ==
* 1); }
*/
public void swap(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
if (Math.abs(pos0 - swapPos) == 1) {
swapPos1(swapPos, arr, otherPairs);
} else {
swapPos0(swapPos, arr, otherPairs);
}
}
public void swapPos0(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsKey(swapChar)) {
p = otherPairs.get(swapChar);
}
arr[pos0] = swapChar;
int swappedPos = pos0;
pos0 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
public void swapPos1(int swapPos, char[] arr, HashMap<Character, Pair> otherPairs) {
char swapChar = arr[swapPos];
Pair p = null;
if (otherPairs.containsKey(swapChar)) {
p = otherPairs.get(swapChar);
}
arr[pos1] = swapChar;
int swappedPos = pos1;
pos1 = swapPos;
arr[swapPos] = c;
if (p != null) {
if (p.pos0 == swapPos) {
p.pos0 = swappedPos;
} else {
p.pos1 = swappedPos;
}
}
}
}
public static void main(String[] args) {
SwapCounter2 swapCnt = new SwapCounter2();
String inpStr = "CABEABEDDC";
// String inpStr = "CABABDDC";
// String inpStr = "CABBAC";
// String inpStr = "AABCCDBEFGGEHH";
// String inpStr = "caabbddc";
char[] input = inpStr.toCharArray();
int result = swapCnt.countSwaps(input);
System.out.println(" Input: " + inpStr);
System.out.println(" Result: " + new String(input) + " swaps:" + result);
System.out.println("\n====================================");
}
}
Okey, here we go
So the idea is to "sit couples together".... That requiere comparing sits of couples and generating some expensive calculations in special cases (such as where couples are separated by a single space and require to be cascade-reacomodated in order to be all couples together) so....... I think this problem can be "re-focused", if we approach as "sitting the I.T. guys between couples"... so, the algorithm will be something like:
public static void reacomodation() {
int i;
char myCandidate2; // my candidate belong to a couple
char myCandidate1; // my candidate are alone
String myPeople = "AABHCCDEFFGBH" // original people
String myPeople = "AABHCCdeFFgBH" // people where LowerCase are single guys
for (i=1; i<=myPeople.length; i++) { // cycle to re-acomodate single people
if (myPeople[i].isUpper)
if (myPeople[i-1].isUpper && myPeople[i+1].isUpper) myCandidate2=i;
if (myPeople[i].isLower) {
myCandidate1=i;
swap(myCandidate1, myCandidate2);
}
}
for (i=1; i<=myPeople.length; i++) { // cycle to join together couples
// in the case there are Uppers alone, try to join together them.
}
}
Hoping your replys
This problem can be solved using BFS (the worst case O(n^2)). Below is the java code which has been tested with above inputs.
import java.util.*;
import java.util.concurrent.atomic.AtomicReference;
public class GG_SwapSeats {
int swapSeats(String s)
{
Queue<String> queue = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
ArrayList<Character> singles = new ArrayList<>();
ArrayList<Character> couples = new ArrayList<>();
for(int i=0; i<s.length(); ++i)
{
if(singles.contains(s.charAt(i)))
{
couples.add(s.charAt(i));
singles.remove(new Character(s.charAt(i)));
}
else singles.add(new Character(s.charAt(i)));
}
if(couples.size()==0) return 0;
queue.add(s);
visited.add(s);
int level = 0;
Integer c1;
c1=1;
AtomicReference<Integer> c2 = new AtomicReference<>(0);
while(queue.size()>0)
{
String s1 = queue.poll();
boolean isValid = true;
HashMap<Character, ArrayList<Integer>> charMap = new HashMap<>();
ArrayList<Character> separatedCouples = new ArrayList<>();
for(int i=0; i<s1.length(); ++i)
{
if(charMap.containsKey(s1.charAt(i))) {
ArrayList<Integer> list = charMap.get(s1.charAt(i));
list.add(i);
if(Math.abs(list.get(0)-list.get(1))>1) {
isValid = false;
separatedCouples.add(s1.charAt(i));
}
}
else {
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
charMap.put(s1.charAt(i), list);
}
}
if(isValid)
break;
for(int i=0; i<separatedCouples.size(); ++i) {
ArrayList<Integer> list = charMap.get(separatedCouples.get(i));
if (list.get(0) > 0)
addToQueue(s1, list.get(0) - 1, list.get(1), c2, visited, queue);
if (list.get(0) < s1.length() - 1)
addToQueue(s1, list.get(0) + 1, list.get(1), c2, visited, queue);
if (list.get(1) > 0)
addToQueue(s1, list.get(1) - 1, list.get(0), c2, visited, queue);
if (list.get(1) < s1.length() - 1)
addToQueue(s1, list.get(1) + 1, list.get(0), c2, visited, queue);
// must consider the singles
for (int j = 0; j < singles.size(); ++j) {
addToQueue(s1, charMap.get(singles.get(j)).get(0), list.get(0), c2, visited, queue);
addToQueue(s1, charMap.get(singles.get(j)).get(0), list.get(1), c2, visited, queue);
}
if (--c1 == 0) {
c1 = c2.get();
c2.set(0);
level++;
}
}
}
return level;
}
void addToQueue(String s,
int x,
int y,
AtomicReference<Integer> childCount,
HashSet<String> visited,
Queue<String> queue)
{
char[] arr = s.toCharArray();
Util.exchange(arr, x, y);
String child = new String(arr);
if (!visited.contains(child)) {
queue.add(child);
visited.add(child);
childCount.set(childCount.get() + 1);
}
}
}
My solution is,
1. Run through each character, if there is another character matching just in the next position, Mark it.
2. Run through the modified string now, which contain the single guys, Put them in the hashmap with count as 1.
Whenever we find another single guy already in the Hashmap, remove the element from Hashmap and increment the swaps.
Brief pseudocode:
public static int numSwaps(String str)
{
char[] chars=str.toCharArray();
int numSwaps=0;
HashMap<Integer,Integer> singleGuys=new HashMap<>();
for(int i=0;i<chars.length-1;i++)
{
//Take a unique char, I take 'X' as the unique char
if(chars[i]!='X'&&chars[i]==chars[i+1])
{
chars[i]='X',chars[i+1]='X';
}
}
for(int i=0;i<chars.length;i++)
{
if(chars[i]!='X')
{
Object val=singleGuys.get(chars[i]);
if(Object==null)
{
singleGuys.put(chars[i],1);
}
else
{
numSwaps++;
singleGuys.remove(chars[i]);
}
}
}
return numSwaps;
}
The problem can be solved in linear time given that we only need to return number of swaps required and don't need to the swaps using this code
public static int minimalSwaps(String seating) {
Set<Character> singles = new HashSet<>();
Character previous = seating.charAt(0);
int adjustment = 0;
for(int i = 1; i < seating.length(); i++) {
if(seating.charAt(i) != previous) {
if(!singles.add(seating.charAt(i))) {
adjustment++;
singles.remove(seating.charAt(i)); //check for twins ;)
}
previous = seating.charAt(i);
}
}
return adjustment;
}
I think I have got the idea:
Observation:
Scan the seats from left to right, if you have found a person P who is not single and is not sitting with his/her counterpart Q
1. If one of P's neighbor or Q's neighbor is a single, swapping P or Q with the single man never hurt the optimality - add only 1 swap
2. If swapping the man sitting on right side of P (who is also sitting with his counterpart) does not break them, swap him with Q. i.e. the case ABBA, swapping the first B with the second A does not break the BB couples - add only 1 swap
3. Find 2 single men sitting together and do 2 swaps with them, this also never hurt the optimality since all other ways would require to break at least one couple in this case, ending up using at least 2 swaps to fix that in total - add only 2 swaps
4. As the last resort, greedily swaps the person sitting on the right side of P with Q(which breaks the couples) - at least 2 swaps, can be more
The idea is not too complex and the code can be a bit long, this method passes the following testcases:
AABCCDDEEBFFGGHI - 2 swaps
CABBADDCEETK - 2 swaps
AABCCDBFHGGFEE - 2 swaps
I wonder what the interviewer had in mind when he asked this question. This is a question where Skeina got in argument with other algorithmic experts (see Nik's link). And for people who pasted pages of code above: "your code is garbage if you don't explain it first to others".
- ashish.kaila October 10, 2015