# Data Structures & Algorithms

Data Structures and Algorithms form the basic back bone of programming.

Whether you are creating a simple Hello World program or a complex enterprise application you are going to deal with data structures and algorithms.

Data structures are used to hold data temporarily or permanently.

Algorithms are ways to operate on that data to get your required output.

Product companies like Google , Facebook , Amazon etc evaluate candidates first based on their expertise on data structures and algorithms.

There are certain fixed categories of algorithms they prefer to ask during interviews.

Though these algorithms are hardly used in everyday programming at work, they are still used to screen entry level candidates.

Passing these tests require a lot of hard work and practice.

Note that we evaluate how good an algorithm is based on the time it takes to complete and the memory required on the computer to execute the program.

The lesser the time and the memory the better the algorithm is .

So candidates are expected to explain the time and space complexity of the algorithms they solve.

Here are top 100 algorithms asked during interviews with their solution in Java under different categories.

All these problems were solved on leetcode for optimal time complexity.

The time complexity and space complexity for each algorithm is also explained.

## String

1. Repeating Characters
2. Valid Anagram
3. Longest Repeating Character Replacement
4. Minimum Window Substring
5. Group Anagrams
6. Valid Parantheses
7. Valid Palindrome
8. Longest Palindromic Substring
9. Palindromic Substrings
10. Encode and decode strings
11. Roman to Integer
12. First Unique character
13. Excel sheet to column number

## Arrays:

1. Two Sum
2. Best time to buy and sell stock
3. Contains Duplicate
4. Product of Array except self
5. Maximum Subarray
6. Maximum Product Subarray
7. Minimum in Rotated Sorted Array
8. Search in Rotated Sorted Array
9. Three Sum
10. Container with most water
11. Longest consecutive sequence
12. Longest common prefix
13. Remove duplicates
14. Plus One on an array
15. Merge sorted array
16. Valid Soduku
17. Single non duplicate number in array
18. Find the element which appears more than half the size
19. Sort three colors
20. Kth largest element
21. First missing positive integer
22. Peak element
23. Next highest permutation
24. Rotate array
25. First and last position of element in sorted array
26. Median of two sorted arrays

## Binary

1. Sum of two integers
2. Number of 1 bits in an integer
3. Counting bits
4. Missing Number
5. Reverse Bits

2. Detect Cycle in Linked List
3. Merge two sorted lists
4. Reorder list
5. Remove nth node from the last
6. Merge k sorted lists
8. Find if linked list is a palindrome
10. Delete node given only the node

## Intervals

1. Insert new interval
2. Merge intervals
3. Non overlapping intervals
4. Meeting Rooms
5. Meeting Rooms II

## Matrix

1. Set Matrix zeroes
2. Spiral Matrix
3. Rotate Image
4. Word Search

## Dynamic Programming

1. Climbing Stairs
2. Minimum Coin Change
3. Longest Increasing Subsequence
4. Longest Common Subsequence
5. Word Break
6. House Robber
7. House Robber II
8. Jump Game
9. Combination Sum
10. Decode Ways
11. Unique Paths

## Tree

1. Valid Binary Tree
2. Same tree or not
3. Invert Binary Tree
4. Maximum Path Sum in a Binary Tree
5. Level Order Traversal
6. Subtree of another tree
7. Valid BST or not?
8. Construct Binary tree from Preorder and Inorder Traversals
9. Kth smallest element in BST
10. Lowest Common Ancestor of two nodes in BST
11. Serialize and Deserialize
12. Inorder traversal
13. Is Tree symmetric

## Trie

1. Implement Trie
2. Word Dictionary for adding and searching words
3. Word Search II

## Graph

1. Clone Graph
2. Course Schedule
3. Pacific and Atlantic Water Flow
4. Number of Islands
5. Number of Connected Components in Undirected Graph
6. Valid tree
7. Alien Dictionary
8. Course Schedule II