DEV Community: Deniss Sudak

Applying matching algorithms to real allocation problems. Part 2

Deniss Sudak — Mon, 09 Jun 2025 01:48:43 +0000

In Part 1, we discussed how to match applicants to roles. In this part, we’ll explore how to determine which roles need to be filled to complete the team. Let’s describe this problem through examples.

Let’s start with a simple case. Suppose we have a job that needs two people with “skill-1.” We’ve assigned this role to one person. We still need someone with “skill-1” to complete the team.

Now let’s say we have a job that requires one person with “skill-1” and one person with “skill-2.” We’ve assigned the “skill-1” role to someone who has both “skill-1” and “skill-2.” To complete the team, we obviously need someone with “skill-2,” but actually, someone with “skill-1” will do as well, as we can reassign the current applicant to the “skill-2” role.

As you can imagine, in complex scenarios with multiple roles and applicants with multiple skills, we can reshuffle role assignments in many ways to accommodate a new applicant who helps complete the team.

Here, we’ll discuss how to determine which applicants with which skills could join the team without replacing anyone currently on it.

Suppose we have the following roles to fill:

And right now, we have two applicants:

In other words, any applicant is suitable for any role.

Here’s how our problem would look like in a flow network form.

Now, let’s say that after running our matching algorithm, both applicant-1 and applicant-2 are assigned to the “skill-1” role. To do that, I’m running a push-relabel maximum flow algorithm. By the time it terminates, the original network will have been transformed into the following residual graph:

You can think of a residual graph as a network of the remaining (residual) capacity after the flow has been set. For example, since applicant-1 is assigned the “skill-1” role, there is no more flow from A-1 to S-1. However, it’s possible to “undo” this assignment by directing flow from the Sink to S-1 and from S-1 to A-1. From there, excess can flow to S-2 and then to the Sink, thus reassigning applicant-1 to the “skill-2” role.

So how do we determine which applicants with which skills could join the team without replacing anyone already on it?

If a team requirement needs more members than are currently assigned, then clearly we need applicants with those skills.

If a team requirement is already satisfied — that is, it has the number of team members it requires (like S-1 in our example) — then we need to check whether at least one of those team members could be reassigned to another role. We do that in the following way:

We add 1 to the capacity of the arc that emanates from the Source and ends at each node corresponding to team members linked to the team requirement in question. If that increases the flow, then at least one of those team members found another role (without displacing anyone), and so we can say that we need another applicant with those skills.

This is like cloning applicants already assigned to a role and then checking if at least one of them can take on a different role without kicking anyone out.

Try it yourself

You can experiment with this algorithm using the following repo:

👉 https://github.com/denissudak/applicant-job-matching

I hope you’ll find it useful.

Applying matching algorithms to real allocation problems. Part 1

Deniss Sudak — Mon, 09 Jun 2025 01:42:06 +0000

The problem

Many allocation problems can be reduced to the maximum bipartite matching: assigning workers to jobs, students to courses or residencies, tasks to available servers, and so on. This series of articles walks through a concrete example and then extends it to more advanced scenarios that you might encounter in the real world. I’ll assume you’re familiar with graphs and flow networks. If not, you can always learn these subjects — there is a lot of excellent material out there.

For everything I talk about here there is working code you can download and play with.

Example: matching applicants to jobs

Suppose we have a single job with these requirements:

And three applicants whose skills look like this:

Our goal is to assign applicants to roles so that the maximum number of positions is filled.

If, for a moment, we ignore how many people each role needs, the problem can be modelled as a bipartite graph:

Nodes on the left represent the applicants. Nodes on the right represent the roles. The edges that connect them signify that an applicant has the skills required for the role. For example A-1 has skill-1 and skill-2 and that’s why they are connected to S-1 and S-2.

There are numerous algorithms that find the maximum matching in bipartite graphs. Some of them do it via flow networks — the problem is reduced to finding a maximum flow in a network and then the flow is converted back into matching. For our problem I prefer the flow network approach as it allows us to easily encode that we need 2 people with skill-2 and 2 more people with skill-3. Here’s how our problem would look like in a flow network form.

The new nodes are the source and the sink. The flow emanates from the source and needs to find its way to the sink via directed edges without exceeding the capacity of any of the edges.

The edges that go from the source to the nodes that represent applicants all have a capacity of one. This represents the fact that we have only one of each of the applicants. Edges that connect applicants to the role nodes also have a capacity of one — each applicant can only do one role. If applicant-1 is assigned the role that requires skill-1 then that’s it, they can’t be assigned anything else. The capacities of edges that connect role nodes to the sink represent the number of people required for that role. For example, S-2 needs two people and so has the capacity to take the flow from both A-1 and A-2.

Once we have the flow network the goal is to find the path the flow should take in order to reach its maximum. Just as there could be several maximum matchings in a bipartite graph, there could be several maximum flows in the network. Here’s one of them:

Here’s another:

In both cases the flow is 3, meaning that all three applicants are assigned roles. It’s easy to convert the flow back to role assignments. Using the first flow: applicant-1 is assigned the role that requires skill-1; applicant-2 is assigned skill-3; applicant-3 is assigned skill-2.

Try it yourself

If you want to explore the examples above and experiment with matching applicants to jobs, you can download the code here: https://github.com/denissudak/applicant-job-matching

Continue to Part 2 that talks about how to calculate what roles are still in demand (what skills are still required to complete the team). 🙂

How to keep unread notifications relevant

Deniss Sudak — Mon, 02 Jun 2025 20:42:50 +0000

You’ve probably puzzled over this at some point in your career. Don’t worry — the answer is here.

First of all, what do I mean by keeping unread notifications relevant? What’s the problem? Like a lot of things, it’s easier to explain with an example.

Let’s say we have a system that helps you find people for upcoming job shifts. It sends a notification to someone asking if they want a shift on Saturday from 12 pm to 3 pm at a given address. A few people respond “yes,” you pick someone, and that person gets notified that they’ve got the gig. If the time of the shift changes or it gets cancelled altogether, the system sends them another notification.

Now let’s zoom in. The job is offered. That notification says something like:

New job on 18th of April, 12pm — 3pm, 48 Pirrama Rd, Pyrmont NSW 2009

They get a ping that there’s a new notification. They’re out and about and haven’t read it yet. In the meantime, you realise the shift is longer and update the job in the system. It issues another notification:

The job has changed to 18th of April, 12pm — 5pm, 48 Pirrama Rd, Pyrmont NSW 2009

When they finally check their notifications, ideally we’d like them to see a single notification:

New job on 18th of April, 12pm — 5pm at 48 Pirrama Rd, Pyrmont NSW 2009

Now let’s say they’ve got the job, and a few days later the details change again:

The job has changed to 18th of April, 12pm — 5pm, 14 Vine St, Redfern NSW 2016

Just like before, they’re out and haven’t checked their phone. Then you realise the job is cancelled. The system sends one more notification:

The job is cancelled.

Again, when they check their notifications, we’d like them to see only the cancellation — the previous job updates are no longer relevant once the job is cancelled.

There could be many more notifications, with various ways they affect one another. Here’s how to structure your code in a way that’s robust and easy to expand.

Structure

We have two main parts: a set of existing notifications and a new notification that gets added to the set. It’ll either update some of the existing notifications or be added as a new one.

Going back to our example, let’s say our set of existing notifications contains a single job notification:

New job on 18th of April, 12pm — 3pm, 48 Pirrama Rd, Pyrmont NSW 2009

The new job change notification gets added to the set:

The job has changed to 18th of April, 12pm — 5pm, 48 Pirrama Rd, Pyrmont NSW 2009

As a result, we expect the set to contain just one notification:

New job on 18th of April, 12pm — 5pm at 48 Pirrama Rd, Pyrmont NSW 2009

We loop through existing notifications and “update” them one by one with the new notification. In that process, we check whether both the new and old notifications are still relevant and act accordingly:

Example

What’s a technical article without a class diagram?

Here NotificationSet represents the set of existing notifications that we want to update with the new notification. This new notification is passed to the add method as a parameter of type NotificationData.

Each existing notification has its own update logic that is represented by ExistingNotificationUpdate. It interacts with NewNotificationAddition — the logic of adding the new notification to the set. After all these interactions it determines if this new notification isRelevant(). Similarly the ExistingNotificationUpdate determines if it should be deleted via isDeleted() method.

Java implementation

Here’s Java implementation of the above pseudo-code:

public void add(NotificationData newNotificationData) {
    checkNotNull(newNotificationData);

    NewNotificationAddition newNotificationAddition = newNotificationData.createNewNotificationAddition();
    for (Notification n : newHashSet(notifications)) {
        ExistingNotificationUpdate existingNotificationUpdate = notificationUpdateFactory.createNotificationUpdate(n);
        newNotificationAddition.call(existingNotificationUpdate);
        if (existingNotificationUpdate.isDeleted()) {
            notifications.remove(n);
        }
    }
    if (newNotificationAddition.isRelevant()) {
        notifications.add(notificationFactory.newNotification(newNotificationData));
    }
}

I’ve written a working example that demonstrates this pattern: https://github.com/denissudak/unread-notifications-update

Even if you don’t work with Java, I’d still recommend checking it out as it communicates the idea through working code.

I hope you find it useful. Enjoy!

How to build multi-step message processing

Deniss Sudak — Mon, 02 Jun 2025 20:27:44 +0000

Let’s say you have a service that, in response to some event, performs a series of operations that can’t be wrapped into an atomic transaction. For example, this service might integrate with an accounting system and, in response to a sale event, create an invoice (Step 1) and send that invoice to a customer (Step 2). If either of these two steps fails, the entire sale event processing should be retried. However, if Step 1 succeeds, but emailing the invoice fails, we obviously should retry only the email step and not create a duplicate invoice.

The idea is simple: persist the status of each processing step (e.g. invoice creation and emailing) in a database, and during a retry, resume from the failed step.

These statuses will be fetched from the database using an ID derived from the received message. A status can have one of the three values:

PROCESSING
SUCCESS
TRY_AGAIN

SUCCESS means that the step has completed successfully and not to be executed again.

TRY_AGAIN means that the step has failed in a way that is safe to retry. For example our accounting system returned 4xx error, indicating that the action wasn’t successful.

PROCESSING is set temporarily while the step is in progress. If it succeeds, we set it to SUCCESS. If it fails in a way where it’s unclear whether to retry (e.g. 5xx error), the status remains PROCESSING. In this case, the entire workflow is locked and cannot proceed until a human (or automation) determines what happened and updates the state.

Processing context

Every step may produce data that is required by the next step. For example, sending the invoice requires an invoice ID, which is generated by the external accounting system in the first step.

Data produced by the successful steps (like the invoice ID) will be stored in the message processing context. This way, when the message is retried, all the data is already there and ready to use.

Here’s the example of the event processing record:

{
  "eventId": "sale-1",
  "createdInvoiceId": "abc-xyz-123",
  "stepProcessingStatuses": [
    {
      "stepCode": "create-new-invoice",
      "status": "SUCCESS"
    },
    {
      "stepCode": "email-invoice",
      "status": "TRY_AGAIN"
    }
  ],
  "locked": false
}

Here, “sale-1” is the ID of the event that is being processed. This is the ID used to look up the record when the event is retried. If the “email-invoice” step fails, during the second attempt this record will be fetched. I’ll show that “create-new-invoice” was successful and should be skipped. The “email-invoice” step will then reuse the previously stored “createdInvoiceId”.

What’s “locked”?

To ensure that the same step isn’t executed more than once, we must prevent multiple workers from processing the same message simultaneously.

This might not be an issue depending on your message queue. For example, AWS SQS FIFO queues have exactly-once delivery guarantees.

It’s less critical if duplicate execution isn’t a big deal. For instance, in a multi-step AI pipeline where each step processes data from the previous one, concurrent processing might just result in some extra API usage — not the end of the world.

However if your queue comes with at-least-once delivery guarantee (like standard AWS SQS), and you don’t want to create duplicate invoices then having a way to lock an event processing from other workers is essential.

On a high level this simply means that before processing an event, a worker has to successfully acquire a lock and release the lock after it’s done with the event. If any other worker picks up the message while it’s locked then it would ignore the event.

Pick a database that guarantees atomic updates, so only one worker can successfully acquire the lock at a time.

Code example

I’ve written a working example that demonstrates this pattern using Java Spring, AWS SQS and DynamoDB: https://github.com/denissudak/multi-step-event-processing

DynamoDB is a good choice for this use case.

Condition expressions support the locking functionality that we need.
Flexible schema allows any shape of processing context data (like “createdInvoiceId”).
You can use a single table to store processing records for multiple event types.

Even if you don’t work with Java, I would still suggest checking it out as it communicates the idea via working code.

I hope you find it useful. Enjoy!

Java proxy for overlapping interfaces

Deniss Sudak — Mon, 02 Jun 2025 18:59:31 +0000

If you are writing in Java and need to convert a DTO (data transfer object) to JSON before sending it out, there are libraries that will do this task for you. Jackson is one of them. It’ll use Java reflection to look for getters to figure out what data to write to JSON.

Let’s say you have a few of these DTOs and some parts of them overlap, that is they have the same fields in common. You don’t need many overlapping DTOs before you end-up with code duplication that you can’t overcome with inheritance alone. Does it matter? DTOs are just lightweight data containers. There is no business logic in them. What duplication are we talking about?

Fine. But a DTO doesn’t have to be just a POJO when it has the potential to be so much more :) For example, it can represent your integration with an accounting system:

class AccountingDTO {
   List<LineItem> getProfitLoss();
   List<ListItem> getBalanceSheet();
   List<Invoice> getInvoices();
}

Imagine that these getters fetch data from Xero.

Now let’s say you only need to P&L and balance sheet converted to JSON to serve the first request. Another request requires P&L and invoices, and the third needs only invoices and, again, the balance sheet. Giving the entire AccountingDTO to Jackson will serialise everything making unnecessary requests to that accounting system as well as sending back JSON larger than is needed. If you split into 3 DTOs then, for example, the getProfitLoss method would have to appear in two of them and that’s duplication.

The solution I came up with is to create three interfaces that list only the getters required for their corresponding requests while keeping all the business logic in AccountingDTO.

For each of these interfaces, create what I call a super‑interface proxy — a proxy instance that exposes only the required subset of methods, while every call is passed through to the full AccountingDTO implementation. Giving one of these proxies to Jackson generates JSON that contains only what the interface (and not the underlying implementation) specifies.

public class SuperInterfaceProxyFactory<Super, T extends Super> {
    private final Class<Super> superClass;

    public SuperInterfaceProxyFactory(Class<Super> superClass) {
        this.superClass = requireNonNull(superClass);
    }

    public Super newProxy(T obj) {
        checkNotNull(obj);
        return (Super) Proxy.newProxyInstance(
                superClass.getClassLoader(),
                new Class[]{superClass},
                new PassThroughInvocationHandler(obj)
        );
    }

    private static class PassThroughInvocationHandler implements InvocationHandler {
        private final Object target;

        private PassThroughInvocationHandler(Object target) {
            this.target = requireNonNull(target);
        }

        @Override
        public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
            return method.invoke(target, args);
        }
    }
}

Here your Super could be AccountingDTO1 interface, and T the implementation that contains all the methods. The object
returned by newProxy will generate JSON that you need. Have a look at the code example: https://github.com/denissudak/java-super-interface-proxy

I hope you find it useful. Enjoy!