1
\$\begingroup\$

I am trying to resolve following problem to improve my DS knowledge. Please advice which part of the code can be improved.

You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

record(order_id): adds the order_id to the log get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N. You should be as efficient with time and space as possible.

Code explanation:

I choose linked list with single pointer (prev) to keep transaction logs. I suppose it would be called Stack Linked List.

stProduct -> linked list node

stProdStack -> struct to keep database information, namely ll tail and size (N)

record() examines db information struct tail pointer and order_id within range, then calls actual method to add node to the list: add_product().

I did not implement unit testing due to limited time to seat on.

PARDON MY ENGLISH xD

Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//backward/stack linked list for storing transaction action log
typedef struct stProduct
{
    struct stProduct * prev;
    unsigned int order_id;
}
stProduct;

typedef struct stProdStack
{
    struct stProduct * tail;
    unsigned int size;
}
stProdStack;

stProduct* add_product(stProduct *tail, unsigned int order_id)
{
    stProduct *product = malloc(sizeof *product);
    if (!product) return NULL;
    product->order_id = order_id;
    product->prev = tail;
    return product;
}

bool record(stProdStack *stListInfo, unsigned int order_id)
{
    if (!stListInfo)
        return false;
    stProduct *tail = add_product(stListInfo->tail, order_id);
    if (tail)
    {
        stListInfo->tail = tail;
        return true;
    }
    else
    {
        return false;
    }
}

unsigned int get_last(const stProdStack *stListInfo, unsigned int i)
{
    if (!stListInfo) return 0;
    if (i > stListInfo->size) return 0;

    stProduct *current = stListInfo->tail;
    for (int j = 0; j < i - 1; j++)
    {
        current = current->prev;
    }

    return current->order_id;
}

int main(void)
{
    unsigned int N = 100;
    stProdStack product_stack = { NULL, N  };

    for (unsigned int i = 0; i < 300; i++)
    {
        if (!record(&product_stack, 1000 + i))
        {
            printf("transaction log record failed\n");
            break;
        }
    }

    printf("10th last product ID: %u\n", get_last(&product_stack, 10));

}

Result: 10th last product ID: 1290

\$\endgroup\$
2
\$\begingroup\$
  • The code doesn't fulfill the requirements. You are supposed to log the last N orders. Instead you log all of them. The old orders shall be removed from the list as it grows beyond N.

  • Bug. The list is initialized with the size being set to N. However, at the beginning it may contain less than N elements. In the scenario

      List is empty
      An order is added
      get_last(2) is called
    

    the loop

      for (int j = 0; j < i - 1; j++)
      {
          current = current->prev;
      }
    

    is guaranteed to access a null pointer.

  • The above loop complexity is \$O(N)\$.

All that said, I recommend to use not a list, but a circular buffer. No need to malloc anything, and get_last is executed in \$O(1)\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.