## Google Interview Question for SDE1s

Country: United States

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

The problem can be viewed as a graph problem. "Given the graph, determine if the graph is bipartite". In other words, is it possible to color the graph using two colors such that no nodes with the same color are connected? Proposed solution assumes that the graph is connected:

(i) using the pairs, construct a graph G
(ii) chose any node as a source node
(iii) starting from the source node, perform BFS, at each step, color the neighbors, toggle the color. If a neighbor is already colored with different color, the graph is not bipartite, return None
(iv) group nodes by color and return two sets

``````class Bipartite:

def __init__(self, G):
self.G = G
self.st = {}

def test(self, src):
if (self._is_bipartite(src)):   return self._split()
else:                           return None

def _is_bipartite(self, src):
q = deque()
q.append(src)           # enqueue source

color = 0               # initial color label
while not q.empty():
curr = q.pop()
if st.has_key(curr):
continue        # skip node
self.st[curr] = color

for node in G.neighbours(curr):
if not st.has_key(node):
q.append(node)
else if self.st[node] == color:
return False
color = color^1     # toggle color label

return True

def _split(self):
A = set()
B = set()
for node in st.keys():
return A,B``````

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

``````import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

public class SplitRelations {
static class Node{
int val;
Set<Node> set;
int tag;
Node(int val){
this.val = val;
set = new HashSet<Node>();
tag = -1;
}
}

static void ProcessRelationList(int[][] relationList, HashSet<Node> set0, HashSet<Node> set1) throws Exception{
HashMap<Integer, Node> map  = new HashMap<Integer, Node>();

for (int i=0; i< relationList.length; i++){
int rel1 = relationList[i][0];
int rel2 = relationList[i][1];
if (!map.containsKey(rel1)){
map.put(rel1, new Node(rel1));
}
if (!map.containsKey(rel2)){
map.put(rel2, new Node(rel2));
}
Node node1 = map.get(rel1);
Node node2 = map.get(rel2);
}

Integer[] keyArr = map.keySet().toArray(new Integer[map.size()]);
map.get(keyArr[0]).tag = 0;

while(!q.isEmpty()){
Node node = q.remove();
int childTag = (node.tag+1)%2;
if (node.tag == 0){
}else if (node.tag == 1){
}
for (Node child: node.set){
child.set.remove(node);
if (child.tag == -1){
child.tag = childTag;
}else if (child.tag!= childTag){
throw new Exception("Parent " + node.val + "'s Child " + child.val + " is in " + child.tag + " Retrying in :" + childTag);
}
}
node.set.clear();
}
}

static void PrintSet(HashSet<Node> set1,HashSet<Node> set2){
Node[] arr1 = set1.toArray(new Node[set1.size()]);
Node[] arr2 = set2.toArray(new Node[set2.size()]);
System.out.print("Set1 : ");
for (int i=0; i< arr1.length; i++){
System.out.print(arr1[i].val + ((i==arr1.length-1)?(""):(", ")));
}
System.out.print("   Set2 : ");
for (int i=0; i< arr2.length; i++){
System.out.print(arr2[i].val + ((i==arr2.length-1)?(""):(", ")));
}
System.out.println();
}

public static void main(String[] args){
HashSet<Node> set1 = new HashSet<Node>();
HashSet<Node> set2 = new HashSet<Node>();
int[][] relationList;

set1.clear();
set2.clear();
relationList = new int[][] {{1,2}, {2,3}, {3,4}};
try {
ProcessRelationList(relationList, set1, set2);
PrintSet(set1, set2);
} catch (Exception e) {
System.out.println("Exception : " + e.getMessage());
}

set1.clear();
set2.clear();
relationList = new int[][] {{1,2}, {1,3}, {2,3}, {3,4}};
try {
ProcessRelationList(relationList, set1, set2);
PrintSet(set1, set2);
} catch (Exception e) {
System.out.println("Exception : " + e.getMessage());
}
}
}``````

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

yeah it's a problem of bipartite graph :)

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

yeah it's a problem to check ,given graph is bipartite or not !!

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

``````bool split(vector<pair<int, int>> rel)
{
map<int,node*> myset;

for (auto r : rel)
{
if (myset.find(r.first) != myset.end())
{
node* t = myset[r.first];
t->friends.push_back(r.second);
if (myset.find(r.second) != myset.end())
{
t = myset[r.second];
t->friends.push_back(r.first);
}
else
{
t = new node(r.second);
myset[r.second] = t;
t->friends.push_back(r.first);
}
}
else
{
node* t = new node(r.first);
t->friends.push_back(r.second);
myset[r.first] = t;
if (myset.find(r.second) != myset.end())
{
t = myset[r.second];
t->friends.push_back(r.first);
}
else
{
t = new node(r.second);
myset[r.second] = t;
t->friends.push_back(r.first);
}
}
}

int color = 1;
for (auto item : myset)
{
for (auto f : item.second->friends)
{
if (myset[f]->color == 0)
myset[f]->color=color;
else
if (myset[f]->color != color)
return false;
myset[f]->color = color;
}
color = color == 1 ? 2 : 1;
}
return true;
}``````

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

Check whether the graph is bipartite. A simple solution using dfs. (1 and -1 are used for colors)

``````public static class Graph {
int n;
int[] colors;

public Graph(int n) {
this.n = n;
colors = new int[n];
for (int i=0; i<n; i++) {
}
}

public void addEdge(int u, int v) {
}

public boolean isGroupingPossible(int root, int color) {
if (colors[root] == 0) colors[root] = color;
else if (colors[root]!=color) {
return false;
} else {
return true;
}

for (Integer child : adjList[root]) {
if (!isGroupingPossible(child, color*-1)) return false;
}
return true;
}

}``````

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

``````package google;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class SplitUsersIntoGroups {
public static void main(String args[]) {
int[][] friendRelations = { { 1, 2 }, { 2, 3 }, { 3, 4 } };

HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();

for (int i = 0; i < friendRelations.length; i++) {

checkAndPut(friendRelations[i][0], friendRelations[i][1], map);
checkAndPut(friendRelations[i][1], friendRelations[i][0], map);
}

HashSet<Integer> visited = new HashSet<Integer>();

boolean result = true;
for (int cur : map.keySet()) {

if (!visited.contains(cur)) {
HashSet<Integer> group1 = new HashSet<Integer>();
HashSet<Integer> group2 = new HashSet<Integer>();
boolean curGrp1 = true;
result = result && recurseFindGroupable(group1, group2, curGrp1, cur, map);
}

}

System.out.println(result);

}

private static boolean recurseFindGroupable(HashSet<Integer> group1, HashSet<Integer> group2, boolean curGrp1,
int cur, HashMap<Integer, ArrayList<Integer>> map) {
HashSet<Integer> curSet = curGrp1 ? group1 : group2;
HashSet<Integer> otherSet = curGrp1 ? group2 : group1;
boolean result = true;
if (curSet.contains(cur)) {
return true;
} else if (otherSet.contains(cur)) {
return false;
} else {
}
for (int user : map.get(cur)) {
result = result && recurseFindGroupable(group1, group2, !curGrp1, user, map);
}
return result;
}

public static void checkAndPut(int first, int second, HashMap<Integer, ArrayList<Integer>> map) {
if (map.containsKey(first)) {
} else {
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(first, list);
}
}
}``````

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

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

using namespace std;

class Node
{
public:
vector<Node*> to_nodes_;
};

bool IsConnectedComponentBipartite(Node* start_node, unordered_set<Node*>& seen)
{
unordered_map<Node*, bool> part;
queue<Node*> q;
q.push(start_node);
part[start_node] = true;
while (!q.empty())
{
Node* n = q.front();
q.pop();
if (seen.find(n) == seen.end())
{
seen.insert(n);
bool p = part[n];
for (Node* to_node : n->to_nodes_)
{
auto it = part.find(to_node);
if (it != part.end())
{
if (it->second != !p)
{
return false;
}
}
else
{
part[to_node] = !p;
}
q.push(to_node);
}
}
}
return true;
}

bool IsBipartite(const vector<Node*>& nodes)
{
unordered_set<Node*> seen;
for (Node* n : nodes)
{
if (seen.find(n) == seen.end())
{
if (!IsConnectedComponentBipartite(n, seen))
{
return false;
}
}
}
return true;
}

int main()
{
Node n1, n2, n3, n4;
vector<Node*> graph = {&n1, &n2, &n3, &n4};

n1.to_nodes_.push_back(&n2);
n2.to_nodes_.push_back(&n1);

n2.to_nodes_.push_back(&n3);
n3.to_nodes_.push_back(&n2);

n3.to_nodes_.push_back(&n4);
n4.to_nodes_.push_back(&n3);

cout << IsBipartite(graph) << "\n";

n3.to_nodes_.push_back(&n1);
n1.to_nodes_.push_back(&n3);

cout << IsBipartite(graph) << "\n";

return 0;
}``````

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.