Another 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 TrueI typically don’t like math problems. This one seems like a “small” enough one to maybe introduce students to and get familiar with the notation, so they have at least some tools if an interviewer decides to spring something like this on them. So I like it for that reason. Basically a variation of the fib. sequence.
The commitment to the “get” method is a bit odd. Maybe really trying to get to the memoization, stateful approach? Not really needed, unless if I’m really missing something…. Presumably a limitation of the test design itself.
class Pell(object):
def get(self, n):
if n == 0:
return 0
if n == 1:
return 1
nprev = 1
x = 2
for i in range(3,n+1):
nprevprev = nprev
nprev = x
x = (2*nprev) + nprevprev
return xI guess what I’m curious about in my one “musings” post is what code wars calls “fundamentals”. This is one such question. I think it’s a really nice one. It is very approachable and understandable, but finicky enough where it’s not completely trivial. It also invites the question about certain “quality of life” improvements one can find in a language. If nothing else, I’m a big proponent of the “max” function, which can play a role here. Mea culpa, I hadn’t read the question fully and forgot the case if there are two candidate numbers.
def highest_rank(arr):
counter = {}
for x in arr:
if x not in counter:
counter[x] = 0
counter[x] += 1
maxCount = 0
maxCand = None
for k in counter:
if maxCount < counter[k]:
maxCount = counter[k]
maxCand = k
if maxCount == counter[k] and maxCand is not None:
maxCand = max(maxCand, k)
return maxCandDid this one a while ago. “Just” an exercise in DFS, counting connected subgraph or something. A nice enough word-problem for exercising “recognizing” when graphs appear. Ah, that’s a nice topic to consider.
class Solution(object):
def visited(self, i, j):
return (i, j) in self.seenSet
def mark(self, i, j):
self.seenSet.add((i, j))
def neighbors(self, i, j):
ns = []
if i > 0:
ns.append((i-1, j))
if j > 0:
ns.append((i, j-1))
if i < (len(self.grid) - 1):
ns.append((i+1, j))
if j < (len(self.grid[0]) - 1):
ns.append((i, j+1))
return ns
def markIsland(self, i, j):
assert(self.grid[i][j] == '1')
assert(not self.visited(i, j))
toMark = [(i, j)]
while toMark:
i, j = toMark.pop()
if self.visited(i, j):
continue
self.mark(i, j)
for n in self.neighbors(i, j):
a, b = n
if self.grid[a][b] == '1':
if not self.visited(a, b):
toMark.append(n)
def numIslands(self, grid):
self.seenSet = set([])
self.grid = grid
islandCount = 0
for i in range(len(grid)): # for each row
for j in range(len(grid[i])): # for each column
if grid[i][j] == "0":
continue
if self.visited(i, j):
continue
self.markIsland(i, j)
islandCount+=1
return islandCountNow this I’m certain is a classic. I like how it’s not, well, a single tree! A neat second-lecture problem on binary trees, I’d think.
class Solution(object):
def isSameTree(self, p, q):
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val != q.val:
return False
if not self.isSameTree(p.left, q.left):
return False
if not self.isSameTree(p.right, q.right):
return False
return TrueThis “design” or style of programming is curious. Would the students suspect that “I thought about enough cases, and figured if there’s no other reason, we can return true”? I guess reasoning by cases never felt very persuasive to me when I was starting out, it’s hard to convey that we really have covered all the cases. I don’t know what threshold I crossed to feel more confident about reasoning-by-cases. Now that I do feel comfortable, I think this can be a valuable real-world tool, too.
Other binary tree problems with solutions can be found here.
Postscript: About 9 months after posting this, I was adding more questions, and I had misread my notes and thought this wasn’t a question I solved yet. My new approach is almost character-for-character the exact as listed above! Surprising.
This one is interesting. It tricked me, I had answered the wrong question at first! It is curious how it defines the depth, that it requires a leaf node. I was computing something else, something like max height.
This one’s interesting because it provides a somewhat (unless if I’m missing something) complicated inductive case. Good to know!
class Solution(object):
def minDepth(self, root):
if root is None:
return 0
lDepth = self.minDepth(root.left)
rDepth = self.minDepth(root.right)
# Were we a leaf?
if lDepth is 0 and rDepth is 0:
return 1
if lDepth is 0:
return rDepth + 1
if rDepth is 0:
return lDepth + 1
return min(lDepth, rDepth) + 1I think I want to do a battery of tree exercises. Here’s one. The names some of these community-contributed questions come up with are quite striking.
We can either think about maintaining some global, “ah, here is the value we should compare again”, or we can exploit the transitive nature of equality.
class Solution(object):
def isUnivalTree(self, root):
if root is None: return True
if root.left is not None and root.left.val != root.val:
return False
if root.right is not None and root.right.val != root.val:
return False
return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)Hey, let’s do the global approach too, why not. Well, not global exactly, but you know.
class Solution(object):
def isUnivalTreeInternal(self, root):
if root is None: return True
if root.val != self.val: return False
return self.isUnivalTreeInternal(root.left) and self.isUnivalTreeInternal(root.right)
def isUnivalTree(self, root):
if root is None: return True
self.val = root.val
return self.isUnivalTreeInternal(root)This is another good one, I think. Strings and arrays are commonly-requested topics.
class Solution(object):
def longestCommonPrefix(self, strs):
if len(strs) == 0:
return ""
root = strs[0]
if len(root) == 0:
return ""
prefixLen = 0
for i in range(len(root)):
for s in strs[1:]:
if i >= len(s):
return root[:prefixLen]
if s[i] != root[i]:
return root[:prefixLen]
prefixLen += 1
return rootThis one’s a classic! I’m a big fan of this as a warm-up question. A simple exercise of looping, strings, exercising two different cases with dictionaries (what if the key already exists, what if it’s new), and best of all it’s a pretty reasonable distillation of real programming scenarios.
def count(string):
m = {}
for c in string:
if c in m:
m[c] += 1
else:
m[c] = 1
return mI’m sure there are very fancy ways of doing this. I’d rather use a default-dictionary, but otherwise I’m happy with this solution.