DSA CHEAT SHEET — Save This Post!
Most Asked Patterns in TCS Infosys Amazon Interviews!

====================================

90% of coding interviews use THESE 10 patterns.
Master these = crack any tech interview!

====================================
PATTERN 1: TWO POINTERS
Use when: Sorted array, find pairs, remove duplicates
Problems: Two Sum, Reverse String, 3Sum
Logic: left=0, right=n-1, move based on condition
Companies: Amazon, Microsoft, TCS

PATTERN 2: SLIDING WINDOW
Use when: Subarray/substring with condition
Problems: Max sum subarray, Longest substring
Logic: Expand right, shrink left when invalid
Companies: Infosys, Wipro, Google

PATTERN 3: BINARY SEARCH
Use when: Sorted array, find position/condition
Problems: Search in rotated array, Find peak
Logic: mid = (lo+hi)//2, eliminate half each time
Companies: Amazon, Flipkart, Accenture

PATTERN 4: LINKED LIST (Fast & Slow Pointer)
Use when: Cycle detection, find middle
Problems: Detect cycle, Find middle, Palindrome
Logic: slow moves 1 step, fast moves 2 steps
Companies: TCS, Infosys, HCL

PATTERN 5: TREE BFS (Level Order)
Use when: Level-by-level traversal, shortest path
Problems: Level order, Zigzag, Right side view
Logic: Use queue, process level by level
Companies: Amazon, Cognizant, Capgemini

====================================
PATTERN 6: TREE DFS
Use when: Path sum, depth, validate BST
Problems: Max depth, Path sum, Inorder traversal
Logic: Recursion — visit node, left, right
Companies: Microsoft, Wipro, IBM

PATTERN 7: DYNAMIC PROGRAMMING
Use when: Optimization, count ways, max/min
Problems: Fibonacci, Knapsack, LCS, Coin change
Logic: Break into subproblems, store results
Companies: Amazon, Goldman Sachs, Barclays

PATTERN 8: STACK
Use when: Matching brackets, next greater element
Problems: Valid Parentheses, Stock Span, Min Stack
Logic: Push/pop based on LIFO order
Companies: TCS, Accenture, Infosys

PATTERN 9: HASHING (HashMap)
Use when: Count frequency, find duplicates, grouping
Problems: Two Sum, Anagram, Group Anagrams
Logic: key=element, value=count/index
Companies: Google, Amazon, Flipkart

PATTERN 10: GREEDY
Use when: Local optimal = global optimal
Problems: Activity selection, Jump game, Intervals
Logic: Always pick the best option at each step
Companies: Wipro, HCL, Mindtree

====================================
MUST KNOW COMPLEXITY:

Array access -> O(1)
Binary Search -> O(log n)
Linear Search -> O(n)
Bubble Sort -> O(n2)
Merge/Quick Sort-> O(n log n)
HashMap get/put -> O(1) average
BFS/DFS -> O(V + E)

====================================
30-DAY DSA PLAN FOR PLACEMENTS:

Week 1: Arrays + Strings + Hashing
Week 2: Linked List + Stack + Queue
Week 3: Trees + Binary Search
Week 4: DP + Greedy + Mock Tests

Practice on: LeetCode / GeeksForGeeks
Target: 2 problems daily = 60 problems/month

====================================
SAVE this post now!
You will need it before every interview!

Want FREE projects for your resume too?
https://t.me/Projectwithsourcecodes

Share with your placement batch!

#DSA #DataStructures #Algorithms #CodingInterview
#TCS #Infosys #Wipro #Amazon #Microsoft #Google
#LeetCode #PlacementPrep #CampusPlacement
#BTech2026 #MCA2026 #BCA2026 #OffCampus
#DynamicProgramming #BinarySearch #LinkedList
#ProjectWithSourceCodes #StudentsOfIndia #Coding

DSA CHEAT SHEET — Save This!
Data Structures Asked in Every Interview!

====================================

DSA is tested in ALL product company interviews!
Amazon, Google, Microsoft, Flipkart, Adobe —
ALL start with DSA rounds. Master this!

====================================
ARRAYS — Most Basic, Most Asked!

Find max/min in array -> O(n) linear scan
Reverse an array -> two pointer approach
Find duplicates -> use HashSet O(n)
Rotate array by k -> reverse technique
Two Sum problem -> HashMap O(n)
Sliding Window -> for subarray problems

====================================
STRINGS

Palindrome check -> two pointers
Anagram check -> sort both or HashMap
Longest common prefix -> vertical scan
Count vowels/consonants -> loop + set
String reversal -> s[::-1] in Python

====================================
LINKED LIST — Very Frequently Asked!

Reverse a linked list -> 3 pointer trick
Detect cycle -> Floyd's algo (slow/fast)
Find middle node -> slow/fast pointers
Merge 2 sorted lists -> compare & merge
Remove Nth node from end -> two pass

====================================
STACK & QUEUE

Stack: LIFO — use for:
-> Valid parentheses check
-> Next Greater Element
-> Undo/Redo operations

Queue: FIFO — use for:
-> BFS (level order traversal)
-> Sliding window maximum

====================================
TREES — 30% of Interview Questions!

Inorder: Left -> Root -> Right
Preorder: Root -> Left -> Right
Postorder: Left -> Right -> Root

Level Order -> use Queue (BFS)
Height of tree -> recursion
Check BST -> inorder should be sorted
LCA of two nodes -> recursive approach

====================================
SORTING ALGORITHMS

Bubble Sort -> O(n²) | Simple
Selection Sort -> O(n²) | Simple
Insertion Sort -> O(n²) | Best for small
Merge Sort -> O(nlogn) | Stable sort
Quick Sort -> O(nlogn) | In-place

For interviews: Know Merge Sort well!

====================================
SEARCHING

Linear Search -> O(n) | Unsorted array
Binary Search -> O(logn) | Sorted array only

Binary Search template:
low, high = 0, len(arr)-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: low = mid+1
else: high = mid-1

====================================
TIME COMPLEXITY QUICK REFERENCE:

O(1) -> Constant | Array index access
O(logn) -> Log | Binary search
O(n) -> Linear | Single loop
O(nlogn) -> Linearithmic | Merge sort
O(n²) -> Quadratic | Nested loops

====================================
TOP DSA PLATFORMS TO PRACTICE:
LeetCode -> leetcode.com (must!)
HackerRank -> hackerrank.com
GeeksForGeeks -> geeksforgeeks.org
Codeforces -> codeforces.com

====================================
Save this post — revise before every interview!
Get FREE projects with DSA implementation:
https://t.me/Projectwithsourcecodes

Share with your placement batch!

#DSA #DataStructures #Algorithms #LeetCode
#CodingInterview #TechInterview #Placements
#BTech2026 #MCA2026 #BCA2026 #CompetitiveCoding
#Java #Python #DSACheatSheet #FAANG
#ProjectWithSourceCodes #StudentsOfIndia

DSA CHEAT SHEET - Save This!
Data Structures Asked in Every Tech Interview!

====================================

DSA is tested at Amazon, Google, Microsoft,
Flipkart, Adobe, Uber, Swiggy — ALL of them!
Master these before your placement rounds!

====================================
ARRAYS - Most Basic, Most Asked!

Two Sum -> HashMap O(n)
Find max/min -> linear scan O(n)
Reverse array -> two pointers O(n)
Find duplicates -> HashSet O(n)
Rotate by k -> reverse technique O(n)
Subarray sum -> sliding window O(n)
Merge sorted arrays -> two pointer O(n+m)

====================================
STRINGS

Palindrome check -> two pointers O(n)
Anagram check -> sort or HashMap O(n)
Longest substring no repeat -> sliding window
String reversal -> s[::-1] in Python
Count char frequency -> HashMap O(n)

====================================
LINKED LIST - Very Frequently Asked!

Reverse linked list -> 3 pointer trick O(n)
Detect cycle -> Floyd's slow/fast O(n)
Find middle -> slow/fast pointers O(n)
Merge 2 sorted lists -> compare & link O(n)
Remove Nth from end -> two pass O(n)

====================================
STACK & QUEUE

Stack (LIFO) - use for:
-> Valid parentheses {[()]}
-> Next Greater Element
-> Undo/Redo operations

Queue (FIFO) - use for:
-> BFS (level order tree traversal)
-> Sliding window maximum

====================================
TREES - 30% of Interview Questions!

Inorder: Left Root Right
Preorder: Root Left Right
Postorder: Left Right Root
Level Order: BFS using Queue

Height of tree -> recursion O(n)
Check BST valid -> inorder sorted check
Lowest Common Ancestor -> recursive O(n)
Path sum root to leaf -> DFS O(n)

====================================
GRAPHS

BFS -> Queue, shortest path unweighted
DFS -> Stack/Recursion, path finding
Detect cycle undirected -> Union Find
Detect cycle directed -> DFS + visited
Topological Sort -> Kahn's algo (BFS)

====================================
DYNAMIC PROGRAMMING

Fibonacci -> memoization O(n)
0/1 Knapsack -> 2D DP O(n*W)
Longest Common Subsequence -> 2D DP
Coin Change -> bottom-up DP O(n*amount)
Climb Stairs -> DP same as Fibonacci

====================================
TIME COMPLEXITY QUICK REFERENCE:

O(1) Constant | Array index
O(logn) Log | Binary search
O(n) Linear | Single loop
O(nlogn) Linearithmic | Merge sort
O(n2) Quadratic | Nested loops
O(2n) Exponential | Recursion tree

====================================
TOP DSA PRACTICE PLATFORMS:
LeetCode -> leetcode.com (must!)
GeeksForGeeks -> geeksforgeeks.org
HackerRank -> hackerrank.com
Codeforces -> codeforces.com

====================================
Save this - revise before every interview!
Get FREE projects with DSA implementations:
https://t.me/Projectwithsourcecodes

Share with your placement batch!

#DSACheatSheet #DSA #DataStructures #Algorithms
#LeetCode #CodingInterview #Placements #FAANG
#BTech2026 #MCA2026 #BCA2026 #CompetitiveCoding
#Java #Python #TechInterview #DynamicProgramming
#ProjectWithSourceCodes #StudentsOfIndia

🚀 Advanced Coding Interview Questions with Answers (Part 3)
1️⃣1️⃣ Find the Top K Frequent Elements
👉 Given an array, return the k elements that appear most frequently.

from collections import Counter

def top_k_frequent(nums, k):
    frequency = Counter(nums)
    return [num for num, count in frequency.most_common(k)]

print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))

📌 Output:

[1, 2]

⏱️ Time Complexity: O(n log n)
💾 Space Complexity: O(n)
1️⃣2️⃣ Generate All Permutations of a String
👉 Generate every possible arrangement of the characters in a string using Backtracking.

def permutations(s):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append("".join(path))
            return

        for i in range(len(remaining)):
            backtrack(
                path + [remaining[i]],
                remaining[:i] + remaining[i + 1:]
            )

    backtrack([], s)
    return result

print(permutations("ABC"))

📌 Output:

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

⏱️ Time Complexity: O(n × n!)
💾 Space Complexity: O(n × n!)
1️⃣3️⃣ Find the Minimum Coins for a Given Amount
👉 Given coin denominations, find the minimum number of coins required to make a target amount.

def min_coins(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0

    for current in range(1, amount + 1):
        for coin in coins:
            if coin <= current:
                dp[current] = min(
                    dp[current],
                    dp[current - coin] + 1
                )

    return dp[amount] if dp[amount] != float("inf") else -1

print(min_coins([1, 2, 5], 11))

📌 Output:

3

💡 5 + 5 + 1 = 11
⏱️ Time Complexity: O(amount × number of coins)
💾 Space Complexity: O(amount)
1️⃣4️⃣ Find the Maximum Product Subarray
👉 Find the contiguous subarray whose elements have the largest product.

def max_product_subarray(nums):
    current_max = nums[0]
    current_min = nums[0]
    result = nums[0]

    for num in nums[1:]:
        if num < 0:
            current_max, current_min = current_min, current_max

        current_max = max(num, current_max * num)
        current_min = min(num, current_min * num)

        result = max(result, current_max)

    return result

print(max_product_subarray([2, 3, -2, 4]))

📌 Output:

6

💡 The maximum product comes from [2, 3].
⏱️ Time Complexity: O(n)
💾 Space Complexity: O(1)
1️⃣5️⃣ Implement an LRU Cache
👉 An LRU (Least Recently Used) Cache removes the item that has not been accessed for the longest time when the cache reaches its capacity.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1

        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)

        self.cache[key] = value

        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

📌 Example:

cache = LRUCache(2)

cache.put(1, "A")
cache.put(2, "B")

print(cache.get(1))

cache.put(3, "C")

print(cache.get(2))

📌 Output:

A
-1

⏱️ Average Time Complexity: O(1) for get() and put()
💾 Space Complexity: O(capacity)
💬 Save this for your advanced coding interview preparation!
🔥 Part 4 will cover 5 advanced problems on Dijkstra's Algorithm, Trie, Union-Find, Matrix & Dynamic Programming.
#Coding #CodingInterview #Python #DSA #AdvancedCoding #Algorithms #DynamicProgramming #Graph #DataStructures #Programming