## Google Interview Question for Interns

• 1
of 1 vote

Country: United States

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

I guess I would start with an O(n^2*p) version (n: #objects, p: #properties): compare for each pair all properties and output if at least one property equals

Alternative, one can build indexes over all objects and all properties (e.g. in a hash table). Then it's finding the sets of objects equal to a single property and union this sets for all properties. That is worst case O(p*n), but probably much better in average (depends on the number of objects that have equality)

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

``````int const P = 3;
typedef array<int, P> MyObject;

vector<unordered_map<int, list<MyObject>>> find_all_matches(vector<MyObject>& lst){
vector<unordered_map<int, list<MyObject>>> maps(P);

for(int p = 0; p < P; p++){ //for each property of my object
for(int i = 0; i<lst.size(); i++){ // for each object
if(maps[p].find(lst[i][p]) != maps[p].end()){
maps[p][lst[i][p]].push_back(lst[i]);
} else {
maps[p][lst[i][p]] = list<MyObject>{};
maps[p][lst[i][p]].push_back(lst[i]);
}
}
}

return maps;
}``````

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

First iterate through each attribute and object, while tracking the first object to have a specific attribute value. When we build out the undirected graph, future objects with the same attribute/value are given edges to connect them.

Building the graph is O(m*n).

Then iterate through the graph by vertices using a "mark and sweep strategy". Each pass through the graph uses a new unique id. These ids will find all clusters.

Finally convert the graph back into an array of clusters by iterating through the vertices and keeping an array for each found cluster id.

``````class Vertice:
obj = None
edges = None
mark = None
visited = None

def __init__(self, o):
self.obj = o
self.edges = []
self.mark = None
self.visited = False

def build_graph(obj_array, attributes):
vertices = []

for obj in obj_array:
v = Vertice(obj)
vertices.append(v)

for index, attr in enumerate(attributes):
map = {}
for v in vertices:
attr_value = v.obj[index]
if attr_value in map:
v.edges.append(map[attr_value])
map[attr_value].edges.append(v)
else:
map[attr_value] = v

for v in vertices:
mark = uuid.uuid1()
dfs(v, mark)

clusters = defaultdict(list)
for v in vertices:
clusters[v.mark].append(v.obj)

for c in clusters:
print(clusters[c])

def dfs(v, mark):
if v.visited:
return

v.visited = True
v.mark = mark
for neighbor in v.edges:
dfs(neighbor, mark)``````

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

``````import math
class car:
def __init__(self, model, engine, turbo, car_class):
self.model = model
self.engine = engine
self.turbo = turbo
self.car_class = car_class

class vector_space:
def __init__(self):
self.object_feature = []

def train(self, cars):
self.create_vector_space(cars)
self.find_similarities()

def create_vector_space(self, cars):
for car in cars:
self.object_feature.append([car.model,car.engine, car.turbo, car.car_class])

def find_similarities(self):
for vector_index1 in range(len(self.object_feature)):
for vector_index2 in range(vector_index1+1,len(self.object_feature)):
sim = self.euclidean_dist_sim(self.object_feature[vector_index1],self.object_feature[vector_index2])
print(vector_index1, vector_index2 , sim)

def euclidean_dist_sim(self, vector1, vector2):
distance = [abs(a-b)**2 for a, b in zip(vector1, vector2)]
distance = math.sqrt(sum(distance))
return distance

car1 = car(1,1,1,1)
car2 = car(1,0,1,1)
car3 = car(0,1,0,0)
car4 = car(1,0,0,0)
cars = [car1, car2, car3, car4]
vector_space = vector_space()
vector_space.train(cars)``````

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

``````import math
class car:
def __init__(self, model, engine, turbo, car_class):
self.model = model
self.engine = engine
self.turbo = turbo
self.car_class = car_class

class vector_space:
def __init__(self):
self.object_feature = []

def train(self, cars):
self.create_vector_space(cars)
self.find_similarities()

def create_vector_space(self, cars):
for car in cars:
self.object_feature.append([car.model,car.engine, car.turbo, car.car_class])

def find_similarities(self):
for vector_index1 in range(len(self.object_feature)):
for vector_index2 in range(vector_index1+1,len(self.object_feature)):
sim = self.euclidean_dist_sim(self.object_feature[vector_index1],self.object_feature[vector_index2])
print(vector_index1, vector_index2 , sim)

def euclidean_dist_sim(self, vector1, vector2):
distance = [abs(a-b)**2 for a, b in zip(vector1, vector2)]
distance = math.sqrt(sum(distance))
return distance

car1 = car(1,1,1,1)
car2 = car(1,0,1,1)
car3 = car(0,1,0,0)
car4 = car(1,0,0,0)
cars = [car1, car2, car3, car4]
vector_space = vector_space()
vector_space.train(cars)``````

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.