dsa-programs

Data Structures and Algorithm Programs

• Language: Java

Table of Contents

• Data Structures & imp classes
• Basic Programs
• Algorithms
• FAANG Companies hiring process
• Sources

Contents

• Data Structures & important classes

  • Dynamic int[] Array
  • Stream API
  • Collections Utility Class
  • List
  • LinkedList, DoubleLinkedList & CircularLinkedList
  • HashMap
  • Queue, Dequeue & PriorityQueue
  • Stack
  • Binary Search
  • BinaryTreeNode sample / example class
  • BinaryTree Basics
  • Binary Search Tree BST
  • Graphs
  • Disjoint Set Union DSU / Union Find
  • Annotation Type
  • Enum Types & Conversions
  • Functional Interface
  • Record
  • Date & Time
  • Multi-Threading in Java

• Basic Programs

  • AllDivisors
  • ArmstrongNumber
  • CountDigits
  • GCD_HCF
  • LeapYear
  • Palindrome Or ReverseNumber
  • Patterns and shapes
  • PrimeNumber
  • Anagram
  • WordPattern
  • Number of Steps to Reduce the Number to Zero
  • Fizz Buzz
  • Richest Customer Wealth
  • Running Sum of 1D Array

• ALGORITHMS

1. BackTracking

   • Combination Sum I & Backtracking Intro
   • Combination Sum II
   • Combination Sum III
   • LetterCombinations of a PhoneNumber
   • NonContiguousSubArraySum
   • GenerateParentheses
   • Permutations
   • N-Queens
   • Subsets
   • WordSearch
   • PalindromePartitioning
   • Unique 3-Digit Even Numbers
   • Find Unique BinaryString

2. Binary Search

   • Median of Two Sorted Arrays
   • Search in Rotated Sorted Array
   • Find First and Last Position of Element in Sorted Array
   • Search Insert Position
   • Search in 2D Sorted Matrix
   • BinaryTree MaximumPathSum
   • Find Min in RotatedSortedArray
   • Guess Number Higher or Lower
   • Successful Pairs of Spells and Potions
   • Find Peak Element
   • Koko Eating Bananas
   • H-Index

3. BinaryTrees & BinarySearchTrees BST

   • InvertBinaryTree
   • BinaryTreeInOrderTraversal
   • ValidateBinarySearchTree
   • SymmetricTree
   • BinaryTree LevelOrderTraversal
   • BinaryTree using PreOrder & InOrder Traversals
   • SortedArray to BinarySearchTree
   • Flatten BinaryTree to LinkedList
   • BinaryTree RightSideView
   • Kth Smallest Element in BST
   • Lowest Common Ancestor of a Binary Tree / LCA of BT
   • Lowest Common Ancestor of a Binary Search Tree / LCA of BST
   • PathSumIII
   • Diameter of BinaryTree
   • Leaf Similar Trees
   • Count Good Nodes in Binary Tree
   • Longest ZigZag Path in a Binary Tree
   • Maximum Level Sum of a Binary Tree
   • Search in a Binary Search Tree
   • Delete Node in a BST

4. BitManipulation

   • Single Number
   • Counting Bits
   • Minimum Bit Flips to Convert Number
   • Minimum Flips to Make a OR b Equal to c

5. Disjoint Set Union DSU / Union Find

   • Number of Connected Components in an Undirected Graph
   • Number Of Provinces
   • Find the Index of the First Occurrence in a String
   • Redundant Connection
   • Accounts Merge
   • Number of Operations to Make Network Connected
   • Regions Cut By Slashes
   • Satisfiability of Equality Equations
   • Min Cost to Connect All Points
   • Number Of Good Paths
   • Longest Consecutive Sequence
   • Path With Minimum Effort
   • Minimize Hamming Distance After Swap Operations
   • Evaluate Division

6. Divide and Conquer

   • Maximum SubArray
   • Majority Element
   • Kth Largest Element In an Array
   • Search a 2D Matrix II
   • Top K Frequent Elements
   • Median of Two Sorted Arrays
   • Merge k Sorted Lists
   • BinaryTree using PreOrder & InOrder Traversals
   • SortedArray to BinarySearchTree
   • SortList

7. DynamicProgramming

   • Fibonacci_DP_Recursive_Backtracking & DP intro
   • Fibonacci_DP_TopDown_Memoization & DP intro
   • Fibonacci_DP_BottomUp_Tabulation & DP intro
   • Fibonacci_DP_BottomUp_NoMemory & DP intro
   • Partition Equal Subset Sum (Classic 0-1 Knapsack problem without an explicit values[])
   • Classic 0-1 Knapsack Problem (Weights, Values, Capacity)
   • LongestCommonSubsequence
   • LongestPalindromicSubstring
   • LongestValidParenthesis
   • UniquePaths
   • MinimumPathSum
   • ClimbingStairs
   • Edit Distance - Levenshtein Distance Algorithm
   • PascalsTriangle
   • WordBreak
   • MaximumProductSubArray
   • HouseRobber
   • LongestIncreasingSubsequence
   • PerfectSquares
   • CoinChange
   • Maximum possible stability of any subset of servers
   • N-th Tribonacci Number
   • Min Cost Climbing Stairs
   • Domino and Tromino Tiling
   • Best Time to Buy and Sell Stock
   • Best Time to Buy and Sell Stock II
   • Best Time to Buy and Sell Stock with Transaction Fee
   • JumpGame I
   • JumpGame II

8. Graphs

   • Graphs Intro
   • GiftingGroups
   • Number of Islands
   • Course Schedule
   • Rotting Oranges
   • Keys and Rooms
   • Number of Provinces
   • Reorder Routes to Make All Paths Lead to the City Zero
   • Evaluate Division
   • Nearest Exit from Entrance in Maze

9. GreedyAlgorithms

   • OptimizingBoxWeights
   • MinimumNumberOfSwapsToSort
   • JumpGame I
   • JumpGame II
   • BestTime To Buy And Sell Stock
   • Partition Labels
   • H-Index
   • Gas Station
   • Candy

10. Hashing (HashMap, HashSet)

    • GroupAnagrams
    • RansomNote
    • Longest Consecutive Sequence
    • 2Sum
    • SubArraySumEqualsK (contiguous sub-array sum)
    • Find the Difference of Two Arrays
    • Unique Number of Occurrences
    • Determine if Two Strings Are Close
    • Equal Row and Column Pairs

11. Heap / PriorityQueue (minHeap & maxHeap)

    • Kth Largest Element In an Array
    • Top K Frequent Elements
    • Find Median from Data Stream
    • Smallest Number in Infinite Set
    • Maximum Subsequence Score
    • Total Cost to Hire K Workers

12. IntegerArray

    • MaximumRepeatingNumber
    • Closest Equal Element Queries
    • Maximum Unique SubArray Sum After Deletion
    • Count Beautiful Numbers
    • Minimum Cost to Reach Every Position
    • Kids With the Greatest Number of Candies
    • Can Place Flowers
    • Minimum Pair Removal to Sort Array I
    • Increasing Triplet Subsequence
    • Count Special Quadruplets
    • Count Good Triplets
    • Merge Sorted Array
    • Remove Element
    • Remove duplicates from Sorted Array
    • Remove duplicates from Sorted Array II
    • Rotate Array by K times
    • H-Index
    • Insert Delete GetRandom O(1)
    • Product of Array Except Self

13. Intervals

    • Teemo Attacking
    • Merge Intervals
    • Non-overlapping Intervals
    • Minimum Number of Arrows to Burst Balloons

14. LinkedList Algos

    • MiddleOfTheLinkedList
    • Reverse LinkedList
    • Zipper LinkedLists
    • AddTwoNumbers
    • Remove Nth Node From End of List
    • Merge Two Sorted Lists
    • Merge k Sorted Lists
    • Swap Nodes In Pairs
    • Reverse Nodes in k-Group
    • Copy/Clone ListWithRandomPointer
    • LinkedListCycle
    • LinkedListCycle 2
    • SortList
    • LRUCache
    • Intersection of Two LinkedLists
    • Palindrome LinkedList
    • Delete the Middle Node of a Linked List
    • Odd Even Linked List
    • Maximum Twin Sum of a Linked List

15. Matrix

    • Gifting Groups
    • Rotate Image
    • Spiral Matrix
    • Set Matrix Zeroes
    • Search a 2D Matrix II
    • Design Spread sheet

16. Misc

    • Majority Element
    • Maximum SubArray
    • Find the Duplicate Number
    • Sort Colors - 0,1,2
    • Next Permutation
    • First Missing Positive

17. Monotonic Stack

    • Daily Temperatures & Monotonic Stack Intro
    • Daily Temperatures & Monotonic Stack Intro

18. PrefixSum

    • SubArraySumEqualsK (contiguous sub-array sum)
    • ContiguousBinaryArray
    • Find the Highest Altitude
    • Find Pivot Index

19. Queue, Deque & (NOTE: PriorityQueue is Heap)

    • Recent Counter
    • Dota2 Senate

20. Recursion

21. Searching

    • BinaryRecursionSearch
    • BinarySearch
    • LinearSearch

22. Sliding Window

    • Find all the Anagrams in a String
    • LengthOfLongestSubstring
    • Minimum Window Substring
    • Sliding Window Maximum
    • Maximum Average SubArray I
    • Maximum Number of Vowels in a Substring of Given Length
    • Max Consecutive Ones III
    • Longest SubArray of 1's After Deleting One Element

23. Sorting

    • SelectionSort
    • BubbleSort
    • BucketSort
    • CombSort
    • CountingSort
    • HeapSort
    • InsertionSort
    • MergeSort
    • QuickSort
    • RadixSort
    • ShellSort
    • TimSort

24. Stack

    • ValidParentheses
    • DailyTemperatures
    • Largest Rectangle in Histogram
    • Min Stack
    • Decode String
    • Removing Stars From a String
    • Asteroid Collision

25. Strings

    • Parentheses perfection kit
    • Binary String to Palindrome
    • Longest Common Prefix
    • Longest Palindrome After Substring Concatenation I
    • Merge Strings Alternately
    • Greatest Common Divisor of Strings
    • Reverse Vowels of a String
    • Reverse Words in a String
    • String Compression
    • Zigzag Conversion
    • RomanToInteger

26. Tries / Prefix Tree

    • Implement Trie (Prefix Tree)
    • Search Suggestions System

27. Two Pointers

    • ContainerWithMostWater - maxArea
    • Move Zeros
    • 3Sum
    • Trapping Rain Water
    • Is Subsequence
    • Max Number of K-Sum Pairs

COMPANIES Hiring Overview (FAANG / MAANG PROCESS)

NOTES

1. GitHub - xizhang20181005/Leetcode_company_frequency

AMAZON

1. Hiring Process
2. Check out my "Amazon Interview Process" personal Google Keep notes
3. LeetCode Amazon top questions
4. GitHub - xizhang20181005/Leetcode_company_frequency #amazon
5. GiftingGroups
6. OptimizingBoxWeights
7. MinimumNumberOfSwapsToSort
8. Parentheses perfection kit
9. Maximum possible stability of any subset of servers
10. Binary String to Palindrome
11. Find median for k elements in n array. Return new int[]{maxMedian, minMedian}
12. 1 to m-1 cities and n warehouses, cityStart=[1,2,1], cityEnd=[2,5,9]. cityStart.length == cityEnd.length == n of warehouses. Multiple warehouse connect to same city. Find cityWarehouseCounter <city, num of warehouses>

GOOGLE

1. Hiring Process
2. LeetCode Google top questions
3. GitHub - xizhang20181005/Leetcode_company_frequency #Google

MICROSOFT

1. Hiring Process
2. LeetCode Microsoft top questions
3. GitHub - xizhang20181005/Leetcode_company_frequency #Microsoft

META

1. Hiring Process
2. LeetCode Meta / Facebook top questions
3. GitHub - xizhang20181005/Leetcode_company_frequency #Facebook

APPLE

1. Hiring Process
2. LeetCode Apple questions in discussion

NETFLIX

1. Hiring Process

UBER

1. GitHub - xizhang20181005/Leetcode_company_frequency #Uber

BLOOMBERG

1. GitHub - xizhang20181005/Leetcode_company_frequency #Bloomberg

LINKEDIN

1. GitHub - xizhang20181005/Leetcode_company_frequency #LinkedIn

My LeetCode Notes

1. My "50 Days badge 2025" received on 12 March 2025
2. My "Top 100 Liked" badge received on 20 March 2025
3. My "100 Days badge 2025" received on 01 May 2025
4. My "LeetCode 75" badge received on 26 May 2025
5. My AMAZON OA Question 1 Discussion Parentheses Perfection Kit
6. My AMAZON OA Question 2 Discussion Get Maximum Stability

Sources

1. From my LeetCode experience- leetcode/srinivasvadige
2. Hackerrank
3. Personal experience and research
4. Official java documentations, blogs
5. WilliamFiset - YT Data structures playlist
6. takeuforward.org - Strivers A2Z DSA Course/Sheet
7. COURSERA DSA ROADMAP PART 1
8. COURSERA DSA ROADMAP PART 2
9. GFG DSA course
10. FCC DSA course with 48hrs YT video
11. GFG interview DSA FAQs
12. Columbia University DSA Research Papers

Owner

Author: Srinivas Vadige

Email: [email protected]

LinkedIn: linkedin.com/in/srinivasvadige

My Leetcode profile: leetcode.com/srinivasvadige

License

This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects. Attribution is optional but appreciated.

Other Github project (williamfiset/Algorithms and MaRuifeng/DummyLovesAlgorithms)

List of algorithmic questions

• Integer Array
  • Find the largest sub-array sum of a given integer array
  • Find the largest absolute difference of two non-overlapping sub-arrays of a given integer array
  • Find total number of reverse pairs in a given integer array
  • Find the largest sum of a sub-array with size K in a given integer array
  • Find the k'th smallest item from a given array of distinct integers
  • Find number pairs each of which sums up to a fixed value from an integer array
  • All hail Recursion! Find required add and subtract operations to produce a fixed sum
  • Find the greatest common divisor of an array of integers
  • Print numbers along matrix diagonals
  • Print spiral numbers
  • Bitwise operations
  • Merge sorted integer arrays
  • All hail Recursion! Find all subsets of an integer set
  • Patch a given array to produce list of sums from 1 to N
  • Binary search in a sorted array rotated at an unknown pivot
  • All hail Recursion! Number permutation
  • All hail Recursion! Number combination
  • Random number with different entropies
  • Binary search in matrix
  • Multiple-Condition Check Insert intervals
  • Reverse an integer number
  • Recover a rotated sorted array
  • NP Hard Bin packing problem
  • Boyer–Moore Majority Vote Algorithm Find majority numbers
  • Monkey crossing river
  • Number of ways to sum up to a given number with consecutive positive integers
  • Array based circular queue
• Linked List
  • Reverse a linked list
  • LRU cache implemented with HashMap and LinkedList
  • LRU cache implemented plainly
• Dynamic Programming
  • Fibonacci Numbers
  • Binomial Coefficients
  • Catalan Numbers Find all expressions of balanced n pairs of parentheses
  • Coin change problems
    • Number of possible combinations for given sum
    • List of possible combinations for given sum
    • Least number of coins needed for given sum
  • Number arrangements to get a fixed sum
  • Maximum sub-array sum
  • Ugly Numbers
  • Maximum stock profit
  • Digit sequence decoder
  • Longest common subsequence
  • Longest common substring
  • Longest increasing subsequence
  • Edit distance algorithm
  • Set partition for minimum sum difference
  • Distance and steps
  • Longest path in matrix
  • NP-Complete Subset of fixed sum
  • Optimal coin game strategy
  • Minimum insertions for palindrome
  • NP-Complete 0-1 Knapsack problem
  • Wildcard pattern match check
  • Beware of integer overflow! Boolean parenthesization
  • DP Enhancement Find required add and subtract operations to produce a fixed sum
  • Shortest common supersequence
  • Least arithmetic operations for matrix chain multiplication
  • equals and hashCode method override Rod cutting for maximum gain
  • Resolve a string with dictionary words
  • Rope cutting for maximum length product
  • Dice rolling for fixed sum
  • Egg dropping puzzle
  • K non-overlapping subarrays of maximum sum
  • LEGO part assembler
  • NP-Complete Minimum time for fixed sum of points
• String
  • Remove duplicates in string
  • Remove alternate duplicates in string
  • Remove adjacent duplicates in string
  • Remove consecutive duplicates in string
  • Longest valid parentheses substring
  • Parentheses checker
  • In-place string rotator
  • Backtracking String permutation
  • KMP Algorithm Search for patterns in string
  • DP Check interleaved string
  • Minimum window substring
  • IPv4 address regex matcher
  • Functional Programming Credit card number Luhn check
  • String to int converter
  • Longest palindromic substring
• Binary Tree
  • Plain Binary Tree implementation with linked nodes
    • Pre-order Traversal
    • Post-order Traversal
    • Level-order Traversal
    • Clone via pre-order traversal
    • Serialization/de-serialization
  • Plain Binary Search Tree implementation with linked nodes
  • Parse a BST from its pre-order traversal
  • Parse a BST from its post-order traversal
  • Parse a BST from its level-order traversal
  • Convert a BT to a BST with tree structure maintained
  • Divide and Conquer Search range in BST
  • Sum up greater keys with each node in BST
  • Sum up greater keys for each node in BST
  • Convert integer array to BST
  • Convert integer linked list to BST
  • All possible BSTs from 1 to N Catalan Numbers
  • Convert BST to min heap
  • Convert BT to doubly linked list
  • Convert complete BST to conditional min heap where left sub-tree smaller than right sub-tree
  • Binary tree mirror image
• Binary Heap
  • Plain Binary Heap implementation with array
  • Heap Sort
  • Least Frequently Used Cache implementation via PriorityQueue
• Graph
  • Plain Directed Graph implementation with adjacency list
    • Breadth First Search
    • Depth First Search
    • Linear paths from source to destination
• Backtracking Technique
  • N-Queen puzzle
  • Knight tour problem