adr
BAN USER- 5of 5 votes
AnswersDesign a voting system. 100M users will be logging in within a window of 24h (not necessarily uniformly). Every user will be able to choose from a fixed list of options. If the user has already voted the system should not let them to vote a second time. Additional constraint: only the first 100K votes are accepted. If the quota is exceeded any attempt to vote should be rejected.
- adr in United States| Report Duplicate | Flag | PURGE
Software Engineer System Design - 0of 0 votes
AnswersYou are standing in the top-left corner of n*m grid. At each step you can only move up, down, right or left. Count the number of unique paths to the bottom-right corner of the grid (paths cannot cross themselves). The interviewer suggested that a backtracking solution is not the most performant one.
- adr| Report Duplicate | Flag | PURGE
Software Engineer
If one can fit the entire map in memory, then union-find is an overkill
import random
n,m=3,4
grid=[[random.choice("XO") for _ in xrange(m)] for _ in xrange(n)]
def numIslands(grid):
count = 0
for p in xrange(n*m):
r,c = p/m,p%m
if grid[r][c] == 'X':
count += 1
l = [p]
while l:
p = l.pop()
for z in filter(lambda z: 0<=z<n*m
and grid[z/m][z%m] == 'X'
and abs(z/m-p/m)*abs(z%m-p%m)<2,
[p-1,p+1,p-m,p+m]):
grid[z/m][z%m] = 'V'
l += [z]
return count
for v in grid:
print v
print numIslands(grid)
Recursive:
def topoSort(ts):
r,g,v = ([[]],{},set())
for [a,b] in ts:
g.update({a: g.get(a, []) + [b]})
def go(k):
if k not in v:
for m in g.get(k, []):
go(m)
v.add(k)
r[0] += [k]
for k in g.keys():
go(k)
return r[0][::-1]
print topoSort(["AB", "CE", "CD", "DE", "AC", "BC"])
Iterative:
def topoSort(ts):
r,g,v = ([],{},set())
for [a,b] in ts:
g.update({a: g.get(a, []) + [b]})
for k in g.keys():
st = [(k, g.get(k, []))]
while st:
(k,ms) = st.pop()
if k not in v:
if ms:
st += [(k, ms[1:])]
st += [(ms[0], g.get(k, []))]
else:
v.add(k)
r += [k]
return r[::-1]
print topoSort(["AB", "CE", "CD", "DE", "AC", "BC"])
If the generator string has the property that no two prefix and suffix substrings share a common prefix (e.g. "ab" in the description has this property wheras "aba" does not) then the problem has a simple O(n) solution:
def isValid(s, g):
if not g:
return False
(st, gi) = ([], 0)
for c in s:
if c == g[gi]:
gi += 1
if gi == len(g):
gi = st.pop() if st else 0
elif c == g[0]:
st += [gi]
gi = 1
else:
return False
return not st and gi == 0
print isValid("abcababccabc", "abc")
O(n) solution, uses O(2**k) memory.
def foo(s, k):
if len(s) < k + 2**k - 1:
return False
(count, v) = (2**k-1, [0]*2**k)
q = reduce(lambda a,b:2*a+b, s[:k], 0)
v[q] = 1
z = 2**(k-1)
for si in xrange(len(s)-k):
q = (q-s[si]*z)*2+s[si+k]
if v[q] == 0:
v[q] = 1
count -= 1
if count == 0:
return True
return False
print foo([1, 0, 0, 1, 1], 2)
BFS solution:
import random
(n, m) = (10, 15)
(mx,s) = ([random.randint(0, 9) for _ in xrange(n*m)], random.randint(1, 50))
(v,l,r) = ([0]*m*n, [[[0], mx[0]]], [])
while l:
nl = []
for [p, ps] in l:
if ps == s:
r = p
break
if ps < s:
pp = p[-1]
for np in [pp + d for d in [-1, 1, -m, m]
if 0<=pp+d<n*m and abs((pp+d)%m - pp%m)<2 and v[pp+d] == 0]:
v[np] = 1
nl += [[p + [np], ps + mx[np]]]
l = nl
def printm(mx):
print ""
for i in xrange(n):
print '[' + ' '.join(map(str, mx[i*m:i*m+m])) + ']'
print "target =", s
printm(mx)
if r:
printm([1 if i in r else 0 for i in xrange(n*m)])
Output:
target = 34
[9 1 1 6 9 1 4 8 5 3 2 5 9 4 4]
[7 1 6 6 3 6 9 3 3 7 0 9 3 0 1]
[9 2 6 7 3 7 0 7 8 1 6 7 0 7 5]
[0 3 3 3 4 2 9 4 8 5 4 5 0 9 0]
[4 3 1 4 4 4 5 0 6 9 5 7 8 7 5]
[4 7 1 4 6 5 4 0 1 9 0 1 8 6 0]
[6 8 5 9 7 8 3 6 7 5 5 1 0 4 4]
[1 6 2 9 8 2 5 9 7 4 9 9 7 5 5]
[9 1 9 9 0 9 5 6 4 9 4 4 9 9 9]
[4 1 5 3 1 5 9 0 2 4 1 2 8 4 3]
[1 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
import random
(n, m, bcount) = (5, 10, 4)
(pos, bpos) = (random.randint(0, n*m-1), set(random.sample(xrange(n*m), bcount)))
(l, visited) = (set([pos]), set())
(r, steps) = (bpos.intersection(l), 0)
while l and not r:
steps += 1
l = set([p + d for p in l for d in [-1, 1, -m, +m]
if 0<=p+d<n*m and abs(p%m - (p+d)%m)<2 and p+d not in visited])
visited.update(l)
r = bpos.intersection(l)
bmap = ['*' if i == pos else 'X' if i in r else 'x' if i in bpos else ' ' for i in xrange(n*m)]
for i in xrange(n):
print "|" + ''.join(bmap[i*m:i*m+m]) + "|"
print "distance =", steps
Output:
|x * |
| x X |
| |
| x |
| |
distance = 2
I assume by infinitely large you mean an array that does not fit in memory otherwise your program will never terminate obviously. If that's the case this sounds like a simple problem
* Create k files (k - number of tags)
* Read the input array by blocks that fit in memory
* If an element in the block has tag i add it to i-th file
* When you are done processing the array, just traverse your files in order
We just need to maintain k largest elements seen so far. We can use a min-heap for this:
* Load the huge array by blocks that fit in memory
* If a number in the block is greater or equal to the min element in the heap or if the heap is empty, add it to the heap and remove the min element if the number of elements in the heap became k+1
* When we are done processing the array, the min element in the heap is the result
Under these assumptions I would do this:
* Create a bit array of 2**32 bits (only 512MB required).
* Load the huge array by blocks that fit in memory
* If a number in the block has been seen before (bit corresponding to this number is set), output it as a duplicate, otherwise set the bit.
O(n*n*m), uses O(m) memory
from operator import add, sub
import random
def maxseq (s, k):
first = i = cost = 0
r = [0,[0,0]]
def update():
if r[0] < i-first:
r[0] = i-first
r[1] = [first, i]
while i < len(s):
if s[i] + cost <= k:
cost += s[i]
i += 1
else:
update()
cost -= s[first]
first += 1
update()
return r[1]
def maxrect(v, k):
first = 0
end = len(v)
r = [0,[0,0,0,0]]
def update (beg, end, arr):
[b, e] = maxseq (arr, k)
a = (e-b)*(end-beg)
if r[0] < a:
r[0] = a
r[1] = [beg, end, b, e]
return e - b
while first < end:
arr = v[first]
ub = (end - first) * len(arr)
for j in xrange (first, end):
if r[0] < ub:
ub = (end - first) * update(first, j+1, arr)
if j+1 != end:
arr = map(add, arr, v[j+1])
arr = map(sub, arr, v[first])
first += 1
for j in reversed(xrange(first, end)):
if r[0] < (j-first+1)*len(arr):
update(first, j+1, arr)
if first != j:
arr = map(sub, arr, v[j])
first += 1
return r
random.seed(42)
k = random.randint(1, 42)
n = 10
m = 15
v = [[random.randint(1, 7) for _ in range(m)] for _ in range(n)]
for vv in v:
print vv
print k
[a, r] = maxrect(v, k)
for i in xrange(r[0], r[1]):
print v[i][r[2]:r[3]]
import string
import math
import operator
alph = string.ascii_lowercase
primes = [x for x in range(2, 100) if all(x % y != 0 for y in range(2, int(math.ceil(math.log10(x)))))]
foo = lambda str: reduce(operator.mul, map(lambda x: primes[x], map(lambda x: alph.index(x), str)), 1)
def bar(dict, xdict, str, n):
for p in [str[n:z:] for z in range(n, len(str)+1)]:
x = foo(p)
if (x in xdict):
r = [dict[xdict.index(x)]]
if (n + len(p) != len(str)):
rs = bar(dict, xdict, str, n + len(p))
if (len(rs) != 0):
return r+rs
else:
return r
return []
def unscramble(dict, str):
xdict = map(foo, dict)
return (" ".join(bar(dict, xdict, str, 0)))
d = ['llo', 'hell', 'ocrazyworl', 'ld', 'crazyw', 'ell', 'llocra', 'azyworl', 'll', 'razywo', 'ocr', 'zywo', 'ocrazyw', 'ywor', 'azywo', 'llocrazyworl', 'razywor', 'ellocr', 'yw', 'zyworl', 'lloc', 'ellocrazyw', 'h', 'l', 'cra', 'ywo', 'el', 'llocrazywo', 'ocrazywo', 'crazywo', 'hellocra', 'zy', 'cr', 'ocrazy', 'azyw', 'locraz', 'wor', 'ra', 'rl', 'llocrazy', 'hellocraz', 'razyworl', 'llocr', 'wo', 'ocra', 'ellocrazy', 'orl', 'llocrazywor', 'llocraz', 'razy', 'c', 'ocraz', 'hellocrazy', 'llocrazyw', 'oc', 'o', 'hellocrazyw', 'w', 'lo', 'or', 'hellocrazywo', 'hellocr', 'locrazyworl', 'loc', 'elloc', 'craz', 'hel', 'locrazy', 'hellocrazywor', 'locrazywo', 'locrazyw', 'crazyworl', 'he', 'locr', 'ellocraz', 'worl', 'azy', 'r', 'z', 'crazy', 'helloc', 'azywor', 'ellocrazyworl', 'az', 'raz', 'locrazywor', 'crazywor', 'zywor', 'hellocrazyworl', 'ellocra', 'ellocrazywo', 'ello', 'ocrazywor', 'a', 'locra', 'razyw', 'yworl', 'e', 'ellocrazywor', 'zyw', 'y', 'hello']
str = "hellocrazyworld"
assert(unscramble(d, str) == "h e l l o c r a z y w o r ld")
def match(s, p):
n = len(s)
m = len(p)
ms = [[False] * (m + 1) for _ in xrange(n + 1)]
ms[0][0] = True
for j in xrange(1, m+1):
ms[0][j] = ms[0][j-1] and p[j-1] in ['*', '+']
for i in xrange(1, n+1):
for j in xrange(1, m+1):
if p[j-1] == '*':
ms[i][j] = ms[i][j-1] or ms[i-1][j]
elif p[j-1] == '+':
ms[i][j] = ms[i][j-1] or ms[i-1][j-1]
else:
ms[i][j] = p[j-1] == s[i-1] and ms[i-1][j-1]
return ms[n][m]
Repjohnsantana9ytt9, Backend Developer at Accolite software
I am working as a Support service manager at Pro Star Garden Management . I had a different experience while working ...
Rephuslafenena, Backend Developer at Absolute Softech Ltd
I am working as a Teletype operator at Midwest TV & Appliance . It's been almost ten years since I've ...
Repathenajbarnarda, Android Engineer at ABC TECH SUPPORT
I am a graduate in Civil Engineering with nearly 7 years of experience in planning and implementing technical solutions for ...
RepSaanviJones, abc at 8x8
I am working as an office worker in a softage company. I am responsible for an office assistant position in ...
RepLicholsLowry, Associate at AMD
I am Lichols, I am an outreach worker in Desmonds Formal Wear company .I specialise in a variety of different ...
Repericsumm059, Backend Developer at ASU
My name is EricSummey . I am working as a Sound engineering technician at Foreman & Clark . as a sound technician it ...
RepEileenWenda, DIGITAL MARKETING at Accenture
I am Eileen , a football Referee skilled at maintaining a safe environment for both players and observers, inspecting the playing ...
Repwoodscarla116, Associate at ASAPInfosystemsPvtLtd
I am a nurse . My name is CarlaWoods . I am working as a Clinical social worker. I met many people ...
Reprginiarist, DIGITAL MARKETING at Accenture
I am Rginia Credentialing Specialists ensure that medical staff members' maintain current credentials and licenses to work legally in their ...
Repvickidsmithv, Android Engineer at 247quickbookshelp
Hello, I am a Managing editor. I have completed my studies from New York. Apart from this, whenever I am ...
Quickselect. No extra space needed. O(n) expected time, O(n*n) worst case time
O(n) extra space if mutating the input is not allowed:
- adr June 26, 2018