Algorithms and Data Structures in Ruby

Featured on Awesome-algorithms & Ruby-bookmarks

This repository contains Ruby implementation of various Algorithms and Data structures and solution of many challenges of Leetcode, Exercism, HackerRank and Codility

Content :

• Searching
• Heuristic
• Sorting
• Arrays
• Strings
• Hashing
• Stacks
• Linked List
• Bit Algorithms
• Mathematics
• Trees
  • Binary Tree
  • Binary Search Tree
• Dynamic Programming
• Exercism Ruby Track
• LeetCode
  • Grind-75
  • Striver's Sheet
• HackerRank
• Codility

Searching

1. Binary Search
2. Ubiquitous Binary Search (Binary search implementation with various applications)
3. Problems based on Binary Search
   • Find fixed point in sorted array
   • Find smallest missing number in sorted array
   • Find majority element in sorted array
   • Find minimum element in sorted rotated array
   • Search element in sorted rotated array
   • Find maximum element in a Bitonic Array
   • Find no. of occurences of an element in a sorted Array
   • Find floor and ceil of given element in a sorted Array
   • Find the element with odd occurences if all other elements have even occurences
   • Find the median of two sorted array of equal size
   • First Bad Version

Heuristic

1. Minimax Algorithm

Sorting

1. Bubble Sort
2. Optimized Bubble Sort
3. Selection Sort
4. Insertion Sort
5. Shell Sort
6. Merge Sort
7. Quick Sort
8. 3 way Quick Sort
9. Counting Sort
10. Pancake Sort
11. Sort array in wave form
12. Sort a given array by frequency of elements
13. Radix Sort
14. Heap Sort

Arrays

1. Swapping two numbers
2. Algorithm for reversing an array
3. Algorithms for array rotation
   • Juggling Algorithm for array rotation
   • Reversal Algorithm for array rotation
   • Block Swap Algorithm for array rotation
     • Recursive
     • Iterative
4. Subarray Problems(Kadane's Algorithm)
   • Algorithm to find maximum continuos sum in an array
   • Algorithm to find maximum continuos product in an array
   • Find max diff between 2 elements such that larger appears after smaller(Approach 2)
5. Find missing number in array
6. Shuffling an Array
   • Knuth shuffling Algorithm
   • Fitcher-Yates shuffling Algorithm
7. Find pair in array with sum equal to given value
8. Find pair in array with difference equal to given value
9. Find pair in array with sum closest to given value
10. Find triplet in array with sum equal to given value
11. Find Pythagorean triplet in given array
12. Find equilibrium index in an array
13. Find fixed point in an array
    • fixed point in unsorted array
    • fixed point in sorted array
14. Dutch National Flag Problem
    • Segregate Os and 1s in a given array
    • Segregate Os,1s and 2s in a given array
15. Move all zeros to the end of array
16. Find all Leaders in an array
17. Find smallest missing number in sorted array
18. Majority Element in an array
    • Find majority element in unsorted array(Moore's voting algorithm)
    • Find majority element in sorted array
19. Find minimum element in sorted rotated array
20. Search element in sorted rotated array
21. Find maximum element in a Bitonic Array
22. Find no. of occurences of an element in a sorted Array
23. Find floor and ceil of given element in a sorted Array
24. Replace every element by product of previous and next
25. Find the element with odd occurences if all other elements have even occurences
26. Print the maximum element in each k-sized subarray
27. Print Next Greatest Element for each element of array
28. Replace every element by maximum element on the right side(Next Greatest Element)
29. Find the smallest and second smallest in a given array
30. Find the maximum sum with no adjacent elements
31. Given two sorted arrays find the union and intersection of arrays
32. Given unsorted array of numbers check if numbers are consecutive
33. Sort a given array by frequency of elements
34. Create a product array from given array
35. Find the median of two sorted array of equal size
36. Given a 2D array,print its all elements in spiral order
37. Find two repeating elements in given array
38. Minimum length unsorted subarray,sorting which makes the array sorted
39. Find max diff between 2 elements such that larger appears after smaller
40. Find duplicates in array in O(n) time and constant space
41. Print all distinct elements of given array
42. Given an array array, find the maximum j – i such that the element later is bigger

Strings

1. Longest Palindrome
2. Valid Anagram
3. Valid Palindrome
4. Longest Common Prefix

Hashing/HashMaps

1. Find pair in array with sum equal to given value(Approach 1)
2. Find pair in array with difference equal to given value(Approach 2)
3. Sort a given array by frequency of elements
4. Print all distinct elements of given array(Approach 2)
5. Longest Palindrome

Stacks

1. Print Next Greatest Element for each element of array
2. Backspace String Compare
3. Evaluate Reverse Polish Notation
4. Implement Queue using Stacks
5. Min Stack

Linked List

1. Reverse Linked List
2. Middle of the Linked List
3. Linked List Cycle
4. Merge Two Sorted Lists
5. Palindrome Linked List
6. Remove nth node from end in list

Bit Algorithms

1. Check if a given number is power of 2 or not
2. Check if a given number is even or odd
3. Given a number return a number with last bit unset
4. Count the number of set bits(Brian Kernighan's method)
5. Find missing number in array(Approach 2)
6. Find two repeating elements in given array(Approach 4)
7. Add Binary
8. Counting Bits
9. Number of Set Bits
10. Reverse Bits

Mathematics

1. Fast multiplication of two numbers(Russian Peasant Multiplication)
2. Babylonian Method to find Square root of a number
3. Find missing number in array(Approach 1)
4. Find two repeating elements in given array(Approach 1)

Trees

Binary Trees

1. Tree Node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
5. Invert Binary Tree
6. Height of Binary Tree
7. Same Tree
8. Balanced Binary tree
9. Symmetric Tree
10. Subtree of Another Tree
11. Binary Tree Level order Traversal

Binary Search Trees

1. Lowest Common Ancestor of BST
2. Sorted Array to BST

Dynamic Programming

1. Climbing Stairs

Exercism Ruby Track

Problems

1. Hello World
2. Lasagna
3. Amusement Park
4. Amusement Parks Improvements
5. Log Line Parser
6. Assembly Line
7. Savings Account
8. Port Palermo
9. Chess Game
10. BlackJack
11. Bird Count
12. Boutique Inventory
13. Boutique Inventory Improvements
14. Locomotive Engineer
15. Moviegoer
16. Simple Calculator
17. Two fer
18. Resistor Color Duo
19. Acronym
20. High Scores
21. Reverse String
22. D&D Character
23. Matrix
24. Series
25. Word Count
26. Eliud's Eggs
27. Hamming
28. Raindrops
29. Isogram
30. Scrabble Score
31. Luhn
32. Clock
33. Twelve Days
34. Tournament
35. Gigasecond
36. Resistor Color
37. Rna Transcription
38. Leap
39. Pangram
40. Space Age
41. Triangle
42. DIfference of Squares
43. Anagram
44. Spiral Matrix
45. Sum of Multiples
46. Transpose
47. Armstrong Numbers
48. Flatten Array
49. Phone Number
50. Grains
51. Resistor Color Trio
52. Saddle Points
53. ETL
54. Nucleotide Count
55. Pythogorean Triplet
56. Collatz Conjecture
57. Seive
58. Proverb
59. Palindrome Products
60. Parallel Letter Frequency
61. Bob
62. Nth Prime
63. Perfect Numbers
64. Binary Search
65. Matching Brackets
66. All Your Base
67. Allergies
68. Run Length Encoding
69. Robot Simulator
70. Beer Song
71. Protein Translation
72. Wordy
73. Secret Handshake
74. Atbash Cipher
75. Crypto Square
76. List Ops
77. Simple Linked List
78. Binary Search Tree
79. Rotational Cipher
80. Largest Series Product
81. Prime Factors
82. Linked List
83. ISBN Verifier
84. Complex Number
85. Microwave
86. Darts
87. Bank Account
88. Gilded Rose

LeetCode

1. Insert Delete GetRandom in O(1)
2. Binary Tree Level order Traversal

Grind-75

1. Two Sum
2. Valid Parentheses
3. Merge Two Sorted Lists
4. Best Time to Buy and Sell Stock
5. Valid Palindrome
6. Invert Binary Tree
7. Valid Anagram
8. Binary Search
9. Linked List Cycle
10. Reverse Linked List
11. Middle of the Linked List
12. Majority Element
13. Contains Duplicates
14. Squares of sorted array
15. Move zeroes
16. Longest Palindrome
17. Palindrome Linked List
18. First Bad Version
19. Missing Number
20. Single Number
21. Palindrome Number
22. Backspace String Compare
23. Ransom Note
24. Climbing Stairs
25. Lowest Common Ancestor of BST
26. Add Binary
27. Max Depth of Binary Tree
28. Sorted Array to BST
29. Maximum Subarray Sum
30. Same Tree
31. Counting Bits
32. Number of Set Bits
33. Reverse Bits
34. Meeting Rooms
35. Roman to Integer
36. Merge Intervals
37. Insert Intervals
38. Product of Array Except self
39. Sort Colors
40. Evaluate Reverse Polish Notation
41. Remove nth node from end in list
42. Implement Queue using Stacks
43. Longest Common Prefix
44. Three Sum/3sum
45. 3sum Closest
46. Min Stack
47. Balanced Binary tree
48. Symmetric Tree
49. Subtree of Another Tree

Striver's Sheet

1. Buy and Sell Stock
2. Majority Element
3. Reverse Linked List
4. Middle of the Linked List

Hacker Rank

Algorithms

Warm up

1. A Very Big Sum
2. Diagnol Difference
3. Plus Minus
4. Simple Array Sum
5. Solve Me First
6. Staircase
7. Time Conversion

Implementation

1. Angry Professor
2. Chocolate Feast
3. Cut The Sticks
4. Find Digits
5. Service Lane
6. Sherlock And Squares
7. Sherlock And The Beast
8. Utopian Tree

Others

1.Modified Kaprekar Number~New approach added by @madmantalking

Codility

Lessons

Iterations

• BinaryGap

Arrays

• CyclicRotation
  • Reversal Algorithm(Solution 1)
  • Juggling Algorithm(Solution 2)
• OddOccurencesInArray

Time-complexity

• FrogJmp
• PermMissingElem
• TapeEquilibrium

Counting Elements

• FrogRiverOne
• MaxCounters
  • Solution 1
  • Solution 2
• MissingInteger
• PermCheck

Prefix Sums

• CountDiv
• MinAvgTwoSlice
• Passing Cars
  • Solution 1
  • Solution 2

Sorting

• Distinct
• MaxProductofThree
• Triangle

Stacks and Queues

• Fish
• Brackets
• Nesting

Leader

• Dominator

Maximum Slice Problem

• MaxDoubleSliceSum

Prime and Composite numbers

• CountFactors
• MinPerimeterRectangle

Others

• Find the length of smallest array with the same binarian value