Data structure to record and get last element – Twitter Interview Question

Last modified date

Comments: 0

Question

Twitter Interview Question

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(orderId): adds the order Id to the log
getLast(i): gets the ith last element from the log. (i is guaranteed to be smaller than or equal to N.)

Solution

There are several solutions to this problem using Arrays or Lists, however they would both end up having O(n) runtimes in the worst case since it would involve shifting elements and traversing long lists.

There is a clever technique we can use that will give us a time complexity of O(1) and space complexity of O(n).

That is to use a circular buffer. A circular buffer takes advantage of the % Modulus operator to loop back around to the start of an array once you reach the end. This means we can have a pointer to insert the next element and then calculate the last ith element index and for getting the last ith element. Therefore maintaining our O(1) time complexity.

Hopefully you found this useful. If you have any questions leave them in the comments below or visit our forum.

If you liked this tutorial and explanation you will also find this leet code problem useful for your development as well.

JakTech

Leave a Reply

Your email address will not be published. Required fields are marked *

Post comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.