Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
from collections import defaultdict
def tree():
return defaultdict(tree)
def getAndInsert(value, tree):
# Adds a value to the tree, returns how much of the input collided
collisionLength = 0
cur = tree
for v in value:
if v in cur:
collisionLength += 1
cur = cur[v] # causes the subtree to be written.
return collisionLength
# Example
t = tree()
print getAndInsert("cat", t) # 0
print getAndInsert("car", t) # 2
# uuids are length 36, len(str(uuid.uuid4()))
import uuid
t = tree()
longestCollision = 0
while True:
u = str(uuid.uuid4())
collision = getAndInsert(u, t)
if collision > longestCollision:
longestCollision = collision
print "Longest:", longestCollision
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment