## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

``````from z3 import *

N=10

M =  'x........x'
M += '.xxxxx.xxx'
M += '.xxxx..xxx'
M += '.xxx..x..x'
M += '.xx.x.xxx.'
M += '.x...xx...'
M += '...xxxxx..'
M += '.xx.x.xx..'
M += '.xx.x...x.'
M += 'xxxx.....x'

cells = [Int('cell_%d' % i) for i in range(N)]

def overlaps(i,j):
return M[i*N + j] == 'x'

s = Optimize()

for i in range(N):
for j in range(i+1, N):
s.add(Or(overlaps(i,j) == False, cells[i] + cells[j] <= 1))

s.maximize(Sum(cells))

if s.check() == sat:
res = [x for x in cells if s.model()[x] == 1]
print (len(res))
print (res)``````

Output:

``````5
[cell_0, cell_3, cell_5, cell_7, cell_8]``````

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

If you need to compute a maximal subset where adding a new tower forces the subset to have an overlap with it then this is a Maximal Independent Set (MIS) problem. If on the other hand you need to compute a largest such subset then this is a Maximum Independent Subset problem (MaxIS).

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.