Coding assesment
Given a string with only values * and |, & set of starting and ending index with below rule
- 2 set of
|forms a compartment. - 1
*is an item.
Given a range, return then number of items in all the closed compartment in that range.
ex:
**||***|*|*|
index_list = [(1,9), (1,2),(7,10)]
return: [3, 0, 1]
Note: 1<=index_list.length<=10^4
I wasted my time on solving only this question. :'(
Below is my code, I believe i am doing something wrong calculation at the result.append step in the last for loop of solve method.
Feel like shit, I have google's interview scheduled after 1 month. After seeing my performance on this, I am thinking , may be i should to cancel google.
class Solution(object):
def __init__(self):
...
def solve(self, st, six, eix):
ls = len(st)
p = [[0 for _ in range(2)] for i in range(ls)]
s = [[0 for _ in range(2)] for i in range(ls)]
p[0] = [0, -1] if st[0]=="*" else [1,0]
s[0] = [0, -1] if st[-1] == "*" else [1,ls-1]
for i in range(1,ls):
if st[i] == "*":
p[i] = p[i-1][::]
else:
p[i][0] = p[i-1][0] + 1
p[i][1] = i
for i in range(ls-1-1, -1, -1):
if st[i] == "*":
s[i] = s[i+1][::]
else:
s[i][0] = s[i+1][0] + 1
s[i][1] = i
#print(p)
#print(s)
print(st)
result = []
for i in range(len(six)):
si = six[i]-1
ei = eix[i]-1
print(ei, si, p[si], p[ei],s[si], s[ei])
csi = p[ei][1]
ssi = s[si][1]-1
ts = p[ei][0]
result.append(max(0,csi-ssi-ts)))
return result
if __name__ == "__main__":
S = Solution()
s = "**|*|***|*"
six = [1,1,5,2,1,4]
eix = [3,9,8,8,5,9]
print(S.solve(s,six,eix)) update: below is the correct for loop
for i in range(len(six)):
si = six[i]-1
ei = eix[i]-1
csi = p[ei][1]
ssi = s[si][1]-1
ts = p[csi][0] - p[ssi+1][0] +1
#print(ei, si, p[si], p[ei],s[si], s[ei], csi, ssi)
print(six[i], eix[i], max(0,csi-ssi-ts))Comments (8)