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 HackerRank and Codility

Content :

• Searching
• Sorting
• Arrays
• Hashing
• Stacks
• Bit Algorithms
• Mathematics
• 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

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

Hashing

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)

Stacks

1. Print Next Greatest Element for each element of array

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)

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)

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