sherxon/algods

Implementation of Algorithms and Data Structures, Problems and Solutions

English | 简体中文

Algorithms and Data Structures

This is the collection of Algorithms, Data Structures and Interview Questions with solutions. This repository contains my solutions for common algorithmic problems and implementation of Data Structures in Java. I've created this repository to learn about algorithms. I am adding solutions continuously.

Algorithms, Data Structures and more than 300 Problems and Solutions are provided so far.

Questions

Here are questions divided by difficulty level:

1. Easy Questions and Answers
2. Medium Questions and Answers
3. Hard Questions and Answers

Problems:

Arrays

1. Rotate Array
2. Contains Duplicate
3. Find Peak Element
4. Maximum Subarray
5. Kth Largest Element in an Array
6. Find All Duplicates in an Array
7. Longest Increasing Subsequence
8. Rotate Image, matrix
9. Shuffle an Array
10. Find Min in Rotated Array
11. Search in Rotated Array

Linked List

1. Singly Linked List Implementation
2. Doubly Linked List Implementation
3. Delete Node in a Linked List
4. Palindrome Linked List
5. Reverse Linked List
6. Intersection of Two Linked Lists
7. Linked List Cycle
8. Remove Nth Node From End of List
9. Merge Sort List
10. Find Linked List Cycle
11. Merge k Sorted Lists
    And many other Linked list problems

Binary Tree

1. Binary Tree Level Order Traversal
2. Sum of Left Leaves
3. Invert Binary Tree
4. Binary Search Tree Iterator
5. Binary Tree Postorder Traversal
6. Binary Tree Preorder Traversal
7. Flatten Binary Tree to Linked List
8. Symmetric Tree
9. Binary Tree Inorder Traversal
10. Same Tree
11. Maximum Depth of Binary Tree
12. Balanced Binary Tree
13. Minimum Depth of Binary Tree
14. Sorted List to Balanced Binary Search Tree
15. Validate Binary Search Tree
16. Sorted List to Balanced BST
17. Kth Smallest Element in a BST
18. Binary Tree Zigzag Level Order Traversal
19. Delete Node in a BST
20. Lowest Common Ancestor of BST
21. Binary Tree Left Side View
22. Binary Tree Right Side View
23. Mode in BST
24. Most Frequent Subtree Sum
25. Find Largest Element in Each Row
26. Serialize and Deserialize BT
    And many other tree problems

Math

1. Integer Break
2. Reverse Bits
3. Palindrome Number
4. Math.pow
5. Jug and Water Problem
6. Sieve of Eratosthenes
7. Fermat's primality
8. Evaluate Reverse Polish Notation

Stack & Queue

1. Min Stack
2. Min Queue
3. Implement Stack Using Queue
4. Implement Queue Using Stack
5. Sort Stack

Dynamic Programming

1. Fibonacci Numbers
2. Word Break
3. Subset Sum
4. 0/1 Knapsack Problem
5. Shortest Palindrome (KMP)
6. Minimum Square Sum
7. Maximum weight transformation of a String
8. Coin Change

Misc

1. Union Find
2. Permutations
3. Subsets

Algorithms

Sorting And Searching

1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Counting Sort
5. Binary Search , Lower & Upper Bounds
6. MergeSort
7. QuickSort

Graphs

1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Prim's Minimum Spanning Tree (MST)
4. KrusKal's Minimum Spanning Tree (MST)
5. Topological Sorting
6. Shortest Path Dijsktra
7. Shortest Path Bellman-Ford
8. A* Heuristic Path Finding
9. Is Graph Bipartite
10. Is Graph Connected
11. Cycle Detection
12. Undirected Graph Bridge Detection

String

1. Rabin Karp Subsequence search
2. Ransom Note
3. Reverse String
4. Longest Common Prefix
5. Is Anagram
6. Needle and Haystack
7. Word Break
8. Meta Strings

Data Structure:

Trees

1. Binary Search Tree (recursive)
2. Binary Search Tree (iterative)
3. AVL Tree
4. Trie (Prefix tree)
5. Hashed Array Tree
6. LRU Cache

Contribute

Did you find a bug? Any way to do it better? Please feel free to pull-request it. :)

algods's Issues

CycleDetection

Looks like CycleDetection will fail if Graph has multiple component.

i can not find the BSTWithDuplicate.java file

can i see your solution for dealing with duplicates?

Why not provide unit test for these solutions?

hope provide unit test for these solutions
thanks :)

Implementation of algorithms in other language

Sieve of Erastosthenes improvements

It will be almost twice as fast, using half as much space, if you only sieve over odd numbers.

CycleDetection

Whether or not there is a cycle, this program always returns true after running
` for (Integer neighbor : graph.getNeighbors(start)) {

        if(visited.contains(neighbor) && !exited.contains(neighbor)) return true;

        if(!visited.contains(neighbor) && dfs(neighbor)) return true;
    }`

Fibonacci using matrix multiplication

Hello.
I'm not fluent in Java so I won't implement it by myself, however there is an O(log n) solution for finding nth Fibonacci number which is based on matrix exponentiation -

[[1 1] [1 0]]^n = [[F_{n+1} F_n] [F_n F_{n-1}]]

This can be done with exponentiation by squaring which is O(log n).

FindPeakElement is wrong

if array is {8,7,6,7,4},result is wrong

Bloom filter

It would be really cool to have Bloom Filter.

Another approach to Math.abs()

hi I like your code for ReverseInteger. Why do you use the Math.abs()? Here is another approach with less code:

public int reverse(int x) {
    int rev = 0;
    while(x != 0){
        rev = rev*10 + x%10;
        x = x/10;
    }
 
    return rev;
}

Overflow in ContainsDuplicate

https://github.com/sherxon/AlgoDS/blob/master/src/interviewquestions/easy/ContainsDuplicate.java#L17:

    for (int i : nums) {
        if (!set.add(-2 * i)) return true;
    }

Why multiply by -2?

See https://repl.it/HBRv/0: new int[] {2147483646, -2} contains duplicates.

Add a license

Suggestion: Second Minimum Node In a Binary Tree

In your solution you have used priority queue to fetch second minimum node. Wouldn't it be much more efficient if you simply returned leftmost element in the right subtree of the root ?