Overview A key-value store (key-value database) is a non-relational database Unique identifier keys can be plain text or hashed value Short keys are more performant than longer keys Values can be strings, lists, or objects, etc Values are usually treated as opaque objects in Amazon Dynamo DB, Memcached, Redis. (Opaque objects are not coded to interfaces) Key-value stores support the following operations: put(key, value) get(key) Scope Keep key size small: less than 10 KB Large storage capacity High availability Automatic scaling (add / remove servers) Tunable consistency Low latency Single server architecture A single server key-value store can be implemented with an in memory hash map Optimization: Compress data Keep frequently used data in memory and store the rest on disc A single server key-value store cannot be scaled to support big data Distributed architecture A distributed key-value store is also called a distributed hash table CAP theorem & distributed systems According to the CAP Theorem, a distributed system can only achieve two of the following properties:...

Problem Statement A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i....

What is hashing? Hashing is transforming a piece of data of an arbitrary size to another value. If the data is transformed into an integer for example, the hash space is a range of integers from 0 to xn. The smaller the range, the greater the probability of collisions (multiple pieces of data mapping back to the same value). A good hash function reduces the probability of collisions. A data structure called a hash map uses an array of size xn+1 where each element points to a data bucket....

Overview An HTTP rate rate limiter can: block requests that exceed defined thresholds prevent resource starvation caused by Denial of Service DoS attacks reduce costs by limiting excess requests. (Critically important for services that use paid third party services) prevent server overload from bots or malicious users Scope Questions: q: What type of rate limiter? a: server side q: What type of rules are we writing: (Number of API requests, IP, user id, other properties)?...

Problem Statement You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad....