System Design Solution
Tiny URL Design:
reference:
https://www.interviewbit.com/problems/design-url-shortener/#
http://blog.gainlo.co/index.php/2016/03/08/system-design-interview-question-create-tinyurl-system/
https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904
Vending Machine Design:
Vending Machine should have following Functionality expected to implements.
1. Inventory Management system.[itemID-NumOfUnit-Menu_ID_Price]
2. Coin and Note collection for exchange
3. Money Verification System
4. Amount collection system and Exchange
5. Menu Board for Customer
6. Mapping System Menu with Item, Price, Quantity
7. Price evaluation for selected items.
8. Verify collected amount against Selected Items price
9. If changes is available for refund
10. Order place system synchronized with some mechanical system.
11. Refund system
12. Admin System
13. Enable and Disable Menu Based on available Inventory
14. Feedback System.
Facebook or Google Chat messenger
Reference: https://www.youtube.com/watch?v=zKPNUMkwOJE
Basic Functionality:
- How come to know who are online. How Come to know came online and went offline
2. Sent Message to Respective User or Friend
3. Online deliver message
4. If Intended user is offline than deliver message when He will come online.
5. Acknowledgment Message delivered
6. Share Image and Videos
7. Allow download images and Videos
8. How To maintain ordering of message
9. Maintain Chat history
10. Notification system
Technologies:
1. Cassandra for Chat and Its History
2. Redis for In-memory DB for Storing Online Users details by updating the heartbeat info.
3. Load Balancer
4. Cloud Flair: Blob Storage for images and Video Storage []
5. Kafka between servers for finally sending message.
Design LRU cache.
http://blog.gainlo.co/index.php/2016/05/17/design-a-cache-system/
A. Using LinkedHashMap .
Note: Either we can extends LRU class with LinkedHashmap to customize its functionality or When we instantiate Linked Hashmap then override removeEledestEnrty function.
B. Using HashMap and Doubly Linked List. Here doubly LinkedList is used for maintain key order.
C. In case of Get() Method: Implement following logic to achieve LRU[Least Recently Used]
Note: If key is already exist, then make it recently used. To achieve it first remove this key and add again in collection to maintain LRU.
Note above solution because to get least recently item based on usage in map, in get() method we first check it exist or not. If exist than remove and again add in map [ordered map]
Alternative Solution: Using one Map and MinHeap [Timebased Solution]
Least recently Used Item will be decided based on timestamp when it was request last.
Hence when there is request to access item available in cache, then update the timestamp.
There are two approach:
1. Maintain one more Map that hold <key, TimeStamp>. When get(key) method called. If element is exist then update timestamp with respect to key. When Cache size is exhausted then remove element from TimeMap based on timestamp [oldest entry not in use from long time], At first position,
2. Recommended Solution: Take another data structure, MinHeap and each node would be <Key, timestamp>, We will form Heap based on timestamp. Root contain oldest entry. Hence when Cache window is exhausted then remove root element, replace it with new <key,timestamp> and remove value with respect to deleted key from minheap at same time.
Resolve the Concurrency issue:
1. [At single system]First Map should be Concurrent LinkedHashMap, So then N number of thread concurrently work.
2. When we put data in cache, then only one thread allow to access data with respect to key, So that other thread will not put different value with respect to key.
3. When Eviction happen, synchronization or locking mechanism needed.
4. In case of get no locking needed.
Distributed Cache: If number of request is very high then one system is not able to handle requests then, sharding is needed based on key.
Sharding:
A. Range Based
B. Hashing based [recommended] Hash value is hexadecimal number% Number of Machine [hexadecimal], delicate request to respective server.