Google Interview Question for Software Engineers


Country: United States




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is no solution with allowed singletons.

- Yola January 24, 2016 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Some discussion around a similar problem: [http]://www3.cs.stonybrook.edu/~rezaul/Fall-2012/CSE642/SeatSwap2.pdf

- nik October 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interesting observation and algorithm by Chao Xu.

- blckembr October 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually , the algorithm says "3" for input "CABBADDCEETK", which is correct!

- blckembr October 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

CABBADDCEETK
AABBCDDCEETK
AABBDDCCEETK
2 swap is enough, do I miss something?

- Tim October 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

AABBCDDCEETK
AABBCCDDEETK
should be 2, do I miss something?

- Tim October 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Wont work for AABCCDDEEBFFGGHI. It got 3, the actual optimum is 2.

- Anonymous October 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I guess instead of providing your code you should give the algorithm as every body preparing for an interview will know how to code. It is much easier to grasp a algorithm than a code of anybody else.

- anonymous October 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

Wont work for AABCCDBEFGGEHH. From left or right it takes 3, the actual optimum is 2.

- Anonymous October 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

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

Is '2' the right answer for "CABBADDCEETK"?

- blckembr October 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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====================================");

	}

}

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

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====================================");

	}

}

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

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====================================");

	}

}

- artak.a.petrosyan October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an impractical question to ask in an interview. Nik correctly pointed out a similar question where experts got into debate with the optimal nature of the algorithm.

- Ashish Kaila October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- miguelangel.rodel October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }
    }
}

- jiangok2006 November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- sabarish November 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
  }

- dk November 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi dk, It seems that doesn't work for: DADABCBC, you will need only two swips, but your function give you 3...

- rromero November 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- onsankawai February 28, 2016 | 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