DEV Community: Ahmad Ra'fat

Multi-Tenancy Is the Real Agent Platform Problem

Ahmad Ra'fat — Tue, 23 Jun 2026 12:33:46 +0000

Overview

Read on Hashnode

What I have seen when building agent platforms is that most agent demos work because there is only one tenant. One user, one memory store, one tool set, one trace, one notebook, and one happy path. Nothing to keep apart.

Then teams turn the demo into a platform, and prompts stop being the hard part. The hard question becomes a boring one: can every database query, cache key, stream, tool call, trace, and memory lookup prove which tenant it belongs to? If even one of them cannot, you have a leak waiting to happen.

I keep seeing agent-platform conversations start in the wrong place. They open on model choice, orchestration style, or memory quality, and only later get around to the question of whether one tenant's data, tools, costs, and traces stay away from another's.

That boundary is not a hardening task you bolt on at the end. It is the shape of the platform, and you pay for it later if you pretend otherwise.

So here is the mechanism I would look for in a real agent platform: a typed request context, carried into the graph, scoped access at every boundary, and tests that make a tenant leak boring to catch before it becomes an incident.

The Demo Version Hides the Problem

A single-user agent can hold state in memory and still look impressive. It calls a search tool with no tenant filter. It stores chat history under a bare thread_id. It writes traces with raw prompts in them, because nobody else is looking.

But this seems fine, right?

Yes, but only for a demo. Not for a platform.

What changes is the unit of correctness. The agent is no longer just answering "what should I do next?" It is also carrying a boundary through every step it takes. Drop that boundary, and the model can still hand back a perfectly good answer, and you have still failed, because the answer went to the wrong tenant.

If you have worked on multi-tenant platforms before, that means: every operation that touches data, tools, memory, cost, traces, or events must be scoped by tenant before the model gets a chance to improvise.

Multi-Tenant Design Rules for Agent Platforms

These are not agent-specific ideas. This is normal backend security applied to an agent runtime. We translate the multi-tenant and authorization guidelines we already know into the places an agent platform leaks: memory, tools, retrieval, streams, and traces.

Concept	In a multi-tenant platform	In an agent platform
Tenant isolation (source)	Tenant context, cross-tenant access, cache/session isolation, database isolation, file isolation, logging, and audit all need explicit controls.	Agent memory, tools, streams, and traces are tenant-isolation surfaces too.
Retrieval authorization (source)	RAG systems need access-control metadata, retrieval-time authorization, deletion propagation, and tests for cross-tenant retrieval.	Vector filtering is not optional platform glue. It is part of authorization.
Least-privilege tools (source)	Agents need least-privilege tools, explicit authorization for sensitive actions, memory isolation, and safe tool design.	Tool catalogs should be filtered before the model can call them.
Object-level authorization (source)	Every endpoint that acts on an object ID needs an authorization check for that object.	Every tool call, memory lookup, vector search, file read, and background job needs the same object-level check.
Function-level authorization (source)	Function access should be denied by default and granted explicitly by role or policy.	Do not expose every tool to every agent. Scope tools by tenant, role, domain, and action.
No implicit trust (source)	Access decisions should be explicit, per request, and policy-driven.	The graph runtime should not inherit trust from "inside the service." Nodes and tools still need context-aware checks.
Application-boundary enforcement (source)	Cloud-native applications need granular application access controls, service identity, and policy enforcement near application boundaries.	Agent gateways, graph runtimes, and tool services should each enforce policy at their own boundary.
Attribute-based policy (source)	ABAC decisions use subject, object, action, and environment attributes.	Tenant, user, role, tool, target resource, and runtime context belong in the policy decision.
Structural guardrails (source)	Use the simplest agentic shape that works, design tools carefully, and add guardrails where the agent can compound errors.	Applied to tenancy, this means enforcement belongs around tools and data access, not inside a prompt asking the model to behave.
Trace correlation (source)	Context travels across service and process boundaries so telemetry can be correlated.	Trace IDs are not enough. Tenant-safe attributes must be attached deliberately and kept out of untrusted downstream calls.

The agent view says the same thing from another angle, though let me be precise about it: Anthropic is not publishing a multi-tenancy standard. I am taking its tool design and guardrail guidance and pointing it at a tenancy problem.

The principle that carries over is to push enforcement to the most structural layer you have. A prompt is the softest layer there is. A scoped repository, a policy check, or a tenant-aware tool wrapper is harder to bypass.

Where Tenant Context Has to Travel

The first and most common mistake I have seen is treating tenant_id as an HTTP-layer concern. It starts there, but it cannot stay there. In an agent platform, the agent graph is a second execution environment, the tools are a third, and the context has to survive every hop between them.

Read this diagram as three things moving together, none of them moves on its own:

Context: identity, tenant, role, locale, and trace metadata travel from the API layer down into the graph and the tools.
Boundary: every hop is a chance to drop the scope, infer it from the wrong place, or let a caller quietly override it.
Invariant: nothing touches storage, retrieval, cache, a stream, or a trace write until the tenant context is already resolved.

Look at the diagram for a moment. The important path is RequestContext through Agent service, Graph state, Node execution, and Tool wrapper. That is the tenant boundary. Storage, vector search, cache, stream events, and trace attributes should only see a request after that boundary is already present. I would design that path first, before I write a single prompt.

The Mechanism I Would Build

I would start with what not to do: I would not thread tenant_id, user_id, role, locale, and trace_id through every function as five loose parameters. That turns isolation into a copy-paste exercise, and copy-paste is exactly where we forget one.

Instead, I would use a single explicit request context object, and then make every boundary either accept it or fail closed. No third option.

Start With a Typed Context

This code snippet is illustrative. It shows the shape I mean.

from dataclasses import dataclass
from typing import Literal

Role = Literal["owner", "admin", "member", "viewer"]

@dataclass(frozen=True)
class RequestContext:
    # These values should come from trusted auth and membership lookup,
    # not from user-supplied request fields.
    tenant_id: str
    user_id: str
    role: Role
    locale: str
    trace_id: str

    def require_tenant(self) -> str:
        # Missing tenant context is a platform bug. Fail before any model,
        # storage, or tool boundary can run unscoped.
        if not self.tenant_id:
            raise PermissionError("missing tenant context")
        return self.tenant_id

I know it is boring, but that boring little require_tenant function is the whole point. If a background job, a tool, or a graph node tries to run without tenant context, the platform stops right there. Missing scope is not something the model can recover from by trying harder. It is a bug in the platform, and it should fail like one.

Put Context Into the Graph Boundary

If you are building an agent platform, you will have flows or graphs. A useful rule: the graph should pull context from runtime metadata or state, not from the user prompt.

You should never ask the model to remember the tenant for you. The model can reason over data it is allowed to see, but it should never be the decision maker on who owns that data.

Check this illustrative snippet.

async def run_agent(message: str, ctx: RequestContext) -> AgentResult:
    # Keep tenant context outside the user prompt. The model can use allowed
    # data, but it should not enforce ownership.
    state = {
        "messages": [{"role": "user", "content": message}],
        "request_context": ctx,
    }

    return await graph.ainvoke(
        state,
        config={
            "configurable": {
                # Scope the thread so memory/checkpoint lookup cannot
                # collide across tenants.
                "thread_id": f"{ctx.tenant_id}:{ctx.user_id}",
            },
            "metadata": {
                # Metadata is for observability, not authorization.
                "tenant_id": ctx.tenant_id,
                "trace_id": ctx.trace_id,
            },
        },
    )

Be careful when it comes to observability context.

OpenTelemetry baggage can carry account or user identifiers downstream, but its own docs warn that baggage can cross service boundaries and should not contain credentials, API keys, or PII. I would keep tenant IDs opaque and scrub propagation before calling external services.

So you should not let baggage, trace attributes, user headers, or model-visible state be the source of authorization. Treat any incoming propagation header as untrusted until your own auth and membership lookup rebuild the request context from scratch. W3C Baggage has no integrity protection either, making it a carrier of correlation data rather than proof of anything.

The split I keep coming back to is simple. Authorization context comes from trusted auth claims and a membership lookup. Observability context is there to help you debug a request after the decision has already been made. Attaching a safe, opaque tenant tag to a trace so an operator can find a broken flow is fine. Letting that same trace tag decide which documents a tool can read is not, and the gap between those two is where engineers get burned.

Watch the propagation scope too. Internal service-to-service calls may genuinely need tenant-safe correlation metadata. A third-party model call rarely needs your tenant identifier riding along in baggage. If you do need correlation out there, use a request ID that cannot be traced back to a customer or a workspace.

Make Storage APIs Tenant-Scoped by Construction

This is where I want the structural layer to earn its keep.

The query API should make the safe path the short one and the unsafe path the awkward one.

People usually follow the path of least resistance, so make the path of least resistance correct.

class MemoryStore:
    async def list_facts(self, ctx: RequestContext, subject_id: str) -> list[Fact]:
        # Force callers through the tenant-aware API before building a query.
        tenant_id = ctx.require_tenant()
        rows = await db.fetch_all(
            """
            select id, subject_id, fact, source
            from memory_facts
            where tenant_id = :tenant_id
              and subject_id = :subject_id
            order by created_at desc
            """,
            {"tenant_id": tenant_id, "subject_id": subject_id},
        )
        return [Fact.from_row(row) for row in rows]

I do not like APIs like list_facts(subject_id) in a multi-tenant platform. They ask every caller to remember the boundary. That is what fails once the same rule has to be repeated across too many call sites.

The better move is to make the scoped path the only normal path. Pass a RequestContext, a tenant-scoped repository, or a tenant-scoped DB session into the storage layer, and hide the raw unscoped query behind a small internal API that only migrations, repair jobs, and reviewed admin tooling ever touch.

Check this illustrative snippet showing the API I am pointing at:

class TenantMemoryStore:
    def __init__(self, db: Database, tenant_id: str):
        # The tenant is captured once, when the scoped repository is created.
        # Callers cannot forget it on each method call.
        self._db = db
        self._tenant_id = tenant_id

    @classmethod
    def from_context(cls, db: Database, ctx: RequestContext) -> "TenantMemoryStore":
        return cls(db=db, tenant_id=ctx.require_tenant())

    async def list_facts(self, subject_id: str) -> list[Fact]:
        # No tenant argument here. The repository is already scoped.
        rows = await self._db.fetch_all(
            """
            select id, subject_id, fact, source
            from memory_facts
            where tenant_id = :tenant_id
              and subject_id = :subject_id
            order by created_at desc
            """,
            {"tenant_id": self._tenant_id, "subject_id": subject_id},
        )
        return [Fact.from_row(row) for row in rows]

Check this flow showing what I mean:

You may say the payoff here is small. I would agree. But it matters: this shape makes sure the graph node gets handed a repository that is already scoped. It can ask for facts by subject all day long, and there is no spelling of that request that turns into a cross-tenant read.

This is not just a security win. It makes tests cleaner too. A cross-tenant test can call the same public repository method the graph calls, instead of poking around trying to confirm that every caller remembered to tack on tenant_id by hand.

Wrap Tools With Policy Before the Model Sees Them

Another layer we should treat with care is the tools given to the model.

Tools are the place where an agent platform quietly turns into an authorization system, whether you planned for that or not. The model asks for an action. The platform decides whether that action even exists for this tenant and this role.

I would model that as an ABAC decision rather than a role check sprinkled through the codebase wherever someone happened to think of it. The policy input wants the subject, the tenant, the tool or action, the target resource, and the environment.

Implement it with OPA, Cedar behind Amazon Verified Permissions (AVP), OpenFGA, or a plain in-process policy module, whatever fits your stack. None of those choices makes the decision point itself optional.

Check this illustrative example:

class ToolGate:
    def __init__(self, policy: PolicyEngine, registry: ToolRegistry):
        self.policy = policy
        self.registry = registry

    async def call(self, ctx: RequestContext, tool_name: str, args: dict) -> ToolResult:
        tool = self.registry.get(tool_name)

        # Decide before invocation, so the model cannot bypass tenancy by
        # selecting a more powerful tool.
        decision = await self.policy.can_call_tool(
            tenant_id=ctx.tenant_id,
            user_id=ctx.user_id,
            role=ctx.role,
            tool_name=tool_name,
            args=args,
        )

        if not decision.allowed:
            # Return a recoverable denial instead of leaking tool internals.
            return ToolResult.permission_denied(reason=decision.reason)

        return await tool.invoke(ctx=ctx, args=args)

This is the cleanest match to the point of the whole article. The prompt is allowed to describe the behavior you want. The tool gate is what enforces it. And when the two disagree, which they eventually will, code wins.

What Engineers Forget

Some bugs are obvious, like a DB query missing where tenant_id = .... That one is at least visible in code review.

The bugs that actually leak in production are the quiet ones, hiding in the side channels around the agent that nobody thinks of as "the data layer."

Surface	Common mistake	Safer invariant	Risk shape
Redis keys	`chat:{thread_id}`	`tenant:{tenant_id}:chat:{thread_id}`, with opaque IDs where logs may escape.	Easy to miss
Vector search	Embedding search across one shared collection with no metadata filter.	Tenant and permission metadata travel with every chunk, and retrieval-time checks run before context enters the prompt. If the store cannot enforce this reliably, use separate collections or indexes.	High impact
RAG deletion	Deleting the source document but leaving chunks, embeddings, cached answers, or summaries behind.	Deletion and retention rules cover derived artifacts, not only the original blob.	Stale access
File/blob storage	Object keys or signed URLs that are not bound to the tenant and authorization checks.	File reads go through a tenant-aware access layer, even when the blob store is shared.	Direct leak
Streams	Stream names are built from conversation IDs only.	Stream names include tenant scope, and reconnect tokens cannot subscribe across tenants.	Streaming trap
Background jobs	A queued job carries an object ID but not the tenant and actor context that authorized it.	Jobs carry scoped context and recheck permissions before side effects.	Async drift
Rate limits & quotas	Global limits hide noisy-neighbor behavior and per-tenant abuse.	Budget, quota, and rate-limit keys are tenant-scoped before they are user-scoped.	Shared resource
Tool credentials	One service credential is reused for every tenant-specific integration.	Credential lookup is tenant-scoped and action-scoped before tool invocation.	Policy boundary
Evaluation datasets	Regression cases mixed with tenant-specific prompts or documents.	Use synthetic or approved datasets. Never let tenant data leak into shared eval fixtures.	Data hygiene
Traces & logs	Raw prompts, tool payloads, or document snippets in shared observability sinks.	Attach safe tenant tags for observability and incident response only, never as the source of authorization. Redact prompt and tool payloads before shared sinks.	Exposure risk

Tenant Isolation Checklist

If you hand me an agent platform to review, this is the checklist I would open with. It is deliberately practical. No architecture poetry, just the questions that tend to surface a leak.

Layer	Question to ask	What good looks like
HTTP/API	Where does tenant context come from?	Derived from trusted auth claims or membership lookup, not from a user-controlled parameter alone.
Agent graph	Can a node run without context?	No. Missing context fails before model or tool execution.
Tools	Can every agent call every tool?	No. Tool availability is filtered by tenant, role, domain, and action.
Storage	Can a repository method run unscoped?	Repository methods accept `RequestContext` or a tenant-scoped session.
Vector/RAG	Is tenant filtering required by the API, and do chunks carry access-control attributes?	The retrieval function cannot be called without a tenant filter, and permissions are rechecked at retrieval time.
Cache/Streams	Can one tenant guess another tenant's key?	Keys include tenant scope and use opaque IDs where key names might be logged.
Observability	What crosses into logs, traces, and metrics?	Safe identifiers only. PII, prompt payloads, tool payloads, secrets, and sensitive business data are removed before shared sinks.
Tests	Do tests try cross-tenant reads and writes?	Yes. Cover cross-tenant retrieval, cache leakage, stale permissions, background jobs, and unauthorized tool invocation.
Policy	What attributes feed authorization?	Subject, tenant, action, resource, and environment come from trusted auth and membership data, not telemetry or model-visible state.

A Test That Should Exist

A checklist is useful, but I would still want one boring regression test sitting in CI.

This test has tenant A write a fact. Tenant B reads through the normal scoped API and must get nothing back.

Here is the tell: if you can only make that test pass by reaching for a special bypass, your isolation boundary is living in the wrong layer.

Check this illustrative snippet showing the test shape:

async def test_memory_store_does_not_cross_tenants(memory_store):
    # Tenant A and tenant B share the same subject_id on purpose.
    # The tenant boundary, not the subject ID, must isolate the data.
    tenant_a = RequestContext(
        tenant_id="tenant-a",
        user_id="user-a",
        role="member",
        locale="en",
        trace_id="trace-a",
    )
    tenant_b = RequestContext(
        tenant_id="tenant-b",
        user_id="user-b",
        role="member",
        locale="en",
        trace_id="trace-b",
    )

    # Write through the normal tenant-scoped API.
    await memory_store.save_fact(
        tenant_a,
        subject_id="case-123",
        fact="User approved the draft contract.",
    )

    # A second tenant asks for the same subject. The expected result is empty,
    # or a permission error if your API chooses to fail closed more loudly.
    visible_to_b = await memory_store.list_facts(
        tenant_b,
        subject_id="case-123",
    )

    assert visible_to_b == []

I would push for the same test shape for vector retrieval, cache keys, stream subscriptions, background jobs, and tool calls. One small test per surface is a lot cheaper than writing the incident report for a cross-tenant leak after the fact.

An Honest Tradeoff for an MVP

There is one shortcut I can live with early on: org_id = user_id. For a personal-workspace MVP, that can be enough, as long as the interface already treats "organization" as a real concept and membership still comes from trusted auth data rather than a field the user can set.

The shortcut that actually hurts is pretending the concept does not exist at all. Build every table, cache key, graph thread, and tool policy around a user-only model, and the day your first real organization shows up, moving to tenants is a rewrite across the entire platform instead of a swap behind one abstraction.

Here is my take on both shortcuts:

Acceptable early shortcut:

org_id = user_id behind an OrgContext or RequestContext abstraction, with a trusted membership lookup ready to replace it.
Tables already include tenant_id or org_id.
Tests use two tenants, even if each tenant has one user.

Shortcut that ages badly:

User IDs are threaded everywhere by hand, tools read global configuration, and memory keys are plain thread_id.
The first real organization forces a schema and API redesign at the same time.
There is no clean place to add membership.
There is no reliable way to run cross-tenant leak tests, because the platform is fully centered on a single-user model.

What I would recommend here:

If you are going to defer real organizations, keep the tenant-shaped interface anyway. You can always swap the implementation underneath later. What you cannot do cheaply is add the boundary back after every call site has spent six months learning to ignore it.

Take Away

Multi-tenancy is not a feature you add on top of your orchestration. It is the boundary your orchestration runs inside, and the sooner you treat it that way, the less it costs you later.

If you have to do one thing after reading this article, do this: pick a single agent flow and trace the tenant context from the HTTP request all the way to the final tool call. Write down every spot where the context gets copied, inferred, dropped, logged, or turned into a key. That little map is usually where the real work, and the real risk, has been hiding.

Next, I will probably go a level deeper into request-context propagation for agents: how to carry tenant, locale, role, and trace metadata through the graph without polluting every tool signature to do it.

Resources

Make GitHub Contribution Chart fancier

Ahmad Ra'fat — Tue, 06 Feb 2024 09:23:55 +0000

Hello, fellow developers and the GoLang community!

It always bothered me when I opened my GitHub profile and saw my contribution charts empty, while I did commit every day to work on GitLab.

So, I thought why not bring my GitLab commits to Github and make my contribution chart look a bit fancy? ✨✨

As you know you master a programming language by building things with it, so I thought of building a very basic/simple tool using GoLang that does exactly that, fetch my commits from GitLab, specifically the dates of the commits, then push those to a private GitHub repo as an empty commits reserving their dates for history records.

The tool doesn't get any information from GitLab except the dates and pushes them to GitHub as empty commits with a standard commit message.

And my chart transformed like this! 🌟🌟

The tool is designed in a way to support multiple different repository management tools such as BitBucket, but if you need that your contribution is more than welcome!
Currently, only GitLab & GitHub.

Find it here (Make sure to read the ReadMe file): https://github.com/AhmedRaafat14/universal-commits-migrator
Very basic/intuitive docs: https://ahmedraafat14.github.io/universal-commits-migrator/

Thanks

Unveiling PHP Library Development 101: from Basics to Advanced

Ahmad Ra'fat — Sun, 04 Feb 2024 22:27:10 +0000

🚀 PHP Library Development 101 book is out for FREE 🚀

Hello, DEV Community!

I'm excited to offer my book, PHP Library Development 101: From Basics to Advanced for FREE. With nearly a decade of working experience in PHP, I've distilled my learning and discoveries into this book to help others embark on their journey in building PHP libraries.

This book was reviewed by expert PHP developers to ensure the accuracy of the content.

Why This Book?

This book is not just about understanding PHP libraries; it's a comprehensive guide aimed at shaping you into a proficient PHP developer. Whether you're just starting or are an experienced developer, this book is tailored to enhance your skills deepen your understanding of PHP library development, and put you on the right path in the PHP library development world.

What You'll Learn:

The foundational concepts of PHP libraries.
Advanced topics like Namespaces, Autoloading, Exceptions, and more.
Practical approaches to write reusable code and contribute to the open-source community.

My Learning Philosophy

I believe in learning by sharing and writing. This book embodies that philosophy, serving as a practical starting point for those looking to master PHP libraries and advanced PHP subjects.

Be Part of This Journey

As we approach the release of the book, I invite you to subscribe for exclusive early insights and chapter previews. Your feedback and participation would be invaluable to this journey.

🔗 Get The book
You get:

Two PDF files one in Dark and the other in Light themes.
Two directories contain the code of the library built through the book.

Find it here: https://ahmadraafat.gumroad.com/l/php-library-development-book

And subscribe to my newsletter directly: https://ahmadraafat.gumroad.com/subscribe

Happy Coding!

Unveiling PHP Library Development 101: from Basics to Advanced

Ahmad Ra'fat — Thu, 04 Jan 2024 11:22:04 +0000

🌟 Early Insights Alert: PHP Library Development 101 🌟

Hello, DEV Community!

I'm excited to offer an exclusive sneak peek into my upcoming book, PHP Library Development 101: From Basics to Advanced. With nearly a decade of working experience in PHP, I've distilled my learning and discoveries into this book to help others embark on their journey in building PHP libraries.

Why This Book?

What You'll Learn:

The foundational concepts of PHP libraries.
Advanced topics like Namespaces, Autoloading, Exceptions, and more.
Practical approaches to write reusable code and contribute to the open-source community.

My Learning Philosophy

I believe in learning by sharing and writing. This book embodies that philosophy, serving as a practical starting point for those looking to master PHP libraries and advanced PHP subjects.

Be Part of This Journey

As we approach the release of the book, I invite you to subscribe for exclusive early insights and chapter previews. Your feedback and participation would be invaluable to this journey.

🔗 Sneak Peek and Subscription
Get a glimpse of the content and be among the first to access the book by subscribing: https://ahmadraafat.gumroad.com/l/php-library-development-101-book

Or subscribe to my newsletter directly: https://ahmadraafat.gumroad.com/subscribe

Happy Coding!

30-Day LeetCoding Challenge: Product of Array Except Self

Ahmad Ra'fat — Thu, 16 Apr 2020 11:24:19 +0000

The problem

Solution:

The problem asks us to replace each element in an array with the product of the other array elements and also asks us to do it in O(n).

So, for example if we have this array arr = [1, 2, 3], the result should be ans = [6, 3, 2] do we replaced the 1 with 2 * 3 = 6 and so on.

To do this in O(n) should make you think a little bit about how we can do that! I can think of that we have two arrays one we put for each element the product of the elements before it (left) and another one do the same but from the end (right) some kind of DP. Then we do another loop to multiple for each element the left[i] * right[i] and that will be our answer.

try to do this solution yourself :).

Then I saw that they asking for a follow-up to do it in constant space without considering our output array.

So, I thought of simulating the two array approach but instead of using two arrays, I will just use two pointers one of them will call it left_product and this one will go from the left to right and another pointer called right_product which will go from the right to the left.

The only thing when I do from the left I use index i = 0, 1,..n but from the right we need the invert (~) of this number so we can get it from the right i = -1,-2,...-n, and we keep updating the two pointers with the latest product we find until we finish with the whole array.

Let's do an example to make it more clear.

Example:

Define arr = [1, 2, 3]
We will be using left_product = 1, right_product = 1 we initialise them with 1 as we do product.
We will initialise as well our answer array by the same size of our arr but will be filled with ones ans = [1, 1, 1]
Start with idx = 0 so our num = arr[idx] = 1 now will find our ans[idx] by multiple it by the latest left_product we have so: ans[0] = ans[0] * left_product = 1 * 1 = 1, our new answer is ans = [1, 1, 1].
Now, we calculate the new left_product by multiple it with the current arr[idx] so it will be left_product = left_product * arr[0] = 1 * 1 = 1.
Do the right as we said we need to use the invert so idx = - (idx + 1) or we can just use the invert operator idx = ~idx, and find our new ans[~idx] = ans[-1] will multiple it by the right_product so ans[-1] = ans[-1] * right_product = 1 * 1 = 1, and our new answer is ans = [1, 1, 1].
Calculate the right_product by multiple it's value with the arr[~idx] so it will be right_product = right_product * arr[-1] = 1 * 3 = 3.
Well, keep doing the above procedure over and over until you will reach the final answer array which will be ans = [6, 3, 2]. Do it on paper so you can get the idea very clear.

Pseudocode:

1. define ans = [1] * len(arr)
2. define our pointers left_product,right_product = 1, 1
3. loop over the arr from i = 0 to len(arr)
4.    calculate ans[i] = ans[i] * left_product
5.    calculate left_product = left_product * arr[i]
6.    calculate ans[~i] = ans[~i] * right_product
7.    calculate right_product = right_product * arr[~i]
8. return our ans

Complexity:

Time Complexity: it is so clear we do O(n) one loop over the array.
Space Complexity: taking away the answer array it will be constant space O(1).
Solution in python

How many requests can the 4-cores server that run PHP app take at the same time?

Ahmad Ra'fat — Wed, 15 Apr 2020 09:57:46 +0000

If you have a server with 4-cores and 8GB ram, how many requests can this server take at the same time and how many child processes you can run on it?
I'm taking about PHP and if you are running a PHP application there.

30-Day LeetCoding Challenge: Perform String Shifts

Ahmad Ra'fat — Wed, 15 Apr 2020 07:56:19 +0000

The problem

Solution:

The problem is asking us to do some shifts on a string but doing that with some rules in considerations, it says you will have a string s and an array called shifts that will hold a list of lists (array of arrays) each item will have two elements the first element is the direction of the shift and the second one is the amount to move.

The directions are 0 for left shift and 1 for the right shift.

So, if the shifts array like this shifts = [[0, 1], [1, 2]], so we will shift the string twice the first shift with direction = 0 and amount = 1 means do left shift by the amount = 1 chars so remove the first letter and append it to the end, and the right shift 1 is the opposite remove from the end and put it first.

let's do an example to make it more clear.

Example:

define s = 'abc' and shifts = [[0, 1], [1, 2]]
So with the first shift = [0, 1] we see our direction direction = 0 and our amount amount = 1, so we remove from the beginning and append to the end, so remove a and add to the end s = 'bca' and decrease our amount by 1 amount = 1 - 1 = 0 so we are done with this shift.
Now, the second shift = [1, 2] the direction = 1 says do right shift which means we will move the last amount = 2 to the beginning of the strings:
- First we move the a from s = 'bca' to beginning it will be s = 'abc', and our amount = 2 - 1 = 1.
- Move the c from s = 'abc' to the beginning it will be s = 'cab' and the amount = 1 - 1 = 0 so we are done.
We don't have any other shifts so we stop here with the final answer as s = 'cab'.

If you look more closely to the approach and how we reached our answer you will find a pattern for example to do the left shift by one letter we moved s[0] to the end we can simulate it to be s = s[0+1:] + s[0] = s[1:] + s[0] = s[1:] + s[:1] right from the 1st index to the end plus our one single letter if we look very well that the one in s[1:] & s[:1] is exactly our amount so we can say I need to bring every char after the amount to the beginning and put every char from beginning to the amount at the end so it will be: s = s[amount:] + s[:amount] that's how we do the left shift.

For the right shift we do from the end so in Python to call the string from the end we use the minus (-) sign, for example, indexes from beginning for s = 'abc' is 0, 1, 2 but from the tail (end) is -1, -2, -3 so we can use the same equation with just adding the - to our amount so move from the end to beginning using s = s[-amount:] + s[:-amount].

Pseudocode:

1. loop over the shifts for each shift
2.    define direction = shift[0] and amount = shift[1]
3.    check if direction is 0 so do left shift using s[amount:] + s[:amount]
4.    otherwise direction is 1 do the right shift using s[-amount:] + s[:-amount]
5. return our final s

Complexity:

Time Complexity: So we have a loop over the shifts which will be O(n) where n is the number of shifts we do, in each shift we do modification on the string and that will cost us O(c) where c is the number of chars in the string so our overall time will be O(n . c).
Space Complexity: While modifying the string we keep the old & the new string in memory so that will cost us the length of the string which will be O(c).
Solution in python

30-Day LeetCoding Challenge: Contiguous Array

Ahmad Ra'fat — Tue, 14 Apr 2020 13:51:27 +0000

The problem

Solution:

The problem asking us to find the maximum length of the subarray that contains equal numbers of 0 and 1.

We can say if we have zero counter and one counter our contiguous subarray with an equal number of 0 & 1 will happen when the counters are equal right!

So let's define one counter called count = 0 and when we see 0 we decrease the count by 1 and when we see 1 we increase it with 1 and when the count == 0 that means we have our subarray so calculate the length.

To be able to find our answer which is the maximum length we need to store this counts somewhere associated with their indexes and when we encounter the same count again then we subtract the new index with the stored index and find our answer.

I can't think of any data structure to help us do that besides the hash-map so we will be using it.

Example:

define arr = [0, 0, 1, 0, 0, 0, 1, 1]
define start with map = {0: -1} to hold our counts associated with indexes
define count = 0 to count the number of zeros and ones
define max_length = 0 to hold our answer
When we encounter first arr[0] = 0 so we decrease the count by 1, count -= 1 = -1 do we have count -1 in our map so so store it with the index: map[count] = arr[0] => map = {0: -1, -1: 0}.
When arr[1] = 0 so our new count will be count = -2 not in the map so add it: map = {0: -1, -1: 0, -2: 1}
When arr[2] = 1 now increase our count by one so it will be count = -2 + 1 = -1 do we have this in our map yes we have it so we subtract the current index 2 from the one stored in the map ==> 0, so it will be tmp = 2 - 0 = 2 compare it with our max_length and choose the max: max_length = max(max_length, tmp) = max(0, 2) = 2.
Then we continue doing this until the end we will get our final answer which will be max_length = 6, do it on paper to get the idea.

Pseudocode:

1. define our count_idx_map = {0: -1}
2. define our max_length = 0
3. define count = 0
4. loop over the arr from i = 0 to len(arr)
5.    add 1 to count if arr[i] = 1 and decrease 1 if it is = 0
6.    if count in count_idx_map find our max_length = max(max_length, i - count_idx_map[count])
7.    otherwise add the count to the map count_idx_map[count] = i
8. at end return out max_length

Complexity:

Time Complexity: We do one loop over our array items (n) and inside the loop, we do check if the count in the map or not but this takes only O(1) as it is hash-map, so overall will be O(n).
Space Complexity: Our hash-map in the worst case will be filled with counts for all array items if there is no 0 or 1 so we can say it is O(n).
Solution in python

30-Day LeetCoding Challenge: Last Stone Weight

Ahmad Ra'fat — Tue, 14 Apr 2020 12:49:19 +0000

The problem

Solution:

The problem says that we have an array of stones weights and we need to keep smashing them until we only have one weight remains and return it.

With some conditions which are:

we choose the two heaviest weights x & y.
if the two weights are equal we smash both of them entirely smash x & y.
if the two weights are not equal we destroy x and update the y weight to be y = y - x.

In the end, we will have only one stone left and that will be our answer.

If we think about the first step we need to pick the heaviest two stones with an un-sorted array that is not easy it will cost us a lot of time to find it each time we need to pick a new two stones, so this a perfect use case of max-heap whenever you call it returns the maximum element it has it use tree underlaying to do it or an array or whatever doesn't matter. We need to focus only on the use of it.

So, we use max-heap and call it each time to get the heaviest stones.

Let's do an example so it can be more clear.

Example:

We have list of stones: stones = [2,7,4,1,8,1]
We will create max-heap with the stones array so let's assume it will look like this underlaying: stones_heap = [1,1,2,4,7,8]
We need to pick the heaviest two stones so will pop from the heap: stone_1 = stones_heap.pop() = 8 => stones_heap = [1,1,2,4,7] and stone_2 = stones_heap.pop() = 7 ==> stones_heap = [1,1,2,4].
Now, we check is stone_1 == stone_2 no they are not. So, we destroy stone_1 and update our stone_2 = stone_2 - stone_1 = 8 - 7 = 1, then we add it to our heap stones_heap.push(stone_2) = stones_heap.push(1) ==> stones_heap = [1,1,1,2,4] of course the heap takes care of putting the new weight in the correct place.
We keep doing this process again and again until we will have only one item in our heap stones_heap = [1] and this will be our answer to return.

Do it to the end on paper to get the full idea.

Pseudocode:

We need to keep in mind in some languages like python it only implements min-heap so to be able to use a max-heap we need to transform all the numbers to be negative and transform it back to it is original when we return our answer.

As I am solving in Python I will write the following in the same steps as it is implemented in python.

1. Loop over the stones array from i = 0 to len(stones)
2.    stones[i] *= -1 so we can use the max-heap
3. put the stones in heap: heapq.heapify(stones)
4. loop until the len(stones) is equal to 1
5.    stone_1 = stones.heappop()
6.    stone_2 = stones.heappop()
7.    if stone_1 != stone_2
8.        we need to add the new stone weight to the heap: heapq.heappush(stones, stone_1 - stone_2)
9. if the heap is empty return 0
10. otherwise, return -heapq.heappop(stones)

If you are using language that has max-heap discard the steps 1 & 2 and in the step #10 remove the minus (-) from the beginning.

Complexity:

Time Complexity: To transform the list to heap we will take O(n) where n is the number of stones we have, and the loop will take only O(n - 1) = O(n) and the operations to push & pop will take O(log(n)) so overall will take: O(n log(n))
Space Complexity: In our python solution you should now that it modifies the list in-place and we don't use any extra space so our overall space will be O(1).
Solution in python

30-Day LeetCoding Challenge: Diameter of Binary Tree

Ahmad Ra'fat — Tue, 14 Apr 2020 11:53:28 +0000

The problem

Solution:

It asks us to find a binary tree diameter, it also explains to us that is the diameter of a binary tree is the length of the longest path between any two nodes in a tree.

It is also indicated that doesn't matter if the path passes by the root or not.

So, we need to calculate the depth of each node in the tree and then find the longest path between the nodes.

First the depth of node can be found by node.depth = max(node.left.depth, node.right.depth) + 1.

Also, the path always will be the depth of the left subtree + the depth of the right subtree, so on each node, we need to choose the maximum value that takes us to the final answer so our answer will be: diameter = max(diameter, left_depth + right_depth).

So, how we can calculate that if you look to the illustration above we see that we need to go deep to the tree to get one node depth which means we need to use depth-first search DFS.

We use DFS to find the left subtree depth then find the right subtree depth and later choose between them.

Pseudocode:
diameterOfBinaryTree(root)

1. define our answer
2. call find_depth_helper(root) with the root to find the longest path.
3. return our answer

find_depth_helper(node)

1. if the node is None return 0
2. find_depth_helper(node.left) --> left_depth
3. find_depth_helper(node.right) --> right_depth
4. answer = max(answer, left_depth + right_depth)
5. return the current node depth max(left_depth, right_depth) + 1

Complexity:
Time Complexity: it is so clear that we go over all our nodes so our time will be O(n) where n is the number of nodes in the tree.
Space Complexity: we use recursion stack as we do recursion calls and this stack will be equal to the number of nodes we have so our overall space will be O(n).
Solution in python

30-Day LeetCoding Challenge: Min Stack

Ahmad Ra'fat — Tue, 14 Apr 2020 10:08:23 +0000

The problem

Solution:

The question is asking us to build Stack but a special one that returns the minimum value in it in constant time O(1).

We all now very clear that Stack is working with the LIFO principle which means Last In First Out, and why this is important to think about because we know pushing item to stack takes O(1) and also removing an item from stack takes O(1), and getting the top item of the stack is O(1).

We all know this very clear so it is easy to build stack class using list (array) to store the items.

But here we need a special function called getMin() which should return to us the minimum item in the stack in O(1) if we think about it ooh that is not possible I have to sort the stack first or I should do a loop over the list to find that minimum item and of course that is not O(1).

So how we gonna fix that okay let's see we no whenever we put an element to the stack we will not be able to remove it until we remove the one above it, imagine a stack of plates you can not remove the plate in the middle without moving the top one's first right! So we can apply the same principle by adjusting our stack a little bit to not just store our item no we will store with each one the minimum value we found so far.

So, for example, let's say we are creating our stack and the first item we push is 3 will ask is the stack empty yes it is so that means that 3 is our minimum value we know so far!

Our stack will look like this [(item, min_item)] = [(3, 3)].

So if we add now a new item let's say 2, so we check again the stack now it is not empty so we check is our new item (2) smaller than the minimum one stored with our top item in the stack which is 3, so yes 2 < 3 so we push to our stack our new item associated with the new minimum value.

Our new stack looks [(3, 3), (2, 2)], now if we want to call getMin() it will just return the second element in the top pair in the stack :).

Now, the getMin() will cost O(1).

Try to simulate it on paper with more items.

Pseudocode:
push(number):

    1. if stack is empty
    2.    stack.append((number, number))
    3. otherwise:
    4.    define smallest_num = min(number, stack[-1][-1]) compare with the top
    5.    stack.append((number, smallest_num))

pop()

    1. always get & remove the first number in the top pair: stack.pop()[0]

top()

    1. always get the first number in the top pair: stack[-1][0]

getMin()

  1. always get the second number in the top pair: stack [-1][1]

Complexity:
Time Complexity: for all functions will be O(1)
Space Complexity: we use a list to store the elements as a stack which will be O(n) where n is the number of items, we also have a modified stack that stores the numbers in pairs so it will be 2.O(n) == O(n).
Solution in python

30-Day LeetCoding Challenge: Backspace String Compare

Ahmad Ra'fat — Fri, 10 Apr 2020 12:49:03 +0000

The problem

Solution:

The problem is so easy if you read it carefully it asks if string S and string T are equal consider you typing them in a text editor (notepad), but it is not that easy you will have a special character called # it means backspace so whenever you see it assume you clicked on the backspace button in your keyboard.

So, if you have a string like this ab#c if we follow the rule we mentioned above, you first type a then you find b not a # so type it and it will be ab now we see # and it means backspace so click on the backspace button will remove the b and leave us with a then the last one is c type it ac and this our final result.

It is so obvious now whenever we see the backspace # char we remove the last typed char and this takes to a data structure called Stack as the stack works in LIFO manner which means last-in-first-out.

So, we will go through the two strings to build a stack from their characters and in the end, we compare both of them if they are equal or not.

Let us do an example.

Example:

S = "ab#c"
T = "ad#c"

We will do each string separately and then combine all elements in the stack into one string and then compare them.

We will use stack called typed_chars = [].
Start with S = "ab#c".
Starting with ch = 'a' is our ch == '#' # backspace no it is not so add it to the stack typed_chars = ['a'].
With ch = 'b' is ch == '#' no so add it to the stack typed_chars = ['a', 'b'].
With ch = '#' is ch == '#' yes it is so we simulate the click on the backspace # button by removing the last typed character typed_chars.pop() ==> 'b' so our new stack is typed_chars = ['a'].
With our last S char ch = 'c' is ch == '#' no it is not so add to the stack typed_chars = ['a', 'c'].
Build final string from the typed_chars to be new_s = 'ac' remember it.
Now will do the same with the T = "ad#c" it will be exactly the same process and will end-up with new_t = 'ac'.
If we compare both new_s == new_t = 'ac' == 'ac' = True, and this is our answer.
Pseudocode:

1. define helper function called helper that takes one string: helper(s)
2.      define typed_chars = []
3.      loop for ch in s:
4.          check if ch != '#':
5.              typed_chars.append(ch)
5.          if ch is equal to # and typed_chars not empty:
6.              typed_chars.pop()
7.      return "".join(typed_chars) to return one string
8. check if helper(S) is equal to helper(T) or not and return the result.

Complexity:
Time Complexity:
- We can see that we loop two times to build our stacks the first one is for O(n) where n is our first-string length, and the second time is for O(m) where m is our second string length, so in total it will be O(n + m).
Space Complexity:
- We store our chars in stack two times of course for our first string and our second one, so in total it will be O(n + m).
Solution in python