fahmida.hamid
BAN USER- 2of 2 votes
AnswersDefine a function that can detect whether the characters of a string can be shuffled without repeating same characters as one other's neighbors. E.g. :
- fahmida.hamid in United States
apple >> alpep, so valid
a >> a, valid
aa >> aa, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.
You do not have to find one representation, just have to detect if it is possible or not!| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm
I have done both approaches:
Say, we have a n X m matrix
1. row-wise: converting row to decimal value and then compare it with prev. max => O(n + m)
2. col-wise: for each column, find the rows that have 1's for that specific col. intersect it with the previously found one (prev. col means a col with higher order). I guess, the complexity is O(m * n)
import math
def bin2Dec(xs):
xl = len(xs)
sum = 0
for i,v in enumerate(xs):
if v == 1:
sum += math.pow(2, xl-1-i)
return sum
def maxRow(xss):
local_max = 0
max_row = -1
for r,xs in enumerate(xss):
local_sum = bin2Dec(xs)
if local_sum > local_max:
local_max = local_sum
max_row = r
print(max_row)
def maxByCols(xss):
rL = len(xss)
cL = len(xss[0])
max_row = -1
upperLayer = set()
lowerLayer = set()
for c in range(cL):
lowerLayer = set()
for r in range(rL):
if xss[r][c] == 1:
lowerLayer.add(r)
if len(upperLayer) == 0:
upperLayer = lowerLayer
else:
z = upperLayer.intersection(lowerLayer)
if len(z):
upperLayer = z
print(upperLayer)
a = [[1,1 ,0,0],[0,1,1,0],[1,1,1,1],[1,0,1,1],[1,1,1,0]]
maxRow(a)
maxByCols(a)
Both of them works!!!
- fahmida.hamid February 24, 2016Easy Linear Solution using Python Dictionary Concept:
class LetterList:
def __init__(self, aList):
self.letterDict = self.buildLetterDict(aList)
def buildLetterDict(self, aList):
bDict = dict()
for a in aList:
if a in bDict.keys():
bDict[a] += 1
else:
bDict[a] = 1
return bDict
def isPossible(self, b):
bList = list(b)
bTempDict = self.buildLetterDict(bList)
#print(b)
#print(bTempDict)
for b in bTempDict.keys():
if b not in self.letterDict.keys():
return False
elif bTempDict[b] > self.letterDict[b]:
return False
return True
def findAllPossible(self, bList):
largestW = 0
pList = set()
for b in bList:
if self.isPossible(b):
pList.add(b)
if len(b) > largestW:
largestW = len(b)
print('Largest Possible Word-Length ::', largestW )
return pList
letters = ['a', 'b','o','o','g','k', 'x','l', 't']
wordList = ['axe', 'gooltk','bag', 'book', 'goat', 'book', 'list', 'box', 'boat']
cl = LetterList(letters)
#print(cl.letterDict)
p = cl.findAllPossible(wordList)
#print(p)
The naive solution could be something like the following:
def nextPeer(sortedItems, cval, sum, k):
while k < len(sortedItems) :
z = cval + sortedItems[k]
if z == sum :
return k
else:
k += 1
return -1
def findPeer(sortedItems, sum, p1):
while p1 < len(sortedItems):
cval = sortedItems[p1]
p2 = nextPeer(sortedItems, cval, sum, p1+1)
if p2 == -1:
p1 += 1
else:
return (p1, p2)
return (-1, -1)
def myPair(xSet, sumSet):
pairs = dict()
sorted_x_set = sorted(xSet, key = lambda x: x, reverse = True)
sorted_sum_set = sorted(sumSet, key = lambda x: x, reverse = True)
for s in sorted_sum_set:
j = 0
while sorted_x_set[j] > s :
j+= 1
(peer1, peer2) = findPeer(sorted_x_set, s,j)
if peer1 != -1 and peer2 != -1:
pairs[s] = (sorted_x_set[peer1], sorted_x_set[peer2])
print(sorted_sum_set)
print(sorted_x_set)
for p in pairs:
print(p, '::', pairs[p])
x = [2, 3, 4, 7,20,9]
z = [5, 11, 7, 6, 10, 9,23, 29,15,29]
myPair(x,z)
Sample Output:::
[29, 29, 23, 15, 11, 10, 9, 7, 6, 5]
[20, 9, 7, 4, 3, 2]
5 :: (3, 2)
6 :: (4, 2)
23 :: (20, 3)
7 :: (4, 3)
9 :: (7, 2)
10 :: (7, 3)
11 :: (9, 2)
29 :: (20, 9)
If multiple pairing are possible, this program will only generate one of them!
I think it asks for some answers like:
cheer + ajav + ode => a possoble shuffle for "javacodehere" if "cheer", "ajav", and "ode" are three words found in the dictionary
Another idea could treat the pyramid as a heap-structure, insert the duplicate child twice to resolve the parent-location problem. then do a traversal from leaf to root to find the max-total:
import math
class DAGHeap:
def __init__(self, aVals):
self.vals = aVals
self.vals.insert(0, -1)
self.length = len(self.vals)
print(self.vals)
def parent(self, i):
return int(i/2)
def countT(self, j):
if j == 0:
return 0
else:
return self.vals[j] + self.countT(self.parent(j))
def countMax(self):
pmax = 0
for i in range(self.length-1, math.floor(self.length/2), -1):
currentMax = self.vals[i] + self.countT(self.parent(i))
if pmax < currentMax:
pmax = currentMax
print('Maximum Path Cost: ', pmax)
a = [1 , 20 ,21 ,9, 12,12, 6, 71, 22,22,5, 5, 7]
b = [3,9,4,1,8,8,2,4,5,5,8,8,2]
myDAG = DAGHeap(a)
myDAG.countMax()
myDAG = DAGHeap(b)
myDAG.countMax()
Sample output:
[-1, 1, 20, 21, 9, 12, 12, 6, 71, 22, 22, 5, 5, 7]
Maximum Path Cost: 101
[-1, 3, 9, 4, 1, 8, 8, 2, 4, 5, 5, 8, 8, 2]
Maximum Path Cost: 28
import sys
class Node:
def __init__(self, v):
self.v = v
self.left = None
self.right = None
class BST:
def __init__(self, node):
self.root = node
self.distanceD = sys.maxsize
self.tested = set()
def addNodes(self, nList):
for n in nList:
current = self.root
#print('n:: ', n, ' and current:: ', current.v)
while True:
if n < current.v:
if current.left:
current = current.left
else:
newNode = Node(n)
current.left = newNode
break
elif n > current.v:
if current.right:
current = current.right
else:
newNode = Node(n)
current.right = newNode
break
else:
break
def updateDistance(self, lList):
for i in range(0, len(lList)-1):
for j in range(i+1, len(lList)):
if (lList[j], lList[i]) not in self.tested:
d = lList[j] - lList[i]
self.tested.add((lList[j], lList[i]))
if d < self.distanceD :
self.distanceD = d
def traverseInorder(self, current):
l = []
r = []
c = []
if current.left:
l = self.traverseInorder(current.left)
c = list([current.v])
#print(c)
if current.right:
r = self.traverseInorder(current.right)
z = l + c + r
#print(z)
self.updateDistance(z)
return z
aList = [34, 23, 78, 12, 19, 77, 21, 101, 52]
#aList = [16,5, 12, 20]
r = Node(10)
myBST = BST(r)
myBST.addNodes(aList)
bList = myBST.traverseInorder(myBST.root)
#print(bList)
#print(myBST.tested)
print(myBST.distanceD)
#print('total subcases: ', len(myBST.tested))
Sample Output:
[10, 12, 19, 21, 23, 34, 52, 77, 78, 101]
1
# if possible merge tuple 't', otherwise insert 't' into the dictionary ('myData') of tuples
def mergeOrInsert(t, myData):
merge = False
for k in myData:
if k < t[0] and myData[k] > t[0]:
if t[1] > myData[k]:
myData[k] = t[1]
merge = True
break
if not merge:
myData[t[0]] = t[1]
def mergeXY(lhTuple1, lhTuple2):
myL = dict()
print(lhTuple1)
print(lhTuple2)
i = 0
j = 0
while True:
if i < len(lhTuple1) and j < len(lhTuple2):
n1 = lhTuple1[i]
n2 = lhTuple2[j]
if n1[0] < n2[0]:
nt = n1
i += 1
else:
nt = n2
j+= 1
else:
while i < len(lhTuple1):
mergeOrInsert(lhTuple1[i], myL)
i += 1
while j < len(lhTuple2):
mergeOrInsert(lhTuple2[j],myL)
j += 1
break
#break the while loop
merge = False
print(nt)
mergeOrInsert(nt, myL)
sL = sorted(myL.items(), key = lambda x: x[0])
print(sL)
x = [(3,8), (12, 19), (23, 45), (79, 99)]
y =[(6,18), (40, 65), (70, 101), (103, 110), (115,200)]
mergeXY(x, y)
SAMPLE OUTPUT:
[(3, 19), (23, 65), (70, 101), (103, 110), (115, 200)]
def countFreq(aList):
nFreq = dict()
for a in aList:
if a in nFreq:
nFreq[a] += 1
else:
nFreq[a] = 1
print(aList)
print(nFreq)
lS = sorted(nFreq.items(), key = lambda x: x[1])
print(lS)
leastCommon = lS[0][1]
for x in lS[1:]:
if x[1] > leastCommon:
print('Second Least Common:: ', x[0])
break
l = [1, 3, 5 ,2, 2, 1, 1, 4 ,4, 5, 4, 4 , 7, 3, 2, 1, 4, 5, 2]
countFreq(l)
A simple version is:
def doesNotOverlap(x, y):
# x and y are sets
if x.intersection(y):
return False
else:
return True
def findMax(aList):
wordDict = dict()
maxLen = 0
for i,a in enumerate(aList):
al = len(a)
b = set(list(a))
for j in wordDict.keys():
tj = wordDict[j]
if doesNotOverlap(tj[1], b):
x = tj[0] * al
if maxLen < x: maxLen = x
wordDict[i] = (al, b)
print(wordDict)
print(maxLen)
def testRun():
X = ['apple', 'bow', 'butterfly', 'cute']
findMax(X)
X.append('cattle')
findMax(X)
testRun()
Here is a recursive solution of it:
def subset_sum(numbers, target, partial = []):
s = sum(partial)
if s == target:
print( partial, '= ', s)
if s >= target:
return
for i in range(len(numbers)):
n = numbers[i]
remainings = numbers[i+1:]
subset_sum(remainings, target, partial + [n])
x = [6,4,4,6,5,1,9,2,3]
xSet = set(x)
print(x)
print(xSet)
subset_sum(list(xSet), 10)
subset_sum(list(xSet), 15)
output:
[6, 4, 4, 6, 5, 1, 9, 2, 3]
{1, 2, 3, 4, 5, 6, 9}
[1, 2, 3, 4] = 10
[1, 3, 6] = 10
[1, 4, 5] = 10
[1, 9] = 10
[2, 3, 5] = 10
[4, 6] = 10
Looks like the follwoing could be a O(n) solution in python:
import math
def myPower(aList):
aL = len(aList)
print(aList)
for i,v in enumerate(aList):
if (i+1) < aL:
w = aList[i+1]
z = int(math.pow(v,w))
if z in aList:
ip = aList.index(z)
aList = [0 for i in range (aL-3)]
aList = [v] + [w] + [z] + aList
print(aList)
return
print('No sequence found')
x = [2, 81, 3, 4 ,7 , 5, 16, 18, 9]
myPower(x)
y = [2, 3, 9, 40, 15, 27, 5, 100]
myPower(y)
then it should be just one line:
>>> a = "book"
>>> type(a)
<class 'str'>
>>> a = ['b', 'c', 100]
>>> type(a)
<class 'list'>
>>> a = {'b':1, 'c':2}
>>> type(a)
<class 'dict'>
Can you use the built-in function 'type'? or not?
- fahmida.hamid February 11, 2016def series(x,y, n):
if x == y:
print(x*n)
return
if y < x :
(x,y) = (y,x)
xi = 0
yj = 0
count = 0
xChange = True
yChange = True
last_item = 0
while count < n:
if xChange: xi += x
if yChange: yj += y
if xi == yj:
last_item = xi
iChange = True
jChange = True
elif xi < yj:
last_item = xi
iChange = True
jChange = False
else:
lase_item = yj
iChange = False
jChange = True
count += 1
print(last_item, end = ' :: ')
series(4,6,6)
print('\n')
series(4,6,2)
print('\n')
series(6,3,5)
print('\n')
series(4,4,6)
class tagOverlapping:
def __init__(self, tagList):
self.tagList = tagList
self.startIndex = dict()
self.tagDict = dict()
for t in self.tagList:
s = t[0]
e = t[1]
t_id = t[2]
if t_id in self.tagDict:
self.tagDict[t_id].add((s,e))
else:
self.tagDict[t_id] = set([(s,e)])
sTagList = sorted(self.tagList, key = lambda x: x[0])
tags = set(self.tagDict.keys())
for st in sTagList:
k_id = st[2]
exTags = tags.difference(set([k_id]))
for t in exTags:
vals = self.tagDict[t]
for v in vals:
if v[0] >= st[0] and v[1] <= st[1]:
self.tagDict[k_id].add(v)
print(self.tagDict)
def queryTags(self, qt):
print('Looking for tags in : ', qt)
resultSet = set(self.tagDict[qt[0]])
qt = qt[1::]
for t in qt:
list1 = set(self.tagDict[t])
resultSet = resultSet.intersection(list1)
print(resultSet)
tList = [ [10, 23,0], [50, 70, 1], [9, 15, 2], [6,17,0], [11, 45, 2], [100, 300, 3], [120, 145, 1], [45, 79, 3], [105, 299,4], [7,15, 4], [2, 14, 1]]
print(tList)
myT = tagOverlapping(tList)
myT.queryTags([1,0])
myT.queryTags([0])
myT.queryTags([4,3])
my python solution, but worst-case time complexity is O(nlogC + n)
Sample Output:
- fahmida.hamid February 29, 2016The unsorted array is:
[3, 2, 1]
[1, 9, 4]
[2, 2, 2]
[3, 7, 1]
[6, 5, 2]
The Sorted Array is:
[1, 2, 2]
[1, 2, 3]
[1, 3, 6]
[2, 4, 7]
[2, 5, 9]