Interview Process
- Introduced ourselves to each other
- Asked about resume details (the interviewer was pretty funny — he saw on my resume that I mentioned how much revenue my project had contributed, and he actually asked whether the company had actually paid me that money)
- Algorithm question / system design
- Questions for the interviewer
Algorithm Question / System Design
This part was interesting. It started out as a plain algorithm question, but as the follow-ups went on it gradually turned into something more like a system design question.
The original algorithm question:
The input is two lists, list1 and list2. Find the increment of list1 relative to list2 — i.e., the elements that are in list1 but not in list2.
My approach was to convert both lists into sets, doing some normalization along the way (like lowercasing everything), and then take the set difference.
Follow Up 1
What if list1 becomes a stream — how would you handle that?
My approach was to convert list2 into a set, and then for each element coming in from the list1 stream, look it up in the set — if it's not there, add it to the result set.
Follow Up 2
What if the lists are too large to fully store in memory?
I offered a few approaches:
- Store list2 in a cache like Redis
- Store list2 in some kind of database, then query which elements of list1 are not in the database
- Use a bloom filter, though that comes with false positives
Discussion
Loading comments…