Breadth-first search! Of an arbitrary (not necessarily binary) tree. Glad to have this one. At least in the python implementation it’s weird that they model null as [], it should be None, but whatever.
def tree_to_list(tree_root):
res = []
worklist = [tree_root]
while worklist:
n = worklist[0]
worklist = worklist[1:]
if n == []:
continue
res.append(n.data)
for c in n.child_nodes:
worklist.append(c)
return resThis is probably the right “intro to trees” question I’ve been looking for. The previous one I’ve been doing, “print everything in a binary tree”, is a bit too clunky. For those, people get hung up on the fixation with in-order versus pre-order or whatever, and also the problems usually model it as return an array of the visited nodes; and so they want to pass that as an out-parameter or similar. Ugh!
So I like this better.
def search(n: int, root: Optional[Node]) -> bool:
""" Determines if a value is in a binary tree (NOT bst) """
if root is None:
return False
if root.value == n:
return True
return search(n, root.left) or search(n, root.right)This was a problem a student brought to me. It was very interesting! It suggests 2 approaches of different “trickiness”.
The natural approach suggested by the problem’s description is to use a for-loop. This is complicated by that, in an unusual twist, the for loop (over the provided index parameter) isn’t really related to the length of the array. So while you have the i or whatever in your for loop, you want to resist the temptation to do a[i].
Ultimately you’ll want a secondary variable. While i tracks the provided index, j handles the “wrap-around” logic:
def norm_index_test(seq, ind):
if seq == []:
return None
isneg = ind < 0
ind = abs(ind)
j = 0
for i in range(ind):
j += 1
if j == len(seq):
j = 0
assert(j < len(seq))
if isneg and j != 0:
j = len(seq) - j
return seq[j]This is actually probably the hardest form of the question, complicated by the negative indexes. If I were asking this problem, I would not ask about negative indexes. Ugh!
Once you can trust modular arithmetic (and maybe Python makes it too easy? Not sure if all languages define module of a negative number the same), it’s a one-liner. Cute, but OK.
def norm_index_test(seq, ind):
if seq == []:
return None
return seq[ind%len(seq)]OK, a sequel!
I like:
I don’t think I’m biased to say this one requires a bit of careful thought!
class Solution(object):
def commitLetter(self, chars, c, i, count):
assert(count > 0)
chars[i] = c
i += 1
if count > 1:
w = str(count)
for t in w:
chars[i] = t
i += 1
return i
def compress(self, chars):
if len(chars) == 0: return []
count = 1
j = 0
lastChar = chars[0]
for i in range(1, len(chars)):
if chars[i] == lastChar:
count += 1
else:
j = self.commitLetter(chars, lastChar, j, count)
lastChar = chars[i]
count = 1
j = self.commitLetter(chars, lastChar, j, count)
return jAnother experiment: can leetcode-esque problems provide a useful way to learn computer science topics?
This problem is about run-length-encoding. Still pretty algorithmic, but a bit more applied. Though, as I did it, it really did feel more like understanding the description more than solving the problem. On the other hand, I think this is a great “fundamentals” problem.
class Solution(object):
def decompressRLElist(self, nums):
res = []
for i in range(0, len(nums), 2):
freq = nums[i]
val = nums[i+1]
res += freq*[val]
return resOK this series is winning me over. Cost function is just interesting enough.
def neighbors(maze, i, j):
toTry = []
if i > 0:
toTry.append((i-1, j))
if j > 0:
toTry.append((i, j-1))
if i + 1 < len(maze):
toTry.append((i+1, j))
if j + 1 < len(maze[i]):
toTry.append((i, j+1))
return toTry
def path_finder(maze):
maze = maze.split()
cost = {}
toVisit = set([(0,0)])
cost[(0,0)] = 0
target = (len(maze)-1, len(maze)-1)
while toVisit:
i, j = toVisit.pop()
c = cost[(i, j)]
for (a, b) in neighbors(maze, i, j):
d = abs(int(maze[i][j]) - int(maze[a][b])) + c
if (a, b) not in cost:
cost[(a, b)] = d
toVisit.add((a, b))
elif cost[(a, b)] > d:
cost[(a, b)] = d
toVisit.add((a, b))
if target in cost:
return cost[target]
return FalseI like the idea of a series. I suppose this is a nice-enough warm up to Djiskstra.
def neighbors(maze, i, j):
toTry = []
if i > 0:
toTry.append((i-1, j))
if j > 0:
toTry.append((i, j-1))
if i + 1 < len(maze):
toTry.append((i+1, j))
if j + 1 < len(maze[i]):
toTry.append((i, j+1))
final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
return final
def path_finder(maze):
maze = maze.split()
for row in maze:
assert(len(row) == len(maze))
cost = {}
toVisit = set([(0,0)])
cost[(0,0)] = 0
target = (len(maze)-1, len(maze)-1)
while toVisit:
i, j = toVisit.pop()
c = cost[(i, j)] + 1
for (a, b) in neighbors(maze, i, j):
if (a, b) not in cost:
cost[(a, b)] = c
toVisit.add((a, b))
elif cost[(a, b)] > c:
cost[(a, b)] = c
toVisit.add((a, b))
if target in cost:
return cost[target]
return FalseVariation on island finding. Which is to say, more depth-first-search. Embarrassingly, I forgot some the base case!
def neighbors(maze, i, j):
toTry = []
if i > 0:
toTry.append((i-1, j))
if j > 0:
toTry.append((i, j-1))
if i + 1 < len(maze):
toTry.append((i+1, j))
if j + 1 < len(maze[i]):
toTry.append((i, j+1))
final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
return final
def path_finder(maze):
maze = maze.split()
for row in maze:
assert(len(row) == len(maze))
seen = set([])
toVisit = [(0,0)]
seen.add((0, 0))
target = (len(maze)-1, len(maze)-1)
while toVisit:
i, j = toVisit.pop()
for (a, b) in neighbors(maze, i, j):
if (a, b) in seen:
continue
seen.add((a, b))
toVisit.append((a, b))
return target in seenAnother nice loop! And with a thing where you want to have a table of data. Do you remove things from the set, or validate a hash-table later? Let’s do the latter.
def is_pangram(s):
seen = set([a.lower() for a in s])
for l in "abcdefghijklmnopqrstuvwxyz":
if l not in seen:
return False
return True