Data Structures and System Design Interview Prep Notes

Data Structures and Algorithms Notes Important Concepts Graph  DFS - Max Area of Island - LeetCode BFS - Rotting Oranges - LeetCode Detect cycle in undirected graph Graph Valid Tree - LeetCode Topological Sort + Detect cycle in DAG Course Schedule II - LeetCode   Union Find Algorithm  No of Connected Components Number of Connected Components in an Undirected Graph - LeetCode Redundant Connection - LeetCode   Accounts Merge Dijkstra's Network Delay Time - LeetCode (BFS + Priority Queue) Prims and Kruskal's algorithm Min Cost to Connect All Points - LeetCode (BFS + Priority Queue) and Union Find Algorithm. Sliding Window Algorithm usual pattern is while expanding window          process right element          try to shrink window          update the answer based on the current window Fixed Length Window - Permutations in String   Variable Length Window -  Minimum Window Substring Sliding window with Deque - Sliding window maximum Stack Monotonic Stack -  Largest Rectangle in

HTTP Long Polling vs WebSockets

In a typical client to server model, to communicate with server, client opens a HTTP connection and sends the request over that connection to the server. Server process the request and sends the response back to the client. After that connection is closed. Next time client needs to communicate to the server, client will open a new HTTP connection with the server. In applications, where client needs to repeatedly talk to server for updates in very small intervals of time, this can waste lot of resources. For example, In chat applications client will periodically poll the server in very small intervals of time for the new messages, server might not have new messages all the time. This can lead to wastage of compute resources. We need ways to reduce the number of connections created between client and server. To solve the above problem, there are two most popular solutions. 1. HTTP Long Polling 2. Websockets. HTTP Long Polling In HTTP Long polling, server holds the connection as long as i

Just keep it simple and break it down

"Just keep it simple and break it down" it is not just a statement, it is a mantra we all should think about first when designing any system. If an interviewer asks you how will you design whatsapp? Take a pose for a moment and think about how whatsapp works? what is the core functionality of whatsapp? It is a messaging app, sending and recieving messages is the most important part of it. Lets focus on this part for now and lets not think about how group chats will work? how to manage online/offline status etc? think about plain simple text messages. Lets list down things We need one sender who sends the message and one receiver who recieves the messages. Sender and reciever could be an android app, ios app or a webapp. We need backend server which receives the messages from the sender and sends it to the receiver. Do we need anything else? Umm lets think about. Sender and receiver can be online or offline at any point. It might happen that sender sends the message but receiv