Ever wondered why DSA is so much important in implementing software and as well as hiring process. Why the companies is primarily focused on taking DSA and not some specific language/framework questions?
Knowledge of DSA like Tree, graphs, array and various other algorithm goes a long way in solving problem efficiently with proper tool. Just like a car mechanic needs the right tool to fix a car and make it run properly, a programmer needs the right tool (algorithm and data structure) to make the software run properly. So the interviewer wants to find a candidate who can apply the right set of tools to solve the given problem.
In this blog I'll share some examples of DSA used in real life. So, lets' get started with array
- 2D arrays, commonly known as, matrices, are used in image processing.
- Arrays can be used in speech processing where every speech signal is an array.
- In games like online chess, where the player can store his past moves as well as current moves. It indicates a hint of position.
- It is also used in record management.
- Contacts on a cell phone.
- For CPU scheduling in computer.
- Your viewing screen is also a multidimensional array of pixels.
- Spam email detection.
- Plagiarism detection.
- Linked lists are used to display image containers. Users can visit past, current, and next images.
- They are used to store the history of the visited page.
- They are used to perform undo operations.
- Linked are used in software development where they indicate the correct syntax of a tag.
- Linked lists are used to display social media feeds.
- In a music playlist, songs are linked to the previous and next.
- Used in switching between applications and programs (Alt + Tab) in the Operating system (implemented using Circular Linked List)
- 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.
A queue is a data structure that uses LIFO order.
- Undo/Redo button/operation in word processors.
- Wearing/Removing Bangles.
- Pile of Dinner Plates.
- Stacked chairs.
- Changing wearables on a cold evening, first in, comes out at last.
- Last Hired, First Fired — which is typically utilized when a company reduces its workforce in an economic recession.
- Loading bullets into the magazine of a gun. The last one to go in is fired first. Bam!
- Scratch card’s earned after Google pay transaction.
A queue is a data structure that uses FIFO order.
- In Escalators.
- Printer spooler.
- Sending emails.
- Car washes queue.
- Server while responding to requests.
- Operating System uses queues for job/task scheduling.
- Data packets in communication are arranged in queue format.
- Stack/Queue is used in the back and forward buttons of the web browser.
- While switching multiple applications, windows uses a circular queue.
- A circular queue is used to maintain the playing sequence of multiple players in a game.
- A queue can be implemented in — Linked List-based Queue, Array-based Queue, Stack-based Queue.
- Process scheduling in the kernel.
- Priority queues are used in file downloading operations in a browser.
- Order things by their value.
- Backend Databases (Merge Sort).
- Playing Cards with your friends (Insertion Sort).
- sort() — uses IntroSort (a hybrid of Quicksort, Heapsort, and Insertion Sort), Faster than qsort().
- Facebook, Instagram, and all social media networking sites, every user is Node, use the graph to suggest friends.
- The GPS navigation system also uses shortest path APIs. Google Maps, Apple Maps, and Bing Maps.
- React’s virtual DOM uses graph data structures.
- MS Excel uses DAG (Directed Acyclic Graphs).
- Path Optimization Algorithms, BFS, DFS.
- Recommendation Engines.
- Scientific Computations.
- Flight Networks.
- Page ranking.
- A decision-based algorithm is used in machine learning which works upon the algorithm of a tree.
- Databases also use B-Tree data structures for indexing.
- Domain Name Server (DNS) also uses tree structures.
- The file system of computer or mobile.
- Parsers(XML parser), Filesystem.
- Code Compression(zip).
- DOM in Html.
- Evaluate an expression (i.e., parse).
- Integral to compilers/automata theory.
Binary Search Tree
- 3D Game Engine.
- Computer Graphics Rendering.
- Dictionary application.
- Autocomplete feature in searching.
- Auto-completing the text and spells checking.
- Data stored in databases is generally of the key-value format which is done through hash tables.
- Social network “feeds”.
- 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.
- 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.
- 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.
- Password hashing.
- Used for fast data lookup — symbol table for compilers, database indexing, caches, Unique data representation.
- Systems concerned with security and embedded systems such as Linux Kernel uses Heap Sort because of the O( n log(n) ).
- 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.
- Dijkstra algorithm.
- Shopping on a tight budget but want to buy gifts for all family members.
- Prim’s and Kruskal’s algorithms are used for finding the minimum spanning trees.
- Used in applications like Google Maps to find the shortest path in a graph.
- 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.
- In networking to transfer data from a sender to various receivers in a sequential manner.
- 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.
- Sudoku solver
- 2048 game
Note — I cannot claim 100% copyright on the content, some examples are taken from other sources over Quora(Igor Markov).
Thanks for reading.💗 Connect me on LinkedIn
Did you find this article valuable?
Support Sagar Medtiya by becoming a sponsor. Any amount is appreciated!