# 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

# 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

```   private void findMiddleElement() {

//Move by one node at a time
//Move by two nodes at a time
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.Map;

public class StringUtils {

public static void main(String[] args) {
String str = "abbcdc";
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;
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);
}

}
```
```