Dynamic Programming

Shalini Goyall — Wed, 07 Jan 2026 10:12:29 +0000

Sample Code

dp = [0] * (W + 1)
for weight in weights:
    for w in range(W, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)

tutorial video :

https://www.youtube.com/watch?v=kvyShbFVaY8

Easy (Knapsack Basics)

Medium (Classic 0/1 Knapsack)

System Design : Calendar App

Shalini Goyall — Tue, 06 Jan 2026 20:41:05 +0000

Functional Requirement

create event , modify event , cancel event
user should be able to view calendar daily , weekly or yearly
user should be able to set tup recurring meeting
send notification for any change via email.

Non functional requirement

High availability >> consistency ( eventaul consitency for syncing events)
should support 1B User
low latency to view calendar.
read >> write

Models

User
event
Recurrence

APIs

POST /events/

{
   title 
   userId ( creator)
   userIds []
   start time
   end time
   json blob content - > video call link , description
   - recurrence schedule > weekly , biweekly , monhtly or yearly
}

GET / events/startDay=?&&endDay=? return -> List of events

High Level Design

Deep Dives

1. How to store data into DB for daily or recurring events. Explain it with example.

Event Creation & Storage

Case 1: Simple (One-Time) Event

Example

Doctor Appointment
Jan 10, 3:00–4:00 PM (UTC)

events table (single row)

| event_id | owner_id | title              | start_time_utc   | end_time_utc     | rrule | tz  | version |
| -------- | -------- | ------------------ | ---------------- | ---------------- | ----- | --- | ------- |
| evt_101  | user_1   | Doctor Appointment | 2025-01-10 15:00 | 2025-01-10 16:00 | NULL  | UTC | 1       |

GET Behavior

Row is returned
Rendered directly
No expansion needed

Case 2: Recurring Event (Weekly)

Example

Team Sync
Every Monday, 10–11 AM
Starting Jan 6, 2025

`events` table (still ONE row)

| event_id | owner_id | title     | start_time_utc   | end_time_utc     | rrule                | tz  | version |
| -------- | -------- | --------- | ---------------- | ---------------- | -------------------- | --- | ------- |
| evt_201  | user_1   | Team Sync | 2025-01-06 10:00 | 2025-01-06 11:00 | FREQ=WEEKLY;BYDAY=MO | UTC | 1       |

GET Behavior (Week View)

Fetch base row
Expand rule only for requested range
Generate occurrences in memory

Case 3: Recurring Event with Exception (One Cancellation)

Example

Team Sync
Cancelled only on Jan 20

event_exceptions` table

| exception_id | event_id | exception_date | type      |
| ------------ | -------- | -------------- | --------- |
| ex_301       | evt_201  | 2025-01-20     | CANCELLED |

GET Behavior (Week of Jan 20)

Expand weekly rule → Jan 20 occurrence
Match exception → drop occurrence
Return remaining events

Why This Storage Model Scales

Scenario	Rows Stored
One-time event	1
Weekly for years	1
Weekly + N exceptions	1 + N

✅ Minimal storage
✅ Fast queries
✅ No occurrence explosion

2. View generation and low latency

User flow :
- Client fetch data from server.
- Server fetch data from DB.
- Server expands events for a time range

Server send list of events to client

Optimisation for low latency to get result :

Redis cache : Server can push the events to Redis. When user wants to see the events in couple of hours, it made request to server. server first look into redis and serve. If events are not present , then server made call to DB, fetch events from DB and push to client and redis.

Pros :
- Simple client - no extra logic on client side.
- Consistent shared views

Cons
- Redis explosion at scale
- Hard cache invalidation
- Per-user views don’t reuse well
- Expensive at 1B users

Conclusion:
❌ Not ideal for massive scale.

Client side expansion + SQLite (Hybrid)

User Flow
- User made request to Server.
- Server sends events rules , exceptions to client.
- Client expands events to multiple events
- Client saves occurrences into SQL lite DB.

Pros
- Extremely fast UI
- Offline support
- No server-side expanded cache
- Scales naturally with users

Cons
- More complex client
- Server must manage sync carefully

Conclusion:
✅ Preferred at very large scale.

3. Conflict Detection and Locking Strategy

Optimistic Locking (Default)
- low contention
- best of personal calendar
- retry logic should be there in service.
Pessimistic Locking
- High contention calendars to avoid race condition.
- Lock many rows.

4. Multi-Device Sync ( push and pull)

Pull (Delta Sync) Used for:
- Cold start
- Reconnect
- Missed updates
Push (SSE / Push Notifications)
- Fetches updated rule
- Re-expands locally
- Updates SQLite + UI
SSE preferred:
- One-way
- Lightweight
- Battery friendly
Hybrid model -> Push for freshness, pull for correctness.

5. Database Choice: SQL vs NoSQL

Why SQL works well:
- Strong consistency
- Transactions
- Overlap queries
- Recurrence rules stored efficiently

This is not write-heavy, so SQL scales well.

No SQL tradeoffs

Issue	Explanation
Conflict checks	Hard without transactions
Recurrence queries	Poor fit
Consistency	Eventual by default.
Complexity	Higher for correctness

DEV Community: Shalini Goyall

Dynamic Programming

System Design : Calendar App

GET Behavior

Why This Storage Model Scales