DEV Community

Cover image for Daily DSA and System Design Journal - 15
I.K
I.K

Posted on

Daily DSA and System Design Journal - 15

#dsa #systemdesign #beginners #devjournal

🧩 Day 15 — Sum of Good Subsequences & CDN Fundamentals

🧠 DSA Problems [1 hr]

Problem: 3351. Sum of Good Subsequences

💡 Approach: Dynamic Programming on Value Links

🧠 Intuition

We define two key state trackers:

  • count[a] — number of good subsequences ending with a.
  • res[a] — total sum of all subsequences ending with a.

For each number a in the array:

  • We can start a new subsequence with a.
  • Or extend subsequences ending with a - 1 and a + 1.

Hence,

count[a] = count[a-1] + count[a+1] + 1
Enter fullscreen mode Exit fullscreen mode

Each of these subsequences contributes additional sums based on their totals and the value a:

res[a] = res[a-1] + res[a+1] + a * (count[a-1] + count[a+1] + 1)
Enter fullscreen mode Exit fullscreen mode

We take modulo 10^9 + 7 to keep values bounded.
Finally, the total sum of all subsequences is sum(res.values()).

💻 Code Implementation 

class Solution:
    def sumOfGoodSubsequences(self, A: List[int]) -> int:
        count = Counter()
        res = Counter()
        mod = 10 ** 9 + 7

        for a in A:
            count[a] += count[a - 1] + count[a + 1] + 1
            count[a] %= mod

            res[a] += res[a - 1] + res[a + 1] + a * (count[a - 1] + count[a + 1] + 1)
            res[a] %= mod

        return sum(res.values()) % mod
Enter fullscreen mode Exit fullscreen mode

⚙️ Complexity

Measure Complexity
⏱ Time O(n)
💾 Space O(n)

🧩 Key Insight

  • The solution uses local adjacency relationships (a-1, a+1) to form global subsequence sums.
  • This is a clean example of DP with aggregation via counters instead of full DP arrays — space-efficient and value-oriented.
  • The transitions mimic propagation through neighboring states — a pattern common in DP, graph traversal, and even distributed systems.

🌍 SYSTEM DESIGN — Roadmap.sh [1 hr]

🌐 Content Delivery Networks (CDNs)

A CDN is a globally distributed network that serves web content from servers closer to users, drastically improving latency and scalability.

When you load a site like www.netflix.com, your assets (images, CSS, JS, videos) are often fetched from a nearby CDN edge node — not from Netflix’s origin servers.

⚙️ How It Works

  1. A client requests a resource (e.g., image or video).
  2. DNS resolves the domain to the nearest CDN edge server.
  3. If cached, content is served immediately.
  4. If not, the edge server fetches it from the origin server, caches it, and serves the user.

This reduces latency, distributes load, and saves bandwidth at the origin.

🧱 Types of CDNs

🔹 Push CDN
  • Content is pushed manually or via automation to CDN nodes when it changes.
  • You control cache invalidation and content updates.
  • Best for sites with low traffic or infrequent updates.
  • ✅ Pros: Less redundant traffic, predictable storage.
  • ⚠️ Cons: Manual management, risk of stale content.
🔹 Pull CDN
  • CDN fetches content on demand when requested for the first time.
  • Cached locally afterward for future users.
  • Ideal for high-traffic or dynamic sites.
  • ✅ Pros: Easier setup, automatic caching.
  • ⚠️ Cons: First-request latency, possible redundancy if TTL is too short.

⏳ TTL (Time To Live)

Each cached item has a TTL — after which it expires and must be re-fetched from the origin.
Finding the right TTL is crucial for balancing freshness vs. efficiency.

⚖️ CDN Trade-offs

Advantage Disadvantage
⚡ Faster content delivery 💰 Extra cost based on bandwidth usage
🧭 Global scalability 🕓 Risk of stale content if updates happen before TTL expires
🧱 Reduced load on origin servers 🔗 Requires rewriting URLs for CDN routing

🔍 Example Providers

  • Cloudflare — strong free tier, DDoS protection
  • AWS CloudFront — deep AWS integration
  • Akamai, Fastly, Google Cloud CDN — high-performance enterprise-grade CDNs

🧠 Reflection

Today’s DSA and System Design topics beautifully align:

DSA Concept CDN Analogy
Local adjacency propagation Content caching propagation across edge nodes
Dynamic aggregation via neighbors Dynamic content refresh via TTL and caching rules
O(1) lookups via Counter Constant-time retrieval via global CDN caches

Both rely on localized computation to achieve global efficiency.

✅ Day 15 Summary:

From subsequences to CDNs — efficiency grows when we connect adjacent states and cache intelligently. 🚀

Top comments (0)