# Most frequent words in file

In last post:  find K smallest element in an array, we learned some concepts to find top or bottom element in a given set. Let’s apply those concept again to a different problem called most frequent words in a file.

Given a text file which contains strings/words, find n most frequently occurring words in it i.e. n words whose count is the maximum.

For example, if given file is like follows: one, two, two, three, three, three, four,four, four,four, five, five, five, five, five, six,six, six, six, six, six  and we are looking for three most frequent words, output should be :  six,five, four.

## Line of thoughts

Brute force solution would be really easy, scan the whole file, get the count for each unique words in file. Then sort the output based on that count in descending order and then return first n words.

This problem has three parts to it. First, read all words from file, second created a map which store frequency count of each word on file. Third is to get top n words from that map.

Reading a file is pretty standard operation in any language.  Brush upon Java basics here. We will not focus on that and also that’s not the intention of this question.
Assuming we can read from the file, how can we store frequency count against words. Simple, use a hash map. We read word from file, store in hash if it is not already there with count 1. If words is already in hash map, update the count by 1.

After this step, we have a hash with count of occurrence of each word. Now comes the challenging part:  how to find top n or most frequent words from this hash map. Mind you that hash map does not store elements in sorted or any order.

Rule of thumb is to find top or least from collection of items, heaps are best bet. To find top N most frequently occurring words, let’s try heap.
Which heap would be best?  We need to get a limited set, if we have free entry in that set till n words(as we need n top words). All further words have to pass a test before they enter the set.

If new word is less than the least frequent word in the set, what can be said about this new word? Well, it cannot be in top n words right?
If new word has frequency more than word with least frequency in set, new word should enter the set and  word with least frequency should be moved out.
What we just explained is typical use of min heap, as it give least element at the root. To find top n most frequent words in file, below is the algorithm.

### Most frequent words in file : algorithm

1. Take first N words appearing in map along with their count and create a min heap with these N words.
2. One by one read words from hash and check if frequency of new word is more than least frequent word on heap, i.e word at root of heap.
3. If yes, remove root and add new word in min heap. If not, continue with next word.
4. When done with all words in hash, min heap will contain N most frequently occurring words in file.

#### Implementation

```package com.company;

import javafx.util.Pair;

import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;

/**
* Created by sangar on 1.10.18.
*/
public class FrequentWords {

public static HashMap<String, Integer> readFile(String fileName)
throws IOException {
HashMap<String, Integer> wordMap = new HashMap<>();

Path path = Paths.get(fileName);
try (Scanner scanner =  new Scanner(path)){
while (scanner.hasNextLine()){
String line = scanner.nextLine();
if(wordMap.containsKey(line)) {
wordMap.put(line, wordMap.get(line) + 1);
}
else{
wordMap.put(line, 1);
}
}
}
return wordMap;
}

public static ArrayList<String> mostFrequentWords(String fileName, int n){
ArrayList<String> topWords = new ArrayList<>();

try {
PriorityQueue<Pair<String, Integer>> pq =
new PriorityQueue<>(n, (x,y) -> x.getValue().compareTo(y.getValue()));

int i = 0;
Iterator it = wordMap.entrySet().iterator();
/*
Get first n words on heap
*/
while(it.hasNext()){
if(i == n) break;
HashMap.Entry<String, Integer> entry =
(HashMap.Entry<String, Integer>)it.next();
it.remove();
i++;
}

/*
Check all other words, if anyone more than least
remove the least and add the new word.
*/
for (String key : wordMap.keySet()){
if(pq.peek().getValue() < wordMap.get(key)){
pq.poll();
}
}
while(!pq.isEmpty()){
}
} catch (IOException e) {
e.printStackTrace();
}
}

public static void main(String[] args){
System.out.println(mostFrequentWords("/home/sangar/Documents/test.txt", 3));
}
}

```

Reading M words from file will require O(m) time, where as creating N element heap will take O(n). Also, scanning through all words and inserting them on to heap has complexity of O((m-n) log n). Overall complexity to find top n most frequent words in fileis O(m log m).

## Find Kth smallest element in array

Given an array of integers which is non sorted, find kth smallest element in that array. For example: if input array is A = [3,5,1,2,6,9,7], 4th smallest element in array A is 5, because if you sort the array A, it looks like A = [1,2,3,5,6,7,9] and now you can easily see that 4th element is 5.

This problem is commonly asked in Microsoft and Amazon interviews as it has multiple layers and there are some many things that can be tested with this one problem.

## Kth smallest element : Line of thought

First of all, in any interview, try to come up with brute force solution. Brute force solution to find Kth smallest element in array of integers would be to sort the array and return A[k-1] element (K-1 as array is zero base indexed).

What is the complexity of brute force solution? It’s `O(n2)`? Well, we have sort algorithms like merge sort and heap sort which work in O(nlogn) complexity.

The problem with both searches is that they use additional space. Quick sort is another sorting algorithm. It has problem that it’s worst-case complexity will be `O(n2)`, which happens when input is completely sorted.
In our case, the input is given as unsorted already, so we can expect that quicksort will function with `O(n log n)` complexity which is its average-case complexity. Advantage of using quicksort is that there is no additional space complexity.

Optimising quick sort

Let’s see how quicksort works and see if we can optimize solution further?
Idea behind quicksort is to find the correct place for the selected pivot. Once the pivot is at the correct position, all the elements on the left side of the pivot are smaller and on the right side of the pivot are greater than the pivot. This step is partitioning.

If after partitioning, pivot is at position j, can we say that pivot is actually jth smallest element of the array? What if j is equal to k? Well problem solved, we found the kth smallest element.

If j is less than k, left subarray is less than k, we need to include more elements from right subarray, therefore kth smallest element is in right subarray somewhere. We have already found j smallest elements, all we need to find is k-j elements from right subarray.

What if j is greater than k? In this case, we have to drop some elements from left subarray, so our search space would be left subarray after partition.

Theoretically, this algorithm still has the complexity of `O(n log n)`, but practically, you do not need to sort the entire array before you find k smallest elements.

If you are preparing for a technical interview and need personal coaching along with mock interviews, book a free demo session with us

### Algorithm to find Kth smallest element in array

1. Select a pivot and partition the array with pivot at correct position j
2. If position of pivot, j, is equal to k, return A[j].
3. If j is less than k, discard array from start to j, and look for (k-j)th smallest element in right sub array, go to step 1.
4. If j is greater than k, discard array from j to end and look for kth element in left subarray, go to step 1

Let’s take an example and see if this algorithm works? A =  [4, 2, 1, 7, 5, 3, 8, 10, 9, 6 ], and we have to find fifth smallest element in array A.

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

Start with pivot as first index of array, so pivot = 0, partition the array into two parts around pivot such that all elements on left side of pivot element, i.e. A[pivot] are smaller and all elements on right side are greater than A[pivot].

In our example, array A will look like below after pivot has found it’s the correct position.

If pivot == k-1 (array is represented as zero base index), then A[pivot] is kth smallest element. Since pivot (3) is less than k-1 (4), look for kth smallest element on right side of the pivot.

k remains as it is as opposed to k-j mentioned in algorithm as pivot is given w.r.t entire array and not w.r.t subarray.

In second iteration, pivot = 4 (index and not element). After second execution of quick sort array A will be like

pivot(4) which is equal to k-1(5-1). 5th smallest element in array A is 5.

### Implementation

```package com.company;

/**
* Created by sangar on 30.9.18.
*/
public class KthSmallest {
private void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private int partition(int[] a, int start, int end){
int pivot = a[start];
int i  = start+1;
int j  = end;

while(i <= j){
while(a[i] < pivot) i++;
while(a[j] > pivot) j--;

if(i < j) {
swap(a, i, j);
}
}
swap(a, start, j);
return j;
}

public int findKthSmallestElement(int a[], int start,
int end, int k){
if(start <= end){
int p = partition(a, start, end);
if(p == k-1){
return a[p];
}
if(p > k-1)
return findKthSmallestElement(a, start, p, k);
if(p < k-1)
return findKthSmallestElement(a, p+1, end, k);
}
return -1;
}
}
```

Test cases

```package test;

import com.company.KthSmallest;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 28.8.18.
*/
public class KthSmallestTest {

KthSmallest tester = new KthSmallest();
private int[] a = {4, 2, 1, 7, 5, 3, 8, 10, 9};
@Test
public void kthSmallest() {
assertEquals(7, tester.findKthSmallestElement(a,0,8,6));
}

@Test
public void firstSmallest() {
assertEquals(1, tester.findKthSmallestElement(a,0,8,1));
}

@Test
public void lastSmallest() {
assertEquals(10, tester.findKthSmallestElement(a,0,8,9));
}

@Test
public void kGreaterThanSize() {
assertEquals(-1, tester.findKthSmallestElement(a,0,8,15));
}
@Test
public void emptyArray() {
int[] a = {};
assertEquals(-1, tester.findKthSmallestElement(a,0,0,1));
}

@Test
public void nullArray() {
assertEquals(-1, tester.findKthSmallestElement(null,0,0,1));
}
}
```

Complexity of using quicksort algorithm to find the kth smallest element in the array of integers is still O(n logn).

### Kth smallest element using heaps

Before going into details of this problem, I strongly recommend reading heap fundamentals.

Imagine a case where there are a billion integers in the array and you have to find 5 smallest elements from that array. The complexity of O(n log n) is too costly for that use case. Above algorithm using quicksort does not take into consideration disparity between k and n.

We want top k elements, how about we chose those k elements randomly, call it `set A` and then go through all other n-k elements, call it `set B`, check if element from set B (n-k elements) can displace element in set A (k elements)?

What will be the condition for an element from set B to replace an element in set A? Well, if the new element is less than maximum in set A than the maximum in set A cannot be in the set of k smallest elements right?  Maximum element in set A would be replaced by the new element from set B.

Now, the problem is how to quickly find the maximum out of set A. Heap is the best data structure there. What kind of heap: min heap or max heap? Max heap as it store the maximum of the set at the root of it.

Let’s defined concrete steps to find k smallest elements using a max heap.

1. Create a max heap of size k from first k elements of array.
2. Scan all elements in array one by one.
1.  If current element is less than max on heap, add current element to heap and heapify.
2. If not, then go to next element.
3. At the end, max heap will contain k smallest elements of array and root will be kth smallest element.

Let’s take an example and see if this algorithm works? The input array is shown below and we have to find the 6th smallest element in this array.

Step 1 : Create a max heap with first 6 elements of array.

Step 2: Take the next element from set B and check if it is less than the root of max heap. In this case, yes it is. Remove the root and insert the new element into max heap.

Step 2: It continues to 10, nothing happens as the new element is greater than the root of max heap. Same for 9.  At 6, again the root of max heap is greater than 6. Remove the root and add 6 to max heap.

Array scan is finished, so just return the root of the max heap, 6 which is the sixth smallest element in given array.

### Implementation

```	public int findKthSmallestElementUsingHeap(int a[], int k){
//https://stackoverflow.com/questions/11003155/change-priorityqueue-to-max-priorityqueue

PriorityQueue<Integer>  maxHeap =
new PriorityQueue<>(k, Collections.reverseOrder());

if(a == null || k > a.length) return -1;
//Create max with first k elements
for(int i=0; i<k; i++){
}

/*Keep updating max heap based on a new element
If new element is less than root,
remove root and add new element
*/

for(int i=k; i<a.length; i++){
if(maxHeap.peek() > a[i]){
maxHeap.remove();
}
}
return maxHeap.peek();
}
```

Can you calculate the complexity of above algorithm? `heapify()` has complexity of log(k) with k elements on heap. In worst case, we have to do `heapify()` for all elements in array, which is n, so overall complexity of algorithm becomes O(nlogk). Also, there is additional space complexity of O(k) to store heap.
When is very small as compared to n, this algorithm again depends on the size of array.

We want k smallest elements, if we pick first k elements from a min heap, will it solve the problem? I think so. Create a min heap of n elements in place from the given array, and then pick first k elements.
Creation of heap has complexity of O(n), do more reading on it. All we need to do is delete k times from this heap, each time there will be `heapify()`. It will have complexity of O(log n) for n element heap. So, overall complexity would be O(n + klogn).

Depending on what you want to optimize, select correct method to find kth smallest element in array.

Please share if there is something wrong or missing. If you are interested in taking coaching sessions from our experienced teachers, please reach out to us at [email protected]