Skip to content

Latest commit

 

History

History
446 lines (369 loc) · 42.6 KB

README.md

File metadata and controls

446 lines (369 loc) · 42.6 KB
Raw

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

  1. Binary Search
  2. Ubiquitous Binary Search (Binary search implementation with various applications)
  3. Problems based on Binary Search

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
  4. Subarray Problems(Kadane's Algorithm)
  5. Find missing number in array
  6. Shuffling an Array
  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
  14. Dutch National Flag Problem
  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
  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. Invert Binary Tree
  2. Height of Binary Tree
  3. Same Tree

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

LeetCode

  1. Insert Delete GetRandom in O(1)

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

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
Arrays
Time-complexity
Counting Elements
Prefix Sums
Sorting
Stacks and Queues
Leader
Maximum Slice Problem
Prime and Composite numbers
Others