DEV Community: Arslan Ahmad

The 9 Things Engineers Get Wrong About the System Design Interview (and the 185 Articles I Wrote to Fix Them)

Arslan Ahmad — Mon, 13 Apr 2026 08:38:14 +0000

Every time I sit down to run a system design mock interview, the candidate fails for one of nine reasons.

Not ten. Not seven. Nine.

I've been doing this long enough — coaching engineers, running mocks, swapping debrief notes with hiring managers at Google, Meta, Amazon, Netflix, Microsoft, OpenAI, and a long tail of smaller companies — that the patterns have stopped surprising me. The same nine misconceptions show up in candidate after candidate, regardless of seniority. A junior at a startup makes the same mistakes as a staff engineer at a unicorn. Not the same magnitude, but the same shape.

Over the years, I've written 185+ articles on DesignGurus.io and DEV Community trying to address these exact failure modes one at a time. This essay pulls all of them together, organized not by topic — that's the way I usually shelf them — but by the misconception each one actually exists to correct.

If you're prepping for a system design interview right now, this is the order I'd hand the articles to you in. Read each section. Ask yourself honestly whether the misconception applies to you. Only then click into the posts. The goal isn't to read all 185. The goal is to read the ones that fix what's actually broken in your prep.

One quick note on audience. I write for engineers from junior all the way up through staff, plus engineering managers. Almost every misconception below applies across the board, but where a particular section skews toward one group, I'll say so. Engineering managers especially: don't skip Section 9. The gap between EMs who pass design loops and EMs who don't is almost never about technical depth.

Alright. Here are the nine.

Misconception #1: "It's a memorization test."

This is the most common one, and the most expensive.

Engineers walk in thinking the system design interview is a quiz: name three load balancing algorithms, define CAP theorem, list the four Vs of big data. They study it the way you'd study for a vocabulary test. Then they walk into the room, the interviewer says "design Twitter," and they freeze — because flash cards don't tell you how to start.

The system design interview is not a quiz. It's a structured conversation that tests whether you can reason about ambiguity, gather requirements, make trade-offs out loud, and defend your decisions when challenged. The vocabulary matters — you can't have the conversation without the words — but the vocabulary is the floor, not the ceiling. What you actually need first is a method. A repeatable approach you can fall back on when your brain goes blank.

These are the articles that give you one.

Grokking System Design: A Complete Roadmap for 2026 — If I could hand you a single starting point, this would be it.
2025 System Design Roadmap: From Beginner to Advanced — A second pass at the roadmap if you want a different angle on the same path.
How to Prepare for System Design Interview in 2026 — Concrete weekly cadence for engineers who don't know what "study" even looks like for this round.
How to Approach Any System Design Question — A universal opening framework that works on whatever prompt the interviewer lobs at you.
Your 7-Day System Design Interview Prep Plan — For when your loop is one week away and panic is setting in.
Last-Minute System Design Prep — For when your loop is tomorrow morning.
How to Gather and Prioritize Requirements — The first five minutes of the interview, broken down so you don't waste them.
System Design Interview Prep Guide: 7 Steps — A clean seven-step framework for going from zero to ready.
System Design Interview Guide — 7 Steps to Ace It — The same seven steps, but mapped to what you do live in the room.
System Design Interviews: A Step-By-Step Guide — My Dev Community version of the same step-by-step framework.
Mastering the System Design Interview: A Complete Guide — A long-form guide for engineers who want one canonical reference.
Mastering the System Design Interview: Landing Your Dream Job — The companion piece focused on converting prep into outcomes.
System Design Mastery: Your Roadmap to Acing Interviews — A more advanced roadmap aimed at senior+ candidates.
Demystifying System Design Interviews — What's actually happening on the interviewer's side of the table.
A Comprehensive Breakdown of Systems Design Interviews — The hidden rubric you're being graded on, made explicit.
How To Clear System Design Interview: A Quick Guide — A ruthlessly compressed checklist for passing the round.
7 Tips to Stand Out in Your System Design Interview — How "pass" candidates become "strong hire" candidates.
How 4 Candidates Passed FAANG System Design Interviews — Four real stories that will calm you down if you're spiraling.

Misconception #2: "I know what consistency means."

You probably don't.

Or — more precisely — you know the textbook definition but you can't actually distinguish strong from eventual consistency in a real design conversation, you can't explain when each is appropriate, and you'll mumble something about CAP theorem if you get pushed on it. I've seen this in candidates with eight years of experience.

The fundamentals are called fundamentals because everything else stacks on top of them. If you can't speak fluently about consistency, caching, load balancing, hashing, rate limiting, idempotency, and back-of-the-envelope estimation, the rest of your prep is a house built on sand. This is the section to go deepest on, even if you think you already know this stuff. Especially if you think you already know this stuff.

25 Fundamental System Design Concepts — The twenty-five-concept checklist I run through to gauge readiness.
4 Basic Pillars of System Design — Scalability, availability, reliability, performance — the four qualities you're scored on.
12 System Design Algorithms You Must Know — The dozen algorithms quietly powering most distributed systems.
Eventual vs Strong Consistency — How to talk about consistency without sliding into academic jargon.
Consistency Patterns in Distributed Systems — A tour of the major consistency models and the situations each is built for.
CAP vs PACELC — Why senior interviewers have quietly upgraded from CAP to PACELC.
Load Balancing Algorithms Guide — The algorithms living inside every load balancer, explained without theory bloat.
Complete Load Balancer Guide 2026 — The 2026 deep dive on load balancers in real production deployments.
Mastering the Art of Caching — Cache layers, eviction strategies, and the pitfalls nobody warns juniors about.
Cache Invalidation Strategies — The hardest problem in computer science, finally given a serious treatment.
CDN System Design Basics — When a CDN earns its place in your diagram and when it's just resume garnish.
Consistent Hashing vs Traditional Hashing — The hashing technique that quietly makes horizontal sharding even possible.
Grokking Rate Limiters — Token buckets, leaky buckets, and how to actually implement one on a whiteboard.
Grokking Webhooks — Why webhooks beat polling and how to design them so they don't blow up.
Grokking Events in System Design — What the word "event" really means once you're inside an event-driven architecture.
Grokking Idempotency — The single key concept that keeps distributed systems from corrupting themselves.
Concurrency vs Parallelism — A distinction that more than half my mock candidates get wrong on the first try.
Synchronous vs Asynchronous Communication — The hidden operational cost of going async, and when you should pay it anyway.
Stateless vs Stateful — The single biggest lever you have for horizontal scale.
Mastering Estimation in System Design Interviews — How to do capacity math live without freezing or hand-waving.
Back-of-the-Envelope Estimation — The "numbers every programmer should know," updated for modern interviews.
Observer vs Pub-Sub Pattern — Two patterns that look identical from a distance and behave nothing alike up close.

Misconception #3: "Database choice doesn't really matter."

It's the entire interview.

Walk through any "design X" question that ever gets asked, and you'll find the data layer is where the candidate either earns the offer or loses it. Sharding strategies, replication topology, indexing decisions, the SQL-versus-NoSQL fork — these aren't side topics. They are the conversation.

I've watched too many candidates draw a beautiful service diagram and then wave vaguely at a cylinder labeled "DB" as if the storage layer were beneath their notice. It isn't. Senior interviewers spend half the round on data, and they grade you on how comfortable you are with the trade-offs.

PostgreSQL vs MongoDB vs DynamoDB — The three databases you'll be asked about most, compared honestly.
NoSQL Databases in System Design Interviews — A principled framework for when reaching for NoSQL is actually the right call.
Graph Databases 101 — The class of problem graph databases solve elegantly that relational ones can't.
Why Horizontally Scaling SQL Is Hard — The structural reasons relational systems fight you when you try to scale them out.
Scaling SQL Databases: 8 Challenges — The specific problems you'll hit when you push SQL past its comfort zone anyway.
Complete Database Sharding Guide 2026 — Every sharding strategy worth knowing, plus how each one fails.
Database Replication Fundamentals — Master-slave, multi-master, and quorum replication, demystified.
Data Replication Strategies I Wish I'd Known Earlier — The replication patterns I had to learn the hard way.
B-Tree vs Hash vs R-Tree — Three index structures and the workloads each is built for.
Database Indexing Demystified — A second take on indexing that brings bitmap indexes into the picture.
Grokking Database Indexing — Why indexes make queries fast, derived from first principles.
Normalization vs Denormalization — The eternal "it depends" question, finally given some actual rules.
ACID & Database Transactions 101 — Four letters every candidate should be able to riff on without notice.
From UUID to Snowflake — Why distributed ID generation is its own surprisingly deep topic.
Change Data Capture 101 — How CDC pipelines keep downstream systems coherent without dual writes.
Ultimate Guide to Redis in System Design — Redis explained through the lens of how it actually shows up in interviews.

Misconception #4: "Fast and scalable mean the same thing."

They don't.

A fast system can be impossible to scale. A scalable system can have terrible per-request latency. They are orthogonal qualities, optimized with different techniques, and conflating them is one of the cleanest tells that a candidate hasn't built distributed systems in production. When an interviewer asks "how would you make this faster?" and you start talking about adding more servers, you've revealed the gap.

This section covers the trade-off conversations that show up in every senior loop: scale versus latency, availability versus consistency, build versus buy, performance versus cost. Master these and you'll start sounding like an engineer who's actually shipped something at scale.

Grokking Scalability in System Design — The core mental models for thinking about scale from day one.
Scaling 101 — A thorough primer on scaling real-world systems beginning to end.
Large-Scale System Design Questions — Walkthroughs of questions that operate at billion-user scale.
High Availability — 15 Strategies — Fifteen concrete patterns for keeping a system up through failure.
Autoscaling Strategies — The autoscaling approaches that hold up when traffic actually spikes.
5 Best Leader Election Algorithms — The leader-election algorithms senior interviewers expect you to know on sight.
Best 5 Ways To Reduce Latency — Five concrete levers when "make it faster" lands on your desk.
Demystifying Long-Tail Latency — Why p99 is the number that matters and how to actually attack it.
Read-Heavy vs Write-Heavy Workloads — How to shape your architecture around your read-write ratio.
Top 10 System Design Challenges — The hardest problems in modern distributed systems engineering.
Top 12 System Design Trade-offs — The trade-offs that surface in nearly every senior loop.
System Design Trade-offs Framework — A framework for talking through trade-offs the way a senior engineer would.
Navigating Complex System Design Trade-Offs — Advanced trade-off analysis for staff-level conversations.
The Buy vs Build Decision — How to frame the off-the-shelf-versus-build-it-yourself question convincingly.

Misconception #5: "An API is just an API."

Tell me you haven't done a system design interview without telling me you haven't done a system design interview.

Modern interviews — especially at companies that ship a lot of services — care a lot about how those services talk to each other. Choosing REST versus GraphQL versus gRPC isn't a stylistic preference; it's a load-bearing architectural decision. The differences between a load balancer, a reverse proxy, and an API gateway aren't trivia; they're three different places to put cross-cutting concerns, and interviewers will probe whether you know the difference.

If your last meaningful API design conversation was about whether to use PUT or PATCH, this section is for you.

HTTP/2 vs HTTP/1.1 — The protocol upgrades that genuinely move the needle on performance.
TCP vs UDP — When UDP is the right call and when TCP is non-negotiable.
Cookies vs Sessions 101 — Web session management for engineers who never properly learned the basics.
What Happens When You Type a URL? — The classic warm-up question, walked through end to end.
What is an API? — A first-principles definition for engineers who've used APIs without ever defining one.
Understanding RESTful APIs — What "RESTful" means in interviews versus how it gets butchered in production.
10 Best API Design Practices — Ten habits that mark the difference between a junior and senior API designer.
The API Design Checklist — The mental checklist senior engineers run through before writing any endpoint.
REST vs GraphQL vs gRPC — A head-to-head on the three API paradigms competing for your design.
8 REST API Interview Questions — The REST-flavored questions that keep cycling back through interviews.
Mastering the API Interview — A deep dive on the API-focused round if your target company runs one.
Load Balancer vs Reverse Proxy vs API Gateway — Three boxes that look identical and serve very different purposes.
RabbitMQ vs Kafka vs ActiveMQ — The three message brokers you'll be asked about, head-to-head.
Kafka Streams vs Flink vs Storm — The major stream processing engines, compared by what they're actually good at.
Defensive Coding for Network Timeouts — The defensive patterns that prevent local failures from cascading into outages.
Grokking Messaging Patterns — Queues, Pub/Sub, and event streams — the three workhorses of distributed comms.

Misconception #6: "Microservices are obviously the right answer."

They're obviously the right answer the way a chainsaw is obviously the right tool for opening a letter.

I've lost count of the number of candidates who reach for microservices reflexively when asked to design even modestly sized systems. They name-drop service meshes, mention Kubernetes for no clear reason, and end up with diagrams that have more boxes than the actual product would have users in its first year.

A senior engineer knows when not to use microservices. A senior engineer can defend a monolith. A senior engineer can articulate what SOA actually was, what each style's failure modes look like in production, and when "boring" is the right answer. This section will get you there.

Monolithic vs Microservices vs SOA — A fair comparison of the three major architectural styles.
Top 10 Software Architecture Patterns — The ten patterns every senior engineer should be able to name and apply.
10 Myths About Microservices — The myths that push teams into microservices for all the wrong reasons.
10 Common Microservices Anti-Patterns — The anti-patterns I see most often in real production codebases.
19 Essential Microservices Patterns — Nineteen patterns worth keeping in active vocabulary.
Essential Software Design Principles (SOLID) — SOLID via real examples instead of canned definitions.
Beginner's Guide to Object-Oriented Programming — An OOP refresher for engineers who came up through other paradigms.
The Ultimate Kubernetes Guide for System Design — Kubernetes from a system design lens, not a DevOps one.
Virtual Machines vs Containers — VMs and containers, explained without the cloud-vendor marketing.
A Beginner's Guide to Distributed Systems — A friendly on-ramp to thinking distributed-first.
Distributed System Design Guide for Beginners — Concepts and patterns for engineers building their first distributed system.
Apache ZooKeeper's Architecture — A look at how ZooKeeper holds distributed state together.
Idempotency 101: Fault-Tolerant Distributed Systems — A production-grade treatment of idempotency in distributed contexts.
How to Use Consistent Hashing in a System Design Interview — Applying consistent hashing live in an interview, walked through.

Misconception #7: "I've memorized 'design Twitter,' I'm fine."

You're not.

The case studies you'll find in this section are not scripts to memorize. They're worked examples of a thinking process — and the goal is to internalize the process, not the answer. If your interviewer asks you to design Twitter and you regurgitate a memorized solution, a sharp interviewer will immediately pivot — "OK, now make it work for live video instead of text" — and you'll be flailing again because you never learned to think, only to recite.

The right way to use this section: read each case study once for ideas, then close the tab and design the same system from scratch on a blank piece of paper. Compare. The gap between your version and mine is your study plan for the next day.

How to Design Instagram — A worked walkthrough of the Instagram design question.
How to Design a Social Media News Feed — Designing a scalable news feed from first principles.
How to Design a URL Shortener Service — The classic URL shortener, solved end to end.
URL Shortener — Dev Community Version — A second take on the same problem from a slightly different angle.
How to Design a Web Crawler — Designing a distributed crawler the way you'd actually build one.
How to Build a Search Engine — How search engines actually get built, from crawler to ranker.
How to Design a Recommendation System — The architecture behind Netflix-style recommendations.
How to Design a Cloud Storage Service — Designing Dropbox or Google Drive, including the parts most writeups skip.
How to Design a Real-Time Chat Application — Designing WhatsApp or Slack from scratch.
How to Design a Real-Time Collaborative Editor — How the Google Docs collaboration model actually works under the hood.
How to Design a Video Conferencing System — The architectural choices behind Zoom-style calls.
How to Design a Ride Sharing Service — Designing Uber end to end without hand-waving over geospatial.
Designing an E-Ticketing System — A ticketing system that survives flash-sale traffic.
Design a Scalable E-Commerce Platform — A modern e-commerce architecture built for scale from day one.
Designing a Parking System — The classic OOD parking lot question, answered properly.
10 Must-Do System Design Interview Questions — My ten must-do questions with full solutions.
64+ System Design Interview Questions — The full canonical question list, grouped by theme.
64 Questions Ranked by Difficulty — The same set, ranked from easiest to hardest.
50 Advanced System Design Questions — Fifty harder questions calibrated for senior and staff loops.

Misconception #8: "An interview is an interview."

Companies vary wildly in what they actually grade.

Google's bar is mostly about depth and rigor — they want you reasoning from first principles and acknowledging what you don't know. Amazon weaves leadership principles through every technical answer. Meta cares about product judgment alongside system judgment, and actually runs two different design rounds depending on the role. Netflix wants pragmatism and ownership. OpenAI is its own beast right now and changes faster than any blog post can keep up with.

If you're prepping with a generic curriculum and then walking into a specific company's loop without tuning, you're leaving offers on the table. Pick your target. Study the rubric.

FAANG System Design Interviews — Strategies from Real Experts — Strategies straight from people who've sat on both sides.
Mastering the FAANG Interview — The complete guide to the entire FAANG loop, not just design.
FAANG Interviews in 2025: What Changed — What shifted in FAANG loops last year and how to adapt your prep.
Google, Amazon, and Meta Compared — How the three biggest companies differ in how they actually run the design round.
Google System Design Interview Questions — Google's favorite questions with sample answers.
Google System Design Secrets — Insider notes on Google's specific scoring habits.
Pass Google System Design as a Non-Programmer — Yes, PMs and TPMs can clear this round — here's the playbook.
Amazon System Design Interview: 5 Sample Questions — Five Amazon-flavored questions worked through.
Amazon System Design Mock Interview Prep — How to run a mock that actually mirrors Amazon's loop.
Amazon Interview Questions: Ultimate Guide — The complete Amazon prep guide, including leadership principles.
Meta System Design Interview Questions — Meta's design questions with structured solutions.
Meta System Design vs Product Design — How to tell Meta's two different design rounds apart.
Mastering Meta's Product Design Interview — A complete guide to Meta's product architecture round.
Mastering the Meta Technical Screen — A thorough walkthrough of Meta's screen for senior candidates.
All You Need to Know About the Meta Interview — A complete overview of Meta's hiring loop.
How to Ace the Meta Engineering Manager Interview — The Meta EM loop, broken down by round.
Netflix System Design Interview Questions — Netflix's design questions with the context they're usually asked in.
Microsoft System Design Interview Questions — Microsoft's rubric and most-asked questions.
OpenAI System Design Interview Questions — The questions to expect when interviewing at OpenAI.
Tesla System Design Interview Questions — How Tesla's design questions diverge from the FAANG mold.
Salesforce System Design Mock Interview — A mock built around Salesforce's actual loop.
Acing the PayPal Software Engineer Interview — A deep dive on PayPal's interview process.

Misconception #9: "Coding and behavioral don't matter for senior roles."

They might matter more.

I have watched far more senior engineers fail FAANG loops on behavioral rounds than on system design. The math is brutal: you can ace four out of five rounds and still get a no-hire because one interviewer didn't believe your "tell me about a time you disagreed with your manager" story. Coding rounds, similarly, do not get easier as you climb the ladder — they get harder, because the bar shifts from "can you solve it" to "can you solve it cleanly while explaining your trade-offs out loud."

This section is the reminder that the design round is one slice of a longer loop, and the candidates who get offers are the ones who prep all of it. Don't skip these because they aren't "the fun part." They're often the part that decides the offer.

Don't Just LeetCode — Follow Coding Patterns — Why pattern-based prep beats raw LeetCode volume every time.
Ultimate Coding Patterns Cheat Sheet — The cheat sheet I hand to every candidate I mentor.
10 Top LeetCode Patterns for FAANG — The ten patterns that unlock most FAANG coding questions.
Top LeetCode Patterns — Dev Community Version — The same breakdown from a slightly different angle.
20 Essential Coding Patterns — Twenty patterns that cover the vast majority of coding interview territory.
5 Essential Algorithms for Coding Interviews — The five algorithms worth committing to memory.
Top 20 Coding Questions for the Google Interview — Twenty Google-favorite coding questions.
10 Coding Interview Mistakes to Avoid — The mistakes I see candidates repeat over and over.
The Ultimate Strategy for Coding Interview Prep — My complete approach to preparing for coding rounds.
Grokking LeetCode — A Smarter Way to Prepare — A smarter alternative to grinding until you drop.
Key Steps to Prepare for a Software Engineer Interview — The core steps to structure your prep from day one.
Software Engineer Interview Preparation: Complete Guide — An end-to-end SE interview prep guide.
The Roadmap to Clearing Technical Interviews in 2025 — A full roadmap for technical interview prep.
12 Weeks Tech Interview Preparation Bootcamp — A structured twelve-week bootcamp plan.
All You Need to Know About an Interview Bootcamp — What to expect from a structured bootcamp and who actually benefits.
Behavioral Interviews at FAANG — What FAANG interviewers are really listening for in behavioral rounds.
FAANG Behavioral Interview Guide — A thorough behavioral prep guide for FAANG loops.
How to Craft Compelling Behavioral Interview Stories — A storytelling framework that turns flat answers into memorable ones.
Culture Fit in Tech Companies — What "culture fit" actually means to hiring committees.
Soft Skills for Software Engineering Interviews — The soft skills that quietly carry the most weight.
Software Engineer Survival Kit 2026 — The skills I'd focus on now to stay relevant through the AI era.
Skills Junior Developers Need in the AI Era — What junior engineers should focus on as the field shifts under them.
Job Hunting in 2025: LinkedIn's 'Open to Work' Badge — Whether the Open to Work badge actually helps your search.
3 Technologies That Will Shape the Future — My take on three technologies quietly reshaping the field right now.

Reference Shelf

A handful of pieces that don't fit cleanly into any single misconception but are worth keeping bookmarked. Cheat sheets, course reviews, recommended papers, tools, and meta-essays on the discipline.

The Ultimate System Design Cheat Sheet (2026) — The current version of the most-saved cheat sheet on the site.
System Design Cheat Sheet for Senior Engineers — A one-page reference tuned specifically for senior-level expectations.
System Design Interview PDF — A downloadable roadmap and checklist for offline prep.
System Design Primer: The Ultimate Guide — A reference primer on every term you'll need to know.
System Design Tutorial for Beginners (2025) — A tutorial that builds intuition through worked examples.
System Design 101 — Beginner's Guide — The absolute first-timer introduction to the vocabulary.
System Design Interview Guide for Beginners — A gentler ramp for engineers with no distributed systems background.
System Design Interview Guide 2025 — A current top-to-bottom guide for FAANG-style design rounds.
Top System Design Interview FAQs — Straight answers to the questions candidates ask me on repeat.
7 Must-Read System Design Papers — The foundational papers every senior candidate should have read.
Top 7 Tools for Creating System Design Diagrams — The diagramming tools I actually use when teaching.
Best System Design Courses for Beginners — A comparison of the entry-level options on the market.
Navigating the Best System Design Courses — How to pick a course that actually matches your level and target.
What Is Grokking the System Design Interview? — A full tour of the flagship course for readers deciding if it fits them.
How to Use Grokking System Design Interview to Ace FAANG — Tactics for getting maximum value out of the course.
Is Grokking the System Design Interview Worth It? — An honest self-review for readers weighing the decision.
Grokking the System Design Interview — 5 Lessons — Five hard-won lessons from years of teaching this material.
HighScalability.com vs DesignGurus.io — A fair comparison of two popular resources and how they complement each other.
Why Practicing System Design Is Crucial — Why this is a long-term career skill, not just interview theater.
Is System Design Important for Data Scientists? — Why data folks should care about system design too.

How to Actually Use This Guide

A few last notes.

One misconception at a time. Don't open all nine sections at once. Pick the one that bites you hardest, work through those articles in sequence, do the exercises in your head as you go, and only then move on. Engineers who spread their attention across all nine misconceptions in parallel make about a third of the progress they'd make working serially.

Practice harder than you read. The single biggest mistake in interview prep is consuming material instead of producing it. After every case study, close the tab and design the same system on paper. After every fundamentals article, try to explain the concept to an imaginary junior engineer in three sentences. Your gaps will show up almost immediately, and they'll be far more useful than another article would have been.

Trust the misconception framing. I organized this post around mistakes rather than topics deliberately. Engineers who frame their prep around weaknesses improve faster than engineers who frame it around coverage. "Read every database article" is a tempting goal because it's measurable, but it doesn't actually correct what's broken in your performance. "I freeze when asked about consistency, so I'm spending three days on Section 2 until I can talk about it cold" — that does.

Come back when you've cleared the loop. I've kept this list updated for years specifically because engineers who land offers write to tell me which articles helped and which were missing. If you make it through and break in, please send me that note. Those messages are why I keep writing this stuff in the first place.

Good luck. You've got this.

64 System Design Interview Questions, Ranked From Easiest to Hardest

Arslan Ahmad — Sun, 12 Apr 2026 02:28:29 +0000

If you've ever stared at a list of 200 system design interview questions and felt your motivation drain out through your shoes, this article is for you.

Here's the uncomfortable truth about preparing for system design interviews: most curated lists you'll find online are useless not because the problems are bad, but because they're presented as a flat soup. Designing TinyURL and designing a stock exchange are not the same kind of challenge. They don't take the same amount of preparation. They don't test the same skills. And lumping them together makes you feel like you have an impossibly long road ahead, when really the road is much shorter than it looks — you just need to walk it in the right order.

So I sat down with the four most respected system design courses on the internet — the original Grokking series, its Volume II successor, the advanced case-studies course, and the newer crash course — and pulled out every single design question. I ended up with 64 of them. Then I did something nobody else seems willing to do: I ranked them from easiest to hardest, in five clean tiers.

The result is a roadmap. Start at Tier 1, work your way up, stop when you hit the level your interview demands. No more drowning in a sea of equally-weighted problems. Let's go.

How to read this tier list

A few ground rules before you dive in.

Difficulty here means interview difficulty, not real-world difficulty. A problem like "design Amazon S3" is genuinely terrifying to build in real life, but as an interview question it's well-trodden territory and a strong candidate can navigate it with relatively few surprises. By contrast, "design a flash sale" sounds simple until your interviewer starts asking about fairness and you realize there are no easy answers. I've ranked by how hard the interview conversation tends to go, not by lines of code.

You don't need to finish every tier. If you're a junior engineer interviewing for a backend role, mastering Tiers 1 and 2 will get you a long way. Mid-level and senior candidates should be comfortable through Tier 3. Staff and principal candidates need Tier 4 in their bones, and Tier 5 — the real-world case studies — is where they go to win the room.

Repetition is intentional. A few problems appear twice across the four source courses (there are two YouTube questions, two Uber questions, two typeahead questions). I've kept all 64 because the alternate treatments often emphasize different angles, and reading both is genuinely educational.

With that out of the way, here are the 64 system design interview questions you should know in 2026, ranked.

Tier 1 — Warm-ups (8 questions)

These are the gentlest problems on the list. They typically focus on a single core idea — generating IDs, limiting throughput, building a simple lookup — and they're where every system design beginner should start. If you can't comfortably whiteboard these, no amount of advanced material will save you. Get fluent here first.

Design TinyURL

The first problem nearly everyone tackles. The whole exercise is about turning a long URL into a six-character code, but along the way you'll bump into hash collisions, base62 encoding, read amplification, and your first taste of when to introduce a cache. A perfect on-ramp.

Design Pastebin

A natural follow-up. Now your "value" is a multi-kilobyte text blob instead of a URL, which forces you to think about where blobs actually live (hint: not your relational database) and how to expire content gracefully without scanning the entire dataset.

Design an API rate limiter

Every backend engineer should be able to draw a token bucket from memory by the end of this one. The single-machine version is short and sweet — the perfect place to learn the algorithms before facing their distributed cousin.

Design a distributed rate limiter

Now imagine the same rate limiter, except enforced consistently across fifty edge servers in different regions. Suddenly the simple counter becomes a real distributed systems problem. This is your introduction to "consistency costs latency."

Design a unique ID generator

Why isn't auto-increment good enough? Spend twenty minutes on this question and you'll learn about Twitter's Snowflake, the role of clock skew, and why ordering identifiers by time is sometimes worth more than uniqueness alone.

Design typeahead suggestion

Your first encounter with the trie data structure in an interview context. The fun part isn't the trie — it's the constraint: you have under 100 milliseconds to return ranked suggestions, and your dictionary has tens of millions of entries.

Design typeahead/autocomplete

The crash course's modernized take on the same problem, with extra emphasis on personalization, fuzzy matching, and how trending queries get added to the suggestion pool in near-real-time. Worth doing both versions back-to-back.

Design an API gateway

The component everyone nods at and few can describe in detail. Authentication, throttling, request routing, and response transformation all live here. Designing one is the fastest way to understand what your microservice architecture is actually missing.

Tier 2 — The classics (15 questions)

This is the meat of the list — the system design interview questions that have been asked at FAANG companies for over a decade and remain in heavy rotation. If your interview is in two weeks, this is the tier where you should be spending most of your time. Every problem here exercises at least two non-trivial design dimensions, and most have a famous "right answer" that interviewers expect you to at least be aware of.

Design Twitter

The single most asked system design interview question, full stop. The conversation will inevitably arrive at the question of when to materialize a user's home timeline — at write time, at read time, or some hybrid — and your answer reveals more about your seniority than almost anything else you'll say.

Design Twitter timeline

A laser-focused version of the previous question that strips away everything except the timeline-generation problem. If you struggled with the broad version, this is the one to drill until your fan-out reasoning becomes second nature.

Design Instagram

Twitter, but the payload is photos and videos instead of text. That single change pulls in CDN strategy, image transformation pipelines, and a much more complicated story about storage tiers — hot, warm, and cold — than text-based systems require.

Design Facebook's newsfeed

Twitter, but ranked. The presence of a ranking layer changes everything: now you need a feature store, an ML serving layer, and a way to score thousands of candidate posts in milliseconds. A great problem to learn what production ML infrastructure actually looks like.

Design Reddit

Threaded comments are the technical highlight here, but the more interesting story is the time-decaying score function that powers Reddit's "hot" sort. Implementing it once gives you a tool you can apply to dozens of other ranking problems.

Design Facebook Messenger

A messaging system that has to handle billions of users, millions of concurrent connections, and the merciless requirement that messages arrive in order, without duplicates, and even when the recipient is offline. Long-polling vs. WebSockets is the appetizer; the main course is delivery semantics.

Design WhatsApp

Take Facebook Messenger and add end-to-end encryption, multi-device support, and the operational reality that most users are on bandwidth-constrained mobile networks. The cryptography rabbit hole is optional but rewarding.

Design Dropbox

The first problem on this list where the client matters as much as the server. Chunking, deduplication, delta sync, and conflict resolution turn a simple file upload service into a surprisingly intricate distributed systems problem.

Design Yelp or Nearby Friends

The geospatial indexing primer everyone needs at least once. Geohashes, quadtrees, and S2 cells all make appearances. Once you've internalized them, every other "find things near me" problem feels like a minor variation.

Design the Uber backend

Yelp's geospatial indexing meets a real-time matching engine. The dispatch algorithm — which driver gets which rider — is where most candidates either shine or stumble. Have a concrete answer ready.

Design Uber/Lyft

The crash course's updated treatment, with more attention to surge pricing economics, ETA prediction, and the subtle differences between batched and continuous matching. Read after the original Uber question for maximum effect.

Design a web crawler

The front-end of any search engine. The crawler itself is mostly a queue and a politeness budget — the hard parts are URL deduplication at scale, dealing with infinite URL spaces, and not getting your IPs banned from the entire internet.

Design Twitter search

The first system design interview question that forces you to confront inverted indexes. You'll learn how documents become postings lists, why sharding by term is harder than it sounds, and how to keep an index fresh when new documents arrive every millisecond.

Design Ticketmaster

The poster child for "strong consistency is expensive but sometimes necessary." Two people cannot buy the same seat. Period. Get this question wrong and you've burned a sold-out concert; get it right and you've demonstrated you understand distributed locking.

Design Google Calendar

Looks like a CRUD app, behaves like a logic puzzle. Recurring events, time zones, daylight saving time, and invitation propagation conspire to create one of the most underrated data modeling questions in the entire list.

Tier 3 — Modern systems (16 questions)

Tier 3 problems show up disproportionately in interviews at companies founded in the last decade or two. They tend to involve real-time collaboration, AI/ML, or operational concerns that older problems don't surface. If you're targeting modern infrastructure-heavy roles or AI-first companies, this is the tier that separates "competent" from "current."

Design Discord

Chat plus voice plus the unique pain of supporting servers with hundreds of thousands of members in a single channel. The naive fan-out approach explodes; the right answer involves hierarchical message distribution and very careful state management.

Design a live comment streaming service like Twitch chat

A million viewers, a few thousand chatters, and a chat that has to feel instantaneous. The trick is realizing that perfect delivery to every viewer is neither possible nor desirable — and architecting accordingly.

Design Google Docs

The system design interview question that introduces most engineers to operational transforms (or, more recently, CRDTs). Have at least a basic mental model of one of these algorithms before you sit down for this interview — bluffing is obvious.

Design a collaborative whiteboard like Miro

Google Docs, but the data model is a 2D plane of arbitrary objects and the latency budget is even tighter. The CRDT discussion gets weirder. The infrastructure discussion gets harder. A favorite at companies building real-time tools.

Design ChatGPT

The newest entry on the list and rising fast. The infrastructure conversation centers on GPU scheduling, KV cache reuse, streaming token responses, and conversational state management — none of which appear in any other interview question. Essential for AI infrastructure roles.

Design a notification system

Push, email, SMS, and in-app, all flowing through one pipeline. The interesting part isn't sending notifications — it's managing user preferences, channel-specific rate limits, and retries when downstream providers fail.

Design a Netflix-style recommendation system

A whirlwind tour of production ML: candidate generation, feature pipelines, batch model training, online serving, A/B testing infrastructure. Each piece is its own interview-worthy problem in disguise.

Design Gmail

Not just mailbox storage, but search-over-personal-data, threading, labels, spam filtering, and attachment handling. The variety of subsystems makes this a deceptively rich question.

Design Google News as a global aggregator

Crawling, deduplication, story clustering, and personalized ranking — all running continuously over a firehose of new articles. A great test of whether you can think in pipelines instead of in request-response.

Design a code judging system like LeetCode

Running untrusted code at scale is harder than it sounds. The architecture revolves around sandboxing, time and memory isolation, queue-based job dispatch, and aggressive result caching. A fun problem because every developer has used the system being designed.

Design a code deployment system

How do you ship code from a git push to a thousand production servers without anyone noticing? Blue-green deploys, canary releases, automated rollback triggers, and the orchestration layer that ties them together.

Design a metrics and monitoring system like Datadog

Time-series data has very different access patterns than general-purpose data, and the storage engines that handle it well — TSDB, columnar formats, hierarchical aggregation — are worth understanding even if you never build one yourself.

Design LinkedIn connections

Computing whether two users are connected through one, two, or three intermediate hops sounds easy. Doing it for a billion-user graph in under 100 milliseconds is one of the more elegant graph-precomputation problems on this list.

Design Facebook "People You May Know"

The graph problem with a recommendation twist. You're not just finding friends-of-friends — you're ranking them by signals that have little to do with the graph itself, which means an offline pipeline lurks behind the scenes.

Design Airbnb

A two-sided marketplace with search, availability calendars, reservations, payments, and reviews. Each subsystem could be its own interview, but the value of doing it as a single problem is learning how the pieces fit together.

Design a reminder alert system

Scheduling a billion future tasks efficiently is a problem nobody thinks about until they have to. The answer involves timing wheels, priority queues, and a careful consideration of what happens when a server hosting upcoming reminders crashes.

Tier 4 — Heavy hitters (18 questions)

Now we're in deep water. These are the system design interview questions that demand real depth — in distributed systems, in storage internals, in financial correctness, or in the economics of moving petabytes around. Senior and staff candidates should be able to handle these confidently. Junior candidates can absolutely study them, but don't beat yourself up if the conversations feel slippery on a first pass.

Design YouTube or Netflix

The original combined treatment of video streaming. Transcoding pipelines, adaptive bitrate streaming, and CDN economics dominate the conversation. This is where you learn that video is mostly a bandwidth problem dressed up as a software problem.

Design YouTube

A standalone, modernized YouTube design with extra weight on live streaming, viewer engagement metrics, and recommendation serving. Use this to deepen the parts the original glossed over.

Design Netflix

Pure focus on Netflix-specific challenges: the Open Connect appliance program, the microservices tangle that powers the product, and the chaos engineering ethos that keeps the whole thing running during a Friday night peak.

Design Google Search

Crawling, indexing, ranking, serving, and personalization — the whole stack behind the world's most-used query bar. Few candidates can do this question full justice in 45 minutes, but having attempted it gives you a framework for any search-related problem.

Design a distributed cache like Redis

Building a cache from scratch — sharding, replication, eviction, persistence, hot keys, and the nasty edge cases like cache stampedes. Mid-tier on the surface, but the conversation gets deep fast if your interviewer cares about durability.

Design a key-value store like DynamoDB

The cache's grown-up sibling, with full durability requirements. Quorum reads and writes, anti-entropy mechanisms, vector clocks, hinted handoff — all the concepts the Dynamo paper introduced and that every NoSQL store has had to grapple with since.

Design Amazon S3

The most durable storage system humans have ever built. Erasure coding, multi-region replication, the bucket-versus-key abstraction, and the strong-read-after-write semantics that make S3 such a reliable foundation for everything above it.

Design Amazon Lambda

Container pools, predictive warming, multi-tenant isolation, and the per-millisecond billing math that makes serverless economically viable. A surprisingly complex system hiding behind a simple programming model.

Design a distributed lock manager like Chubby

Coordination primitives for distributed systems, done right. Paxos or Raft, lease management, fencing tokens, and the corrosive realization that "implementing distributed locks with Redis" is full of bugs nobody warned you about.

Design a distributed job scheduler like cron

A cron daemon is trivial. A globally distributed cron that fires each scheduled job exactly once, even when machines die mid-execution, is one of the hardest exactly-once problems in the canon.

Design a payment system

Idempotency, double-entry bookkeeping, reconciliation, and the unforgiving truth that monetary correctness has zero tolerance for "eventually consistent." Get this right and you immediately sound like a senior engineer.

Design the Stripe payment gateway

The API-first cousin of the payment system question, with extra attention to webhooks, retries, idempotency keys, and the specific guarantees a payment processor offers to its merchants. Surprisingly hard if you've never thought about it.

Design Amazon shopping cart

The original use case for Amazon Dynamo. The interesting question isn't how to store items in a cart — it's how to merge two carts that diverged on different devices, and why the answer involves accepting eventual consistency.

Design a flash sale for an e-commerce site

Inventory of 100 items. A million users hitting "buy" at the same instant. How do you protect the database, allocate items fairly, handle the inevitable losers gracefully, and not crash the entire site? One of the most operationally interesting questions on the list.

Design Google Ads

Real-time auctions, bid optimization, budget pacing, click tracking, and ad fraud detection. Easily the largest "design X" problem on this list by surface area, and the one most candidates underprepare for.

Design an ad click aggregator

A focused drill on the click-counting and deduplication piece of an ad system. Pure stream-processing territory, with all the exactly-once and late-arriving-data fun that implies.

Design a stock exchange

Microsecond latency, deterministic ordering, and a regulator looking over your shoulder. The matching engine is the centerpiece, and even thinking about it for an hour will recalibrate your sense of what "fast" means in software.

Design a YouTube likes counter

A whole question about counting. Sounds dumb until you try to count millions of likes per second on a single video without losing data and without creating a single hot row that takes down your database. The answer is sharded counters, and it's beautiful.

Tier 5 — Real-world case studies (7 papers)

The final tier is different from everything above it. These aren't open-ended "design X" questions — they're guided tours through real, production-scale systems whose papers and source code shaped modern infrastructure. At staff and principal interviews, an interviewer might casually ask, "How does Cassandra handle replication?" or "Why did Kafka choose a log-based design?" These case studies prepare you for exactly those moments.

Treat them like papers, not like problems. Read slowly. Take notes. Come back to them.

Amazon Dynamo

The paper that launched the NoSQL era. Consistent hashing, vector clocks, sloppy quorums, and Merkle-tree anti-entropy — every modern key-value store traces its lineage back to the ideas in this paper.

Apache Cassandra

Dynamo's open-source descendant, reimagined with a wide-column data model and an LSM-tree storage engine. The case study walks you through gossip-based cluster management, tunable consistency, and the compaction process that keeps everything tidy.

Apache Kafka

The distributed log that became the spine of every modern event-driven architecture. Understand partitions, consumer groups, leader election, and the precise meaning of each delivery semantic — at-most-once, at-least-once, and the elusive exactly-once.

Google Chubby

The original distributed lock service that inspired ZooKeeper, etcd, and every coordination system built since. The most valuable lesson here isn't the Paxos implementation — it's the design philosophy behind preferring coarse-grained locking to fine-grained.

Google File System

A 2003 paper that made everyone reconsider what a filesystem had to be. Single master, 64MB chunks, weak consistency, optimization for append-heavy workloads — every design choice in GFS is a teaching moment.

Hadoop Distributed File System

The open-source response to GFS. The interesting exercise is comparing the two side by side and noticing where the open-source community made different trade-offs than Google's internal team — and why.

Google BigTable

The wide-column data model that influenced HBase, Cassandra, and the entire wave of column-family databases that followed. Beyond the data model, BigTable is a stunning example of system composition: it's built on top of GFS for storage and Chubby for coordination, and the architecture only makes sense when you understand both.

A final word: study tier by tier, not problem by problem

Here's my advice if you do nothing else with this list:

Pick one problem from each tier you need to master. Whiteboard it from scratch — no notes, no peeking. Then read the linked solution. Compare your design to theirs. Note every place you missed something, and write the missed concept on a separate sheet. That sheet, after a dozen problems, becomes your personal study guide. It's better than any list a stranger on the internet can give you, because it tells you exactly where your gaps are.

Repeat the process. Move up the tiers. By the time you've worked through 15 to 20 of the 64 system design interview questions on this list, you'll notice something strange: the new ones start to feel familiar before you even read the prompt. That's not memorization. That's the patterns clicking into place.

And when the patterns click, the interview stops being scary. It becomes a conversation — one where you're the person with the toolbox, calmly picking the right tool for the problem in front of you.

That's the goal. Good luck out there.

20 Essential Coding Patterns to Ace Your Next Coding Interview

Arslan Ahmad — Thu, 02 Nov 2023 00:41:53 +0000

Navigating through coding interviews requires more than just a good grasp of algorithms and data structures; it demands a strategic approach and a keen eye for patterns. In todays competitive world of tech job interviews, understanding and mastering coding patterns can significantly enhance your problem-solving skills and boost your performance.

Coding patterns, or as we like to call them, are recurring techniques that provide a structured approach to solving complex problems. Think of them as the building blocks of algorithms, helping you to break down problems into more manageable parts.

In this blog, we will explore 20 essential coding patterns that are pivotal for acing coding interviews. We will delve into the pros and cons of each pattern, providing you with a balanced view to help you make informed decisions during your interviews. And to top it off, we will equip you with real problem examples from the Grokking the Coding Interview course. I'm the author of this course, feel free to reach out to me if you have questions.

Let's go through each pattern one by one.

1. Two Pointers

Description

The Two Pointers technique is a clever strategy used in algorithm design, particularly when dealing with arrays or linked lists. Imagine you have two fingers, and you place each at different ends or positions of an array. These ‘fingers’ or pointers then traverse through the array, helping you to compare, search, or even manipulate the data efficiently.

Usage

Ordered Data Structures: This pattern shines when applied to ordered arrays or lists, allowing for intelligent, position-based decisions that can significantly optimize the algorithm.
Efficiency: By reducing the need for nested loops, the Two Pointers technique helps in achieving linear time complexity, making your algorithm faster and more efficient.

Pros and Cons

Pros:
- Efficiency: Achieves O(n) time complexity for problems that might otherwise require O(n^2).
- Simplicity: Once mastered, it provides a straightforward and elegant solution.
Cons:
- Applicability: Mainly beneficial for problems involving sequences or intervals.
- Initial Complexity: It might take some time to get the hang of this pattern and understand where and how to move the pointers.

Example Problems from Grokking the Coding Interview

Pair with Target Sum: Find a pair in an array that adds up to a specific target sum.
Squaring a Sorted Array: Given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.
Triplet Sum to Zero: Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

2. Island (Matrix Traversal) Pattern

Description

The Island pattern, also known as Matrix Traversal, is a technique used to navigate through a 2D array or matrix. The primary goal is to identify and process contiguous groups of elements, often referred to as ‘islands’. This pattern is particularly useful when you need to explore and manipulate grid-based data.

Usage

Grid-Based Problems: Excelling in problems where you need to traverse a grid to find connected components or regions.
Contiguous Elements: Ideal for situations where you need to group together adjacent elements that share a common property.

Pros and Cons

Pros:
- Comprehensive: Provides a thorough way to explore all the elements in a grid.
- Versatile: Can be used to solve a variety of problems related to 2D arrays.
Cons:
- Complexity: Can be more complex to implement compared to linear data structure traversal.
- Space Overhead: May require additional space for recursion or queue/stack for breadth-first/depth-first traversal.

Example Problems from Grokking the Coding Interview

Number of Islands: Count the number of islands in a given 2D matrix.
Biggest Island: Find the largest island in terms of area or number of cells.
Flood Fill: Change the color of an image represented by a 2D array.

3. Fast & Slow Pointers

Description

The Fast & Slow Pointers technique involves two pointers traversing through a data structure at different speeds. This ingenious approach is particularly useful in identifying cycles, finding middle elements, and solving various other problems related to linked lists and arrays.

Usage

Cycle Detection: Perfect for identifying cycles in a linked list or array, which is a common interview question.
Finding Middle Elements: Efficiently find the middle element of a linked list without knowing the length beforehand.
Problem-Specific Solutions: Solve specific problems like finding the start of a cycle in a linked list.

Pros and Cons

Pros:
- Space Efficiency: Achieves solutions without the need for extra space, adhering to O(1) space complexity.
- Versatility: Applicable to a variety of problems, making it a versatile pattern to know.
Cons:
- Initial Complexity: Understanding how to move the pointers and at what speed can be tricky at first.
- Specificity: While versatile, it is mostly beneficial for problems related to linked lists and certain array problems.

Example Problems from Grokking the Coding Interview

LinkedList Cycle: Determine if a linked list has a cycle.
Middle of the LinkedList: Find the middle node of a linked list.
Palindrome LinkedList: Check if a linked list is a palindrome.

4. Sliding Window

Description

The Sliding Window pattern involves creating a ‘window’ over a portion of data and sliding it across to solve problems efficiently. This technique is particularly useful for array or list-based problems where you need to find or calculate something among all the contiguous subarrays or sublists of a given size.

Usage

Contiguous Subarrays: Ideal for problems that require you to deal with contiguous subarrays or sublists.
Variable Sized Window: Can be adapted for problems where the window size is not fixed and needs to be adjusted based on certain conditions.

Pros and Cons

Pros:
- Efficiency: Provides a way to reduce time complexity from O(n^2) to O(n) for specific problems.
- Versatility: Can be used for a variety of problems, including maximum sum subarray, smallest subarray with a given sum, and longest substring with K distinct characters.
Cons:
- Initial Complexity: Understanding how to adjust the window size and when to slide the window can be challenging initially.
- Specificity: Mainly beneficial for problems involving contiguous subarrays or sublists.

Example Problems from Grokking the Coding Interview

Maximum Sum Subarray of Size K: Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any contiguous subarray of size ‘k’.
Fruits Into Baskets: Given an array of characters where each character represents a fruit tree, you are given two baskets, and your goal is to put maximum number of fruits in each basket.
Longest Substring with K Distinct Characters: Given a string, find the length of the longest substring in it with no more than K distinct characters.

5. Merge Intervals

Description

The Merge Intervals pattern is a powerful technique used to deal with overlapping intervals or ranges. It involves sorting and then merging intervals based on specific conditions. This pattern is incredibly useful for time-based problems, scheduling, and range manipulation.

Usage

Overlapping Intervals: Perfect for problems where you need to merge overlapping intervals or find if an interval overlaps with any other.
Interval Scheduling: Useful for problems that involve scheduling based on time intervals.

Pros and Cons

Pros:
- Clarity: Provides a clear and systematic way to deal with overlapping intervals.
- Efficiency: Helps in reducing the problem complexity and achieving optimal solutions.
Cons:
- Sorting Overhead: Requires the intervals to be sorted beforehand, which could add to the time complexity.
- Specificity: Mainly beneficial for problems involving intervals and ranges.

Example Problems from Grokking the Coding Interview

Merge Intervals: Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.
Insert Interval: Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.
Intervals Intersection: Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.

6. Cyclic Sort

Description

Cyclic Sort is a unique and intuitive sorting algorithm, particularly well-suited for problems where you are given a range of numbers and asked to sort them. The beauty of this pattern lies in its ability to sort the numbers in-place, utilizing the fact that the numbers are consecutive or have a specific range.

Usage

Consecutive Numbers: Ideal for scenarios where you have an array of numbers in a specific range, and you need to sort them or find missing/duplicate numbers.
In-Place Sorting: Provides a way to sort the numbers without using any extra space.

Pros and Cons

Pros:
- Space Efficiency: Achieves sorting without the need for additional space, adhering to O(1) space complexity.
- Time Efficiency: Offers a linear time complexity solution for specific range-based sorting problems.
Cons:
- Limited Applicability: Best suited for problems involving numbers in a specific range and may not be applicable for other types of sorting problems.
- Initial Learning Curve: Understanding the cyclic sort pattern and knowing when to apply it can take some time.

Example Problems from Grokking the Coding Interview

Find the Missing Number: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Find all Duplicates: Find all the duplicate numbers (without using extra space and in O(n) runtime).
Duplicates In Array: Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

7. In-place Reversal of a Linked List

Description

The In-place Reversal of a Linked List pattern is a technique used to reverse the elements of a linked list without using additional memory. This is achieved by manipulating the pointers of the nodes in the linked list to reverse their direction.

Usage

Memory Efficiency: Since no additional data structures are used, this pattern is memory efficient.
Reversing Sub-lists: Can be extended to reverse sub-lists within a linked list, providing versatility in solving more complex problems.

Pros and Cons

Pros:
- Space Efficiency: Achieves in-place reversal, ensuring O(1) space complexity.
- Versatility: Can be used to solve various problems related to linked lists, including reversing sub-lists and finding palindromes.
Cons:
- Pointer Manipulation: Requires careful manipulation of pointers, which can be error-prone.
- Initial Learning Curve: Understanding how to reverse the pointers without losing the rest of the linked list can be challenging initially.

Example Problems from Grokking the Coding Interview

Reverse a LinkedList: Given the head of a Singly LinkedList, reverse the LinkedList.
Reverse a Sub-list: Given the head of a LinkedList and two positions ‘p’ and ‘q’, reverse the LinkedList from position ‘p’ to ‘q’.
Reverse Every K-element Sub-list: Given the head of a LinkedList and a number ‘k’, reverse every ‘k’ sized sub-list starting from the head.

8. Tree Breadth First Search

Description

The Tree Breadth First Search (BFS) pattern involves traversing a tree level by level, ensuring that you visit all the nodes at the current depth before moving on to the nodes at the next depth level. This is usually implemented using a queue.

Usage

Level Order Traversal: Ideal for problems that require you to traverse a tree in level order or when you need to perform operations on nodes at the same depth.
Minimum Depth: Useful for finding the minimum depth of a tree, as you can stop the traversal once you find the first leaf node.

Pros and Cons

Pros:
- Complete Traversal: Ensures that every node in the tree is visited.
- Level Order Information: Provides information about the depth or level of each node.
Cons:
- Space Overhead: Requires additional space for the queue, which can be as large as the number of nodes at the largest level.
- Not as Efficient for Depth-Related Queries: For problems that depend on depth information, a depth-first search might be more efficient.

Example Problems from Grokking the Coding Interview

Binary Tree Level Order Traversal: Traverse a tree in level order and return the values of the nodes at each level.
Reverse Level Order Traversal: Traverse a tree in reverse level order.
Zigzag Traversal: Traverse a tree in a zigzag order.

9. Tree Depth First Search

Description

The Tree Depth First Search (DFS) pattern involves traversing a tree in a depth-first manner, meaning you go as deep as possible down one branch before backing up and exploring other branches. This is typically implemented using recursion or a stack.

Usage

Path Finding: Ideal for problems where you need to find a path or check the existence of a path with certain properties.
Complex Tree Traversals: Useful for more complex tree traversal problems where you need to maintain state or perform operations as you traverse.

Pros and Cons

Pros:
- Space Efficiency: For a balanced tree, DFS uses less space than BFS.
- Simplicity: Recursive implementations can be more straightforward and concise.
Cons:
- Can Be Less Efficient for Wide Trees: For very wide trees, DFS can use more space than BFS.
- May Not Find the Shortest Path: If you're looking for the shortest path in an unweighted tree, BFS is generally a better choice.

Example Problems from Grokking the Coding Interview

Binary Tree Path Sum: Given a binary tree and a number ‘S’, find if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals ‘S’.
All Paths for a Sum: Find all root-to-leaf paths in a binary tree that have a sum equal to a given number.
Count Paths for a Sum: Find the number of paths in a tree that sum up to a given value.

10. Two Heaps

Description

The Two Heaps pattern involves using two priority queues (heaps) to maintain a running balance or median of a set of numbers. One heap keeps track of the smaller half of the numbers, and the other keeps track of the larger half.

Usage

Running Median: Perfect for problems where you need to find the median of a set of numbers as new numbers are added.
Balanced Partition: Useful for problems where you need to maintain a balanced partition of numbers.

Pros and Cons

Pros:
- Efficiency: Provides a way to efficiently find the median or maintain balance in O(log N) time.
- Dynamic: Can handle dynamic datasets where numbers are added over time.
Cons:
- Complexity: Implementation can be more complex due to the need to balance the two heaps.
- Space Overhead: Requires additional space to store the numbers in the heaps.

Example Problems from Grokking the Coding Interview

Find the Median of a Number Stream: Design a class to calculate the median of a number stream.
Sliding Window Median: Find the median of all subarrays of size ‘K’ in the array.
Maximize Capital: Given a set of investment projects with their respective profits, we need to find the most profitable projects. We are given an initial capital and are allowed to invest only in a fixed number of projects. Our goal is to choose projects that give us the maximum profit.

11. Subsets

Description

The Subsets pattern involves dealing with problems that require generating all possible combinations or subsets of a set. This pattern is particularly useful when you need to explore all the different ways to combine elements, which is a common scenario in many coding problems.

Usage

Combinatorial Problems: Ideal for problems where you need to generate all possible combinations of elements.
Exhaustive Search: Useful when you need to perform an exhaustive search over all possible subsets of a set.

Pros and Cons

Pros:
- Comprehensive: Ensures that you consider all possible combinations of elements.
- Versatile: Can be used to solve a variety of problems, including generating power sets, combinations, and permutations.
Cons:
- Time Complexity: Can lead to exponential time complexity, as the number of subsets of a set is 2^N.
- Space Complexity: Requires additional space to store all the subsets.

Example Problems from Grokking the Coding Interview

Subsets: Given a set with distinct elements, find all of its distinct subsets.
Subsets With Duplicates: Given a set of numbers that might contain duplicates, find all of its distinct subsets.
Permutations: Given a set of distinct numbers, find all of its permutations.

12. Modified Binary Search

Description

The Modified Binary Search pattern involves adapting the classic binary search algorithm to solve various problems, often related to searching in a sorted array or finding the boundary of a condition.

Usage

Sorted Arrays: Perfect for problems involving searching or making decisions based on sorted arrays.
Finding Boundaries: Useful for finding the start or end of a condition in a sorted array.

Pros and Cons

Pros:
- Efficiency: Provides a logarithmic time complexity solution for searching problems, making it highly efficient.
- Versatility: Can be adapted to solve a wide range of problems beyond simple searching.
Cons:
- Applicability: Mainly beneficial for problems involving sorted arrays or conditions with clear boundaries.
- Implementation Nuances: Requires careful implementation to handle edge cases and avoid infinite loops.

Example Problems from Grokking the Coding Interview

Order-agnostic Binary Search: Given a sorted array of numbers, find the index of a given number. The array could be sorted in ascending or descending order.
Ceiling of a Number: Given an array of numbers sorted in ascending order, find the ceiling of a given number. The ceiling of a number is the smallest number in the given array greater than or equal to the given number.
Next Letter: Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’.

13. Bitwise XOR

Description

The Bitwise XOR pattern involves using the XOR bitwise operator to solve problems, often related to finding missing numbers or duplicate numbers in an array. XOR is a binary operator that returns 1 when the two bits are different and 0 when they are the same.

Usage

Finding Missing or Duplicate Numbers: Ideal for problems where you need to find a missing number or duplicate numbers in an array.
Bit Manipulation: Useful for problems that require manipulation of bits to achieve the desired result.

Pros and Cons

Pros:
- Efficiency: Provides a constant space solution for certain problems, making it highly efficient.
- Simplicity: Once understood, the XOR operator can be used to create elegant and simple solutions.
Cons:
- Specificity: Mainly beneficial for problems involving finding missing or duplicate numbers.
- Learning Curve: Understanding how the XOR operator works and when to use it can take some time.

Example Problems from Grokking the Coding Interview

Single Number: In a non-empty array of integers, every number appears twice except for one, find that single number.
Two Single Numbers: In a non-empty array of numbers, every number appears exactly twice except two numbers that appear only once. Find the two numbers that appear only once.
Complement of Base 10 Number: For a given positive number N in base-10, return the complement of its binary representation as a base-10 integer.

14. Top 'K' Elements

Description

The Top 'K' Elements pattern involves finding the 'K' largest or smallest elements in an array or stream of data. This pattern is particularly useful when dealing with large datasets and you need to maintain a subset of the data based on certain criteria.

Usage

Priority Queue: Utilizes a min-heap or max-heap to efficiently keep track of the 'K' largest or smallest elements.
Streaming Data: Ideal for scenarios where the data is streaming in, and you need to maintain the 'K' largest or smallest elements at any given time.

Pros and Cons

Pros:
- Efficiency: Provides a way to find the 'K' largest or smallest elements in O(N log K) time.
- Space Efficiency: Only requires O(K) space, regardless of the size of the dataset.
Cons:
- Limited to 'K' Elements: Only maintains information about the top 'K' elements, not the entire dataset.
- Heap Maintenance: Requires careful maintenance of the heap to ensure efficiency.

Example Problems from Grokking the Coding Interview

Top 'K' Numbers: Given an unsorted array of numbers, find the ‘K’ largest numbers in it.
Kth Smallest Number: Given an unsorted array of numbers, find the Kth smallest number in it.
‘K’ Closest Points to the Origin: Given an array of points in the a 2D plane, find ‘K’ closest points to the origin.

15. K-way Merge

Description

The K-way Merge pattern involves merging multiple sorted arrays or lists into a single sorted list. This pattern is highly useful in scenarios where you have multiple sorted datasets that you need to combine and maintain the sorted order.

Usage

Multiple Sorted Arrays: Ideal for merging multiple sorted arrays or lists.
External Sorting: Useful in external sorting, where the data to be sorted does not fit into memory and is stored in sorted chunks.

Pros and Cons

Pros:
- Efficiency: Provides a way to merge multiple sorted arrays in O(N log K) time, where ‘N’ is the total number of elements across all arrays, and ‘K’ is the number of arrays.
- Space Efficiency: Only requires O(K) space for the priority queue.
Cons:
- Dependent on Sorting: The efficiency of this pattern depends on the arrays being sorted.
- Priority Queue Overhead: Requires maintenance of a priority queue, which adds to the complexity.

Example Problems from Grokking the Coding Interview

Merge K Sorted Lists: Given an array of ‘K’ sorted LinkedLists, merge them into one sorted list.
Kth Smallest Number in M Sorted Lists: Given ‘M’ sorted arrays, find the K’th smallest number among all the arrays.
Find the Smallest Range Covering Elements from K Lists: Given ‘M’ sorted arrays, find the smallest range that includes at least one number from each of the ‘M’ lists.

16. Topological Sort

Description

Topological Sort is a pattern used for linearly ordering the vertices of a directed graph in such a way that for every directed edge (U, V), vertex U comes before V. This pattern is particularly useful in scenarios where you have a set of tasks and some tasks depend on others.

Usage

Task Scheduling: Ideal for problems where tasks need to be scheduled in a specific order, respecting their dependencies.
Course Scheduling: Useful in scenarios like course scheduling where some courses have prerequisites.

Pros and Cons

Pros:
- Clarity: Provides a clear and systematic way to order tasks or vertices.
- Detecting Cycles: Helps in detecting cycles in a directed graph, which is important for understanding if a valid ordering is possible.
Cons:
- Applicability: Mainly beneficial for problems involving directed graphs and ordering of vertices.
- Complexity: Implementation can be complex, especially for beginners.

Example Problems from Grokking the Coding Interview

Topological Sort: Given a directed graph, find the topological ordering of its vertices.
Tasks Scheduling: Find if it is possible to schedule all the tasks.
Tasks Scheduling Order: Find the order of tasks we should pick to finish all tasks.

17. Trie

Description

A Trie, also known as a prefix tree, is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. It is particularly useful for retrieval of a key in a dataset of strings, which makes it highly efficient for solving word-based problems.

Usage

Autocomplete: Ideal for implementing autocomplete functionality in search engines or text editors.
Spell Checker: Useful for building spell checkers in word processors.
IP Routing: Used in IP routing to store and search routes.

Pros and Cons

Pros:
- Efficiency: Provides fast retrieval of strings and is more efficient than hash tables or sets when it comes to string keys.
- Prefix Searching: Excellent for problems that require prefix searching or matching.
Cons:
- Space Overhead: Can use more space compared to other data structures when the dataset is sparse.
- Complexity: Implementation can be complex, especially when handling deletion of words from the Trie.

Example Problems from Grokking the Coding Interview

Insert into and Search in a Trie: Implement insertion and search in a Trie.
Longest Common Prefix: Find the longest common prefix of a set of strings.
Word Search: Given a 2D board and a word, find if the word exists in the grid.

18. Backtracking

Description

Backtracking is a general algorithmic technique that considers searching through all the possible configurations of a search space in order to solve computational problems. It is particularly useful for optimization problems and when a complete search of the solution space is required. The main idea is to explore each possibility until the solution is found or all possibilities have been exhausted.

Usage

Combinatorial Problems: Ideal for solving problems that require generating all possible configurations like permutations, combinations, and subsets.
Puzzle Solving: Useful for solving puzzles such as Sudoku, crossword puzzles, and the N-Queens problem.

Pros and Cons

Pros:
- Completeness: Ensures that the entire solution space is explored, guaranteeing that the optimal solution will be found if it exists.
- Space Efficiency: Uses less memory as it only needs to store the current state and the decision stack.
Cons:
- Time Complexity: Can lead to exponential time complexity, as it explores all possible configurations.
- Optimization Required: May require additional optimizations like pruning to be practical for larger instances.

Example Problems from Grokking the Coding Interview

Subsets: Given a set of numbers, find all of its subsets.
Permutations: Given a set of distinct numbers, find all of its permutations.
N-Queens: Place N queens on an N×N chessboard so that no two queens threaten each other.

19. Monotonic Stack

Description

A Monotonic Stack is a specialized data structure that maintains elements in a sorted order while supporting stack operations. It is particularly useful for problems where you need to find the next greater or smaller element in an array or when you need to maintain a running maximum or minimum value efficiently.

Usage

Next Greater Element: Ideal for finding the next greater element for each element in an array.
Maximum Area Histogram: Useful for problems like finding the largest rectangular area under a histogram.

Pros and Cons

Pros:
- Efficiency: Provides a way to solve certain problems in linear time, making it highly efficient.
- Simplicity: Once understood, the monotonic stack can lead to concise and elegant solutions.
Cons:
- Specificity: Mainly beneficial for problems involving finding the next greater or smaller element and related problems.
- Learning Curve: Understanding how and when to use a monotonic stack can take some time.

Example Problems

Next Greater Element: Given an array, find the next greater element for each element in the array.
Maximum Area Histogram: Given a histogram, find the largest rectangular area under the histogram.
Largest Rectangle in Histogram: Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

20. 0/1 Knapsack (Dynamic Programming)

Description

The 0/1 Knapsack problem is a classic optimization problem that falls under the category of Dynamic Programming. In this problem, you are given a set of items, each with a weight and a value, and a knapsack with a maximum capacity. The goal is to determine the maximum value that can be accommodated in the knapsack without exceeding its capacity. The "0/1" part of the name reflects the fact that you can't break an item, you either take it or leave it.

Usage

Resource Allocation: Ideal for problems where you need to optimally allocate limited resources to maximize profit or minimize cost.
Budgeting: Useful for budgeting scenarios where you need to choose a subset of projects or investments to maximize return.

Pros and Cons

Pros:
- Optimality: Ensures that the optimal solution is found, provided that the problem satisfies the principle of optimality.
- Generality: Can be adapted to solve a wide variety of optimization problems.
Cons:
- Time and Space Complexity: The naive implementation has a time and space complexity of O(nW), where n is the number of items and W is the capacity of the knapsack. This can be prohibitive for large inputs.
- Requires Integer Weights and Values: The classic 0/1 Knapsack problem requires weights and values to be integers.

Example Problems from Grokking the Coding Interview

0/1 Knapsack: Given the weights and profits of ‘N’ items, put these items in a knapsack which has a capacity ‘C’. The goal is to get the maximum profit out of the items in the knapsack.
Equal Subset Sum Partition: Given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both subsets is equal.
Subset Sum: Given a set of positive numbers, determine if there exists a subset in the set whose sum is equal to a given number ‘S’.

Conclusion

Mastering these patterns is definitely not about memorizing solutions; it’s about understanding the underlying principles and learning how to apply them to a wide array of problems. The versatility of these patterns ensures that you are well-equipped to handle different challenges, making you a formidable candidate in any coding interview.

Remember, practice is key. The more problems you solve using these patterns, the more proficient you will become in recognizing problem types and applying the appropriate patterns. So, keep practicing, stay persistent, and you will find yourself excelling in coding interviews, ready to tackle any problem that comes your way.

Want to read more about coding patterns:

Key Steps to Prepare for a Software Engineer Interview

Arslan Ahmad — Fri, 25 Aug 2023 23:23:17 +0000

1. Deciphering Software Engineering Interviews

Before diving deep into coding exercises or system design preparation, it's vital to understand the essence of a software engineering interview. It’s not just about testing your coding skills, but also about understanding if you fit the company's culture and can contribute to its objectives.

What Are Hiring Managers Looking For in a Software Engineer?

Problem-solving skills: The crux of any software engineering role is to solve problems. Hiring managers are on the lookout for individuals who can break down a complex problem, approach it logically, and find a suitable solution. A 2020 survey conducted by LinkedIn highlighted that problem-solving topped the list of soft skills desired by employers.

Technical prowess: Employers wish to see a good command over programming languages and tools. They want candidates who can adapt to new technologies, as the tech landscape is ever-evolving. In a Stack Overflow Developer Survey, more than 75% of developers believed that learning new technologies is an essential part of their job.

Team Collaboration: Software development is rarely a solo endeavor. Engineers frequently collaborate with different teams, from UI/UX designers to product managers. Hence, your ability to work in a team and communicate effectively can make you stand out.

Cultural fit: Every company has its own culture and values. Hiring managers often gauge whether a candidate would fit into their work environment and resonate with the company’s ethos.

Types of Software Engineer Interviews

Coding Interviews: These assess your technical coding skills. You may be asked to write a piece of code, debug, or solve algorithms. Websites like LeetCode and Design Gurus have popularized such problems, preparing aspirants for FAANG and other top tech company interviews.

System Design Interviews: Here, you're usually posed with designing a system or architecture. It tests your broader understanding of system components and how they interact. Check the following article for a detailed discussion on system design interview: Demystifying System Design Interviews: A Guide

Behavioral Interviews: This focuses on your past experiences, behavior in certain scenarios, and how you deal with challenges or conflicts. They gauge your soft skills and are a predictor of how you'd fit into the company's culture.

Technical Screening: Before an in-depth interview, many companies have a technical screening round, usually over the phone or through platforms like Codility. This is a preliminary check to see if you possess the basic technical skills required.

Take-home Assignments: Some companies provide assignments that you must complete at home. These give a more extended window (like a week) and are beneficial for employers to see how you approach real-world tasks.

To conclude, while strong technical skills are a necessity, soft skills and a keen understanding of what hiring managers are looking for can provide the edge you need to stand out.

2. Preparing for the Technical Aspects of the Interview

Understanding the technical intricacies is pivotal for any software engineer. The coding interview can be a battleground, and the right preparation is your armor. Let's simplify how to tackle this.

How Long It Takes to Prepare For a Technical Engineering Interview

Time is subjective: On average, dedicated aspirants spend 2-4 months preparing for technical interviews at top-tier companies. However, remember, it's not about the number of hours but the quality of your preparation.

Consistency is key: Like any skill, consistent practice hones your coding acumen. Spending even an hour daily on platforms like LeetCode can help you grasp patterns and improve speed. A survey from 2019 on CodeSignal revealed that candidates who practiced regularly, even for short durations, had a 20% higher success rate in interviews compared to intermittent learners.

Choosing a Programming Language

Stick to what you know: For coding interviews, it's advisable to pick a language you’re most comfortable with. Most companies are language-agnostic in interviews, prioritizing logic and problem-solving over syntax.

Popular choices: While it's about comfort, languages like Python, Java, and JavaScript often emerge as favorites. Python's readability and simplicity make it a go-to choice for many. In fact, according to the PYPL (PopularitY of Programming Language) Index, Python's popularity grew by 18.9% in 2020, showcasing its rising prominence.

Understanding Key Concepts: Arrays, Linked Lists, Hash Tables, etc.

Arrays: They are fundamental data structures that store elements of the same type. Understanding their operations, such as insertion, deletion, and traversal, is critical. Did you know? Almost 25% of problems on LeetCode are array-based!

Linked Lists: Unlike arrays, linked lists have nodes connected by pointers. Mastering their types (singly, doubly) and operations can set you on the right track.

Hash Tables: This data structure is vital for optimizing solutions. They store key-value pairs and provide quick access, making them indispensable for problems involving frequencies or grouping. A fun fact – Hash tables are so versatile that their use-cases span from database indexing to caching!

Regular Practice: These are just a few key concepts, and the realm of data structures and algorithms is vast. Regularly practicing and internalizing these structures can dramatically improve your problem-solving skills. According to GeeksforGeeks, understanding these basic data structures can help in solving around 70% of the coding problems in interviews.

3. System Design and Behavioral Interview Preparation

Beyond algorithms and code, a comprehensive interview prep must address system design and behavioral questions. Let's unpack these aspects to ensure you present a holistic version of yourself in the interview.

Preparing for Behavioral Questions: The STAR Format

Why Behavioral Questions Matter: Behavioral questions might feel less technical, but they're just as vital. Companies are keen on understanding your experiences, decision-making process, and how you handle challenges. After all, a great coder with poor interpersonal skills might not be an asset in team projects.

The STAR Technique: This is your secret weapon to nail behavioral questions.

Situation: Begin by describing the context or backdrop.
Task: What were you responsible for?
Action: Detail the specific steps you took to address the task.
Result: Conclude with the outcome of your actions.

For example, when asked about a time you faced a tight deadline, you could discuss a project, explain your responsibility, describe how you prioritized tasks, and finally, share the successful completion or lessons learned. solution

A CareerBuilder survey highlighted that 62% of employers are looking for candidates who can effectively communicate – and using the STAR format is an excellent method to demonstrate this ability.

On-Site Interview: Personality Questions and Skill Tests

The All-Encompassing On-Site: After initial rounds, many companies invite candidates for an on-site interview. This comprehensive round aims to assess both your technical prowess and personality fit.

Personality Questions: Here, interviewers want to gauge how well you'd mesh with the company culture. They might ask about your preferred work environment, teamwork experiences, or how you handle criticism.

Skill Tests: While earlier rounds test foundational skills, on-site rounds might involve deeper dives into specialized areas. For instance, if you're applying for a web developer role, you might be asked to critique a website's design or pinpoint performance bottlenecks.

A tip to remember: on-site interviews can be draining. A study by Glassdoor indicated that software engineer interviews, especially at top tech companies, can last more than two hours. So, ensure you’re well-rested and hydrated!

To sum up this section, while technical skills can get your foot in the door, your behavioral responses and on-site performance can seal the deal. Approach them with the same rigor as you would a coding challenge. The more holistic your preparation, the better equipped you are to impress potential employers!

4. Commonly Asked Interview Questions for Software Engineers

Cracking a software engineering interview often requires familiarity with frequently asked questions. While each interview can be unique, several core questions test foundational skills and thought processes. Let's unravel some of these typical questions.

Technical Questions

Algorithm Challenges:
- "Given an array of integers, find two numbers such that they add up to a specific target number." solution
- "Given a positive integer, check if it is a prime number or not." solution
- "Given a stair with 'n' steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps." solution

Why they're asked: These gauge your algorithmic thinking and problem-solving prowess. Such questions assess if you can develop efficient solutions to common coding challenges.

Check Grokking the Coding Interview for top coding patterns for interviews.

Data Structures:
- "Explain the difference between a stack and a queue."
- "How would you implement a hash table?"

Insight: Data structures are the backbone of software engineering. Employers want to ensure you have a firm grip on these concepts, as they play a pivotal role in real-world applications.

Databases:
- "Can you explain the difference between SQL and NoSQL?"
- "How would you optimize a slow-performing query?"

Takeaway: As data drives decisions in today's digital age, knowledge of databases is imperative. These questions assess your understanding of data storage, retrieval, and optimization.

Conceptual and Design Questions

Software Design Patterns:
- "Can you explain the Singleton pattern and its use cases?"
- "What’s the difference between MVC and MVVM patterns?"

Purpose: These questions aim to understand if you're aware of established patterns that streamline software development, ensuring consistency and efficiency.

System Design:
- "How would you design a scalable global chat system like WhatsApp or Facebook Messenger?" solution
- "Describe the architecture you'd suggest for an e-commerce platform." solution

Understanding: System design questions evaluate your broader perspective on software. They're not just about writing code but about how different components interact in a system.

Soft Skill and Behavioral Questions

Teamwork and Collaboration:

"Describe a time when you disagreed with a team member. How did you resolve it?"
"Tell me about a challenging team project and your role in it."

The Rationale: Companies are keen on team players. These questions gauge your ability to collaborate, communicate, and sometimes, compromise for the greater good.

Motivation and Passion:

"Why did you choose a career in software engineering?"
"What coding project are you most proud of, and why?"

The Reason: Passion often drives excellence. Interviewers want to see if you're genuinely enthusiastic about coding and if you'll bring that zest to the workplace.

To sum up, while technical prowess is vital, a holistic approach to these questions can set you apart. It's not always about the right answer but the journey you take to arrive there. Stay informed, practice regularly, and always approach questions with a problem-solving mindset. Remember, each question is an opportunity to showcase your expertise and passion!

Acing the Coding and Whiteboard Exercises

In the realm of software engineering interviews, coding challenges and whiteboard exercises are the ultimate proving ground. These hands-on tests assess your ability to translate abstract problems into tangible solutions. Let's delve into strategies to shine in these exercises.

Conquering the Whiteboard Exercise

1. Understand Before You Write: Before diving in, clarify any ambiguities. Asking questions not only showcases your thoroughness but ensures you're on the right track. As stated by TechCrunch, nearly 45% of interviewers are impressed when candidates ask insightful questions.

2. Start with a Brute Force Solution: It's okay to begin with a simple solution. Once outlined, you can then refine for better efficiency.

3. Explain Your Thought Process: Articulation is crucial. The whiteboard isn't just about the final solution, but the journey to get there. A LinkedIn survey emphasized that 92% of hiring professionals value soft skills, like communication, equally or more than technical abilities.

4. Test with Real-World Examples: After jotting down your approach, walk through a real-world example. This checks the feasibility of your solution and potentially uncovers any oversights.

5. Embrace Feedback: Sometimes, interviewers might play devil's advocate or suggest modifications. Rather than being defensive, adapt and iterate. This shows resilience and a willingness to learn.

Navigating Coding Challenges

1. Optimize Your Workspace: Whether it's an online IDE or a platform specified by the company, ensure you're familiar with the environment. A clutter-free, familiar workspace can significantly reduce unnecessary stress.

2. Time Management: Most coding challenges are timed. Break down your total time – a fraction for understanding, a chunk for coding, and the remainder for testing. According to a report by HackerRank, 70% of employers zero in on problem-solving skills during coding tests. Being systematic can help manifest this skill.

3. Edge Cases are Crucial: It's not enough to just solve the problem. Ensure your solution caters to edge cases. This demonstrates thoroughness and deep understanding.

4. Maintain Clean Code: Remember, it's not just about getting the solution but the quality of your code. Consistent naming conventions, comments, and modular code reflect professionalism and attention to detail.

5. Stay Calm and Debug: Bugs are inevitable. If something goes awry, stay composed. A structured approach to debugging showcases your problem-solving aptitude under pressure.

Conclusion: Your Next Steps for Software Engineer Interview Success

You've traversed the depths of interview preparation, from understanding the intricacies of the process to nailing whiteboard challenges. Yet, as we wrap up this guide, it's pivotal to remember that preparation is an evolving journey, not a destination. So, what should be your subsequent steps for ensuring success?

Continuous Learning

The Tech Landscape is Dynamic: Software engineering is perpetually evolving. Stay updated with emerging technologies, languages, and industry trends. A survey by Stack Overflow emphasizes that 75% of developers learn a new technology every year. Be part of that proactive majority.

Mock Interviews

Practice Makes Perfect: Beyond solitary preparation, engage in mock interviews. Platforms like Pramp or Design Gurus offer real-time practice with peers or industry professionals. This not only sharpens your skills but offers invaluable feedback from a third-person perspective.

Build and Reflect

Your Portfolio Speaks Volumes: Regularly update your GitHub or portfolio with projects that you're passionate about. But don't just build – reflect on what you've created. Understand the 'why' behind your choices. This introspection aids in articulating your decisions during interviews.

Network and Engage

You're Not Alone: Join local or online tech communities. Engage in discussions, attend webinars, or even participate in hackathons. A study by LinkedIn suggests that 85% of jobs are filled via networking. So, don't underestimate the power of genuine connections.

Self-care

A Healthy Mind in a Healthy Body: While technical prowess is vital, mental and physical well-being is paramount. Regular breaks, hobbies, and even meditation can significantly reduce stress. After all, a relaxed mind can think clearer and innovate better.

In essence, your journey towards software engineering interview success is a blend of technical mastery, continuous learning, and holistic well-being. It's not about memorizing solutions but understanding and enjoying the process. So, embrace the journey, celebrate small victories, and remember that every interview, whether successful or not, is a stepping stone to your ultimate goal. Keep coding, keep learning, and most importantly, keep believing in yourself!

Follow me on LinkedIn and medium to get more insights on tech interviews.

Top LeetCode Patterns for FAANG Coding Interviews

Arslan Ahmad — Fri, 29 Jul 2022 11:29:00 +0000

Preparing for coding interviews can be made easier by focusing on coding patterns. Every software engineer should learn coding patterns such as Sliding Window, Two Pointers, Two Heaps, etc. By doing so, software engineers will be able to develop the skill of “mapping a new problem to an existing one.” In this post, we will learn which coding patterns have the highest return on investment for software engineers.

Grokking the Coding Interview came up with a list of 18 patterns for coding questions based on the similarities in the techniques needed to solve them. The course’s idea is to teach famous coding patterns so that once someone is familiar with a pattern, they will be able to solve dozens of problems with it.

LeetCode Problems Distribution

LeetCode (LC), being the largest repository of coding problems, contains more than 2k+ questions. Each question on LC can be tagged with one or more topics. These topics are either data structures like Array, HashTable, Tree, etc., or algorithmic techniques like Greedy, Divide and Conquer, Sorting, etc., or coding patterns like Sliding Window, Depth First Search, Topological Sort, etc. Here is the topic distribution for LC questions:

The top topic is Array with 1142 problems, followed by String with 549 problems, and so on. Let’s take a closer look at each category of topics, namely Data Structures, Algorithms, and Coding Patterns.

Top Data Structures with Best ROI

Here are the top Data Structures with the highest return on investment:

Array (1142 problems)
String (549)
Hash Table (392)
Tree (191)
Matrix (171)
Stack (128)
Heap or Priority Queue (107)
Graph (102)
Linked List (69)
Trie (44)

Top Algorithmic Techniques with Best ROI

Here are the top algorithmic techniques with the highest return on investment:

Dynamic Programming (383)
Sorting (253)
Greedy (248)
Binary Search (186)
Backtracking (91)
Recursion (44)
Divide and Conquer (38)

Top Coding Patterns with Best ROI

Here are the top coding patterns with the highest return on investment:

Depth First Search (250)
Breadth First Search(198)
Binary Search (186)
Two Pointers (147)
Sliding Window (72)
Monotonic Stack (44)
Union Find (63)
Memoization (32)
Topological Sort (28)
Segment Tree (27)

Best Coding Patterns with Highest ROI

Combining all categories from the above data, here is the list of best coding patterns/techniques with the highest ROI:

1. Two Pointers (Arrays, Strings, Fast & Slow Pointer)
This pattern covers a huge set of questions related to Arrays and Strings, which are the highest tagged data structures. Fast & Slow Pointer can be easily understood as a variation of the Two Pointers pattern.

2. Sliding Window (Arrays, Strings, Hash Tables)
Sliding Window covers most of the problems related to top data structures like Arrays, Strings, and HashTables.

3. Tree and Graph Depth First Search (Matrix Traversal)
Most Trees and Graphs problems can be solved using Depth First Search (DFS). Matrix Traversal, which is also DFS based pattern, covers most of the matrix-related problems.

4. Tree and Graph Breadth First Search (Queue, Subsets, Matrix Traversal, Topological Sort)
Breadth First Search (BFS) is a very handy pattern. BFS’s patterns like Subsets, Matrix Traversal, and Topological Sort cover a good number of problems.

5. Binary Search (Arrays)
Binary Search and its variants are used to solve a huge number of coding questions.

6. Interval Merge
Although there are not many problems related to Interval Merge, these problems frequently appear in coding interviews.

7. Recursion/Backtracking
Backtracking and recursion are used to solve a wide range of problems. Mastering these techniques is highly recommended.

Conclusion

Most programming interviews include LeetCode-type questions. Software engineers practice such coding problems before interviews. The highest return on investment is achieved by preparing smartly and focusing on the problem patterns. You can learn more about these patterns and related problems in Grokking the Coding Interview and Grokking Dynamic Programming for Coding Interviews.

Preparing for system design interviews, see this: The Complete Guide to Ace the System Design Interview

System Design Interview Question: Designing a URL Shortening Service

Arslan Ahmad — Sun, 02 Jan 2022 01:25:00 +0000

How to design a URL shortening service like TinyURL?

Software engineers usually struggle with system design interviews partly due to their lack of experience developing large-scale systems and partly due to the unstructured nature of system design interviews. Even advanced and experienced developers find system design interviews challenging since the design questions are open-ended and have no standard answer. To help with that, in my previous post, we discussed a step-by-step approach for solving system design interview questions. Let’s follow that approach to solve a classical system design question: Designing a URL shortening service like TinyURL.

Question Statement: Let’s design a URL shortening service like TinyURL. This service will provide short aliases redirecting to long URLs.

1. Why do we need URL shortening?

URL shortening is used to create shorter aliases for long URLs. Let’s call these shortened aliases “short links.” Users are redirected to the original URL when they hit these short links. Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs.
For example, when we shortened this page through TinyURL:

https://www.designgurus.io/course/grokking-the-system-design-interview

We got:

https://tinyurl.com/vzet59pa

The shortened URL is nearly one-third the size of the actual URL.

URL shortening is used to optimize links across devices, track individual links to analyze audience, measure ad campaigns’ performance, or hide affiliated original URLs.
If you haven’t used tinyurl.com before, please try creating a new shortened URL and spend some time going through the various options their service offers. This will help you a lot in understanding this chapter.

2. Requirements and Goals of the System

Our URL shortening system should meet the following requirements:

Functional Requirements:

Given a URL, our service should generate a shorter and unique alias of it. This is called a short link. This link should be short enough to be easily copied and pasted into applications.
When users access a short link, our service should redirect them to the original link.
Users should optionally be able to pick a custom short link for their URL.
Links will expire after a standard default timespan. Users should be able to specify the expiration time.

Non-Functional Requirements:

Such a system should be highly available. This is required because, if our service is down, all the URL redirections will start failing.
URL redirection should happen in real-time with minimal latency.
Shortened links should not be guessable (not predictable).

Extended Requirements:

Analytics; e.g., how many times a redirection happened?
Our service should also be accessible through REST APIs by other services.

3. Capacity Estimation and Constraints

Our system will be read-heavy. There will be lots of redirection requests compared to new URL shortenings. Let’s assume a 100:1 ratio between read and write.

Traffic estimates

Assuming, we will have 500M new URL shortenings per month, with 100:1 read/write ratio, we can expect 50B redirections during the same period: 100 * 500M => 50B

What would be Queries Per Second (QPS) for our system? New URLs shortenings per second: 500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s

Considering 100:1 read/write ratio, URLs redirections per second will be: 100 * 200 URLs/s = 20K/s

Storage estimates

Let’s assume we store every URL shortening request (and associated shortened link) for 5 years. Since we expect to have 500M new URLs every month, the total number of objects we expect to store will be 30 billion: 500 million * 5 years * 12 months = 30 billion

Let’s assume that each stored object will be approximately 500 bytes (just a ballpark estimate–we will dig into it later). We will need 15TB of total storage: 30 billion * 500 bytes = 15 TB

Bandwidth estimates

For write requests, since we expect 200 new URLs every second, total incoming data for our service will be 100KB per second: 200 * 500 bytes = 100 KB/s

For read requests, since every second we expect ~20K URLs redirections, total outgoing data for our service would be 10MB per second: 20K * 500 bytes = ~10 MB/s

Memory estimates

If we want to cache some of the hot URLs that are frequently accessed, how much memory will we need to store them? If we follow the 80–20 rule, meaning 20% of URLs generate 80% of traffic, we would like to cache these 20% hot URLs.

Since we have 20K requests per second, we will be getting 1.7 billion requests per day: 20K * 3600 seconds * 24 hours = ~1.7 billion

To cache 20% of these requests, we will need 170GB of memory: 0.2 * 1.7 billion * 500 bytes = ~170GB

One thing to note here is that since there will be many duplicate requests (of the same URL), our actual memory usage will be less than 170GB.

4. System APIs

We can have SOAP or REST APIs to expose the functionality of our service. Following could be the definitions of the APIs for creating and deleting URLs:

createURL(api_dev_key, original_url, custom_alias=None, 
user_name=None, expire_date=None)

Parameters:
api_dev_key (string): The API developer key of a registered account. This will be used to, among other things, throttle users based on their allocated quota.
original_url (string): Original URL to be shortened.
custom_alias (string): Optional custom key for the URL.
user_name (string): Optional user name to be used in the encoding.
expire_date (string): Optional expiration date for the shortened URL.
Returns: (string)
A successful insertion returns the shortened URL; otherwise, it returns an error code.

deleteURL(api_dev_key, url_key)

Where “url_key” is a string representing the shortened URL to be retrieved; a successful deletion returns ‘URL Removed’.

How do we detect and prevent abuse? A malicious user can put us out of business by consuming all URL keys in the current design. To prevent abuse, we can limit users via their api_dev_key. Each api_dev_key can be limited to a certain number of URL creations and redirections per some time period (which may be set to a different duration per developer key).

5. Database Design

A few observations about the nature of the data we will store:

We need to store billions of records.
Each object we store is small (less than 1K).
There are no relationships between records — other than storing which user created a URL.
Our service is read-heavy.

Database Schema:
We would need two tables: one for storing information about the URL mappings and one for the user’s data who created the short link.

What kind of database should we use? Since we anticipate storing billions of rows, and we don’t need to use relationships between objects — a NoSQL store like DynamoDB, Cassandra, or Riak is a better choice. A NoSQL choice would also be easier to scale.

6. Basic System Design and Algorithm

The problem we are solving here is how to generate a short and unique key for a given URL.

In the TinyURL example in Section 1, the shortened URL is “https://tinyurl.com/vzet59pa”. The last eight characters of this URL constitute the short key we want to generate. We’ll explore two solutions here:

a. Encoding actual URL

We can compute a unique hash (e.g., MD5 or SHA256, etc.) of the given URL. The hash can then be encoded for display. This encoding could be base36 ([a-z ,0–9]) or base62 ([A-Z, a-z, 0–9]) and if we add ‘+’ and ‘/’ we can use Base64 encoding. A reasonable question would be, what should be the length of the short key? 6, 8, or 10 characters?

Using base64 encoding, a 6 letters long key would result in 64⁶ = ~68.7 billion possible strings.
Using base64 encoding, an 8 letters long key would result in 64⁸ = ~281 trillion possible strings.

With 68.7B unique strings, let’s assume six letter keys would suffice for our system.

If we use the MD5 algorithm as our hash function, it will produce a 128-bit hash value. After base64 encoding, we’ll get a string having more than 21 characters (since each base64 character encodes 6 bits of the hash value). Now we only have space for 6 (or 8) characters per short key; how will we choose our key then? We can take the first 6 (or 8) letters for the key. This could result in key duplication; to resolve that, we can choose some other characters out of the encoding string or swap some characters.

What are the different issues with our solution? We have the following couple of problems with our encoding scheme:
If multiple users enter the same URL, they can get the same shortened URL, which is not acceptable.

What if parts of the URL are URL-encoded? e.g., http://www.designgurus.org/distributed.php?id=design, and http://www.designgurus.org/distributed.php%3Fid%3Ddesign are identical except for the URL encoding.

Workaround for the issues: We can append an increasing sequence number to each input URL to make it unique and then generate its hash. We don’t need to store this sequence number in the database. Possible problems with this approach could be an ever-increasing sequence number. Can it overflow? Appending an increasing sequence number will also impact the performance of the service.

Another solution could be to append the user id (which should be unique) to the input URL. However, if the user has not signed in, we would have to ask the user to choose a uniqueness key. Even after this, if we have a conflict, we have to keep generating a key until we get a unique one.

b. Generating keys offline

We can have a standalone Key Generation Service (KGS) that generates random six-letter strings beforehand and stores them in a database (let’s call it key-DB). Whenever we want to shorten a URL, we will take one of the already-generated keys and use it. This approach will make things quite simple and fast. Not only are we not encoding the URL, but we won’t have to worry about duplications or collisions. KGS will make sure all the keys inserted into key-DB are unique

Can concurrency cause problems? As soon as a key is used, it should be marked in the database to ensure that it is not used again. If there are multiple servers reading keys concurrently, we might get a scenario where two or more servers try to read the same key from the database. How can we solve this concurrency problem?

Servers can use KGS to read/mark keys in the database. KGS can use two tables to store keys: one for keys that are not used yet, and one for all the used keys. As soon as KGS gives keys to one of the servers, it can move them to the used keys table. KGS can always keep some keys in memory to quickly provide them whenever a server needs them.

For simplicity, as soon as KGS loads some keys in memory, it can move them to the used keys table. This ensures each server gets unique keys. If KGS dies before assigning all the loaded keys to some server, we will be wasting those keys–which could be acceptable, given the huge number of keys we have.

KGS also has to make sure not to give the same key to multiple servers. For that, it must synchronize (or get a lock on) the data structure holding the keys before removing keys from it and giving them to a server.

What would be the key-DB size? With base64 encoding, we can generate 68.7B unique six letters keys. If we need one byte to store one alpha-numeric character, we can store all these keys in:

6 (characters per key) * 68.7B (unique keys) = 412 GB.

Isn’t KGS a single point of failure? Yes, it is. To solve this, we can have a standby replica of KGS. Whenever the primary server dies, the standby server can take over to generate and provide keys.

Can each app server cache some keys from key-DB? Yes, this can surely speed things up. Although, in this case, if the application server dies before consuming all the keys, we will end up losing those keys. This can be acceptable since we have 68B unique six-letter keys.

How would we perform a key lookup? We can look up the key in our database to get the full URL. If it’s present in the DB, issue an “HTTP 302 Redirect” status back to the browser, passing the stored URL in the “Location” field of the request. If that key is not present in our system, issue an “HTTP 404 Not Found” status or redirect the user back to the homepage.

Should we impose size limits on custom aliases? Our service supports custom aliases. Users can pick any ‘key’ they like, but providing a custom alias is not mandatory. However, it is reasonable (and often desirable) to impose a size limit on a custom alias to ensure we have a consistent URL database. Let’s assume users can specify a maximum of 16 characters per customer key (as reflected in the above database schema).

7. Data Partitioning and Replication

To scale out our DB, we need to partition it so that it can store information about billions of URLs. Therefore, we need to develop a partitioning scheme that would divide and store our data into different DB servers.

a. Range Based Partitioning

We can store URLs in separate partitions based on the hash key’s first letter. Hence we save all the URL hash keys starting with the letter ‘A’ (and ‘a’) in one partition, save those that start with the letter ‘B’ in another partition, and so on. This approach is called range-based partitioning. We can even combine certain less frequently occurring letters into one database partition. Thus, we should develop a static partitioning scheme to always store/find a URL in a predictable manner.

The main problem with this approach is that it can lead to unbalanced DB servers. For example, we decide to put all URLs starting with the letter ‘E’ into a DB partition, but later we realize that we have too many URLs that start with the letter ‘E.’

b. Hash-Based Partitioning

In this scheme, we take a hash of the object we are storing. We then calculate which partition to use based upon the hash. In our case, we can take the hash of the ‘key’ or the short link to determine the partition in which we store the data object.

Our hashing function will randomly distribute URLs into different partitions (e.g., our hashing function can always map any ‘key’ to a number between [1…256]). This number would represent the partition in which we store our object.

This approach can still lead to overloaded partitions, which can be solved using Consistent Hashing.

8. Cache

We can cache URLs that are frequently accessed. We can use any off-the-shelf solution like Memcached, which can store full URLs with their respective hashes. Thus, the application servers, before hitting the backend storage, can quickly check if the cache has the desired URL.

How much cache memory should we have? We can start with 20% of daily traffic and, based on clients’ usage patterns, we can adjust how many cache servers we need. As estimated above, we need 170GB of memory to cache 20% of daily traffic. Since a modern-day server can have 256GB of memory, we can easily fit all the cache into one machine. Alternatively, we can use a couple of smaller servers to store all these hot URLs.

Which cache eviction policy would best fit our needs? When the cache is full, and we want to replace a link with a newer/hotter URL, how would we choose? Least Recently Used (LRU) can be a reasonable policy for our system. Under this policy, we discard the least recently used URL first. We can use a Linked Hash Map or a similar data structure to store our URLs and Hashes, which will also keep track of the URLs that have been accessed recently.

To further increase the efficiency, we can replicate our caching servers to distribute the load between them.

How can each cache replica be updated? Whenever there is a cache miss, our servers would be hitting a backend database. Whenever this happens, we can update the cache and pass the new entry to all the cache replicas. Each replica can update its cache by adding the new entry. If a replica already has that entry, it can simply ignore it.

9. Load Balancer (LB)

We can add a Load balancing layer at three places in our system:

Between Clients and Application servers
Between Application Servers and database servers
Between Application Servers and Cache servers

Initially, we could use a simple Round Robin load balancer that distributes incoming requests equally among backend servers. This LB is simple to implement and does not introduce any overhead. Another benefit is that if a server is dead, LB will take it out of the rotation and stop sending any traffic to it.

A problem with Round Robin LB is that we do not consider the server load. As a result, if a server is overloaded or slow, the LB will not stop sending new requests to that server. To handle this, a more intelligent LB solution can be placed that periodically queries the backend server about its load and adjusts traffic based on that.

10. Purging or DB cleanup

Should entries stick around forever, or should they be purged? If a user-specified expiration time is reached, what should happen to the link?

If we chose to continuously search for expired links to remove them, it would put a lot of pressure on our database. Instead, we can slowly remove expired links and do a lazy cleanup. Our service will ensure that only expired links will be deleted, although some expired links can live longer but will never be returned to users.

Whenever a user tries to access an expired link, we can delete the link and return an error to the user.
A separate Cleanup service can run periodically to remove expired links from our storage and cache. This service should be very lightweight and scheduled to run only when the user traffic is expected to be low.
We can have a default expiration time for each link (e.g., two years).
After removing an expired link, we can put the key back in the key-DB to be reused.
Should we remove links that haven’t been visited in some length of time, say six months? This could be tricky. Since storage is getting cheap, we can decide to keep links forever.

11. Security and Permissions

Can users create private URLs or allow a particular set of users to access a URL?

We can store the permission level (public/private) with each URL in the database. We can also create a separate table to store UserIDs that have permission to see a specific URL. If a user does not have permission and tries to access a URL, we can send an error (HTTP 401) back. Given that we are storing our data in a NoSQL wide-column database like Cassandra, the key for the table storing permissions would be the ‘Hash’ (or the KGS generated ‘key’). The columns will store the UserIDs of those users that have permission to see the URL.

12. Summary

In my experience, every successful software developer has followed a systematic approach to solve a system design question during an interview. The current interview process requires us to present a reasonable solution within 45 minutes and the key to success is being organized during the system design interview. Hopefully, this step-by-step approach will help you stay on track during the interview.

Please take a look at Grokking the System Design Interview for more system design interview questions:

Designing a file sharing service like Google Drive or Dropbox.
Designing a popular messaging service like Facebook Messenger.
Designing popular social network sites like Twitter or Facebook.
Designing a global video streaming service like Youtube.
Designing a global ride hailing service like Uber.

To learn software architecture and practice advanced system design interview questions take a look at Grokking the Advanced System Design Interview.

System Design Interviews: A Step-By-Step Guide

Arslan Ahmad — Sun, 26 Dec 2021 17:41:00 +0000

How to efficiently manage a 45 minutes system design interview?

System design interviews (SDIs) have gained a lot of focus in the past few years. Now a standard part of every software engineering interview, these interviews assess a candidate’s ability to handle complex systems. Performance in these interviews determines the position and salary offered by the interviewing company. Engineers usually struggle with SDIs partly due to their lack of experience developing large-scale systems and partly due to the unstructured nature of SDIs. Engineers who have experience building such systems still find these interviews uncomfortable, mainly because the design problems are open-ended and have no standard answer.

Generally, software engineers have difficulty with system design interviews for three primary reasons:

SDIs are unstructured, where candidates are asked to take on an open-ended design problem that doesn’t have a standard solution.
Candidates lack experience in developing complex and large-scale systems.
Candidates did not spend enough time preparing for SDIs.

Like coding interviews, candidates who have not put a deliberate effort to prepare for SDIs, mostly perform poorly, especially at top companies like Google, Facebook, Amazon, Microsoft, etc. In these companies, candidates who do not perform above average have a limited chance to get an offer. On the other hand, a good performance always results in a better offer (a higher position and salary) since it proves the candidate’s ability to handle a complex system.

During my professional career, I have taken more than 200 system design interviews. My goal in this post is to provide a step-by-step guide on how to approach system design questions during an interview; it will assist with overcoming the problems highlighted above.

Check Grokking the System Design Interview to learn about important distributed system concepts.

In my experience, candidates who have performed better tend to follow these seven steps:

1. Requirements clarifications: Always ask questions to find the exact scope of the problem you are solving.
2. Back-of-the-envelope estimation: It’s always a good idea to estimate the scale of the system you are going to design. This will also help later, when you will be focusing on scaling, partitioning, load balancing, caching, etc.
3. System interface definition: Define what APIs are expected from the system. This will not only establish the exact contract expected from the system but also ensure that you have not gotten any requirements wrong.
4. Define data model: Defining the system data model early on will clarify how data will flow among different components of the system and later will also guide towards the data partitioning and management.
5. High-level design: Draw a block diagram with 5–6 boxes representing the core components of your system. You should identify enough components that are needed to solve the actual problem from end to end.
6. Detailed design: Dig deeper into 2–3 components; interviewer’s feedback should always guide you towards which parts of the system she wants you to explain further. You should be able to provide different options, their pros and cons, and why are you choosing them?
7. Identifying and resolving bottlenecks: Try to discuss as many bottlenecks (and different approaches to mitigate them) as possible.

Let’s discuss each step in detail with a real case study:

Step 1: Requirements clarifications

It is always a good idea to ask questions about the exact scope of the problem we are solving. Design questions are mostly open-ended, and they don’t have ONE correct answer; that’s why clarifying ambiguities early in the interview becomes critical. Candidates who spend enough time defining the end goals of the system always have a better chance to be successful in the interview. Also, since we only have 35–40 minutes to design a (supposedly) large system, we should clarify what parts of the system we will be focusing on.

Let’s expand this with an actual example of designing a Twitter-like service. Here are some questions for designing Twitter that should be answered before moving on to the next steps:

Will users of our service be able to post tweets and follow other people?
Should we also design to create and display the user’s timeline?
Will tweets contain photos and videos?
Are we focusing on the backend only, or are we developing the front-end too?
Will users be able to search tweets?
Do we need to display hot trending topics?
Will there be any push notification for new (or important) tweets?

All such questions will determine how our end design will look like.

Step 2: Back-of-the-envelope estimation

It is always a good idea to estimate the scale of the system we’re going to design. This will also help later when we will be focusing on scaling, partitioning, load balancing, and caching.

What scale is expected from the system (e.g., number of new tweets, number of tweet views, number of timeline generations per sec., etc.)?
How much storage will we need? We will have different storage requirements if users can have photos and videos in their tweets.
What network bandwidth usage are we expecting? This will be crucial in deciding how we will manage traffic and balance load between servers.

Step 3: System interface definition

Define what APIs are expected from the system. This will not only establish the exact contract expected from the system but will also ensure that we haven’t gotten any requirements wrong. Some examples of APIs for our Twitter-like service will be:

postTweet(user_id, tweet_data, tweet_location, timestamp, …)
generateTimeline(user_id, current_time, user_location, …)
markTweetFavorite(user_id, tweet_id, timestamp, …)

Step 4: Defining data model

Defining the data model in the early part of the interview will clarify how data will flow between different components of the system. Later, it will guide for data partitioning and management. The candidate should be able to identify various entities of the system, how they will interact with each other, and different aspects of data management like storage, transportation, encryption, etc. Here are some entities for our Twitter-like service:
User: UserID, Name, Email, DoB, CreationData, LastLogin, etc.
Tweet: TweetID, Content, TweetLocation, NumberOfLikes, TimeStamp, etc.
UserFollowo: UserdID1, UserID2
FavoriteTweets: UserID, TweetID, TimeStamp

Which database system should we use? Will NoSQL like Cassandra best fit our needs, or should we use a MySQL-like solution? What kind of block storage should we use to store photos and videos?

Step 5: High-level design

Draw a block diagram with 5–6 boxes representing the core components of our system. We should identify enough components that are needed to solve the actual problem from end to end.

For Twitter, at a high level, we will need multiple application servers to serve all the read/write requests with load balancers in front of them for traffic distributions. If we’re assuming that we will have a lot more read traffic (as compared to write), we can decide to have separate servers for handling these scenarios. On the backend, we need an efficient database that can store all the tweets and can support a huge number of reads. We will also need a distributed file storage system for storing photos and videos.

Step 6: Detailed design

Dig deeper into two or three major components; the interviewer’s feedback should always guide us to what parts of the system need further discussion. We should be able to present different approaches, their pros and cons, and explain why we will prefer one approach over the other. Remember, there is no single answer; the only important thing is to consider tradeoffs between different options while keeping system constraints in mind.

Since we will be storing a massive amount of data, how should we partition our data to distribute it to multiple databases? Should we try to store all the data of a user on the same database? What issue could it cause?
How will we handle hot users who tweet a lot or follow lots of people?
Since users’ timelines will contain the most recent (and relevant) tweets, should we try to store our data in such a way that is optimized for scanning the latest tweets?
How much and at which layer should we introduce cache to speed things up?
What components need better load balancing?

Step 7: Identifying and resolving bottlenecks

Try to discuss as many bottlenecks as possible and different approaches to mitigate them.
Is there any single point of failure in our system? What are we doing to mitigate it?
Do we have enough replicas of the data so that if we lose a few servers, we can still serve our users?
Similarly, do we have enough copies of different services running such that a few failures will not cause a total system shutdown?
How are we monitoring the performance of our service? Do we get alerts whenever critical components fail, or their performance degrades?

Summary

To sum up, preparing well and being organized during the interview is key to success in a system design interview. The steps mentioned above should guide you to stay on track and cover all the different aspects while designing a system.

Please take a look at Grokking the System Design Interview and Grokking the Advanced System Design Interview for some good examples of system design interview questions and their answers.

Grokking LeetCode: A Smarter Way to Prepare for Coding Interviews

Arslan Ahmad — Thu, 25 Nov 2021 12:17:00 +0000

To LeetCode or not to LeetCode? What if you don’t want to practice 100s of coding questions before your next coding interview?

There is a part of me that dislikes coding interviews, primarily because it requires me to spend a lot of time preparing for coding questions. Moreover, during an interview, I have to present a reasonable (if not optimal) solution to someone who is evaluating me, something I don’t have to deal with in my everyday life as a software engineer.

Having said that, I do love algorithms and solving coding problems. It is a fun activity for me, it gives me good mental exercise, and I love to spend time on it. In this post, I would like to share some of my learnings and the techniques that I’ve developed over time which makes preparing for coding interviews an exciting and fun activity.

A little about me; my software engineering career spans around 20 years, in which I’ve switched jobs five times. I’ve given around 30 interview loops containing 120+ interviews. I have some experience sitting on the other side of the table too. I’ve taken 300+ coding interviews and 200+ system design interviews.

Background

If you are looking to switch jobs and preparing for coding interviews, you will definitely know LeetCode. It is probably the biggest online repository for coding interview questions and also contains a vibrant community to discuss algorithms with other fellow engineers. Whenever I’m free, I love spending time on LeetCode, trying to solve a new coding question, or learning from other smart solutions that people have developed.

Problems with LeetCode

One of the biggest challenges with LeetCode is that it lacks organization; it has a huge set of coding problems, and one feels lost on where to start or what to focus on. What is an ample amount of questions one should go through before considering themselves prepared for their coding interview? I would love to see a streamlined process that can guide me and teach me enough algorithmic techniques to feel confident for the interview. Being a lazy person myself, I wouldn’t say I like to go through 500+ questions.

The Solution

One technique that people often follow is to solve questions related to the same data structure; for example, focusing on questions related to Arrays, then LinkedList, HashMap, Heap, Tree, or Trie, etc. Although this does provide some organization, it still lacks coherence. For example, many questions can be solved using HashMaps but still require different algorithmic techniques. I would love to see question sets that follow not only the same data structure but also similar algorithmic techniques. The best thing I came across was the problem-solving patterns like Sliding Window, Fast and Slow Pointers, or Topological Sort, etc. Following these patterns helped me nurture my ability to map a new problem to an already known problem. This not only made this whole coding-interview-preparation process fun but also a lot more organized.

I have gathered around 25 of these coding problem patterns, which I believe can help anyone learn these beautiful algorithmic techniques and make a real difference in the coding interviews. The idea behind these patterns is, once you’re familiar with a pattern, you’ll be able to solve dozens of problems with it. For a detailed discussion of these patterns and related problems with solutions, take a look at Grokking the Coding Interview.

So, without further ado, let me list all these patterns:

Sliding Window
Two Pointers
Fast & Slow Pointers
Merge Intervals
Cyclic Sort
In-place Reversal of a LinkedList
Tree Breadth-First Search
Tree Depth First Search
Two Heaps
Subsets
Modified Binary Search
Bitwise XOR
Top 'K' Elements
K-way Merge
0/1 Knapsack
Unbounded Knapsack
Fibonacci Numbers
Palindromic Subsequence
Longest Common Substring
Topological Sort
Trie Traversal
Number of Island
Trial & Error
Union Find
Unique Paths

Following is a small intro of each of these patterns with sample problems:

1. Sliding Window

Usage: This algorithm ic technique is used when we need to handle the input data in specific window size.

Sample Problems:

2. Two Pointers

Usage: In this technique, we use two pointers to iterate the input data. Generally, both pointers move in the opposite direction at a constant interval.

Sample Problems:

3. Fast & Slow Pointers

Usage: Also known as Hare & Tortoise algorithm. In this technique, we use two pointers that traverse the input data at a different speed.

Sample Problems:

4. Merge Intervals

Usage: This technique is used to deal with overlapping intervals. Given two intervals ('a' and 'b'), there will be six different ways the two intervals can relate to each other:

Sample Problems:

5. Cyclic Sort

Usage: Use this technique to solve array problems where the input data lies within a fixed range.

Sample Problems:

6. In-place Reversal of a LinkedList

Usage: This technique describes an efficient way to reverse the links between a set of nodes of a LinkedList. Often, the constraint is that we need to do this in-place, i.e., using the existing node objects and without using extra memory.

Sample Problems:

7. Tree Breadth-First Search

Usage: As the name suggests, this technique is used to solve problems involving traversing trees in a breadth-first search manner.

Sample Problems:

8. Tree Depth First Search

Usage: As the name suggests, this technique is used to solve problems involving traversing trees in depth-first search manner.

Sample Problems:

9. Two Heaps

Usage: In many problems, where we are given a set of elements such that we can divide them into two parts. We are interested in knowing the smallest element in one part and the biggest element in the other part. As the name suggests, this technique uses a Min-Heap to find the smallest element and a Max-Heap to find the biggest element.

Sample Problems:
1.Find the Median of a Number Stream

Next Interval

10. Subsets

Usage: Use this technique when the problem asks to deal with permutations or combinations of a set of elements.

Sample Problems:

11. Modified Binary Search

Usage: Use this technique to search a sorted set of elements efficiently.

Sample Problems:

12. Bitwise XOR

Usage: This technique uses the XOR operator to manipulate bits to solve problems.

Sample Problems:

Top 'K' Elements Usage: This technique is used to find top/smallest/frequently occurring 'K' elements in a set.

Sample Problems:

14. K-way Merge

Usage: This technique helps us solve problems that involve a list of sorted arrays.

Sample Problems:

15. 0/1 Knapsack

Usage: This technique is used to solve optimization problems. Use this technique to select elements that give maximum profit from a given set with a limitation on capacity and that each element can only be picked once.

Sample Problems:

16. Unbounded Knapsack

Usage: Use this technique to select elements that give maximum profit from a given set with a limitation on capacity and that each element can be picked multiple times.

Sample Problems:

17. Fibonacci Numbers

Usage: Use this technique to solve problems that follow the Fibonacci numbers sequence, i.e., every subsequent number is calculated from the last few numbers.

Sample Problems:

18. Palindromic Subsequence

Usage: This technique is used to solve optimization problems related to palindromic sequences or strings.

Sample Problems:

19. Longest Common Substring

Usage: Use this technique to find the optimal part of a string/sequence or set of strings/sequences.

Sample Problems:

20. Topological Sort

Usage: Use this technique to find a linear ordering of elements that have dependencies on each other.

Sample Problems:

21. Trie Traversal

Usage: Use this technique that involves creating or traversing of Trie data structure.

Sample Problems:

Longest Word in Dictionary
Palindrome Pairs

22. Number of Island

Usage: Use this technique to traverse a two-dimensional array and find a set of connected elements.

Sample Problems:

Number of Distinct Islands
Maximum Area of Island

23. Trial & Error

Usage: Use this technique to traverse an array to find a required optimal element. The traversal process runs in a trial & error manner.

Sample Problems:

Find Kth Smallest Pair Distance
Minimize Max Distance to Gas Station

24. Union Find

Usage: Use this technique to solve problems that require maintaining a given set of elements partitioned into multiple non-overlapping subsets.

Sample Problems:

Number of Provinces
Bipartite Graph

25. Unique Paths

Usage: Use this technique to find different/optimal ways to traverse a multi-dimensional array.

Sample Problems:

Find Unique Paths
Dungeon Game

Conclusion

Like it or not, LeetCode-type questions are a part of almost every programming interview, so every software developer should practice them before an interview. Their only option is to prepare smartly and learn problem-solving by focusing on the underlying problem patterns. Learn more about these patterns and sample problems in Grokking the Coding Interview and Grokking Dynamic Programming for Coding Interviews.

Check Design Gurus for some interesting courses on Coding and System Design interviews.

Read more about system design coding interviews:

How to Use Consistent Hashing in a System Design Interview?

Arslan Ahmad — Sat, 19 Jun 2021 23:25:03 +0000

While designing a scalable system, one of the most important aspects is defining how the data will be partitioned and replicated across servers.

Let's first define partitioning and replication so that we are on the same page.

Data partitioning: It is the process of distributing data across a set of servers. It improves the scalability and performance of the system.
Data replication: It is the process of making multiple copies of data and storing them on different servers. It improves the availability and durability of the data across the system.

Data partition and replication strategies lie at the core of any distributed system. A carefully designed scheme for partitioning and replicating the data enhances the performance, availability, and reliability of the system and also defines how efficiently the system will be scaled and managed.

David Karger et al. first introduced Consistent Hashing in their 1997 paper and suggested its use in distributed caching. Later, Consistent Hashing was adopted and enhanced to be used across many distributed systems. In this lesson we will see how Consistent Hashing efficiently solves the problem of data partitioning and replication.

What is data partitioning?

As stated above, the act of distributing data across a set of nodes is called data partitioning. There are two challenges when we try to distribute data:

How do we know on which node a particular piece of data will be stored?
When we add or remove nodes, how do we know what data will be moved from existing nodes to the new nodes? Additionally, how can we minimize data movement when nodes join or leave?

A naive approach will use a suitable hash function to map the data key to a number. Then, find the server by applying modulo on this number and the total number of servers. For example:

The scheme described in the above diagram solves the problem of finding a server for storing/retrieving the data. But when we add or remove a server, all our existing mappings will be broken. This is because the total number of servers will be changed, which was used to find the actual server storing the data. So to get things working again, we have to remap all the keys and move our data based on the new server count, which will be a complete mess!

Consistent Hashing to the rescue

Distributed systems can use Consistent Hashing to distribute data across nodes. Consistent Hashing maps data to physical nodes and ensures that only a small set of keys move when servers are added or removed.

Consistent Hashing stores the data managed by a distributed system in a ring. Each node in the ring is assigned a range of data. Here is an example of the consistent hash ring:

With consistent hashing, the ring is divided into smaller, predefined ranges. Each node is assigned one of these ranges. The start of the range is called a token. This means that each node will be assigned one token. The range assigned to each node is computed as follows:

Range start: Token value

Range end: Next token value - 1

Here are the tokens and data ranges of the four nodes described in the above diagram:

Whenever the system needs to read or write data, the first step it performs is to apply the MD5 hashing algorithm to the key. The output of this hashing algorithm determines within which range the data lies and hence, on which node the data will be stored.

The MD5 (aka MD5 Message-Digest Algorithm) is a hashing function that accepts a message of any length as input and returns as output a fixed-length digest value.

As we saw above, each node is supposed to store data for a fixed range. Thus, the hash generated from the key tells us the node where the data will be stored.

The Consistent Hashing scheme described above works great when a node is added or removed from the ring, as in these cases, since only the next node is affected. For example, when a node is removed, the next node becomes responsible for all of the keys stored on the outgoing node. However, this scheme can result in non-uniform data and load distribution. This problem can be solved with the help of Virtual nodes.

Virtual nodes

Adding and removing nodes in any distributed system is quite common. Existing nodes can die and may need to be decommissioned. Similarly, new nodes may be added to an existing cluster to meet growing demands. To efficiently handle these scenarios, Consistent Hashing makes use of virtual nodes (or Vnodes).

As we saw above, the basic Consistent Hashing algorithm assigns a single token (or a consecutive hash range) to each physical node. This was a static division of ranges that requires calculating tokens based on a given number of nodes. This scheme made adding or replacing a node an expensive operation, as, in this case, we would like to rebalance and distribute the data to all other nodes, resulting in moving a lot of data. Here are a few potential issues associated with a manual and fixed division of the ranges:

Adding or removing nodes: Adding or removing nodes will result in recomputing the tokens causing a significant administrative overhead for a large cluster.
Hotspots: Since each node is assigned one large range, if the data is not evenly distributed, some nodes can become hotspots

In a distributed system, any server responsible for a huge partition of data can become a bottleneck for the system. A large share of data storage and retrieval requests will go to that node which can effectively bring the performance of the whole system down. Such loaded servers are called hotspots.
Node rebuilding: Since each node's data might be replicated (for fault-tolerance) on a fixed number of other nodes, when we need to rebuild a node, only its replica nodes can provide the data. This puts a lot of pressure on the replica nodes and can lead to service degradation.

To handle these issues, Consistent Hashing introduces a new scheme of distributing the tokens to physical nodes. Instead of assigning a single token to a node, the hash range is divided into multiple smaller ranges, and each physical node is assigned several of these smaller ranges. Each of these subranges is considered a Vnode. With Vnodes, instead of a node being responsible for just one token, it is responsible for many tokens (or subranges).

Practically, Vnodes are randomly distributed across the cluster and are generally non-contiguous so that no two neighboring Vnodes are assigned to the same physical node or rack. Additionally, nodes do carry replicas of other nodes for fault tolerance. Also, since there can be heterogeneous machines in the clusters, some servers might hold more Vnodes than others. The figure below shows how physical nodes A, B, C, D, & E use Vnodes of the Consistent Hash ring. Each physical node is assigned a set of Vnodes and each Vnode is replicated once.

Advantages of Vnodes

Vnodes gives the following advantages:

As Vnodes help spread the load more evenly across the physical nodes on the cluster by dividing the hash ranges into smaller subranges, this speeds up the rebalancing process after adding or removing nodes. When a new node is added, it receives many Vnodes from the existing nodes to maintain a balanced cluster. Similarly, when a node needs to be rebuilt, instead of getting data from a fixed number of replicas, many nodes participate in the rebuild process.
Vnodes make it easier to maintain a cluster containing heterogeneous machines. This means, with Vnodes, we can assign a high number of sub-ranges to a powerful server and a lower number of sub-ranges to a less powerful server.
In contrast to one big range, since Vnodes help assign smaller ranges to each physical node, this decreases the probability of hotspots.

Data replication using Consistent Hashing

To ensure highly available and durability, Consistent Hashing replicates each data item on multiple N nodes in the system where the value N is equivalent to the replication factor.

The replication factor is the number of nodes that will receive the copy of the same data. For example, a replication factor of two means there are two copies of each data item, where each copy is stored on a different node.

Each key is assigned to a coordinator node (generally the first node that falls in the hash range), which first stores the data locally and then replicates it to 'N-1' clockwise successor nodes on the ring. This results in each node owning the region on the ring between it and its 'Nth' predecessor. In an eventually consistent system, this replication is done asynchronously (in the background).

In eventually consistent systems, copies of data don't always have to be identical as long as they are designed to eventually become consistent. In distributed systems, eventual consistency is used to achieve high availability.

Consistent Hashing in System Design Interviews

As we saw above, Consistent Hashing helps with efficiently partitioning and replicating data; therefore, any distributed system that needs to scale up or down or wants to achieve high availability through data replication can utilize Consistent Hashing. A few such examples could be:

Any system working with a set of storage (or database) servers and needs to scale up or down based on the usage, e.g., the system could need more storage during Christmas because of high traffic.
Any distributed system that needs dynamic adjustment of its cache usage by adding or removing cache servers based on the traffic load.
Any system that wants to replicate its data shards to achieve high availability.

Consistent Hashing use cases

Amazon’s Dynamo and Apache Cassandra use Consistent Hashing to distribute and replicate data across nodes.

References and further reading

Have a look at Grokking the Advanced System Design Interview for some good examples of how distributed systems use Consistent Hashing.

Check Design Gurus for some good courses on Programming and System Design interviews.

The Ultimate Strategy to Preparing for the Coding Interview

Arslan Ahmad — Tue, 13 Aug 2019 09:50:58 +0000

How to prepare more quickly for coding interviews

Coding interviews are getting harder every day. A few years back, brushing up on key data structures and going through 50–75 practice coding interview questions was more than enough prep for an interview. Today, everyone has access to massive sets of coding problems, and they’ve gotten more difficult as well. The overall interview process has gotten more competitive.
In this post, I’d like to share a strategy I follow to prepare for coding interviews. My software engineering career spans around 15 years, in which I’ve switched jobs five times. I’ve given around 30 interview loops containing 120+ interviews. I have some experience sitting on the other side of the table too. I’ve taken 200+ coding interviews and 100+ system design interviews.

I consider myself a reasonably smart engineer, but I had my challenges solving coding problems on a whiteboard, especially in an interview setting with someone evaluating me. To tackle this, I’d spend a reasonable time for preparation and practice. One thing I didn’t realize was that while doing my preparation, I was following a systematic approach. I would go through 12–15 questions, practicing two hours every day. This meant that I could solve 350+ questions within one month. Using this routine, I was able to crack my interviews for FAANGs (Facebook, Apple, Amazon, Netflix, Google).

How was I able to practice 12+ coding questions every day with a fulltime job? Well, I wasn’t solving coding problems but practicing to map problems onto problems that I’d already solved. I used to read a problem and spend a few minutes to map it to a similar problem I’d seen before. If I could map it, I’d focus only on the different constraints this problem had compared to the parent problem. If it was a new problem, then I’d try to solve it and also read around to find smart ways other people used to devise its algorithm. Over time, I developed a set of problem-patterns that helped me quickly map a problem to an already-known one. Here are some examples of these patterns:

If the given input is sorted (array, list, or matrix), then we will use a variation of Binary Search or a Two Pointers strategy.
If we’re dealing with top/maximum/minimum/closest k elements among n elements, we will use a Heap.
If we need to try all combinations (or permutations) of the input, we can either use recursive Backtracking or iterative Breadth-First Search.

Following this pattern-based approach helped me save a lot of preparation time. Once you’re familiar with a pattern, you’ll be able to solve dozens of problems with it. In addition, this strategy made me confident to tackle unknown problems, as I’ve been practicing mapping unknown problems to known ones.

In the remaining post, I will share all the patterns I’ve collected and present sample problems for a few. For a detailed discussion of these and related problems with solutions take a look at Grokking the Coding Interview.

Sample Problem for Binary Search

Bitonic array maximum

Problem statement
Find the maximum value in a given Bitonic array. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array, arr[i] != arr[i+1].

Example: Input: [1, 3, 8, 12, 4, 2], Output: 12

Solution
A bitonic array is a sorted array; the only difference is that its first part is sorted in ascending order, and the second part is sorted in descending order. We can use a variation of Binary Search to solve this problem. Remember that in Binary Search we have start, end, and middle indices and in each step we reduce our search space by moving start or end. Since no two consecutive numbers are the same (as the array is monotonically increasing or decreasing), whenever we calculate the middle index for Binary Search, we can compare the numbers pointed out by the index middle and middle+1 to find if we are in the ascending or the descending part. So:

If arr[middle] > arr[middle + 1], we are in the second (descending) part of the bitonic array. Therefore, our required number could either be pointed out by middle or will be before middle. This means we will do end = middle.
If arr[middle] <= arr[middle + 1], we are in the first (ascending) part of the bitonic array. Therefore, the required number will be after middle. This means we do start = middle + 1.

We can break when start == end. Due to the above two points, both start and end will point at the maximum number of the Bitonic array.

Code
Here is the Java code to solve this problem:

Sample Problem for Two Pointers

Pair with target sum

Problem statement
Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

Write a function to return the indices of the two numbers (i.e., the pair) such that they add up to the given target.

Example: Input: [1, 2, 3, 4, 6], target = 6, Output: [1, 3] (The numbers at index 1 and 3 add up to 6: 2+4=6)

Solution
Since the given array is sorted, a brute-force solution could be to iterate through the array, taking one number at a time and searching for the second number through Binary Search. The time complexity of this algorithm will be O(N*logN). Can we do better than this?

We can follow the Two Pointers approach. We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we’ve found our pair. Otherwise, we’ll do one of two things:

If the sum of the two numbers pointed by the two pointers is greater than the target sum, we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.

Here is the visual representation of this algorithm for the example mentioned above:

Code
Here is what our algorithm will look like:

Sample Problem

K closest points to the origin

Given an array of points in a 2D plane, find K closest points to the origin.
Example: Input: points = [[1,2],[1,3]], K = 1, Output: [[1,2]]

Solution
The Euclidean distance of a point P(x,y) from the origin can be calculated through the following formula:

We can use a Max Heap to find K points closest to the origin. We can start by pushing K points in the heap. While iterating through the remaining points, if a point (say P) is closer to the origin than the top point of the max-heap, we will remove that top point from the heap and add P to always keep the closest points in the heap.

Code
Here is what our algorithm will look like:

Sample Problem

Subsets

Problem statement
Given a set with distinct elements, find all of its distinct subsets.

Example: Input: [1, 5, 3] Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]

Solution
To generate all subsets of the given set, we can use the Breadth-First Search (BFS) approach. We can start with an empty set, iterate through all numbers one-by-one, and add them to existing sets to create new subsets.

Let’s take the aforementioned example to go through each step of our algorithm:

Given set: [1, 5, 3]

Start with an empty set: [[]]
Add the first number (1) to all the existing subsets to create new subsets: [[], [1]];
Add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];
Add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].

Here is the visual representation of the above steps:

Code
Here is what our algorithm will look like:

Sample Problem

Binary Tree Path Sum

Problem Statement
Given a binary tree and a number S, find if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals S.

Solution
As we are trying to search for a root-to-leaf path, we can use the Depth First Search (DFS) technique to solve this problem.

To recursively traverse a binary tree in a DFS fashion, we can start from the root and, at every step, make two recursive calls, one for the left and one for the right child.

Here are the steps for our Binary Tree Path Sum problem:

Start DFS with the root of the tree.
If the current node is not a leaf node, do two things: a) Subtract the value of the current node from the given number to get a new sum => S = S - node.value, b) Make two recursive calls for both the children of the current node with the new number calculated in the previous step.
At every step, see if the current node being visited is a leaf node and if its value is equal to the given number S. If both are true, we have found the required root-to-leaf path, therefore return true.
If the current node is a leaf, but its value is not equal to the given number S, return false.

Code
Here is what our algorithm will look like:

Conclusion

Following these patterns helped me tremendously to save time for my coding interview prep. Take a look at Grokking the Coding Interview and Grokking Dynamic Programming Patterns for Coding Interviews to find more of such patterns and their sample problems.

Check Design Gurus for some good courses on Programming Interviews and System Design interviews.