Sunday, October 28, 2018

The toughest interview questions asked recently

During a recent round of interviews, I was asked these 5 questions that I found particularly interesting / challenging. They each covered a different interesting pieces of computer science that I thought worth sharing. Check them out and see what you think about them:

1. A set of overlapping ranges are provided in [start, end) format. Find the max number of ranges that overlap each given range. Improve your solution to O(N log N) complexity (basic solution is: O(N^2) complexity for a set of ascending ranges [1,4), [2, 4), [3, 4) etc.).
2. Implement a multithreaded producer / consumer queue using condition variables.
3. Implement a multithreaded rate limiter (token bucket with defined capacity) using no hard-coded poll durations and without a background thread for "filling". Discuss fairness vs head of line blocking tradeoffs of the implementation.
4. Implement a multithreaded scheduler that executes tasks repeatedly at specified time intervals which manages task overruns (task time > interval time) and does not skip scheduled run points. Estimate the maximum number of outstanding threads that a task may produce.
5. Given a matrix of size NxM with 0 and 1 entries, find the number of connected regions in the matrix. Extend your solution to handle updates of 0 entries to 1s that may connect existing regions. Expected solution is O(NxM) complexity in the worst case even for the second case with updates being approximately O(1) and space being O(NxM). Hint: Disjoint sets. 

For System Design, the following were interesting questions:
1. Design typeahead search (given a query prefix, provide completions). 
The interesting part was managing hotspots for small query lengths, the use of a KV store for serving given the low latency requirements and managing personalization.
2. Design an ad click prediction system (ML infra pipeline).
3. Design a lineage system for tracking input data to ML model training to avoid sample bias.

Overall, interviewing was a pleasant process that refreshed a lot of skills. Let me know about other interview questions that might have been interesting for you.

Cheers!
Divye

Friday, August 17, 2018

Great workplace habits


  1. Wellness: Maintaining a healthy body, mind, and spirit/mood.
  2. Self-presentation: Controlling one’s grooming, attire, and manners—given the social and cultural situation at hand—so as to make a positive impression on others.
  3. Timeliness: Arriving early, staying late, and taking short breaks. Meeting or beating schedules and deadlines.
  4. Productivity: Working at a fast pace without significant interruptions.
  5. Organization: Using proven systems for documentation and tracking—note taking, project plans, checklists, and filing.
  6. Attention to detail: Following instructions, standard operating procedures, specifications, and staying focused and mindful in performing tasks and responsibilities.
  7. Follow-through and consistency: Fulfilling your commitments and finishing what you start.
  8. Initiative: Being a self-starter. Taking productive action without explicit direction. Going above and beyond; the extra mile.
Found from: https://www.td.org/insights/8-good-work-habits-that-really-matter

I'm not the best at them, but I've found that they have made me a better person. Highly recommended.

Friday, May 11, 2018

Actionable Production Escalations

I've long considered the following items the basics of an actionable production escalation. These were taught to me by Googlers (mostly when I violated these understated values). The fundamentals of any production escalation require the documentation of the following from SREs:
1. An exception, call graph, logs or metrics showing the problem
2. A first pass characterization of the problem (what is it / how much impact)
3. Why me? (Do we need a PoC that you wouldn't know otherwise?) 
4. What have you already tried. 
5. Things that you have noted that are out of the ordinary.
6. How specifically can I help solve this problem? (Find a PoC? look at the code? Judge downstream impact? Validate severity?)

Following the above process keeps a check on the level of due diligence needed before a Dev escalation. It also helps formulate concrete action items as part of the escalation process. I've found that this helps resolve issues quicker and keeps the prod overhead low for devs. What do you think?