Skip to content

Latest commit

 

History

History
36 lines (21 loc) · 1.69 KB

facts.md

File metadata and controls

36 lines (21 loc) · 1.69 KB

  • patience sorting is used in solitaire game, this technique can be used for nlogn solution of longest increasing subsequence.

  • when you use virtual keyboard and word completion recommendation shows up, because tries work behind the scene

  • famous implementations of flood-fill algorithm :-

    1. Bucket Fill in MS-Paint
    2. Minesweeper
    3. Finding path in a maze with obstacle

  • in stable marriage problem the side that is proposing ends up with the best choice they could have and the side that is being proposed end up with the worst choices they could have...

  • Set in C++ STL is implemented using Self-Balancing Binary Search Tree.

  • Topological Sort is used for graddle dependency resolution in Android Studio.

  • Topological Sort helps Operating systems check for presence of deadlock.

  • heaps are used in Djkstra for finding shortest path.

  • Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not the prefix of code assigned to any other character. This is how Huffman Coding makes sure that there is no ambiguity when decoding the generated bitstream.

  • Maximum and minimum of an array using minimum number of comparisons :-

    1. if n is odd 3*(n-1)/2
    2. if n is even 3n/2-2

  • Hn = 1+1/2+1/3+1/4+....+1/n

    This is a harmonic sequence and it is famous for its very slow growth of its partial sums. Though it seems to be convergent but it is divergent in nature.

    If we take the help of computer to find the approximate values such as:

    For n = 50,000 the sum will be Hn≈11.4

    For n = 100,000 the sum will be Hn≈12.1

    For n = 1,000,000 the sum will be Hn≈14.4