vishal.gupta4081
BAN USERdef minimize_interval(a):
d = {}
for i in range(len(a)):
#print(i)
if a[i][0] in d.keys():
d[a[i][0]].append(a[i])
else:
d[a[i][0]] = [a[i]]
#print(d.keys())
sorted_keys = mergeSort(d.keys())
#print(sorted_keys)
a = []
for i in range(len(sorted_keys)):
for j in range(len(d[sorted_keys[i]])):
a.append(d[sorted_keys[i]][j])
#print(a)
interval = a[0]
for i in range(1,len(a)):
if a[i][0]==interval[1]+1:
interval[1] = a[i][1]
elif a[i][0]<interval[1] and a[i][1]>interval[1]:
interval[1] = a[i][1]
elif a[i][0] > interval[1]+1:
print(interval),
interval = a[i]
if i==len(a)-1:
print interval
a = [[4, 8], [4, 7], [3, 5], [-1, 2], [10, 12]]
minimize_interval(a)
Soln 1 (beauty of python):
a = [1,2,3]
b = [2,3,5,5]
x = int(''.join(str(digit) for digit in a))
y = int(''.join(str(digit) for digit in b))
print (map(int,list(str(x+y))))
This has limitation might cause error if length of integer is greater than max length int can hold.
Soln 2: Overcomes previous limitaion
def findsum_aslist(a,b):
carry = 0
maxiter = max([len(a),len(b)])
list_sum = []
for i in range(maxiter):
x1 = 0
x2 = 0
if i<len(a):
x1 = a[-1-i]
if i<len(b):
x2 = b[-1-i]
y = x1+x2
list_sum.append(y%10)
carry = y//10
if i==maxiter-1 and carry!=0:
list_sum.append(carry)
return list_sum
a = [1,2,3]
b = [2,3,5,5]
list_sum = findsum_aslist(a,b)
print('['),
print(','.join(str(list_sum[-1-i]) for i in range(len(list_sum)))),
print(']')
Minimal Coding.
def find_duplicate(x):
index = -1
for i in range(len(x)):
if x[abs(x[i])] > 0:
x[abs(x[i])] = -1*x[abs(x[i])]
else:
index = i
return index
x = [2,1,2,4,3]
print (find_duplicate(x))
DP Approach
from pythonds.basic import Stack
def maxSum_NStack(stacks,M):
database = []
#sum = 0
for i in range(M):
toPop = 0
for j in range(1,len(stacks)):
if stacks[j].peek()>stacks[toPop].peek():
toPop = j
if i==0:
database.append(stacks[toPop].pop())
else:
database.append(database[-1] + stacks[toPop].pop())
return(database[-1])
x = [
[1, 8, 100, 3],
[2000, 2, 3, 1],
[10, 1, 4]
]
stacks = []
for i in range(len(x)):
stacks.append(Stack())
for j in range(len(x[i])):
stacks[i].push(x[i][j])
print(maxSum_NStack(stacks,5))
Simplest of all
def match_pattern(pattern,inputStr):
d = {}
pattern = pattern.split(' ')
inputStr = inputStr.split(' ')
match = True
for i in range(len(pattern)):
if pattern[i] not in d.keys():
d[pattern[i]] = inputStr[i]
else:
if d[pattern[i]] != inputStr[i]:
match = False
break
return match
pattern = 'a b b a'
inputStr = 'cat dog dog mat'
print(match_pattern(pattern,inputStr))
Using DP
import math
def find_max_fit(points):
#Using DP
database = [['x']*5 for count in range(len(points))]
#print database
count = 0
for i in range(len(points)):
slope_count = {}
for j in range(len(points)):
if i!=j and database[i][j]=='x' and database[j][i]=='x':
#print(str(i)+','+str(j))
database[i][j] = slope(points[i],points[j])
database[j][i] = database[i][j]
#print(str(database[j][i]))
if database[i][j] in slope_count.keys():
slope_count[database[i][j]] = slope_count[database[i][j]] + 1
else:
slope_count[database[i][j]] = 2
if i!=j:
local_count = max(slope_count.values())
if local_count>count:
count = local_count
#print database
return count
def slope(x,y):
if float(y[0]-x[0]) == 0:
return 90.0
else:
return math.degrees(math.atan2((float(y[1]-x[1])),(float(y[0]-x[0]))))
points = [[5,5], [2,2], [3,3], [3,4], [1,1]]
print(find_max_fit(points))
Recursive as well as iterative Solution:
def findChunkPalindrome(s):
print s
if len(s) < 1:
return 1
count = 0
start = 0
end = len(s)-1
while(1):
if s[0:start+1] != s[end:]:
start = start+1
end = end-1
if start>=end:
count = 1
break
else:
#print('start = '+str(start)+'|end = '+str(end))
count = count+2+findChunkPalindrome(s[start+1:end])
break
return count
def findChunkPalindrome2(s):
count = 0
while(len(s)>=1):
start = 0
end = len(s)-1
#print(s)
if len(s)==1:
count = count+1
s = ''
else:
for i in range(len(s)/2+1):
#print(i)
if s[0:start+i+1] == s[end-i:]:
count = count+2
s = s[start+i+1:end-i]
#print(s)
break
elif (start+i+1)>=(end-i):
s = ''
count = count+1
break
return count
s = 'ghiabcdehelloadamhelloabcdeghi'
#s = 'volvo'
print(findChunkPalindrome(s))
print(findChunkPalindrome2(s))
Solution Using Graph(since no loops, so essentially, its a tree) and DFS:
from pythonds.graphs import Graph, Vertex
def buildGraph(D):
org = Graph()
for key in D.keys():
f = key
for i in range(len(D[key])):
#print(f+'->'+D[key][i])
org.addEdge(f,D[key][i],1)
#print(list(org.getVertex(f).getConnections()))
return org
def print_org(g,u,offset):
#dfs
u = g.getVertex(u)
u.setColor('gray')
space = ' '*offset
print(space+'-'+u.id)
nbrs = list(u.getConnections())
#print(nbrs)
#print(':'+str(len(nbrs))+'employee')
if len(nbrs)==0:
pass
#print('-None')
else:
i = 0
while i<len(nbrs):
print_org(g,nbrs[i].id,offset+1)
i = i+1
u.setColor('black')
return
def main():
D = {
'AAA':['CCC','BBB','EEE'],
'CCC':['DDD']
}
root = 'AAA'
offset = 0
org = buildGraph(D)
print_org(org,root,offset)
if __name__=='__main__':
main()
- vishal.gupta4081 December 19, 2016