Skip to content

Latest commit

 

History

History
252 lines (192 loc) · 9.93 KB

README.md

File metadata and controls

252 lines (192 loc) · 9.93 KB
Raw

Real-Life-DSA

Medium Link for the same

Q. Data Structures in real life. Seriously? Why do I need to know this buddy?

-because the interviewer got no chill!

So, girls and boys, allow me to present — what you were not looking for, apparently. Facepalm. There’s no other list over the internet — this extensive. I bet you.

ARRAYS

  1. 2D arrays (as matrix), are used in image processing.
  2. To Store an image (1000 by 1000 pixels) as a bitmap.
  3. Your viewing screen is also a multidimensional array of pixels.
  4. In an online exam question paper numbering.
  5. Sudoku or Chess Board are 2D arrays.
  6. It is also used in speech processing, in which each speech signal is an array.
  7. Arrangement of leader-board of a game.
  8. Book titles in a Library Management Systems
  9. Storing color values
  10. Online ticket booking.
  11. Contacts on a cell phone.

MATRIX

  1. In geology, matrices are used for making seismic surveys.
  2. Used for plotting graphs, statistics and also to do scientific studies and research in almost different fields.
  3. Matrices are also used in representing real-world data like the population of people, infant mortality rate, etc.
  4. They are the best representation methods for plotting surveys.

STRINGS (not really a data structure)

  1. Spam email detection.
  2. Plagiarism detection.

LINEAR SEARCH

  1. Finding a word in a lexicographically-unsorted physical dictionary book.
  2. Searching data in Linked List.

BINARY SEARCH

  1. Finding Page Number in a book, e.g. — Target page number is 35, you open at page no. 15, it’s less, you move ahead and open 43, it is greater, you again move backward.

LINKED LIST

  1. Image viewer software uses a linked list to view the previous and the next images using the previous and next buttons.
  2. Web pages can be accessed using the previous and the next button in a browser.
  3. Music Players next, previous buttons uses doubly/circular linked list based on our preference.
  4. MS-Paint drawings and shapes are connected via a linked list on canvas.
  5. To keep the track of turns in a multi-player game, a circular linked list is used.
  6. Escalators — Circular linked List.
  7. Each of the lines of code in an IDE internally is a record on a doubly-linked list.
  8. Left/Right swipe on Tinder uses a doubly-linked list.
  9. Social media content “feeds”.
  10. Used for symbol table management in a designing compiler
  11. Used in switching between applications and programs(Alt + Tab) in the Operating system (implemented using Circular Linked List)
  12. Train coaches are connected to one another in a doubly-linked list fashion.
  13. It can be used to implement Stacks, Queues, Graphs, and Trees.

STACKS — LIFO

  1. Undo/Redo button/operation in word processors.
  2. Wearing/Removing Bangles.
  3. Pile of Dinner Plates.
  4. Stacked chairs.
  5. Changing wearables on a cold evening, first in, comes out at last.
  6. Last Hired, First Fired — which is typically utilized when a company reduces its workforce in an economic recession.
  7. Loading bullets into the magazine of a gun. The last one to go in is fired first. Bam!
  8. Scratch card’s earned after Google pay transaction.
  9. Stack/Queue is used in the back and forward buttons of the web browser.
  10. Browser History of visited websites.
  11. Syntaxes in languages are parsed using stacks.
  12. Message logs and all messages you get are arranged in a stack.
  13. Call logs, E-mails, Google photos’ any gallery, YouTube downloads, Notifications ( latest appears first ).
  14. Java Virtual Machine.
  15. Recursion.
  16. Used in IDEs to check for proper parentheses matching.
  17. Evaluate an expression (i.e., parse).

QUEUES

  1. In Escalators.
  2. Printer spooler.
  3. Sending emails.
  4. Car washes queue.
  5. Server while responding to requests.
  6. Operating System uses queues for job/task scheduling.
  7. Data packets in communication are arranged in queue format.
  8. Stack/Queue is used in the back and forward buttons of the web browser.
  9. While switching multiple applications, windows use a circular queue.
  10. A circular queue is used to maintain the playing sequence of multiple players in a game.
  11. A queue can be implemented in — Linked List-based Queue, Array-based Queue, Stack-based Queue.
  12. Uploading and downloading photo’s, first kept for uploading/downloading will be completed first (Not if there is threading)

PRIORITY QUEUE

  1. Process scheduling in the kernel.
  2. Priority queues are used in file downloading operations in a browser.

SORTING ALGORITHM

  1. Order things by their value.
  2. Backend Databases(Merge Sort).
  3. Playing Cards with your friends(Insertion Sort).
  4. sort() — uses IntroSort(a hybrid of Quicksort, Heapsort, and Insertion Sort), Faster than qsort().

GRAPHS

  1. Facebook, Instagram, and all social media networking sites, every user is Node, use the graph to suggest friends.
  2. The GPS navigation system also uses shortest path APIs. Google Maps, Apple Maps, and Bing Maps.
  3. React’s virtual DOM uses graph data structures.
  4. MS Excel uses DAG(Directed Acyclic Graphs).
  5. Path Optimization Algorithms, BFS, DFS.
  6. Recommendation Engines.
  7. Scientific Computations.
  8. Flight Networks.
  9. Page ranking.

TREE

  1. A decision-based algorithm is used in machine learning which works upon the algorithm of a tree.
  2. Databases also use B-Tree data structures for indexing.
  3. Domain Name Server(DNS) also uses tree structures.
  4. The file system of computer or mobile.
  5. Parsers(XML parser), Filesystem.
  6. Code Compression(zip).
  7. DOM in Html.
  8. Evaluate an expression (i.e., parse).
  9. Integral to compilers/automata theory.
  10. To store the possible moves in a chess game.
  11. To store the genealogy information of biological species.
  12. Used by JVM (Java Virtual Machine) to store Java objects.
  13. Posting questions on websites like Quora, the comments are a child of questions.
  14. It is used in parsers, filesystems, IP routing tables, data analysis, and data mining applications.

BST

  1. 3D Game Engine.
  2. Computer Graphics Rendering.

Red-Black Trees

  1. Used when there is frequent Insertion/Deletion and few searches.
  2. K -mean Clustering using red-black tree, Databases, Simple-minded database, searching words inside dictionaries, searching on the web.
  3. Process Scheduling in Linux.

AVL Trees

  1. More Search and less of Insertion/Deletion
  2. Data Analysis and Data Mining and the applications which involve more searches

Suffix tree

  1. Fast full-text search, used in most word processors.

TRIE

  1. Dictionary application.
  2. Autocomplete feature in searching.
  3. Auto-completing the text and spells checking.

HASH TABLE

  1. Data stored in databases is generally of the key-value format which is done through hash tables.
  2. Social network “feeds”.
  3. Every time we type something to be searched in google chrome or other browsers, it generates the desired output based on the principle of hashing.
  4. Message Digest, a function of cryptography also uses hashing for creating output in such a manner that reaching the original input from that generated output is almost next to impossible.
  5. In our computers we have various files stored in it, each file has two very crucial information that is, filename and file path, in order to make a connection between the filename to its corresponding file path hash tables are used.
  6. Password hashing.
  7. Used for fast data lookup — symbol table for compilers, database indexing, caches, Unique data representation.
  8. To store a set of fixed keywords that are referenced very frequently.

HEAP

  1. Systems concerned with security and embedded systems such as Linux Kernel uses Heap Sort because of the O( n log(n) ).
  2. If we are stuck in finding the K-th smallest (or largest) value of a number then heaps can solve the problem in an easy and fast manner. used by JVM (Java Virtual Machine) to store Java objects.

GREEDY ALGORITHM

  1. Dijkstra algorithm.
  2. Shopping on a tight budget but want to buy gifts for all family members.
  3. Prim’s and Kruskal’s algorithms are used for finding the minimum spanning trees.

DIJKSTRA ALGORITHM

  1. Used in applications like Google Maps to find the shortest path in a graph.

PRIM’S and KRUSKAL’S

  1. Used for finding the minimum spanning trees.

DYNAMIC PROGRAMMING

A. Real-life examples

  1. In Google Maps to find the shortest path between the source and the series of destinations (one by one) out of the various available paths.
  2. In networking to transfer data from a sender to various receivers in a sequential manner.

B. Applications in Computer science

  1. Multi-stage graph
  2. Traveling salesman problem
  3. Largest common subsequence - to identify similar videos used by youtube
  4. Optimal search binary tree- to get optimized search results.
  5. Single source shortest path- Bellman-Ford Algorithm.
  6. Document Distance Algorithms- to identify the extent of similarity between two text documents used by Search engines like Google, Wikipedia, Quora, and other websites.

BACKTRACKING

  1. Suppose we are coding a chess-playing algorithm and at a certain point, the algorithm finds that a set of steps fails to win. In this situation, the algorithm will reverse back to the safe state and try another possible set of steps.
  2. Sudoku solver
  3. 2048 game

MISC:

  1. Binary search can be used in negotiations. If the seller has a price in mind but does not reveal it, you can name a low bid, to which the seller will respond with a high ask price. You can then raise your bid, and the seller can lower her asking price. Since each of you has an ideal price in mind, the named bids and asks can be roughly halfway toward the price desirable by each side. This is not exactly the binary search algorithm, but very much in the spirit of binary search.
  2. Hashmap has its internal implementation in the AVL tree.

Note — I cannot claim 100% copyright on the content, some lines are taken from other sources over Quora and Youtube.