Bucket Sorting In Java

This algorithm works by distributing the element into a buckets, then sorting the bucket contents, finally combining the all the buckets one by one

Best case and Average case Time complexity is O(n+m), where m is the largest number in the data set

Worst case time complexity is O(n^2)

Please refer the below GitHub repository

https://github.com/dkbalachandar/bucketsorting

Advertisements

Algorithm Time Complexity

O(1) – Completes the operation/process in a single step. Best example is the number to search in an array is present in the first index itself
O(n) – Completes the operation/process in n steps. So the time gets increased linearly. Best example is the number to find in an array is present in the last index only
O(log n) – Completes the operation/process in n/2 steps. Best example, do a binary search in a sorted array.
O(n^2) – Completes the operation n^2 steps. Best example is sorting an array by bubble sort.
O(n log n) – Completes the operation n*n/2 steps. Best example is sorting an array by quick sort.

Find middle element in a linkedlist

Please refer the Linked List code in the below GitHub repo.
https://github.com/dkbalachandar/custom-linkedlist

 

   private void findMiddleElement() {

        //Move by one node at a time
        Node firstPointer = head;
        //Move by two nodes at a time
        Node secondPointer = head;
        while (secondPointer!= null && secondPointer.getNext() != null &&
                secondPointer.getNext().getNext() != null) {
            firstPointer = firstPointer.getNext();
            secondPointer = secondPointer.getNext().getNext();
        }
        System.out.println("Middle Element is: "+ firstPointer.getData());

    }

 

Given a string, calculate the frequency of characters, output the array with the letter and frequency. (such as: for “abbcdc”, the output should be (a,1),(b,2),(c,2),(d,1))



import java.util.LinkedHashMap;
import java.util.Map;


public class StringUtils {

    public static void main(String[] args) {
        String str = "abbcdc";
        Map charFreqMap = new LinkedHashMap();
        char[] charArray = str.toCharArray();
        for (Character ch : charArray) {
            if (charFreqMap.get(ch) != null) {
                charFreqMap.put(ch, charFreqMap.get(ch) + 1);
            } else {
                charFreqMap.put(ch, 1);
            }
        }
        for (Map.Entry mapEntry : charFreqMap.entrySet()) {
            System.out.print("(" + mapEntry.getKey() + "," + mapEntry.getValue() + ")");
            System.out.print(",");
        }
    }
}

An array of 10 Elements with some number are missing, How will you find the missing numbers?


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MissingElementsNoLoop {

    public static void main(String[] args) {

        Integer[] numberArray1 = new Integer[10];
        for (int i = 0; i < numberArray1.length; i++) {
            numberArray1[i] = i + 1;
        }
        Integer[] numberArray2 = {1, 2, 4, 5, 7, 8, 9};
        List list1 = new ArrayList(Arrays.asList(numberArray1));
        System.out.println("All Elements List::" + list1);
        List list2 = new ArrayList(Arrays.asList(numberArray2));
        System.out.println("Input Elements List::" + list2);
        list1.removeAll(list2);
        System.out.println("Missed Elements List::" + list1);
    }

}