I.K

Posted on Oct 28

Daily DSA and System Design Journal - 13

#dsa #devjournal #systemdesign #beginners

🧠 Day 13 — Bitmasking & Background Job Communication ⚙️

🧩 DSA Problems [1 hr]

Problem: 3003. Maximize the Number of Partitions After Operations

💡 Approach: Bitwise Operations + Preprocessing + Enumeration

🧠 Intuition

We can modify at most one character in the string.
Without modifications, we can compute all valid partitions easily.
When we introduce one modification, only its local segment changes — everything before and after it remains unaffected.

To analyze this efficiently:

We split the problem into a left segment and right segment around the position of modification.
Each segment tracks:
- 🧩 Number of splits
- 🧮 Character mask (bitwise representation)
- 🔢 Count of distinct characters

Using bit operations lets us quickly track which characters exist in each split.

We then simulate all modification positions and compute the best outcome.

💻 Code

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        n = len(s)
        left = [[0] * 3 for _ in range(n)]
        right = [[0] * 3 for _ in range(n)]

        num, mask, count = 0, 0, 0
        for i in range(n - 1):
            binary = 1 << (ord(s[i]) - ord("a"))
            if not (mask & binary):
                count += 1
                if count <= k:
                    mask |= binary
                else:
                    num += 1
                    mask = binary
                    count = 1
            left[i + 1][0] = num
            left[i + 1][1] = mask
            left[i + 1][2] = count

        num, mask, count = 0, 0, 0
        for i in range(n - 1, 0, -1):
            binary = 1 << (ord(s[i]) - ord("a"))
            if not (mask & binary):
                count += 1
                if count <= k:
                    mask |= binary
                else:
                    num += 1
                    mask = binary
                    count = 1
            right[i - 1][0] = num
            right[i - 1][1] = mask
            right[i - 1][2] = count

        max_val = 0
        for i in range(n):
            seg = left[i][0] + right[i][0] + 2
            tot_mask = left[i][1] | right[i][1]
            tot_count = bin(tot_mask).count("1")
            if left[i][2] == k and right[i][2] == k and tot_count < 26:
                seg += 1
            elif min(tot_count + 1, 26) <= k:
                seg -= 1
            max_val = max(max_val, seg)
        return max_val

⚙️ Key Learnings

Bitmasking enables constant-time distinct character tracking.
Dividing problems into left and right contexts simplifies otherwise complex state management.
Enumerating possible modifications systematically ensures you don’t miss edge cases.

🏗 System Design — Roadmap.sh [1 hr]

💬 Returning Results from Background Jobs

Background jobs often run asynchronously — decoupled from the main request-response cycle.
But what happens when the caller needs to know if the background task:

finished successfully? ✅
failed? ❌
or made progress? 🔄

That’s where communication mechanisms come in.

🧩 Common Strategies

Method	Description
🧾 Status Store	The job writes its progress or results to a shared datastore (DB, Redis). The UI polls or queries it.
📬 Reply Queue	A “reply-to” queue receives messages from the job — includes `ReplyTo` and `CorrelationId` for mapping results to requests.
🌐 API Endpoint	The job exposes an API for clients to request status updates or results.
🔔 Callback / Webhook	The job calls back to the client via API or publishes an event when it completes.

🧠 Example Scenarios

🧮 Report Generation: The user triggers a report → background job runs → result stored in S3 → UI polls until ready.
🔄 Machine Learning Pipeline: Background task publishes progress to a queue; dashboard listens for updates.
📦 Order Processing: System publishes “order completed” event via a message bus; microservices subscribe to react accordingly.

⚠️ Design Considerations

Concern	Description
🧱 Reliability	Messages or writes can fail — implement retries and acknowledgements.
🧩 Idempotence	Duplicate completion messages shouldn’t cause inconsistencies.
⏳ Timeouts & TTLs	Define how long clients should wait for results.
📡 Scalability	For large systems, prefer async event-driven feedback over polling.

🧠 Reflection

This day beautifully mirrors the DSA concept:

In the algorithm, you used bit-level precision to track states efficiently.
In system design, you used communication-level precision to synchronize async processes.

Both are about smart tracking and controlled feedback — small signals, big coordination.

✅ Day 13 Summary:

Progress isn’t just computation — it’s communication. Systems (and developers) that report back effectively scale gracefully. 🚀

DEV Community