How to Think Before Designing Algorithms

Hello everyone! I am back with a new post which most of the new students struggle while learning about algorithms in undergrad courses. In this post, I will discuss the step by step process on how the developers usually undergo while thinking of solution to the problem and then designing algorithms.

It's the computer scientists who propose and invent new algorithms with improved features (usually time complexity) from the previous ones. For example, just look at searching algorithms. At the end, new constraints or inputs are added to the algorithms. The developers then use this algorithms and fit into the problems to get the things done in less time.

Step 1: Defining Problem

The problem created while discussion with the client and project manager isn't particularly technical, and it needs to be translated into technical terms so that it can be understood by the developers. Nerds!

For example let's take a simple problem statements.

How many users are coming to the application in a day and going to the checkout page and how many are abandoning it. Consider the timeout to be 300 seconds?

This could be shortened to the following

Classify the checkout session as completed or abandoned if it is inactive for 300 seconds, and then group by this label starting from 00:00:00 UTC to 23:59:59 UTC every day.

Step 2: Organising the Steps to Solve

From the problem statements, now it's time to interpret the statement and create the steps involved in the checkout completion or abandonment.

1. Checkout session create
2. Get the status by differentiating the current time with create time
3. If the time difference is 300 seconds, then mark it abandoned

Step 3: Automate it via an Algorithm

Use any programming and database to find all the checkout sessions created whose create time is less than current time and greater then current time - 300 seconds.

I have used MongoDB to implement this logic. You can check it on the playground, shared link below. I would recommend you to tinker with it and learn how it is working.

mongoplayground.net

Note This is supposed to be run periodically, therefore we need a cron job like feature in the application which is supposed to be executed at end of the day, everyday (59 59 23 * * *)

Step 4: Test it and Fix it Iteratively

What if the customer finally completes the checkout after some time has passed and the cron job has not yet been run? In the current scenario, this session will also be marked as abandoned. False positive is the term for this type of error.

Let's come to the second error type: What if the checkout session is abandoned for greater than 300 secs. It should also be counted as the abandoned, but with current logic, it is counted as completed. False negative is the term for this type of error.

What is the fix?

If the checkout is completed, there must be an order id linked to it. Therefore, if the property exists in the document, then the checkout is completed, otherwise it was abandoned by the user.

mongoplayground.net

Step 5: Make Sure your Solution is Effective and Efficient

Create a reusable function and try the same algorithm on real data after you've gotten your algorithm to work on the dummy data. This will help you decide whether or not to include it in the code base.

function getCheckoutStatus(startDate, endDate) {
  return db.collection.aggregate([
    {
      $match: { // get all the 
        createdAt: {
          $gte: startDate,
          $lt: endDate,
        },
      },
    },
    {
      $addFields: { // set status to completed if orderId exists; otherwise, abandon.
        status: {
          $cond: ["$orderId", "completed", "abandoned"],
        },
      },
    },
    {
      $group: { // group and aggregate the count
        _id: "$status",
        count: {
          $sum: 1,
        },
      },
    },
  ]);
}

The SQL equivalent of this could be

SELECT COUNT(*) AS completed FROM table WHERE `orderId` IS NOT NULL;
SELECT COUNT(*) AS abandoned FROM table WHERE `orderId` IS NULL;

If you get an error in this step, it means you didn't understand the problem to begin with. Return to step 2 and repeat the process.

Comments

[João Iacillo]

Nice article! I think the example got me a little bit confused, but I got the idea of it.