How to find the smallest 1000 or largest 1000 items from a billion of items

-
This is one of the most important concept in data structure and frequently asked in interviews. The one solution to this problem is sorting the elements and returning it. But when we see the complexity, it won't be advisable to sort all the billion items.

For cracking this problem, we use a data structure called "min- heap" or "max-heap". For finding the largest 'n' elements, min- heap is used and for smallest 'n' elements, max-heap is used. In max-heap, keys of parent nodes are always greater than the children and the root node will be give the maximum value in that heap. Just the opposite in min-heap.

The algorithm to find the smallest 1000 elements are as follows: -

  • Create a max-heap of size 1000.
  • Put the first 1000 elements to max-heap.
  • For all the elements starting from 1001 to 'N', delete the maximum element from the max-heap and put the latter element.
  • Return the heap.
For finding the largest 1000 elements, use min-heap.

References:

Comments

Post a Comment

Popular posts from this blog

Difference between "diff" and "sdiff" commands in Unix

-
Image
Hi everyone, in this blog post, I will be discussing about the difference between "diff" and "sdiff" commands in Unix. This is my first post about Unix. diff command diff command will compare two files and prints the difference between the 2 files. The format of diff command is diff file1 file2 . sdiff command sdiff command will compare two files side by side. The format of sdiff command is sdiff file1 file2. The contents of files are displayed side by side with a marker denoting the difference between each files. Some of the important markers used in sdiff are as follows: | - denotes the 2 files differ in the line completely. < - only the first file contains the line. > - only the second file contains the line. The better way to depict the difference is by showing examples. Here, I am comparing 2 files which are named as " ipl_teams_2008.txt " and " ipl_teams_2015.txt ". Let's see the contents of the files.
Read more

Anonymous classes in C++

-
Anonymous Classes in C++ Anonymous class is a class with no name. The main advantage of using an anonymous class is that it provides reusability of the class. Also anonymous class helps in encapsulation of data. Anonymous class is basically used when only one instance of the class is needed and it has only a short body. By defining an anonymous class, it does the same steps of defining a local class and instantiating it. The anonymous class is rightly used after it is defined. Following specifies an example of anonymous class in C++. class { int a; } c1; Here, c1 is an object of the anonymous class. Usually, anonymous classes in C++ are defined using "typedef" ( a keyword to assign alternative names to existing types). Typedef helps in giving another name to the class. It is shown as below: typedef class { int a; } newclass; newclass c2; Here newclass is the object of the anonymous class and c2 is its instance. Member variables can also be initialized in ano
Read more