It’s been three weeks now and I’m learning a lot. (Take a look at Greedy vs DP for one of the things I learned last week.) I feel that I’m still very much scratching the surface and not getting to dig deeper as I thought I would have an opportunity to. There’s just too much going on and many of the group activities sound interesting and you’re supposed to be making friends, not just coding, right?

Fortunately, I scheduled a one-on-one with Rose Ames, the wonderful facilitator here at RC, and she helped me narrow down my goals and projects.

As my IRC server turned into a futile experiment of refactoring and re-architecturing, I started a new project and wrote a hundred lines of code just in a short hour. It’s a distributed hash table and it turned out to be an amazing learning opportunity for all things cache, from different eviction strategies (LFU, LRU etc.) to access patterns and approaches to resizing and re-arranging the entries (consistent hashing, rendezvous hashing). I spent a few more hours working on implementing consistent hashing with Fahri Cihan Demirci who proved to be extremely helpful with any kind of endeavor over the three weeks I’ve known him.

One of the interesting problems we ran into was implementing a set of hash functions which would have the same behavior as Python’s hash() but differ in the output. One of the key ideas of consistent hashing is that every node is mapped to several ‘random’ places on the ‘ring’. Here’s an example.

node1 = MockNode('Machine 1')
assert resizer.hash1(node1.name) == 14738669757681942741
assert resizer.hash2(node1.name) == 5343253232099587805
assert hash(node1.name) == 3927025894220883735

The size of the ‘ring’ is 2^64 so the three hashes are 80%, 29% and 21% in, respectively. Running both custom hash functions on some arbitrary names seems to give a decent spread of values.

('ben68', 1346343636456462071L, 8810460393886457683L)
('joe83', 18025785565503452379L, 5361342508193306351L)
('joe10', 11590257330418943987L, 638688640983065871L)
('joe95', 13705330057527929501L, 14166207105499503741L)
('jim98', 15996163292322350267L, 7029824721800347759L)
('joe60', 3677717759677110593L, 1156653695824287169L)
('joe95', 13705330057527929501L, 14166207105499503741L)
('joe15', 11617783559467340285L, 8632204697831470845L)
('jim43', 7472172015735855283L, 14038090357976353039L)
('dan60', 8959898799120674591L, 9928304827861693619L)

Here’s the code we ended up using. It’s about 4 times slower than built-in hash() so I’d probably revisit this problem later but will go on to the next steps in implementing consistent hashing ring for now.

def hash1(self, node_name):
    res = 0
    for char in node_name:
        res += 1723**ord(char)
    return res % 2**64

def hash2(self, node_name):
    res = 0
    for char in node_name:
        res += 1327**ord(char)
    return res % 2**64

Some other things I worked on:

  • Brainf*ck REPL with Satabdi Das and Cihan. Ivo Sánchez Checa gave me a tip on adding history to the REPL by using prompt_toolkit which was super helpful. I was hoping to present it on Thursday but all 10 presentation spots were booked so I’ll have to do a presentation this week.
  • Mastermind game implementation via the means of Mob Programming with Alicia Thilani Singham, Aissam Belhachmi, Juan Hernández, Alicja Karolina and Andrea Heyman. It was fun and I would definitely try this again.
  • Many, many interview problems, including a one-on-one whiteboarding session with brilliant Michael Cordover who just got a job at Etsy (yes, he’s that good). Problems included parsing and evaluating arithmetic expressions, counting increasing subsequences and distinct initial matrices, finding maximum of the longest common subsequences and many more less interesting but still nice to revisit array and linked list problems.
  • Last but not least, I teamed up with Joseph Kim and Sofia-Jeanne Caring to solve Weekly Code Dojo challenge. We first coded it in Ruby, Python and Java. All three solutions were accepted by Hackerrank. We still had time left and tried LOLCODE. It was lots of fun but we couldn’t make it work. For the sake of my own sanity, I won’t paste the code here, but you can take a look at the gist.
Share →