Count Inversions in an Array

This problem was asked by Google.

We can determine how “out of order” an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.

Given an array, count the number of inversions it has. Do this faster than time.

Read more

The Secret Improvement of HashMap in Java 8

HashMap is one of the most widely used data structure in Java. As we know, HashMap stores data in a number of buckets and each bucket is a linked list. The new elements will be added into the bucket at index of (n is the current capacity in HashMap). When the size of a single linked list increases, the performance of retrievals gets worse. Java 8 improves the performance by converting the linked list into a Red-black Tree if the size is bigger than a threshold. I am going to talk about the basics of red-black tree and how Java applies this methodology in HashMap.

Read more

Find the Largest K Elements

Find the largest K element in an array is a common code challenge in interviews. You may see this problem in several different formats like K Closest Points to the Origin.

Sorting the whole given array can solve this problem in time complexity of and space complexity of . However, there is another efficient solution, which has a huge improvement of space complexity when K is small, through an import data structure - Heap.

Read more