Practicing System Design in JavaScript: Cache System and the Shortest Path for Graph

Introduction

Data structure is one of unavoidable challenges when applying the software engineer role. I studied basic data structures and wrote down an article in JavaScript before.

However, it’s hard to apply data structures to design a system or solve the real problem.

Learning data structure in JavaScript for beginners

The target of article is for recording common problems with data structures. I choose two interesting problems from Cracking the coding Interview and turn the solutions to JavaScript. We will use hash table, linked list, list(array) to solve these questions.

• Please Design a Cache for a Single System?
• How to Find the Shortest Search Path between Two People?

Please Design a Cache for a Single System?

Requirements

Design a cache system with the following properties.

1. Efficient lookups given a key
2. Expiration of old data so that it can be replaced with new data

Design a Cache System in JavaScript

To design a cache system, we may use the following data structures.

1. Hash Table: the property of Hash Table allows us easy lookups data (O(1) ~ O(n)) but wouldn’t allow easy data purging
2. Linked List: The property of Linked List allows us purging of old data. The purging action consist of moving the fresh item to the front (O(n)) and removing the last element when the list exceeds a certain size(O(n))

Data Structures to use

• Hash Table