Www.hellointerview.com

Sample Problem

You are given two integer arrays:

• greeds, where greeds[i] represents the minimum size of a cookie that a child needs to to be satisfied.
• cookies, where cookies[j] represents the size of a cookie.

Assign cookies such that as many children as possible are satisfied. Each child can receive at most one cookie, and each cookie can be given to only one child.

A Greedy Algorithm

def num_satisfied_children(greeds: List[int], cookies: List[int]) -> int:
  greeds.sort()
  cookies.sort()

  count = 0
  g_idx, c_idx = 0, 0
  while g_idx < len(greeds) and c_idx < len(cookies):
    if cookies[c_idx] >= greeds[g_idx]:
      count += 1
      g_idx += 1

    c_idx += 1

  return count

Web Caching

Web caching was the original motivation for consistent hashing. With a web cache, if a browser requests a URL that is not in the cache, the page is downloaded from the server, and the result is sent to both the browser and the cache. On a second request, the page is served from the cache without contacting the server.

Notes

Sharding comes up when a single database won’t work (e.g., hit storage limits, write throughput limits, or read throughput limits) and you need to split your data across multiple independent servers.

For a user-centric social media app, sharding by user_id means all of a user’s posts, likes, and comments live on one shard. User-scoped queries are fast, but “trending posts across all users” become expensive because of hitting every shard and aggregating results. Mutating transations need to account for the distributed nature of the shards, making them complex and slow.

Notes

At a basic level, understand how services talk to each other and what happens when those connections fail or get slow.

For 90% of the use cases, default to HTTP over TCP.

WebSockets and Server-Sent Events (SSE) come up when you need real-time updates. SSE is unidirectional - the client makes an initial HTTP request to open the connection, and the server pushes data down that connection. WebSockets handle bidirectional communication where both sides send messages freely.

Notes

Indexes make database queries fast. Most relational databases use B-trees, which support exact lookups (find user with email X) and range queries (find all orders between date A and date B). Hash indexes are faster for exact matches but can’t do range queries.

There are external systems that go beyond what the primary DB provider has. Elasticsearch is the go-to for full-text search. PostGIS in Postgres is popular for geospatial queries. Such extensions typically sync from your primary DB and so the search index will lag slightly behind. However, the increased functionality is usually worth it.

Notes

Choosing what data to store and how to structure it directly affects performance, scalability, and maintenance.

Relational databases are useful when you have structured data with clear relationships and need strong consistency (transaction-based actions, enforcing foreign key constraints). NoSQL databases shine for flexible schemas or when you need to scale horizontally across many servers without complex joins.

Normalization refers to splitting data across tables to avoid duplication, e.g., you have a users table, and orders table, and a products table, where each order references a userId and productId. Normalized data is easy to keep consistent, e.g., updating a product name is limited to the products table. However, getting complete data needs joins, which get expensive on huge/many tables.

Notes

The CAP theorem states that you can only have 2 of 3 properties at once:

• Consistency: All nodes see the same data.
• Availability: Every request gets a response.
• Partition Tolerance: System works even when network connections fail between nodes.

In practice, network partitions are unavoidable in distributed system. Choosing consistency means some nodes will refuse to serve requests rather than return potentially stale data. Choosing availability means different nodes might temporarily have different data.

Notes

For read-heavy applications, storing frequently accessed data in fast memory (e.g., Redis) allows you to skip the DB entirely for some reads. A cache hit on Redis takes ~1ms compared to 20-50ms for a typical DB query, and this speedup is impactful in the order of millions of requests.

Caching requires a solution for invalidating stale data, e.g., user updates their profile in the DB. Strategies include invalidating the cache immediately after writes, using short TTLs, etc.

Notes

For 90% of interviews, default to REST, which maps resources to URLs and uses HTTP methods to manipulate them, e.g., POST /events/{id}/bookings for creating a booking.

When returning large result sets, pagination comes into play. Cursor-based pagination works better for real-time data where new items get added frequently. Offset-based pagination is fine for most cases.

Requirements (~5min)

Functional Requirements

Completions for “Users/Clients should be able to…”, e.g., for Twitter: post tweets, follow other users, and see tweets from users they follow. Keep the list targeted and prioritized (e.g., top 3) as your job is to develop a system that meets those requirements.

Non-Functional Requirements

Completions for “The system should be…”, e.g., for Twitter:

• Highly available, prioritizing availability over consistency.
• Scale to support 100M+ daily active users.
• Low latency, rendering feeds in under 200ms.

#intervals-algorithms

Merge Overlapping Intervals

Problem Statement: Merge Overlapping Intervals

Given an integer array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals. For example \([[1,3],[2,6],[8,10],[15,18]] \to [[1,6],[8,10],[15,18]]\) because \([1,3]\) and \([2,6]\) overlap and merge into \([1,6]\).

Solution: Sort by Start Time and then Linear Scan

Like Minimum Size Subarray Sum , contiguity hints at a linear scan being useful. If we sort intervals by start, then it’s a matter of starting at some intervals[i] and expanding until some intervals[j], \(j > i\) is no longer overlapping.

Problem Description

Given a 1-indexed array of integers that is sorted in non-decreasing order, find two numbers such that they add up to a target number.

Solution: Linear Scan with Binary Search

#binary-search

At its core, the problem is a binary search one. Given \(a\), find \(b = t - a\) in the right side of array. If \(a > \lfloor t / 2 \rfloor\), then there is no possible \(b\) to the right because \(b \ge a\) and \(2a > t\).