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.
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.
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.
I happened to get an chance to optimize the Solr configuration of Home Depot Canada. My mainly improvement is focused on the segments merge policies. However there are limited resources on-line, I spent some time looking into the source code of LogMergePolicy and TieredMergePolicy. I am going to share how does these two mostly used Solr merge polices work and my findings.