Scribd
Upload
277 views4 pages

DSA Cheat Sheet

This document provides a cheat sheet on common data structures and algorithms used in coding interviews. It summarizes the main uses of hash sets, hash maps, binary search, two pointers, sliding window, prefix sum, bit manipulation, intervals, matrices, and array lists. For each technique, it lists examples of problems they can help solve and key characteristics. The document aims to help interview candidates understand when and how to apply different approaches.

Uploaded by

Joe Sunil Devotta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
277 views4 pages

DSA Cheat Sheet

This document provides a cheat sheet on common data structures and algorithms used in coding interviews. It summarizes the main uses of hash sets, hash maps, binary search, two pointers, sliding window, prefix sum, bit manipulation, intervals, matrices, and array lists. For each technique, it lists examples of problems they can help solve and key characteristics. The document aims to help interview candidates understand when and how to apply different approaches.

Uploaded by

Joe Sunil Devotta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

DSA CheatSheet

HashSet

HashMap

Binary Search

Two Pointers or Iterators

Sliding Window

Prefix Sum

Bit Manipulation

Intervals

Matrix

ArrayList

HashSet
● When you have to find a unique element or check if the set of elements have
duplicates
○ Contains Duplicates
● When you have to keep track of a unique set of elements
○ Happy Number
● To achieve faster lookups or O(1) time complexity.

HashMap
● When you have to find the frequency or count of occurrences
○ First Unique Integer, Majority Element, Word Frequencies
● When you have to store the mapping of keys to their value
○ Two Sum In Unsorted Array, Three Sum
● To achieve faster lookups or O(1) time complexity.
● Anagram/Permutation/Palindrome - which you can solve by keeping track of the
number of occurrences of characters
○ Valid Anagram, Find All Anagrams In a String, Permutation Palindrome
Binary Search
● When you are given a sorted array
○ Search in a rotated sorted array, Find Minimum in Rotated Sorted Array
● To perform search operation in O(log N) time complexity
○ Find Peak Element, Find First and Last Position of Element in Sorted Array
● Problems related to “Maximise the minimum” or “Minimize the maximum” something is
usually solved using Binary Search
○ Koko Eating Bananas, Capacity to ship packages within D Days, Find Smallest
divisor given a threshold

Two Pointers or Iterators


● In Two pointers - the set of pointers move in either of the pattern given below
○ One pointer starts from the beginning while the other pointer starts from the end
■ Container with Most Water, Squares of Sorted Array, Rotate Array
○ One will be a slow-runner and the other fast-runner also known as the Hare &
Tortoise algorithm. This approach is quite useful when dealing with cyclic
linked lists or arrays.
■ Detect LinkedList Cycle, Remove Nth Node from the end of the list,
Middle of the LinkedList
● In scenarios when you have to track two variables or nodes in a linear data structure
such as LinkedList, Arrays and ArrayList it is more commonly used. It is often useful
when searching for pairs.
○ Remove Duplicates from Sorted Array, Move Zeroes
● Two Pointers is especially helpful to solve problems Inplace or O(1) Space complexity.
○ Reverse a Linked List, Dutch National Flag Problem or Sort Colours

Sliding Window
● The Sliding Window technique is used when we’re supposed to consider all
subarray/substrings with some particular constraint such that it is possible to
increment/decrement the window size in each iteration.
○ Longest Substring without repeating characters, Longest Substring with at most
K Distinct Character, Length of the Longest substring without repeating
characters
● It's also implemented by using TwoPointers which act as a window that is constant in
size or grows or shrinks with respect to the problem you are solving.
○ Minimum Window Substring, Fruits into Basket

Prefix Sum
● Whenever the value at a particular position of an array depends on all previous
elements or all the next elements, we can either use prefix sum or suffix sum.
○ Product of Array, Find Pivot Index, Minimum size subarray sum
● As values are precomputed it reduces the time complexity to O(n).
● When the subarray sum is to be equal to a given value
○ Zero Sum Subarrays, Prefix Sum Array applications

Bit Manipulation
● XOR of A ^ A = 0 and A ^ 0 = A. Thus used to find unique elements.
○ Single Number, Missing Numbers, Single Number - 2
● To remove the last set bit - A&(A-1)
○ Number of 1 bits or Hamming Weight, Counting Bits
● To find Union of A and B - or operation A | B and to find the intersection of A and B - and
operation A & B
○ Sum of two Numbers
● Bit Masking is the act of applying a mask to a value defining which bits you want to
keep, and which bits you want to clear. Masking. << to shift bits to left and >> or >>> to
shift bits to right.
○ Reverse Bits

Intervals
● If you hear the term overlapping intervals or are asked to produce a list with mutually
exclusive intervals/non-overlapping intervals.
○ Insert Interval, Non-overlapping intervals
● Sorting by start time or end time makes it easier to solve
○ Merge Intervals, Meeting Rooms
● Heap may be applicable to solve intervals
○ Minimum Meeting Rooms

Matrix
● Matrix problems are about understanding boundary conditions and the finding pattern
or logic by trying out the sample inputs.
○ Set Matrix Zeroes, Spiral Matrix, Rotate Image, Diagonal Traverse

ArrayList
● When we need to dynamically insert elements (not fixed size). Otherwise same
characteristics as an array
○ Find all numbers disappeared in an array, Intersection of two arrays, Minimum
Index sum of two lists

References
● Smarter way to prepare for coding interviews
● Sliding Window for beginners
● Binary Search for beginners

You might also like