## Google Interview Question for SDE1s

Country: United States

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

Clarify.
I just have to pair socks of same color right ?
Problem can be reduced to sorting of array containing 0 and 1.

Then do another parse through the sorted array. With start index and end index. Start pairing start and end. Stop when pairing is not possible.

We may need to keep another array with the indexes of the socks

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

Because, if the question is: is it possible to pair them (Put all the white sockets in the bucket#1 and all the black sockets in the bucket#2)? Then:
- if the number of socks is not paired {number} % 2 != 0 - then the answer is immediately False.
- if the number is paired - we need to go through the list of the socks (could be both directional iteration) and put the socks on 2 different buckets. Once the number of socks (black or white) becomes bigger than half of all the socks - the answer is False.
- if the balancing of both lists works - then we will end the iteration with the balanced number of socks in both buckets.

If we need to differentiate by "left" and "right" for each color - then the flow is different.

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

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

Works for any number of sock colors. O(N) time, O(K) space, where K is number of colors:

``````#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

enum Sock {
black = 0,
white = 1
};

vector<pair<Sock, Sock>> Pair(vector<Sock> const &a)
{
vector<pair<Sock, Sock>> out;
unordered_set<Sock, hash<int>> part1;
for (auto &s : a) {
if (part1.find(s) != part1.end()) {
out.push_back(pair<Sock, Sock>(s, s));
part1.erase(s);
} else {
part1.insert(s);
}
}
cout << (part1.empty() ? "all paired\n" : "not all paired\n");
return out;
}

int main()
{
vector<pair<Sock, Sock>> pairs = Pair({black, white, white, black, white, black, white, black});
for (auto &p : pairs) {
cout << p.first << ", " << p.second << "\n";
}
}``````

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.