Author: devangini123

🌙 Quick Sort (Divide and Conquer) [8, 3, 1, 7, 0, 10, 2] [1, 0, 2, 7, 3, 10, 8] Now, Choose 8 as pivot: [0, 1, 2, 7, 3, 8, 10] Now Choose 3 as pivot [0, 1, 2, 3, 7, 8, 10]: SORTED ARRAY We can choose any element as the pivot, but for simplicity, we select the last element since it makes the algorithm easier to implement. Algorithm Steps Choose a pivot element Select one element from the array (commonly first, last, middle, or random). Partition the array Rearrange elements so that: Elements smaller than the pivot…

🌙 Problem Statement: A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie Class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false…

🌙 Time & Space Complexity in Tries Time Complexity Insert: O(n) where n: no. of character in words. Search: O(n) where: n = no. of character in words. Prefix: O(P) where: p = no. of words in prefix. Space Complexity O(total character) speed >>> space In a Trie data structure, the space complexity is relatively high, but this trade-off is acceptable because it provides much faster search performance. When to use Trie Data Structure? Prefix Search: All words that starts with ‘any letter’. Auto Complete Dictionary-based problems Word Suggestions Spell Checking Whe NOT to use Trie Data Structure? Exact Search…

🌙 Trie Node Structure Code: class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } Trie Structure Code: class Trie { constructor() { this.root = new TrieNode(); } } Points to Remember The root node is the starting point of a Trie data structure. Each Trie node has two main properties: children and an end-of-word flag. A Trie requires only a root node, and all words and operations originate from it. Trie Operations Insert, Search, Prefix ant, and, cat, cap, car, card Insert: Search(cat): It checks the path and verifies the end-of-word flag, then returns true. Search(cal):…

🌙 Trie Trie is a tree like data structure that is used to store strings efficiently, especially when prefix based operations are required. It is also known as Prefix-Tree. Specification of the Data Structure: Words are stored character by character. Common prefix are shared. Each path represents a prefix. Some of them are marked as words. What is the purpose of using a Trie data structure? Determine the number of words that begin with ‘ca’. [car, cat, cap, cup, cupboard, cut, cutter, cot] Advantage’s of Trie Data Structure Prefix-based operations: It efficiently supports prefix searches, making it ideal for autocomplete…

🌙 Problem Statement You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi – xj| + |yi – yj|, where |val| denotes the absolute value of val. Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points. Example 1: Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as shown above to get the minimum…

🌙 Problem Statement You are in a city that consists of n intersections numbered from 0 to n – 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections. You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from…

🌙 Problem Statement There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1. Example 1: Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 Output: 700 Explanation: The graph is shown above. The optimal path…

🌙 Problem Statement: There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network. You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it is…

🌙 Comparison – Prim’s vs Kruskal Algorithm