light
BAN USER
Comments (5)
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
we maintain an auxiliary array that holds the result upto a given value. rest is straight forward, very simple code
#!/usr/bin/python
def noncons(lst):
n=len(lst)
res=[0]*(n+2)
for i in range(n):
l,r=res[i]+lst[i],res[i+1]
res[i+2]=max(l,r)
return res[n+1]
if __name__=='__main__':
lst=[1,2,3,4,5,6]
print noncons(lst)

light
January 31, 2013 Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
#!/usr/bin/python
def permute(s,cur,pos,n):
#prints all permutation of a given string O(n*n!)
#assuming unique characters present it prints the lexicographicunique sequence
#but it fails to print unique sequence if there are repeating characters
global visited
if pos==n:
print ''.join(cur)
return
for i in range(n):
if not visited[i]:
cur[pos]=s[i]
visited[i]=True
permute(s,cur,pos+1,n)
visited[i]=False
def permutations(s): #solution to the above problem
#prints all unique permutation of a given string in lexicographic order TIME:O(n*n!)
n=len(s)
def next():
k,l=1,1
for i in range(n1):
if s[i]<s[i+1]: k=i
if k==1: return None
for i in range(k+1,n):
if s[k]<s[i]: l=i
cur=list(s[k:])
cur[0],cur[lk]=cur[lk],cur[0]
return s[:k]+'%c%s'%(cur[0],''.join(cur[:0:1]))
while s:
print s
s=next()
if __name__=='__main__':
s='aabcd'
n=len(s)
#visited=[False]*n
#permute(s,[0]*n,0,n)
permutations(s)

light
January 31, 2013 Comment hidden because of low score. Click to expand.
0
of 0 vote
#!/usr/bin/python
def partition(cur,pos,m,n):
#prints all unique partitions of a number (lexicographic order)
if n==0:
print cur[:pos]
return
for i in range(m,n+1):
cur[pos]=i
partition(cur,pos+1,i,ni)
def apart(cur,pos,n): #this solves the given question
#prints all paritions of a number (no order)
if n==0:
print cur[:pos]
return
for i in range(1,n+1):
cur[pos]=i
apart(cur,pos+1,ni)
if __name__=='__main__':
n=5
#partition([0]*n,0,1,n)
apart([0]*n,0,n)

light
January 31, 2013 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
found one small bug in the code!
 light February 23, 2013updated = splits[0].strip()+' ('+splits[1].strip()+')'
is the correct update and not
updated = splits[0].strip()+' '+splits[1].strip()