Data Structures Implementation

A catalogue of data structures implementation + algorithms and coding problems around them.

2D-arrays

• Search for a word in a board
• Flip a matrix
• Largest area of 1s in a matrix
• Multi dimensional search
• Rotate a matrix 90º anti-clockwise
• Rotate a matrix 90º clockwise
• Spiral traverse a two-dimensional array
• Zigzag traverse a two-dimensional array

Arrays

• Check Pythogorean triplet in array
• Find first duplicate element
• Find smallest positive integer
• K-sorted lists
• Longest peak in an array
• Max product of three integers
• Max sum of k partitions
• Merge sorted arrays
• Merge overlapping intervals
• Move element to end of array
• Neighboring products of ith element
• Rotate list by k elements
• Smallest difference between two arrays
• Sparse array
• Sub-array sort to sort whole array
• Trap water in elevation map
• Two sum
• Three sum
• Three product

Binary Search Trees

• BST with insertion, deletion and removal operations
• BST construction from array
• BST validation
• Find BST node closest to a given value
• Find second largest node
• Remove a node from BST
• Determine whether two arrays can form same BST

Binary Trees

• All paths from root to leaves
• Check whether tree T is subtree of S
• Depth of a tree
• Diameter of a tree
• Find successor of a given node
• Sum nodes within a given range
• Invert a binary tree
• Binary tree sum
• Flatten a binary tree
• Is binary tree balanced?
• Print binary tree nodes level-wise
• Serialize and deserialize binary tree
• Traverse in-order iteratively

Bit Manipulation

• Longest consecutive ones
• Recurring character in a string

Dynamic Programming

• Count ways to decode
• Disk stacking
• Efficient fibonacci
• Find denominations
• Kadenes algorithm
• Longest common subsequence
• Knapsack problem
• Levenshtein dinstance
• Max sum increasing subsequence
• Max sum of non-adjacent elements in array
• Minimum number of coins to make change
• Minimum number of jumps to last index
• Min number of squares adding to n
• Throw dice
• Ways to make change given denominations

Graphs

• Boggle game
• Breadth first search
• Breadth first search using double-ended queue
• Depth first search
• Longest path of a weighted tree
• Single cycle check
• Youngest common ancestor

Hashmaps

• Hashmap implementation
• First non-repeating character
• Grouping titles

Heaps

• Given buildings, model a skyline
• Min heap construction + heap operations

Linked Lists

• Doubly linked list and all operations
• Find whether linked list has loop
• Linked list and all operations
• LRU Cache implementation
• Remove all consecutive nodes that add to zero
• Remove kth node from end
• Reverse linked list
• Sort linked list in O(N log N) time and constant space

Queues

• Executing the kth prisoner in a circle of prisoners

Recursion

• Count all sets adding to a target
• Binary Tree Diameter
• Fibonacci
• Greatest common divisor
• Maximum matrix coins
• Recursive binary search
• Simulate rocket countdown
• Find min and max in array
• Tower of Hanoi

Searching

• Binary search implementation
• Fibonacci search
• Search for min value using pivot in log time
• Three largest numbers search

Sorting

• Bubble sort
• Insertion sort
• Merge sort
• Quick sort
• Selection sort
• Sort using a min-heap and k positions

Stacks

• Is a string of brackets balanced?
• Interleave elements in a stack
• Constant time push, pop, max for a stack
• Min stack with constant time operations
• Reconstructing array using clues

Strings

• Count invalid parenthesis in string
• Caesar cipher
• String palindrome checker
• Check if string A can be shifted to get string B
• Number palindrome checker
• Reverse words but maintain delimiters order
• Reverse mutable string
• Validate IP address

Tries

• Trie implementation

Others

• Fisher-Yates Shuffle
• Hit Counter
• Job Scheduler
• Kaprekar's constant
• Regular expression matching
• Stable marriage problem
• Url on the browser
• Word sense disambiguation