constt
BAN USER
Comments (4)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
def isvalid(s):
"""Check if the expression given in string 's' is a valid arithmetic
expression.
Eg: (())())  Invalid expression, (()())  Valid expression
>>> isvalid('(())())')
False
>>> isvalid('(()())')
True
"""
if not s:
return 0
ps = [] # stack of parentheses
for c in s:
if c in '()':
if ps and ps[1] == '(' and c == ')':
ps.pop()
else:
ps.append(c)
return len(ps) == 0
if __name__ == '__main__':
import doctest
doctest.testmod()

constt
October 24, 2015 Comment hidden because of low score. Click to expand.
0
of 0 vote
def minpar(s):
"""Given a string s of parentheses (ex: '(()'), return the minimum number of
parentheses that need to be inserted to make it into a well formed
(balanced) string. Time complexity O(n).
>>> minpar('')
0
>>> minpar(')')
1
>>> minpar('(((s)')
2
>>> minpar(')a(b(c)(')
3
>>> minpar(')a)b)c)')
4
"""
if not s:
return 0
ps = [] # stack of parentheses
for c in s:
if c in '()':
if ps and ps[1] == '(' and c == ')':
ps.pop()
else:
ps.append(c)
return len(ps)
if __name__ == '__main__':
import doctest
doctest.testmod()

constt
October 23, 2015 Comment hidden because of low score. Click to expand.
0
of 0 vote
def rmsubrange(rs):
"""Given an array of 'array ranges' (rs), return an optimized array by
deleting subarrays. Time complexity O(n*log(n)).
NOTE: Array range (2,6) represents (2,3,4,5,6)
>>> rmsubrange([(2, 6), (3, 5), (20, 21), (7, 21)])
[(2, 6), (7, 21)]
>>> rmsubrange([(10, 13), (1, 8), (2, 6), (15, 18), (12, 18)])
[(1, 8), (10, 13), (12, 18)]
"""
if not rs or len(rs) == 1:
return rs
rs.sort(key=lambda x: x[0])
rs_opt = []
for i in range(len(rs)  1):
if rs[i]:
if not (rs[i][0] >= rs[i+1][0] and rs[i][1] <= rs[i+1][1]):
rs_opt.append(rs[i])
if rs[i+1][1] < rs[i][1]:
rs[i+1] = None
return rs_opt
if __name__ == '__main__':
import doctest
doctest.testmod()

constt
October 23, 2015 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
 constt October 24, 2015