Some of these problems I have taken from Cracking the Coding Interview by Gayle Laakmannn McDowell, which in my copy has Java solutions, and some others I have been asked from various other sources.
def sunique(s_input, builtin=True):
"""
Determine if a string has all unique characters, using built-in data structures
"""
#Clarify is spaces need to be stripped.
if len(s_input)==0:
#CLARIFY with interviewer what they would like if empty string
return -1
if not builtin:
unique= []
for s in s_input:
if s not in unique:
unique.append(s)
else:
unique = set(s_input)
if len(unique) == len(s_input):
return True
else:
return False
print(sunique('test'))
print(sunique('helo wrd', builtin=False))
print("Construction of unique set is O(n), and then check of length is constant time.\n"+
"Overall O(n)")
def firstuniquechar(s_input):
"""
Takes a string s_input, and returns the first character that is not repeated
"""
#Generate set of unique elements from input
unique = set()
removed = set()
if len(s_input)==0:
return "String is empty"
for s in s_input:
#Remove duplicate elements
if s in unique:
unique.remove(s)
removed.add(s)
#Add new elements
else:
if s not in removed:
unique.add(s)
if len(unique)==0:
print("No unique elements")
return None
for s in s_input:
if s in unique:
return s
print(firstuniquechar('aabbcdedecycz'))
firstuniquechar('aaa')
def reverse(sInput):
"""
return the reverse of sInput
"""
return sInput[::-1]
reverse('abcd')
def spermutation(input1, input2):
"""
Determine if input1 string is a permutation of input2 string
"""
#clarify what to return if both are empty
#clarify if whitespace matters
#Clarify if capital letters matter
if len(input1) != len(input2):
return False
sorted1 = sorted(input1)
sorted2 = sorted(input2)
for i,s in enumerate(input1):
if s != sorted2[i]:
return False
else:
return True
spermutation('acc','aac')
class threestacks:
# i think this question is a bit redundant in python, due to the dynamic memory
# allocation of python.
def __init__(self, array):
self.stack1 = array[0::3] #memory intensive due to copying from slices
self.stack2 = array[1::3]
self.stack3 = array[2::3]
def pop1(self):
self.stack1.pop()
def pop2(self):
self.stack2.pop()
def pop3(self):
self.stack3.pop()
x = [1,2,3,4,5,6,7,8,9]
stack = threestacks(x)
stack.stack1[1] = -1
stack.stack1
x
def childstairs(nsteps, maxstep=3):
"""
Returns the count of the number of ways a child can run up a staircase of n steps with
a max step of maxstep
"""
if nsteps ==1:
# base case
return 1
if nsteps < maxstep:
return childstairs(nsteps, nsteps)
else:
count = nsteps* childstairs(nsteps-maxstep, maxstep=maxstep) + childstairs(nsteps, maxstep= maxstep-1)
return count
##INCOMPLETE
class Node:
def __init__(self, value, nextval=None):
self.value = value
self.nextval = nextval
class singleList:
def __init__(self, headval):
self.head = headval
def show(self):
currentp = self.head
while currentp != None:
yield(currentp.value)
currentp = currentp.nextval
e1 = Node('Mon')
e2 = Node('Tues')
e3 = Node('Wed')
list1 = singleList(e1)
list1.head.nextval = e2
e2.nextval = e3
list(list1.show())
def Dijkstra(graph, source):
"""
Creates and returns a dictionary that has nodes as the keys, and
distance from source as the value.
"""
from collections import deque
inf = float('inf')
nbours = deque()
nbours.append(source)
distances = {source: 0}
unvisited = []
for i in range(len(graph)):
#initialise graph
if i != source:
distances[i] = inf
unvisited.append(i)
while len(unvisited)>0:
i = nbours.pop()
for j in range(len(graph)):
if graph[i][j] != 0 and j !=i:
if j in unvisited:
nbours.append(j)
if distances[j]> distances[i] + graph[i][j]:
distances[j] = distances[i] + graph[i][j]
unvisited.remove(i)
return distances
g = [[0,3,1,2],[3,0,10,0],[1,10,0,0],[2,0,0,0]]
Dijkstra(g,1)
def periodicS(S):
### Order n solution
for n in range(1,len(S)//2+1):
unit = S[:n+1]
if len(S) % len(unit) == 0:
if S == len(S)//len(unit) * unit:
return unit
else:
##failed
print("Not periodic")
return None
periodicS('acdddc'*2 +'e')
periodicS('aceaceraceacer')
def spellcheck(word: str, corpus:{str}):
"""
eg. corpus = {vil, sit, flick, pat, pluck, sat, vat}, input = vit,
return = {sit, vil, vat}
Finds only the first 3 words
"""
matches = set()
for n in corpus:
if len(n) >= len(word)-1 and len(n) <= len(word)+1:
count = 0
if len(n) > len(word):
for i in range(len(word)):
if word[i] != n[i]:
count+=1
if count ==1:
break
else:
matches.add(n)
if len(matches) ==3:
return matches
elif len(n)< len(word):
#word is bigger than corpus word
for i in range(len(n)):
if word[i] != n[i]:
count+=1
if count==1:
break
else:
matches.add(n)
if len(matches) ==3:
return matches
else:
for i in range(len(n)):
if word[i] != n[i]:
count+=1
if count==2:
break
else:
matches.add(n)
if len(matches) ==3:
return matches
else:
if len(matches)>0:
return matches
return None
corpus = {'vil', 'sit', 'flick', 'pat', 'pluck', 'sat', 'vat'}
spellcheck('val',corpus)
def countsubsets(v, K):
"""
eg.
for K = 8 and v = [2,4,5,7], the solution is 5 ([2],[4],[2,4],[2,4,5],[2,5]).
Given the example, we will assume v is sorted, and subsets can be non-sequential
"""
#Unable to grab non-sequential subesets, i.e. [2,5].
subsets = set() #prevents duplicates
if v[0] > K:
return subsets
else:
subsets.add(v[0])
i=1
if len(v) >1:
while v[i] <=K:
##stop if max element is greater than K
if v[0] + v[i] <= K:
if 2*v[i] <=K:
subsets.add(v[i])
#add complete subset
subsets.add(tuple(v[:i+1]))
i+=1
if i >= len(v):
break
return len(subsets), subsets
countsubsets([2,3,4,5,7], 8)