Scaler

Steps for System Design Define MVP -> Requirement gathering Estimate Scale wrt #users, #traffic Design Goals(CAP theorem) API Design System Design 1 Billion is 1 Giga byte.  Databases HBase - Optimized for high volume of writes. -> columnar DB MongoDB - Read heavy systems. Has tunable consistency. Due to the same, it can good for high writes as well - consistency and partitioning tolerance - MongoDB can have a single-point failure - MongoDB sacrifices availability Dynamo DB, MySQL- Read Heavy Cassandra - Cassandra gives up consistency Reddis- Global cache Queues Kafka/RabbitMQ-  Persistent queue RabbitMQ- allows to push & Kafka only notifies and subscribers have to PULL  Messaging App Facebook: 20-30 Million messages per day How to scale any product which can support when the users increase from 100 to 100Million  Messenger MVP Ability to send and receive messages Message History Login with Facebook accounts Contacts/Friends Messages should have max length(...

Heaps -1 Heap Data structure which can give getMin/extractMin & insert in logN TC It is a Complete Binary Tree Height is always logN Nodes in last level will be ~ N/2 Min or Max Property Value of the node must be greater(max heap)/smaller(min heap) than both LST & RST Store heap in an array Space saving by removing left/right pointers Move from Parent/child in O(1)  last index can be found in O(1) Convert Array to min Heap Approach1: Sort the array O(N log N) Approach 2: Insert into heap 1 by 1 ->TC: O(N) Approach 3: Insert elements from bottom up : TC: O(N) Heap in Java is Priority Queue Magician and Chocolates:  Given  N  bags, each bag contains  B i  chocolates. There is a kid and a magician. In a unit of time, the kid can choose any bag  i , and eat  B i  chocolates from it, then the magician will fill the  ith  bag with  floor(B i /2)  chocolates.  Find the maximum number of chocolates that the kid can...