## Google Interview Question for SDE1s

• 0

Country: United States

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

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void Print(vector<int> const &a)
{
for (int i = 0; i + 1 < a.size(); i += 2) {
cout << "[" << a[i] << ", " << a[i + 1] << "] ";
}
cout << "\n";
}

int CountRec(vector<int> &a, unordered_map<int, int> &seat, unordered_map<int, int> &partner,
unordered_map<int, int> &swaps, unordered_map<string, int> &memo, int idx = 0)
{
if (idx < 0 ||
idx > a.size())
{
return -1;
}
if (idx == a.size()) {
Print(a);
return 0;
}

string memo_key;
for (int i = idx; i < a.size(); ++i) {
memo_key += to_string(a[i]) + "\t" + to_string(swaps[a[i]]) + "\n";
}
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}

if (partner[a[idx]] == a[idx + 1]) {
return CountRec(a, seat, partner, swaps, memo, idx + 2);
}

int min_count = numeric_limits<int>::max();
vector<int> idxes = {idx, idx + 1};
for (int i : idxes) {
int j = seat[partner[a[i == idx ? idx + 1 : idx]]];
if (swaps[a[i]] < 2 &&
swaps[a[j]] < 2)
{
swap(a[i], a[j]);
swap(seat[a[i]], seat[a[j]]);
++swaps[a[i]];
++swaps[a[j]];
int count = CountRec(a, seat, partner, swaps, memo, idx + 2);
if (count != -1) {
count++;
min_count = min(min_count, count);
}
--swaps[a[i]];
--swaps[a[j]];
swap(seat[a[i]], seat[a[j]]);
swap(a[i], a[j]);
}
}
if (min_count == numeric_limits<int>::max()) {
min_count = -1;
}
memo[memo_key] = min_count;
return min_count;
}

int Count(vector<int> a) {
if (a.size() % 2) {
return -1;
}

unordered_map<int, int> seat;
for (int i = 0; i < a.size(); ++i) {
seat[a[i]] = i;
}

unordered_map<int, int> partner;
for (int i = 0; i < a.size(); i += 2) {
partner[i] = i + 1;
partner[i + 1] = i;
}

unordered_map<int, int> swaps;
unordered_map<string, int> memo;
return CountRec(a, seat, partner, swaps, memo);
}

void Shuffle(vector<int> &a)
{
for (int i = 0; i < a.size(); ++i) {
swap(a[i], a[i + (rand() % (a.size() - i))]);
}
}

int main()
{
srand(time(NULL));
int size = 10 * 2;
vector<int> a;
while (a.size() < size) {
a.push_back(a.size());
}
Shuffle(a);
Print(a);
cout << Count(a) << "\n";
}``````

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

Java Code

``````import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
private static int counter = 0;
private static Scanner inp;
public static int  findIndex (int[] array, int t) {
if (array == null) return -1;
int len = array.length;
int i = 0;
while (i < len) {
if (array[i] == t) return i;
else i++;
}
return -1;
}

public static void main(String[] args) {
inp = new Scanner(System.in);
int n = inp.nextInt();// Total pair
int m = 2 * n;// Total number
int[] mapping = new int[2 * n];// array of random sittings
for (int i = 0; i < 2 * n; i++) {
mapping[i] = inp.nextInt();
}
HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
for (int i = 0; i < m; i += 2) {
pairs.put(mapping[i], mapping[i + 1]);
}
for (int i = 0; i < m; i += 2) {
rpairs.put(mapping[i + 1], mapping[i]);
}

int[] arr = new int[m];// array of random sittings
for (int i = 0; i < m; i++) {
arr[i] = inp.nextInt();
}
for (int i = 0; i < m; i += 2) {
if (pairs.containsKey(arr[i])) {
if (arr[i + 1] != pairs.get(arr[i])) {
int ind = findIndex(arr, pairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
} else {
if (arr[i + 1] != rpairs.get(arr[i])) {
int ind = findIndex(arr, rpairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
}
}
System.out.println(counter);
}
}``````

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

Java Code

``````import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
private static int counter = 0;
private static Scanner inp;
public static int  findIndex (int[] array, int t) {
if (array == null) return -1;
int len = array.length;
int i = 0;
while (i < len) {
if (array[i] == t) return i;
else i++;
}
return -1;
}

public static void main(String[] args) {
inp = new Scanner(System.in);
int n = inp.nextInt();// Total pair
int m = 2 * n;// Total number
int[] mapping = new int[2 * n];// array of random sittings
for (int i = 0; i < 2 * n; i++) {
mapping[i] = inp.nextInt();
}
HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
for (int i = 0; i < m; i += 2) {
pairs.put(mapping[i], mapping[i + 1]);
}
for (int i = 0; i < m; i += 2) {
rpairs.put(mapping[i + 1], mapping[i]);
}

int[] arr = new int[m];// array of random sittings
for (int i = 0; i < m; i++) {
arr[i] = inp.nextInt();
}
for (int i = 0; i < m; i += 2) {
if (pairs.containsKey(arr[i])) {
if (arr[i + 1] != pairs.get(arr[i])) {
int ind = findIndex(arr, pairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
} else {
if (arr[i + 1] != rpairs.get(arr[i])) {
int ind = findIndex(arr, rpairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
}
}
System.out.println(counter);
}``````

}

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

``````import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
private static int counter = 0;
private static Scanner inp;
public static int  findIndex (int[] array, int t) {
if (array == null) return -1;
int len = array.length;
int i = 0;
while (i < len) {
if (array[i] == t) return i;
else i++;
}
return -1;
}

public static void main(String[] args) {
inp = new Scanner(System.in);
int n = inp.nextInt();// Total pair
int m = 2 * n;// Total number
int[] mapping = new int[2 * n];// array of random sittings
for (int i = 0; i < 2 * n; i++) {
mapping[i] = inp.nextInt();
}
HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
for (int i = 0; i < m; i += 2) {
pairs.put(mapping[i], mapping[i + 1]);
}
for (int i = 0; i < m; i += 2) {
rpairs.put(mapping[i + 1], mapping[i]);
}

int[] arr = new int[m];// array of random sittings
for (int i = 0; i < m; i++) {
arr[i] = inp.nextInt();
}
for (int i = 0; i < m; i += 2) {
if (pairs.containsKey(arr[i])) {
if (arr[i + 1] != pairs.get(arr[i])) {
int ind = findIndex(arr, pairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
} else {
if (arr[i + 1] != rpairs.get(arr[i])) {
int ind = findIndex(arr, rpairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
}
}
System.out.println(counter);
}``````

}

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

``````import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
private static int counter = 0;
private static Scanner inp;
public static int  findIndex (int[] array, int t) {
if (array == null) return -1;
int len = array.length;
int i = 0;
while (i < len) {
if (array[i] == t) return i;
else i++;
}
return -1;
}

public static void main(String[] args) {
inp = new Scanner(System.in);
int n = inp.nextInt();// Total pair
int m = 2 * n;// Total number
int[] mapping = new int[2 * n];// array of random sittings
for (int i = 0; i < 2 * n; i++) {
mapping[i] = inp.nextInt();
}
HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
for (int i = 0; i < m; i += 2) {
pairs.put(mapping[i], mapping[i + 1]);
}
for (int i = 0; i < m; i += 2) {
rpairs.put(mapping[i + 1], mapping[i]);
}

int[] arr = new int[m];// array of random sittings
for (int i = 0; i < m; i++) {
arr[i] = inp.nextInt();
}
for (int i = 0; i < m; i += 2) {
if (pairs.containsKey(arr[i])) {
if (arr[i + 1] != pairs.get(arr[i])) {
int ind = findIndex(arr, pairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
} else {
if (arr[i + 1] != rpairs.get(arr[i])) {
int ind = findIndex(arr, rpairs.get(arr[i]));
int temp = arr[i + 1];
arr[i + 1] = arr[ind];
arr[ind] = temp;
counter++;
}
}
}
System.out.println(counter);
}
}``````

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

``````static int countSwaps(int[][] seats) {
int n = seats.length;
HashMap<Integer, Integer> unmatches = new HashMap<>();
for (int i = 0; i < n; ++i) {
if (seats[i][0] == seats[i][1]) {
continue;
}

unmatches.put(seats[i][0], seats[i][1]);
}

int count = 0;
while (!unmatches.isEmpty()) {
int l1, r1, l2, r2;
l1 = unmatches.keySet().iterator().next();
r1 = unmatches.get(l1);
l2 = r1;
r2 = unmatches.get(l2);

unmatches.put(l1, r2);
unmatches.put(l2, r1);
++count;

unmatches.remove(l2);

if (l1 == r2) {
unmatches.remove(l1);
}
}

return count;
}``````

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.

### 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.