data-structures-and-algorithms

various data structures and algorithms and interview questions

1.)Sorting Algorithms

• Bubble Sort

  • BubbleSort : Java

  • BubbleSort : Kotlin

  • BubbleSort : Python

  • Test Case

                 O(1) ~ O(N^2)
    

• Selection Sort

  • SelectionSort : Java

  • SelectionSort : Kotlin

  • SelectionSort : Python

  • Test Case

                 O(N) ~ O(N^2)
    

• Insertion Sort

  • InsertionSort : Java

  • InsertionSort : Kotlin

  • Test Case

                 O(1) ~ O(N^2)
    

• Merge Sort

  • MergeSort : Java

  • MergeSort : Kotlin

  • Test Case

              Divide :  O(log n)
              Merge  :  O(n) 
              O(n log n) 
    

• Quick Sort - Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. ... Quicksort partitions an array and then calls itself recursively twice to sort the two resulting sub arrays.

  • Quick Sort : Java
  • [Counting Sort : Kotlin] - todo;
  • Test Case

• Bucket Sort - Todo

• Counting Sort - Unlike above comparision based algorithms, Counting sort is a sorting technique based on keys between a specific range.

  • Counting Sort : Java

  • Counting Sort : Kotlin

  • Test Case

            Best Case :  O(k) where K is the max 
            Worst Case  :  O(n) 
            Overall  O(n + k ) -> O(n)                     
    

2.)Searching Algorithms

• Linear Search

  • Linear Search : Java

  • Linear Search : Kotlin

  • Test Case

             O(N)  
    

• Binary Search

                 Using Recursion     
                                Time : O(log2 n)
                                Storage : O(n)  // since it uses stack for recusion calls
                                
                 Using Iteration
                               Time : O(log2 n)  
                               Storage : O(1)
                  Prefer Recussion apporach :)  
  

• Ternary Search

  • Ternary Search : Java

  • Ternary Search : Kotlin

  • Test Case

               Using Recursion     
                            Time : O(log3 n)   
    

3.)Data Structures Implementation

• Hash Map - Implemented using Chaining method to avoid collation

  • CustomHashTable : Java
  • CustomHashTable : Kotlin
  • Test Case

• Stack - Implementation for the Stack (LIFO)

  • CustomStack : Java
  • CustomStack : Kotlin
  • Test Case

• Queue - Implementation for the Queue (FIFO)

  • Queue (Circular Array) : Java

  • Queue (Circular Array) : Kotlin

  • Queue (With Two Stacks) : Java

  • Queue (With Two Stacks) : Kotlin

    • leetcode 232

      enqueue(item : T) - 0(1)

      peek and pop O(N) -

      Since we have to move items from primary stack to the other

  • Test Case

• Dynamic Array - Implementation for the Array List (Dynamic Array)

  • Dynamic Array : Java
  • Test Case

  Linked List - Implementation for the Linked List

  • Linked List (Singly) : Java
  • Test Case