Data Structures and Algorithms

  The Core Concept: Hashing Both Hash Maps and Hash Sets use a technique called  hashing  to achieve near-instant lookups. What is Hashing? Hashing is the process of taking an input (the  key ) and converting it into a fixed-size numerical value (the  hash code  or  hash value ). This hash code is then used as an index into an underlying array, where the data is stored. Hash Function:  A mathematical function that converts the key into an integer. For example, for a string "ABC," the hash function might calculate the sum of the ASCII values of 'A', 'B', and 'C'. Index Calculation:  Since the hash code can be very large, it is typically reduced to a valid index using the  modulo operator  ( % ) with the size of the underlying array (e.g.,  index = hash_code % array_size ). The Goal of a Good Hash Function The primary goal is to minimize  collisions . A  collision  occurs when two different keys map to the same arr...

 A heap is a  special tree-based data structure  that satisfies two rules: 1.  Heap Property Depending on the type of heap: Min-Heap Every parent node is less than ( ≤)  it's children. The smallest element is always at the  root . Max-Heap Every parent node is  ≥  its children. The largest element is always at the  root . It does  not  require a fully sorted structure, only the parent/child relationship must follow the rule. 2.  Complete Binary Tree Property A heap is always a  complete binary tree , meaning: It is filled  level by level , from left to right. No gaps are allowed except possibly at the last level. This makes it easy to store a heap inside an  array  without needing pointers. How a Heap Is Stored in an Array For a node at index  i : Left child = index  2i Right child = index  2i + 1 Parent = index  i // 2 This mapping is why heaps work efficiently inside arrays.

  The  top k elements  pattern is an important technique in coding that helps us efficiently find a specific number of elements, known as  k, from a set of data. This is particularly useful when we’re tasked with identifying the largest, smallest, or most/least frequent elements within an unsorted collection. Which data structure can we use to solve such problems? A heap is the best data structure to keep track of the smallest or largest k  elements. With this pattern, we either use a max heap or a min heap to find the smallest or largest k elements, respectively, because they allow us to efficiently maintain a collection of elements ordered in a way that gives us quick access to the smallest (min heap) or largest (max heap) element. Algorithm Max Heap => Smallest k elements Min Heap => Largest k elements Top 3 largest numbers

 T he  DNA sequence  is composed of a series of nucleotides abbreviated as  'A' ,  'C' ,  'G' , and  'T' For example,  "ACGAATTCCG"  is a  DNA sequence . When studying  DNA , it is useful to identify repeated sequences within the DNA. Given a string  s  that represents a  DNA sequence , return all the  10 -letter-long  sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in  any order .   Example 1: Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"] Ex ample 2: Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]

Imagine that you're allowed to select 3 chocolate chip cookies in a contiguous subarray. Your goal is to find a window of 3 cookies with the most amount of chips! The same concept can be applied to arrays or strings. The window boundry is defined by the left and right pointers as shown in the picture below: Sliding window, k = 3 Example: Find the Maximum of subarray Detect repeating pattren in a string

  You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and   it will automatically contact the police if two adjacent houses were broken into on the same night . Given an integer array  nums  representing the amount of money of each house, return  the maximum amount of money you can rob tonight  without alerting the police .   Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2: Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12. Answer: Think of the answer in terms of a decision tree. You can either start at position at index 0 or 1. Since ...