Author: devangini123
🌙 Problem Statement: Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows: Given an integer array cuts where cuts[i] denotes a position you should perform a cut at. You should perform the cuts in order, you can change the order of the cuts as you wish. The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two…
🌙 Problem Statement: You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where: 0
🌙 Problem Statement: You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Examples: Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to…
🌙 Problem Statement: You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Examples: Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to…
🌙 Counting Sort (Stable) Stable sort means, relative order of the elements remains unchanged. Example Steps, we follow: Firstly, determine the range of the elements in the array by finding the minimum and maximum values. This range helps decide the size of the count array. Create the count array based on the calculated range and initialize all its values to zero. Then, traverse the original array and store the frequency of each element in the count array. Convert the count array into a prefix (cumulative) array by adding the current count with the previous one. This step helps in determining…
🌙 Interview Cheatsheet One Line Summary Bubble Sort: Keep Swaping adjacent elements until sorted. Selection Sort: Pick the smallest and place it in front. Insertion Sort: Insert each element into its correct position. Merge Sort: Divide, sort halves, then merge. Quick Sort: Place one element correctly, repeat on both sides. Heap Sort: Repeatedly take max/min from a heap. Counting Sort: Count frequencies instead of comparing. Radix Sort: Sort digits one by one using counting sort. Bucket Sort: Distribute into ranges, sort locally, merge. Real-World Use Cases Quick Sort: Default choice in many systems. Merge Sort: Databases, linked lists, stable sorting.…
🌙 Bucket Sort Distribution – based sorting algorithms. Example [0.70, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.23, 0.68] bucket[1] = [0.17] bucket[2] = [0.21, 0.23, 0.26] bucket[3] = [0.39] bucket[6] = [0.68] bucket[7] = [0,70, 0.72] bucket[9] = [0.94] Now, if we read from top to bottom: [0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.70, 0.72, 0.94] Hence, the data is Sorted. If all elements fall into a single bucket, then traditional sorting algorithms must be used. The main advantage of Bucket Sort lies in distribution—if the data is distributed properly, sorting becomes very efficient. Bucket Sort is mainly used when…
🌙 Radix Sort Radix sort is a non-comparison sorting algorithm. Instead of comparing elements directly, it sorts numbers digit by digit (or character by character), starting from either the least significant digit (LSD). Example [170, 45, 75, 90, 802, 24, 2, 66] Sort First LSD: [170, 90, 802, 2, 24, 45, 75, 66] Sort Second LSD: [802, 2, 24, 45, 66, 170, 75, 90] Sort Third LSD: [2, 24, 45, 66, 75, 90, 170, 802] Time Complexity O(d * (n + k)) where k: range, d = digits Effectively o(n) for integers. Space Complexity O(n + k) When to use…
🌙 Counting Sort (Stable) Code Time Complexity O(n + k) where k: range. if k
🌙 Counting Sort Counting Sort is a non-comparison based sorting algorithm. It works by counting how many times each element appears, then reconstructing the sorted array using those counts. Best when: Numbers are non-negative integers. Range (max – min) is small. Time Complexity O(n + k) where k: range. If ‘k’ (range) is small, then this algorithm is efficient. Space Complexity O(K) Points to remember while using this algorithm Elements are integers. Values are small in range. Examples Marks of students (0 to 100) (range) Percentages Sort based on Ages (0-120) Digits(0 – 9) Disadvantage Not Stable algorithm Reasons: We…
