AlgosGeneralConceptIQs.txt

1. Merge Sort vs Quick Sort
1b. Bubble Sort vs QuickSort
2. Bubble Sort vs Selection Sort vs Insertion Sort
2b. When to use what sorting algorithm
2c. Stable Sort vs Unstable Sort
2d. What is Intro Sort
3. Median of Medians:
4. Bit twiddling Stanford material
4b. Count bits set in a number
4c. Set, Unset, Clear, Toggle a Bit
4d. Absolute Value of a number
4e. Reverse Bits in a number
4f. Find leftmost set bit in a number
4g. Find rightmost set bit in a number
5. String Search:
6. Given 2 sorted arrays of integers, find the nth largest number in sublinear time
7. k'th smallest in Union of Two arrays:
8. K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)
9. GCD of two numbers:
10. STOCK PROBLEMS:
11. Sorted Rotated Array:
12. Find all subsets of a set
13. Multiplication of two numers (without using *)
14. Spiral Level Order traversal of a tree
15. Space Complexity for Tree Traversal.
16. Memoization vs Tabulation in Dynamic Programming
17. How to efficiently check whether it's height balanced for a massively skewed binary search tree
18. How to determine if binary tree is balanced
19. Explain Morris inorder tree traversal without using stacks or recursion
20. Count subsequences divisible by K
21. Merge Overlapping intervals
22. Finding all subsets of a Vector of Vector
23. Converting Recursive Algorithm to Iterative
24. Balancing Binary Search Trees
25. Balancing a Heap
26. Why is Heapify O(n)
26b. SiftUp vs SiftDown
27. n way merge
28. B Tree vs B+ Tree
29. Heap vs Binary Search Tree
30. Smallest range that includes at least one number from each of the k lists
31. Select a random number from stream, with O(1) space
32. Design a data structure that supports insert, delete, search and getRandom in constant time
33. Check if a given array contains duplicate elements within k distance from each other
34. Reservoir Sampling
35. Search a Word in a 2D Grid of characters
36. Sort countries based on population
37. Average of a number accounting for integer overflow
38. Swap Endianess / Converting Little Endian to Big Endian
39. How many traversals need to be known to construct a BST
40. Trie vs Ternary Search Tree
41. Find number of possible perfect squares between two numbers
42. Check if an Intger is a perfect square
43. How will you implement your own malloc
44. How will you implement your own memcpy
45. If you are given two traversal sequences, can you construct the binary tree
46. Unique (non-repeating) random numbers in O(1)?
47. Persistent Data Structures (Fully Persistent and Partially Persistent)
48. Bellman Ford - Shortest Path
49. Coin Arbitrage Algorithm
50. Graph Algorigthms
51. Examples of Data Structures in real life
52. The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
53. How to count number of requests in last second, minute and hour
--------------------------------------------------------------------------------------------
1.
Merge Sort vs Quick Sort
http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists?rq=1
http://www.geeksforgeeks.org/why-quick-sort-preferred-for-arrays-and-merge-sort-for-linked-lists/
http://stackoverflow.com/questions/2467751/quicksort-vs-heapsort

    - "Merge sort is very efficient for immutable datastructures like linked lists"
    - "Quick sort is typically faster than merge sort when the data is stored in memory.
    MERGE SORT PROS
    - ACCESSES DATA SEQUENTIALLY
    - Quicksort is also more complicated than mergesort, especially if you want to write a really solid implementation
    - Can easily insert elements in the middle
    - So MERGE doesnot need any extra overhead
    - However, when the data set is huge and is stored on external devices such as a hard drive, merge sort is the clear winner in terms of speed.
    - It minimizes the expensive reads of the external drive" "when operating on linked lists
    - Merge sort only requires a small constant amount of auxiliary storage"

    QUICK SORT PROS
    - ACCESSES DATA RANDOMLY
    - Quicksort is significantly faster in practice than other T(nlogn) algorithms,
    - Because its inner loop can be efficiently implemented on most architectures,
    - In most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time
    - Quick sort is space constant where Merge sort depends on the structure you're sorting
    - Best when able to index into an array or similar structure.
      You would want to access elements at random positions
      When that's possible, it's hard to beat Quicksort.
    - Quicksort is fast when the data fits into memory and can be addressed directly

    - Practically, Quicksort runs fast, much faster than Heap and Merge algorithms.
    - The secret of Quicksort is: It almost doesn't do unnecessary element swaps.
      Swap is time consuming.

    HEAPSORT MERGESORT AND QUICKSORT
    - With HEAPSORT, even if all of your data is already ordered, you are going to swap 100% of elements to order the array.
    - With MERGESORT, it's even worse. You are going to write 100% of elements in another array and write it back in the original one, even if data is already ordered.
    - With QUICKSORT you don't swap what is already ordered. If your data is completely ordered, you swap almost nothing

     IMP:
     - Array of equal elements.
       while (a[i] < pivot) {i++;}
       while (pivot < a[j] ) {j--;}
       if (i < j) swap (a[i], a[j]);

       If we have an array of equal elements, the second code will never increment i or decrement j
     http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L06-QuickSort.htm

        VERY IMP:
        CHECK IF "i <= j"
        After doing a SWAP, decrement j and increment i.
        This is get over duplicate elements.
        http://www.algolist.net/Algorithms/Sorting/Quicksort

    3 way partition:
        Nice explanation of the algorithm:
        http://algs4.cs.princeton.edu/lectures/23DemoPartitioning.pdf

    Dutch National Flag Problem:
        http://stackoverflow.com/questions/11214089/understanding-dutch-national-flag-program

     Merge Sort:
     - Faster when reading from Disk and not everything can be in memory
     - Mergesort is faster when data won't fit into memory or when it's expensive to get to an item.

1b. Bubble Sort vs QuickSort
    If the array is almost sorted, Bubble sort is faster than Quick Sort

2.
Bubble Sort vs Selection Sort vs Insertion Sort

    http://www.sorting-algorithms.com/selection-sort
    Bubble Sort:
        - Check pair of elements and swap them so that the largest gets bubbled to the end.
        PROS:
            If array is almost sorted OR once we have the array sorted, we can STOP there.

        Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead.
        In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).

    Insertion Sort:
        - What we have at any given time is sorted.
        PROS:
            Online Sorting
            Can do binary search for inserting into a position

        Although it is one of the elementary sorting algorithms with O(n2) worst-case time,
        insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

        For these reasons, and because it is also stable, insertion sort is often used as the recursive base case
        (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

    BUBBLE SORT vs INSERTION SORT
        In insertion sort elements are bubbled into the sorted section, while in bubble sort the maximums are bubbled out of the unsorted section.
        Bubble sort always takes one more pass over array to determine if it's sorted.
        On the other hand, insertion sort not need this -- once last element inserted, algorithm guarantees that array is sorted.

        Bubble sort does n comparisons on every pass.
        Insertion sort does less than n comparisons -- once algorith finds position where to insert current element it stops making comparisons and takes next element.

    Selection Sort:
        Select Minimum element each time and put it at the front.
        PROS:
            - Never have to do MORE THAN "n" swaps.

        From the comparions presented here, one might conclude that selection sort should never be used.
        It does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic.

        However, selection sort has the property of minimizing the number of swaps.
        In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

https://www.careercup.com/question?id=4620408242307072
    Bubble/insertion/merge sorts are stable.
    Selection/quick/heap sorts are not stable.

    Selection Sort : Best Worst Average Case running time all O(n^2). However the number of swaps required is always n-1. Hence it is useful when the amount of satellite data(auxiliary data aside from the key) is large and for some reason pointer based swapping is not feasible.

    Insertion Sort : Best case running time is O(n). Hence useful for adding new data to a presorted list. Also this is fast when the number of elements is small/ you need an online algorithm.

    Bubble Sort:Where we know the data is very nearly sorted. Say only two elements are out of place. Then in one pass, BS will finish it and in the second pass, it will see everything is sorted and then exit. Only takes 2 passes of the array.

    Merge Sort : For external sorting algorithms, it is the choice of sort.

    Quicksort : Remember that quicksort is dependent on choice of pivot. So when we have absolutely random data values, and we will need to sort them, we have to use quick sort. Even for very unbalanced split QS produces good results.

    Heap Sort: It is an inplace O(n logn) algorithm hence we can use it when we cannot afford the extra space required for merge sort. Also has a O(n logn) worst case time as compared to O(n^2) of quicksort

2b.
When to use what sorting algorithm
http://stackoverflow.com/questions/1933759/when-is-each-sorting-algorithm-used

    Quick sort:
        - When you don't need a STABLE SORT and average case performance matters more than worst case performance.
        - A good implementation uses O(log N) auxiliary storage in the form of stack space for recursion

    Merge sort:
        - When you need a STABLE, O(N log N) sort, this is about your only option.
        - The only downsides to it are that it uses O(N) auxiliary space and has a slightly larger constant than a quick sort.
        - There are some in-place merge sorts, but AFAIK they are all either not stable or worse than O(N log N).
        - Even the O(N log N) in place sorts have so much larger a constant than the plain old merge sort that they're more theoretical curiosities than useful algorithms.

    Heap sort:
        - When you DON'T NEED A STABLE SORT and you care more about worst case performance than average case performance.
        - It's guaranteed to be O(N log N), and uses O(1) auxiliary space, meaning that you won't unexpectedly run out of heap or stack space on very large inputs.

    Introsort:
        - This is a quick sort that switches to a heap sort after a certain recursion depth to get around quick sort's O(N^2) worst case.
        - It's almost always better than a plain old quick sort, since you get the average case of a quick sort, with guaranteed O(N log N) performance.
        - Probably the only reason to use a HEAP SORT instead of this is in SEVERELY MEMORY CONSTRAINED systems where O(log N) stack space is practically significant.

    Insertion sort:
        - When N is guaranteed to be small, including as the base case of a quick sort or merge sort.
        - While this is O(N^2), it has a very small constant and is a stable sort.

    Bubble sort, selection sort:
        - When you're doing something quick and dirty and for some reason you can't just use the standard library's sorting algorithm.
        - The only advantage these have over insertion sort is being slightly easier to implement.

    NON-COMPARISON SORTS:
    Under some fairly limited conditions it's possible to break the O(N log N) barrier and sort in O(N). Here are some cases where that's worth a try:

    Counting sort:
        When you are sorting integers with a limited range.

    Radix sort:
        When log(N) is significantly larger than K, where K is the number of radix digits.

    Bucket sort:
        When you can guarantee that your input is approximately uniformly distributed

2c.
Stable Sort vs Unstable Sort
http://stackoverflow.com/questions/8311090/why-not-use-heap-sort-always

    A stable sort maintains the relative order of items that have the same key.
    For example, imagine your data set contains records with an employee id and a name.

    The initial order is:
        1, Jim
        2, George
        3, Jim
        4, Sally
        5, George

    You want to sort by name. A stable sort will arrange the items in this order:
        2, George
        5, George
        1, Jim
        3, Jim
        4, Sally

    Note that the duplicate records for "George" are in the same relative order as they were in the initial list.
    Same with the two "Jim" records.

    An unstable sort might arrange the items like this:
        5, George
        2, George
        1, Jim
        3, Jim
        4, Sally

    Heapsort is not stable because operations on the heap can change the relative order of equal items.
    Not all Quicksort implementations are stable.
    It depends on how you implement the partitioning.

2d.
What is Intro Sort

    Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance.
    It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted

3.
Median of Medians:
http://stackoverflow.com/questions/12545795/explanation-of-the-median-of-medians-algorithm
http://stackoverflow.com/questions/9489061/understanding-median-of-medians-algorithm?rq=1

        Think of the following set of numbers:
        5 2 6 3 1

        The median of these numbers is 3. Now if you have a number n, if n > 3, then it is bigger than at least half of the numbers above. If n < 3, then it is smaller than at least half of the numbers above.

        So that is the idea. That is, for each set of 5 numbers, you get their median. Now you have n / 5 numbers. This is obvious.

        Now if you get the median of those numbers (call it m), it is bigger than half of them and smaller than the other half (by definition of median!). In other words, m is bigger than n / 10 numbers (which themselves were medians of small 5 element groups) and bigger than another n / 10 numbers (which again were medians of small 5 element groups).

        In the example above, we saw that if the median is k and you have m > k, then m is also bigger than 2 other numbers (that were themselves smaller than k). This means that for each of those smaller 5 element groups where m was bigger than its medium, m is bigger also than two other numbers. This makes it at least 3 numbers (2 numbers + the median itself) in each of those n / 10 small 5 element groups, that are smaller than m. Hence, m is at least bigger than 3n/10 numbers.

        Similar logic for the number of elements m is bigger than.

http://stackoverflow.com/questions/9489061/understanding-median-of-medians-algorithm
        // L is the array on which median of medians needs to be found.
        // k is the expected median position. E.g. first select call might look like:
        // select (array, N/2), where 'array' is an array of numbers of length N

        select(L,k)
        {
            if (L has 5 or fewer elements) {
                sort L
                return the element in the kth position
            }

            partition L into subsets S[i] of five elements each
                (there will be n/5 subsets total).

            for (i = 1 to n/5) do
                x[i] = select(S[i],3)

            M = select({x[i]}, n/10)

            // The code to follow ensures that even if M turns out to be the
            // smallest/largest value in the array, we'll get the kth smallest
            // element in the array

            // Partition array into three groups based on their value as
            // compared to median M

            partition L into L1<M, L2=M, L3>M

            // Compare the expected median position k with length of first array L1
            // Run recursive select over the array L1 if k is less than length
            // of array L1
            if (k <= length(L1))
                return select(L1,k)

            // Check if k falls in L3 array. Recurse accordingly
            else if (k > length(L1)+length(L2))
                return select(L3,k-length(L1)-length(L2))

            // Simply return M since k falls in L2
            else return M
        }

4.
Bit twiddling Stanford material
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

4b.
Count bits set in a number
http://stackoverflow.com/questions/22081738/how-variable-precision-swar-algorithm-works
http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

    int SWAR(unsigned int i)
    {
        // Count the number of bits set in TWO bits at a time. Like Bits 1,2; 3,4; 5,6 etc
        i = i - ((i >> 1) & 0x55555555);

        // Count the number of bits set in FOUR bits at a time. Like Bits 1,2,3,4; 5,6,7,8 etc
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

        // Count the number of bits set in EIGHT bits
        // (i + (i >> 4)) & 0x0f0f0f0f
        // since 0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1, we have:
        // k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k

        // Add all the number of 1s in EIGHT BITS into the highest ordered byte.
        // We want the last 8 bytes to represent the number of 1s. So right shift >> 24.
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

    unsigned int countSetBits(int n)
    {
        unsigned int count = 0;
        while (n)
        {
          n &= (n-1) ;
          count++;
        }
        return count;
    }

4c.
Set, Unset, Clear, Toggle a Bit
http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c-c?rq=1

    Setting a bit
    number |= 1 << x;

    Clearing a bit
    number &= ~(1 << x);

    Toggling a bit
    number ^= 1 << x;

    Checking a bit
    bit = (number >> x) & 1;

4d.
Absolute Value of a number
http://stackoverflow.com/questions/12041632/how-to-compute-the-integer-absolute-value

    Let's assume a twos-complement number (as it's the usual case and you don't say otherwise) and let's assume 32-bit:

    First, we perform an arithmetic right-shift by 31 bits.
    This shifts in all 1s for a negative number or all 0s for a positive one (but note that the actual >>-operator's behaviour in C or C++ is implementation defined for negative numbers, but will usually also perform an arithmetic shift, but let's just assume pseudocode or actual hardware instructions, since it sounds like homework anyway):

        mask = x >> 31;

    So what we get is 111...111 (-1) for negative numbers and 000...000 (0) for positives

    Now we XOR this with x, getting the behaviour of a NOT for mask=111...111 (negative) and a no-op for mask=000...000 (positive):
        x = x XOR mask;

    And finally subtract our mask, which means +1 for negatives and +0/no-op for positives:
        x = x - mask;

    So for positives we perform an XOR with 0 and a subtraction of 0 and thus get the same number.
    And for negatives, we got (NOT x) + 1, which is exactly -x when using twos-complement representation

4e.
Reverse Bits in a number
http://stackoverflow.com/questions/845772/how-to-check-if-the-binary-representation-of-an-integer-is-a-palindrome
http://www.geeksforgeeks.org/write-an-efficient-c-program-to-reverse-bits-of-a-number/

    {
        uint32_t revNum = 0;
        uint32_t numBits = (int)log2(num) + 1;
        for (; num; num >>= 1)
        {
            revNum = (revNum << 1) | (num & 1);
        }
        revNum = revNum << ((sizeof(num) * 8) - numBits)
    }

    unsigned int reverseBits(unsigned int num)
    {
        unsigned int  NO_OF_BITS = sizeof(num) * 8;
        unsigned int reverse_num = 0;
        int i;
        for (i = 0; i < NO_OF_BITS; i++)
        {
            if((num & (1 << i)))
               reverse_num |= 1 << ((NO_OF_BITS - 1) - i);
       }
        return reverse_num;
    }

    // Using bit shift
        unsigned int v; // 32-bit word to reverse bit order

        // swap odd and even bits
        v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
        // swap consecutive pairs
        v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
        // swap nibbles ...
        v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
        // swap bytes
        v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
        // swap 2-byte long pairs
        v = ( v >> 16             ) | ( v               << 16);

4f.
Find leftmost set bit in a number
http://stackoverflow.com/questions/53161/find-the-highest-order-bit-in-c

1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 8
9 -> 8
...
63 -> 32

    1 << ( int) log2( x)

    int hibit(unsigned int n)
    {
        n |= (n >>  1);
        n |= (n >>  2);
        n |= (n >>  4);
        n |= (n >>  8);
        n |= (n >> 16);
        return n - (n >> 1);
    }

    int hob (int num)
    {
        if (!num)
            return 0;

        int ret = 1;

        while (num >>= 1)
            ret <<= 1;

        return ret;
    }

    hob(1234) returns 1024
    hob(1024) returns 1024
    hob(1023) returns 512

4g.
Find rightmost set bit in a number
http://algorithmsandme.in/2013/10/fun-with-bits-find-rightmost-bit-set-in-given-number/
http://www.geeksforgeeks.org/position-of-rightmost-set-bit/

    unsigned int getFirstSetBitPos(int n)
    {
       return log2(n&-n)+1;
    }

    x & ~(x-1)

To Clear rightmost set bit just do
    x & (x-1)

4h.
Compute the minimum (min) or maximum (max) of two integers without branching

    int x;  // we want to find the minimum of x and y
    int y;
    int r;  // the result goes here

    r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
    r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

    It works because if x < y, then -(x < y) will be all ones, so r = y ^ (x ^ y) & ~0 = y ^ x ^ y = x.
    Otherwise, if x >= y, then -(x < y) will be all zeros, so r = y ^ ((x ^ y) & 0) = y.

4i.
Compute the sign of an integer

    int v;      // we want to find the sign of v
    int sign;   // the result goes here

    // CHAR_BIT is the number of bits per byte (normally 8).
    sign = -(v < 0);  // if v < 0 then -1, else 0.

    // or, for one less instruction (but not portable):
    sign = v >> (sizeof(int) * CHAR_BIT - 1);

5.
String Search:
    Bayer More:
    http://www.geeksforgeeks.org/pattern-searching-set-7-boyer-moore-algorithm-bad-character-heuristic/

6.
Given 2 sorted arrays of integers, find the nth largest number in sublinear time
http://stackoverflow.com/questions/4686823/given-2-sorted-arrays-of-integers-find-the-nth-largest-number-in-sublinear-time

    I think this is two concurrent binary searches on the subarrays A[0..n-1] and B[0..n-1], which is O(log n).

        Given sorted arrays, you know that the nth largest will appear somewhere before or at A[n-1] if it is in array A, or B[n-1] if it is in array B
        Consider item at index a in A and item at index b in B.
        Perform binary search as follows (pretty rough pseudocode, not taking in account 'one-off' problems):
            If a + b > n, then reduce the search set
                if A[a] > B[b] then b = b / 2, else a = a / 2
            If a + b < n, then increase the search set
                if A[a] > B[b] then b = 3/2 * b, else a = 3/2 * a (halfway between a and previous a)
            If a + b = n then the nth largest is max(A[a], B[b])

    I believe worst case O(ln n), but in any case definitely sublinear.

7.
k'th smallest in Union of Two arrays:
http://articles.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

8.
K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)
http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/
http://www.programcreek.com/2014/05/leetcode-kth-largest-element-in-an-array-java/

9.
GCD of two numbers:

    GCD(a,b) = GCD(b,a-b)
    GCD(a,b) = GCD(b,a%b)
    NICE IMP Proof:
        https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

    https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/
    // Recursive function to return gcd of a and b
    static int gcd(int a, int b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }

10.
STOCK PROBLEMS:

    http://stackoverflow.com/questions/9514191/maximizing-profit-for-given-stock-quotes
    Traverse Backwards

    http://stackoverflow.com/questions/1663545/find-buy-sell-prices-in-array-of-stock-values-to-maximize-positive-difference
    http://stackoverflow.com/questions/7086464/maximum-single-sell-profit


11.
Sorted Rotated Array:

    In a rotated sorted array, only one of A and B can be guaranteed to be sorted. If the element lies within a part which is sorted, then the solution is simple:
        just perform the search as if you were doing a normal binary search. If, however, you must search an unsorted part,
        then just recursively call your search function on the non-sorted part.

    This ends up giving on a time complexity of O(lg n).

12.
Find all subsets of a set
http://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set
http://www.geeksforgeeks.org/power-set/
http://stackoverflow.com/questions/15726641/find-all-possible-substring-in-fastest-way

    for (int i = 0; i < A.length(); i++) {
        for (int j = i+1; j <= A.length(); j++) {
            System.out.println(A.substring(i,j));
        }
    }

13.
Multiplication of two numers (without using *)
http://stackoverflow.com/questions/28888068/time-complexity-of-russian-peasant-multiplication-algorithm

    Using LOG:
        10^(log10(A) + log10(B))
        i.e. pow(10, log10(A) + log10(B)

    Use bit shifting AKA
    https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasant_or_binary_multiplication

    Decimal:     Binary:
    11           3       1011  11
    5            6       101  110
    2            12       10  1100
    1            24       1  11000
                 --         ------
                 33         100001

    The method works because multiplication is distributive, so:

        3 * 11 & = 3 * (1 * 2^0 + 1 * 2^1 + 0 * 2^2 + 1 * 2^3)
                 = 3 * (1 + 2 + 8)
                 = 3 + 6 + 24
                 = 33

    IMP:
    1. Time complexity depends on the NUMBER that we are using for doing the shift
       log (a) or log(b) based on which we select as A
    2. In the above example say 11 = A and 3 = B
       - Select A such that it has lesser number of bits.
       - We are repeating the multiplication till A REACHES 1.
       - So select A as the number that has least number of bits set.

14.
Spiral Level Order traversal of a tree
http://www.geeksforgeeks.org/level-order-traversal-in-spiral-form/
http://stackoverflow.com/questions/17485773/print-level-order-traversal-of-binary-tree-in-zigzag-manner

    You have to use two stacks

        1. first stack for printing from left to right
        2. second stack for printing from right to left.

    Start from the root node.
    Store it's children in one stack.
    In every iteration, you have nodes of one level in one of the stacks.
    Print the nodes, and push nodes of next level in other stack.
    Repeat until your reach the final level.

    Time Complexity O(n) and space complexity O(h).

15.
Space Complexity for Tree Traversal.

    O(h) where h is the height of the tree.

    At any time in the stack we will have ones in that depth level
    So space complexity is height of tree.

    BFS:
    Time complexity is O(|V|) where |V| is the number of nodes,you need to traverse all nodes.
    Space complecity is O(|V|) as well - since at worst case you need to hold all vertices in the queue.

    DFS:
    Time complexity is again O(|V|), you need to traverse all nodes.
    Space complexity - depends on the implementation, a recursive implementation can have a O(h) space complexity [worst case], where h is the maximal depth of your tree.
    Using an iterative solution with a stack is actually the same as BFS, just using a stack instead of a queue - so you get both O(|V|) time and space complexity.
            a
       b         e
     c   d     f   g

    a
    |
    |--> b
    |    |
    |    |--> c
    |    |
    |    |--> d
    |
    |--> e
         |
         |--> f
         |
         |--> g

16.
Memoization vs Tabulation in Dynamic Programming
http://stackoverflow.com/questions/6184869/what-is-difference-between-memoization-and-dynamic-programming

    What is the difference between tabulation (the typical dynamic programming technique) and memoization?

    When you solve a dynamic programming problem using tabulation you solve the problem "bottom up",
    i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table.
    Based on the results in the table, the solution to the "top" / original problem is then computed.

    If you use memoization to solve the problem you do it by maintaining a map of already solved sub problems.
    You do it "top down" in the sense that you solve the "top" problem first (which typically recurses down to solve the sub-problems).

    A good slide from here (link is now dead, slide is still good though):

            If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor
                No overhead for recursion and less overhead for maintaining table
                There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further
            If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required

17.
How to efficiently check whether it's height balanced for a massively skewed binary search tree
http://stackoverflow.com/questions/23160438/how-to-efficiently-check-whether-its-height-balanced-for-a-massively-skewed-bin

18.
How to determine if binary tree is balanced
http://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced?lq=1

19.
Explain Morris inorder tree traversal without using stacks or recursion
http://stackoverflow.com/questions/5502916/explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion

20.
Count subsequences divisible by K
http://stackoverflow.com/questions/24518682/count-subsequences-divisible-by-k
https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences/editorial

21.
Merge Overlapping intervals
http://www.geeksforgeeks.org/merging-intervals/
http://stackoverflow.com/questions/4542892/possible-interview-question-how-to-find-all-overlapping-intervals
http://stackoverflow.com/questions/15150188/amazon-interview-design-meeting-scheduler

22.
Finding all subsets of a Vector of Vector
http://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set

    It's very simple to do this recursively.
    The basic idea is that for each element, the set of subsets can be divided equally into those that contain that element and those that don't, and those two sets are otherwise equal.
        For n=1, the set of subsets is {{}, {1}}
        For n>1, find the set of subsets of 1,...,n-1 and make two copies of it. For one of them, add n to each subset. Then take the union of the two copies.
    Edit To make it crystal clear:
        The set of subsets of {1} is {{}, {1}}
        For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
    Repeat till you reach n

23.
Converting Recursive Algorithm to Iterative
http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration
http://programmers.stackexchange.com/questions/194646/what-methods-are-there-to-avoid-a-stack-overflow-in-a-recursive-algorithm

    Usually, I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack.
    In fact, you are replacing the program stack by one of your own.

        Stack<Object> stack;
        stack.push(first_object);
        while( !stack.isEmpty() ) {
           // Do something
           my_object = stack.pop();

          // Push other objects on the stack.

        }

    Note: if you have more than one recursive call inside and you want to preserve the order of the calls, you have to add them in the reverse order to the stack:

        foo(first);
        foo(second);

        has to be replaced by

        stack.push(second);
        stack.push(first);

24.
Balancing Binary Search Trees on a whole
http://stackoverflow.com/questions/14001676/balancing-a-bst

    Day-Stout-Warren:
    1. Using tree rotations, convert the tree into a degenerate linked list.
    2. By applying selective rotations to the linked list, convert the list back into a completely balanced tree.

    The solution is simple - build an "empty" complete binary tree, and iterate the new tree and the input tree (simultaneously) in inorder-traversal to fill the complete tree.
    When you are done, you have the most balanced tree you can get, and time complexity of this approach is O(n)

24b.
Balancing Binary Search Trees after each insertion
How AVL trees gets self balanced
http://www.geeksforgeeks.org/avl-tree-set-1-insertion/

    Left Rotation and Right Rotation
        Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).
        1) Left Rotation
        2) Right Rotation

        T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
        or x (on right side)
                        y                               x
                       / \     Right Rotation          /  \
                      x   T3   -------------->        T1   y
                     / \       < - - - - - - -            / \
                    T1  T2     Left Rotation            T2  T3
        Keys in both of the above trees follow the following order
              keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
        So BST property is not violated anywhere.

    a) Left Left Case
    T1, T2, T3 and T4 are subtrees.
             z                                      y
            / \                                   /   \
           y   T4      Right Rotate (z)          x      z
          / \          - - - - - - - - ->      /  \    /  \
         x   T3                               T1  T2  T3  T4
        / \
      T1   T2

    b) Left Right Case
         z                               z                           x
        / \                            /   \                        /  \
       y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
      / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
    T1   x                          y    T3                    T1  T2 T3  T4
        / \                        / \
      T2   T3                    T1   T2

    c) Right Right Case
      z                                y
     /  \                            /   \
    T1   y     Left Rotate(z)       z      x
        /  \   - - - - - - - ->    / \    / \
       T2   x                     T1  T2 T3  T4
           / \
         T3  T4

    d) Right Left Case
       z                            z                            x
      / \                          / \                          /  \
    T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
        / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
       x   T4                      T2   y                  T1  T2  T3  T4
      / \                              /  \
    T2   T3                           T3   T4

24c.
B+ Tree vs Red Black Trees vs AVL trees
http://stackoverflow.com/questions/13852870/red-black-tree-over-avl-tree
http://stackoverflow.com/questions/1589556/when-to-choose-rb-tree-b-tree-or-avl-tree

    - B-tree when you're managing more than thousands of items and you're paging them from a disk or some slow storage medium.
    - RB tree when you're doing fairly frequent inserts, deletes and retrievals on the tree.
    - AVL tree when your inserts and deletes are infrequent relative to your retrievals.

        1. What's the main aim we are chossing Red black tree instead of Avl tree?
        Both red-black trees and AVL trees are the most commonly used balanced binary search trees and they support insertion, deletion and look-up in guaranteed O(logN) time.
        However, there are following points of comparison between the two:

            1. AVL trees are more rigidly balanced and hence provide faster look-ups. Thus for a look-up intensive task use an AVL tree.
            2. For an insert intensive taks, use a Red-Black tree.
            3. AVL trees store the balance factor at each node.
               This takes O(N) extra space.
               However, if we know that the keys that will be inserted in the tree will always be greater than zero, we can use the sign bit of the keys to store the colour information of a red-black tree.
               Thus, in such cases red-black tree takes O(1) extra space.
            4. In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.

http://stackoverflow.com/questions/16257761/difference-between-red-black-trees-and-avl-trees
        IMP:
        - AVL trees maintain a more rigid balance than red-black trees.
        - The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2), while in red black trees it's at most ~2 lg (n+1).

        - As a result, lookup in an AVL tree is typically faster, but this comes at the cost of slower insertion and deletion due to more rotation operations.
        - So use an AVL tree if you expect the number of lookups to dominate the number of updates to the tree.

    2. What are the application of Red black tree?
        Red-black trees are more general purpose.
        They do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove.
        Red-black tree is used in the following:
            - Java: java.util.TreeMap , java.util.TreeSet .
            - C++ STL: map, multimap, multiset.
            - Linux kernel: completely fair scheduler, linux/rbtree.h

    LARGE DATA vs SMALL DATA: AVL vs RB Tree:
        For small data:
        1. insert:
           RB tree & avl tree has constant number of max rotation but RB tree will be faster because on average RB tree use less rotation.
        2. lookup:
           AVL tree is faster, because AVL tree has less depth.
        3. delete:
           RB tree has constant number of max rotation but AVL tree can have O(log N) times of rotation as worst. and on average RB tree also has less number of rotation thus RB tree is faster.

        for large data:
        1. insert:
           AVL tree is faster. because you need to lookup for a particular node before insertion. as you have more data the time difference on looking up the particular node grows proportional to O(log N). but AVL tree & RB tree still only need constant number of rotation at the worst case. Thus the bottle neck will become the time you lookup for that particular node.
        2. lookup:
           AVL tree is faster. (same as in small data case)
        3. delete:
           AVL tree is faster on average, but in worst case RB tree is faster. because you also need to lookup for a very deep node to swap before removal (similar to the reason of insertion). on average both trees has constant number of rotation. but RB tree has a constant upper bound for rotation.

25.
Balancing a Heap


26.
Why is Heapify O(n)
http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

    When heapify is called, the running time depends on how far an element might move down in tree before the process terminates.
    In other words, it depends on the height of the element in the heap.
    In the worst case, the element might go down all the way to the leaf level.

    Let us count the work done level by level.
    At the bottommost level, there are 2^(h)nodes, but we do not call heapify on any of these, so the work is 0.
    At the next to level there are 2^(h - 1) nodes, and each might move down by 1 level.
    At the 3rd level from the bottom, there are 2^(h - 2) nodes, and each might move down by 2 levels.

    As you can see not all heapify operations are O(log n), this is why you are getting O(n)

26b.
SiftUp vs SiftDown
https://en.wikipedia.org/wiki/Heapsort
http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
https://www.youtube.com/watch?v=MiyLo8adrWw&feature=youtu.be

    Heapify is O(n) when done with siftDown but O(n log n) when done with siftUp.
    The actual sorting (pulling items from heap one by one) has to be done with siftUp so is therefore O(n log n)

    - siftDown swaps a node that is too small with its largest child (thereby moving it down) until it is at least as large as both nodes below it.
    - siftUp swaps a node that is too large with its parent (thereby moving it up) until it is no larger than the node above it.

    The heapify procedure can be thought of as building a heap from the bottom up by successively sifting downward to establish the heap property.
    An alternative version (shown below) that builds the heap top-down and sifts upward may be simpler to understand.
    This siftUp version can be visualized as starting with an empty heap and successively inserting elements, whereas the siftDown version given above treats the entire input array as a full but "broken" heap and "repairs" it starting from the last non-trivial sub-heap (that is, the last parent node).

    Also, the siftDown version of heapify has O(n) time complexity, while the siftUp version given below has O(n log n) time complexity due to its equivalence with inserting each element, one at a time, into an empty heap

    SIFTUP:
        - Insertion of a new element into a heap is done in two steps.
        - First the element is inserted in the only place with room for it,- At the bottom of the tree, - And next it is shifted up the tree until the heap property holds.
        - The insertion is trivial, but the siftup deserves extra attention because of its importance for the performance.

    SIFTDOWN:
        - Deletion of the maximum element from the heap must find an element to replace the maximum element (in the root).
        - As for insertion this is done in to steps.
        - First the maximum element (the root) is replaced with the last element of the heap, and next the new root is shifted down the tree along the path of the largest children.

    The number of operations required for each operation is proportional to the distance the node may have to move.
    For siftDown, it is the distance from the bottom of the tree, so siftDown is expensive for nodes at the top of the tree.
    With siftUp, the work is proportional to the distance from the top of the tree, so siftUp is expensive for nodes at the bottom of the tree.
    Although both operations are O(log n) in the worst case, in a heap, only one node is at the top whereas half the nodes lie in the bottom layer.
    So it shouldn't be too surprising that if we have to apply an operation to every node, we would prefer siftDown over siftUp.

    The buildHeap function takes an array of unsorted items and moves them until it they all satisfy the heap property.
    There are two approaches one might take for buildHeap.
    One is to start at the top of the heap (the beginning of the array) and call siftUp on each item.
    At each step, the previously sifted items (the items before the current item in the array) form a valid heap, and sifting the next item up places it into a valid position in the heap.
    After sifting up each node, all items satisfy the heap property.
    The second approach goes in the opposite direction: start at the end of the array and move backwards towards the front. At each iteration, you sift an item down until it is in the correct location.

    Both of these solutions will produce a valid heap. The question is: which implementation for buildHeap is more efficient? Unsurprisingly, it is the second operation that uses siftDown. If h = log n is the height, then the work required for the siftDown approach is given by the sum

    (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).
    i.e. n/2 nodes might have to move 0 level
         n/4 nodes might have to move 1 level
         n/8 nodes might have to move 2 level
         ...

    Each term in the sum has the maximum distance a node at the given height will have to move (zero for the bottom layer, h for the root) multiplied by the number of nodes at that height. In contrast, the sum for calling siftUp on each node is

    (h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).
    i.e. n/2 nodes might have to move h level

    It should be clear that the second sum is larger. The first term alone is hn/2 = 1/2 n log n, so this approach has complexity at best O(n log n). However, the sum for the siftDown approach can be bounded by extending it to a Taylor series to show that it is indeed O(n). If there is interest, I can edit my answer to include the details. Obviously, O(n) is the best you could hope for.

27.
n way merge
https://www.geeksforgeeks.org/merge-k-sorted-arrays/

    Create a min Heap and insert the first element of all k arrays.
    Run a loop until the size of MinHeap is greater than zero.
    Remove the top element of the MinHeap and print the element.
    Now insert the next element from the same array in which the removed element belonged.
    If the array doesn¿t have any more elements, then replace root with infinite.After replacing the root, heapify the tree.

28.
B Tree vs B+ Tree
http://stackoverflow.com/questions/870218/differences-between-b-trees-and-b-trees/12014474#12014474

    The image below helps show the differences between B+ trees and B trees.
    Leaves in B+ trees contain all the data
    Leaves in B+ trees are connected linerarly

    Advantages of B+ trees:
        Because B+ trees don't have data associated with interior nodes, more keys can fit on a page of memory.
        Therefore, it will require fewer cache misses in order to access data that is on a leaf node.
        The leaf nodes of B+ trees are linked, so doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes.
        A B tree, on the other hand, would require a traversal of every level in the tree.
        This full-tree traversal will likely involve more cache misses than the linear traversal of B+ leaves.

    Advantage of B trees:
        Because B trees contain data with each key, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.

29.
Heap vs Binary Search Tree
http://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst

    - Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)).
    - Insert is O(logN) for both structures.
    - If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.

    Heaps:
        - Average time complexity for Insertion is O(1)
        - Can be implemented using Arrays efficiently
        - WORST CASE Heap creation is O(N)
        - Lookup Max multiple times is O(1)

    BST:
        - Average time complexity for Insertion is O(log(N))
        - CANNOT be implemented using Arrays efficiently
        - WORST CASE Heap creation is O(N Log (N))
        - Lookup Max multiple times could be made O(1) by doing some optimization

30.
Smallest range that includes at least one number from each of the k lists
http://stackoverflow.com/questions/21134720/smallest-range-that-includes-at-least-one-number-from-each-of-the-k-lists

    You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

    For example,
        List 1: [4, 10, 13, 14]
        List 2: [0, 9, 15, 18]
        List 3: [5, 18, 22, 30]
    The smallest range here would be [14, 18] as it contains 14 from list 1, 15 from list 2, and 18 from list 3.

    MY approach is:
        Just use a MinHeap and insert the first elements from K lists
        Remove the the min element and add the next element from the corresponding list
        Simultaneously track the max and min value so that we can calculate the minimum range

31.
Select a random number from stream, with O(1) space

    Keep  track of size of stream.
    Generated random in the stream

32.
Design a data structure that supports insert, delete, search and getRandom in constant time

    - Vector:
    Insert at end : O(1)
    Delete by lookup on Hash, Swap with last element and Delete last: O(1)
    Search: Lookup on Hash
    GetRandom: Find array size and get random element

33.
Check if a given array contains duplicate elements within k distance from each other

    - Put everything in Hashtable
    - Maintain hashtable of size k
    - While inserting a new element A[i], delete A[i-k]

34.
Reservoir Sampling

    Reservoir sampling is a family of randomized algorithms for randomly choosing k samples from a list of n items, where n is either a very large or unknown number.
    Typically n is large enough that the list doesn’t fit into main memory.
    For example, a list of search queries in Google and Facebook.

    - A simple solution is to create an array reservoir[] of maximum size k.
    - One by one randomly select an item from stream[0..n-1].
    - If the selected item is not previously selected, then put it in reservoir[].
    - To check if an item is previously selected or not, we need to search the item in reservoir[].
    - The time complexity of this algorithm will be O(k^2).
    - This can be costly if k is big.
    - Also, this is not efficient if the input is in the form of a stream.

35.
Search a Word in a 2D Grid of characters

    - DFS style search

36.
If you're given a list of countries and its corresponding population, write a function that will return a random country but the higher the population of the country, the more likely it is to be picked at random.
https://softwareengineering.stackexchange.com/questions/150616/return-random-list-item-by-its-weight
https://www.careercup.com/question?id=14582824

    Approach 1:
    - Check Color Picker Logic
    - Have all countries as leaf nodes and build a Sum tree of the population
    - Generate a random number between 1 and Total Sum of Population and go to the Child
      Node that falls within the range

    Approach 2:
    - First of all, sum the population of all countries. Let the sum be N.
    - Now think of it in terms of a number line. Have a number line from 1 to N.
    - Now allocate proportional part of the number line to corresponding country based on its population (Higher the population more numbers in number line and vice versa).
    - Let say 1 to n1 is for 1st country , n1+1 to n2 to second and so on.
    - Now generate a random number between 1 to N.
    - Just return the country which owns that number in that number line.

37.
Average of a number accounting for integer overflow
        double mean(double[] ary) {
            double avg = 0;
            int t = 1;
            for (double x : ary) {
                avg += (x - avg) / t;
                ++t;
            }
            return avg;
        }

38. Swap Endianess / Converting Little Endian to Big Endian

	int little2big(int i) {
		return (i&0xff)<<24 | (i&0xff00)<<8 | (i&0xff0000)>>8 | (i>>24)&0xff;
	}

39. How many traversals need to be known to construct a BST
https://stackoverflow.com/questions/12880718/how-many-traversals-need-to-be-known-to-construct-a-bst

    To construct a BST you need only one (not in-order) traversal.

    In general, to build a binary tree you are going to need two traversals, in order and pre-order for example. However, for the special case of BST - the in-order traversal is always the sorted array containing the elements, so you can always reconstruct it and use an algorithm to reconstruct a generic tree from pre-order and in-order traversals.

    So, the information that the tree is a BST, along with the elements in it (even unordered) are equivalent to an in-order traversal.

    Bonus: why is one traversal not enough for a general tree, (without the information it is a BST)?
    Answer: Let's assume we have n distinct elements. There are n! possible lists to these n elements, however - the possible number of trees is much larger (2 * n! possible trees for the n elements are all decayed trees, such that node.right = null in every node, thus the tree is actually a list to the right. There are n! such trees, and another n! trees where always node.left = null ) Thus, from pigeon hole principle - there is at least one list that generates 2 trees, thus we cannot reconstruct the tree from a single traversal. (QED)


https://stackoverflow.com/questions/33062228/why-it-is-impossible-to-construct-binary-tree-with-pre-order-post-order-and-lev
    We can't build a tree without the in-order traversal. Why? Let's say you are given the pre-order and post-order traversals only.A simple example is shown below.
    Consider two different trees,

    TREE 1:

    root=a;
    root->left=b;
    root->left->right=c;
    Tree 2:

    root=a;
    root->right=b;
    root->right->left=c;
    Both the trees are different, but have same pre-order and post-order sequence.

    pre-order - a b c
    post-order - c b a
    This is so because we cannot separate the left sub-tree and right sub-tree using the pre-order or post-order traversal alone.

    Pre-order, as its name, always visits root first and then left and right sub-trees. That is to say, walking through a pre-order list, each node we hit would be a "root" of a sub-tree.

    Post-order, as its name, always visits left and right sub-trees first and then the root. That is to say, walking through a post-order list backward, each node we hit would be a "root" of a sub-tree.

    In-order, on the other hand, always visits left sub-tree first and then root and then right sub-tree, which means that given a root(which we can obtain from the pre-order or post-order traversal as stated above), in-order traversal tells us the sizes of the left and right sub-trees of a given root and thus we can construct the original tree.(Think this out)

    Same is the case with level-order traversal. Thus if we want to obtain a unique tree we need an in-order traversal along with any other of the three traversals.
    Note - The exception is of course a full binary tree, in which pre-order and post-order traversals can be used to construct the tree, as there is no ambiguity in tree structure.

40. Trie vs Ternary Search Tree
https://www.geeksforgeeks.org/ternary-search-tree/
    Unlike trie(standard) data structure where each node contains 26 pointers for its children, each node in a ternary search tree contains only 3 pointers:
    1. The left pointer points to the node whose value is less than the value in the current node.
    2. The equal pointer points to the node whose value is equal to the value in the current node.
    3. The right pointer points to the node whose value is greater than the value in the current node.

    Tries are suitable when there is a proper distribution of words over the alphabets so that spaces are utilized most efficiently. Otherwise ternary search trees are better. Ternary search trees are efficient to use(in terms of space) when the strings to be stored share a common prefix.

    Applications of ternary search trees:
    1. Ternary search trees are efficient for queries like ¿Given a word, find the next word in dictionary(near-neighbor lookups)¿ or ¿Find all telephone numbers starting with 9342 or ¿typing few starting characters in a web browser displays all website names with this prefix¿(Auto complete feature)¿.

    2. Used in spell checks: Ternary search trees can be used as a dictionary to store all the words. Once the word is typed in an editor, the word can be parallely searched in the ternary search tree to check for correct spelling.

41. Find number of possible perfect squares between two numbers
https://www.geeksforgeeks.org/find-number-perfect-squares-two-given-numbers/
    return (floor(sqrt(b)) - ceil(sqrt(a)) + 1);

42. Check if an Intger is a perfect square
    bool IsPerfectSquare(long input)
    {
        long closestRoot = (long) Math.Sqrt(input);
        return input == closestRoot * closestRoot;
    }

    This may get away from some of the problems of just checking "is the square root an integer" but possibly not all. You potentially need to get a little bit funkier:

    bool IsPerfectSquare(long input)
    {
        double root = Math.Sqrt(input);

        long rootBits = BitConverter.DoubleToInt64Bits(root);
        long lowerBound = (long) BitConverter.Int64BitsToDouble(rootBits-1);
        long upperBound = (long) BitConverter.Int64BitsToDouble(rootBits+1);

        for (long candidate = lowerBound; candidate <= upperBound; candidate++)
        {
             if (candidate * candidate == input)
             {
                 return true;
             }
        }
        return false;
    }

43. How will you implement your own malloc
https://stackoverflow.com/questions/13764711/making-your-own-malloc-function-in-c

    This is a very simple approach, which may get you past your 2 mallocs:
        static unsigned char our_memory[1024 * 1024]; //reserve 1 MB for malloc
        static size_t next_index = 0;

        void *malloc(size_t sz)
        {
            void *mem;

            if(sizeof our_memory - next_index < sz)
                return NULL;

            mem = &our_memory[next_index];
            next_index += sz;
            return mem;
        }

        void free(void *mem)
        {
           //we cheat, and don't free anything.
        }

44. Can anyone explain how malloc() works internally?
https://stackoverflow.com/questions/3479330/how-is-malloc-implemented-internally

Read below link
https://stackoverflow.com/questions/1119134/how-do-malloc-and-free-work
    One implementation of malloc/free does the following:
        - Get a block of memory from the OS through sbrk() (Unix call).
        - Create a header and a footer around that block of memory with some information such as size, permissions, and where the next and previous block are.
        - When a call to malloc comes in, a list is referenced which points to blocks of the appropriate size.
        - This block is then returned and headers and footers are updated accordingly.

45. If you are given two traversal sequences, can you construct the binary tree
https://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/

    Following combination can uniquely identify a tree.

        Inorder and Preorder.
        Inorder and Postorder.
        Inorder and Level-order.

    And following do not.
        Postorder and Preorder.
        Preorder and Level-order.
        Postorder and Level-order.

    For example, Preorder, Level-order and Postorder traversals are same for the trees given in above diagram.
        A       A
      /          \
     B            B
    Preorder Traversal = AB
    Postorder Traversal = BA
    Level-Order Traversal = AB

    So, even if three of them (Pre, Post and Level) are given, the tree can not be constructed.

46. Unique (non-repeating) random numbers in O(1)?
https://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1
   Initialize an array of 1001 integers with the values 0-1000 and set a variable, max, to the current max index of the array (starting with 1000).
   Pick a random number, r, between 0 and max, swap the number at the position r with the number at position max and return the number now at position max.
   Decrement max by 1 and continue.
   When max is 0, set max back to the size of the array - 1 and start again without the need to reinitialize the array.

47. Persistent Data Structures (Fully Persistent and Partially Persistent)
https://www.geeksforgeeks.org/persistent-data-structures/
https://levelup.gitconnected.com/persistent-data-structures-for-gophers-persistent-stack-70aa012d3bfa
    A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral.

48. Bellman Ford - Shortest Path
https://www.youtube.com/watch?v=FtN3BYH2Zes&t=328s
    - Shortest Path if there are negative edges
        - Works by Relaxing the graph N-1 times where N is the number of vertices
    - It doesn't work if there is a cycle whose total path weight is NEGATIVE
                (2)
            5       -10
        (4)     3       (3)
        (2), (4), (3) are vertex/nodes in graph
        5, -10 and 3 are weights of the path; Total = -2

49. Coin Arbitrage Algorithm
https://anilpai.medium.com/currency-arbitrage-using-bellman-ford-algorithm-8938dcea56ea
https://leetcode.com/discuss/interview-question/483660/google-phone-currency-conversion

    Let’s say, 1 U.S. dollar bought 0.82 Euro, 1 Euro bought 129.7 Japanese Yen, 1 Japanese Yen bought 12 Turkish Lira, and 1 Turkish Lira bought 0.0008 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy U.S. dollars, thus turning a 0.82*129.7*12*0.008 =1.02 US dollars, thus making a 2% profit.

    Arbitrage opportunities arise when a cycle is determined such that the edge weights satisfy the following expression
        w1 * w2 * w3 * … * wn > 1
    The above constraint of finding the cycles is harder in graphs. Instead we must transform the edge weights of the graph such that the standard graph algorithms can be applied.

    Let’s take the logarithm on both sides, such that
        log(w1) + log(w2) + log(w3) + … + log(wn) > 0

    Taking the negative log, this becomes
        (-log(w1)) + (-log(w2)) + (-log(w3)) + … + (-log(wn)) < 0
    Therefore we can conclude that if we can find a cycle of vertices such that the sum of their weights if negative, then we can conclude there exists an opportunity for currency arbitrage. Luckily, Bellman-Ford algorithm is a standard graph algorithm that can be used to easily detect negative weight cycles in O(|V*E|) time.

50. Graph Algorigthms
https://towardsdatascience.com/10-graph-algorithms-visually-explained-e57faa1336f3
https://www.youtube.com/watch?v=tWVWeAqZ0WU - Graph Algorithms for Technical Interviews - Full Course
    1. Shortest Path
        a. Dijkstra’s shortest path algorithm
        b. Bellman–Ford algorithm

        Applicaitons
            Used to find directions to travel from one location to another in mapping software like Google maps or Apple maps.
            Used in networking to solve the min-delay path problem.
            Used in abstract machines to determine the choices to reach a certain goal state via transitioning among different states (e.g., can be used to determine the minimum possible number of moves to win a game).
    2. Cycle detection
        a. Floyd cycle detection algorithm
        b. Brent’s algorithm

        Applications
            Used in distributed message-based algorithms.
            Used to process large-scale graphs using a distributed processing system on a cluster.
            Used to detect deadlocks in concurrent systems.
            Used in cryptographic applications to determine keys of a message that can map that message to the same encrypted value.

    3. Minimum spanning tree
        A minimum spanning tree is a subset of the edges of a graph that connects all the vertices with the minimum sum of edge weights and consists of no cycles.

        Prim’s algorithm
        Kruskal’s algorithm

        Applications
            Used to construct trees for broadcasting in computer networks.
            Used in graph-based cluster analysis.
            Used in image segmentation.
            Used in regionalisation of socio-geographic areas, where regions are grouped into contiguous regions.

    4. Strongly connected components
        A graph is said to be strongly connected if every vertex in the graph is reachable from every other vertex.

        Algorithms
            Kosaraju’s algorithm
            Tarjan’s strongly connected components algorithm
        Applications
            Used to compute the Dulmage–Mendelsohn decomposition, which is a classification of the edges of a bipartite graph.
            Used in social networks to find a group of people who are strongly connected and make recommendations based on common interests.

    5. Topological sorting
        Topological sorting of a graph is a linear ordering of its vertices so that for each directed edge (u, v) in the ordering, vertex u comes before v.

        Algorithms
            Kahn’s algorithm
            The algorithm based on depth-first search
        Applications
            Used in instruction scheduling.
            Used in data serialisation.
            Used to determine the order of compilation tasks to perform in makefiles.
            Used to resolve symbol dependencies in linkers.

    6. Graph colouring
        Graph colouring assigns colours to elements of a graph while ensuring certain conditions. Vertex colouring is the most commonly used graph colouring technique. In vertex colouring, we try to colour the vertices of a graph using k colours and any two adjacent vertices should not have the same colour. Other colouring techniques include edge colouring and face colouring.

        Algorithms
            Algorithms using breadth-first search or depth-first search
            Greedy colouring
        Applications
            Used to schedule timetable.
            Used to assign mobile radio frequencies.
            Used to model and solve games such as Sudoku.
            Used to check if a graph is bipartite.
            Used to colour geographical maps of countries or states where adjacent countries or states have different colours.

    7. Maximum flow
        We can model a graph as a flow network with edge weights as flow capacities. In the maximum flow problem, we have to find a flow path that can obtain the maximum possible flow rate.

        Algorithms
            Ford-Fulkerson algorithm
            Edmonds–Karp algorithm
            Dinic’s algorithm
        Applications
            Used in airline scheduling to schedule flight crews.
            Used in image segmentation to find the background and the foreground in an image.
            Used to eliminate baseball teams that cannot win enough games to catch up to the current leader in their division.

    8. Matching
        A matching in a graph is a set of edges that does not have common vertices (i.e., no two edges share a common vertex). A matching is called a maximum matching if it contains the largest possible number of edges matching as many vertices as possible.

        Algorithms
            Hopcroft-Karp algorithm
            Hungarian algorithm
            Blossom algorithm
        Applications
            Used in matchmaking to match brides and grooms (the stable marriage problem).
            Used to determine the vertex cover.
            Used in transportation theory to solve problems in resource allocation and optimization in travel.

51. Examples of Data Structures in real life
https://stackoverflow.com/questions/54466641/examples-of-data-structures-in-real-life

    You have to store social network "feeds". You do not know the size, and things may need to be dynamically added.
        Hash table (uniquely identifies each feed while allowing additional feeds to be added (assuming dynamic resizing))

    You need to store undo/redo operations in a word processor.
        Linked List (doubly-linked: from one node, you can go backwards/forwards one by one)

    You need to evaluate an expression (i.e., parse).
        Tree (integral to compilers/automata theory; rules determine when to branch and how many branches to have. look up parse trees)

    You need to store the friendship information on a social networking site. I.e., who is friends with who.
        Graph (each person is a point, and connections/friendships are an edge)

    You need to store an image (1000 by 1000 pixels) as a bitmap.
        Array (2-dimensional, 1000x1000, storing color values)

    To implement printer spooler so that jobs can be printed in the order of their arrival.
        Queue (like a queue/line of people waiting to get through a checkpoint)

    To implement back functionality in the internet browser.
        Stack (you can add to the stack with each site visited, and pop off as necessary to go back, as long as you don't care about going forward. If you care about forward, this is the same scenario as the word processor, so linked list)

    To store the possible moves in a chess game.
        Tree (can follow any game move by move, down from the root to the leaf. Note that this tree is HUGE)

    To store a set of fixed key words which are referenced very frequently.
        Hash table (If you want to use the keywords as keys, and get all things related to them, I would suggest a hash table with linked lists as the keys' corresponding values. I might be misunderstanding this scenario, the description confuses me a little as to how they are intended to be used)

    To store the customer order information in a drive-in burger place. (Customers keep on coming and they have to get their correct food at the payment/food collection window.)
        Queue or Hash Table (if this is a drive thru, assuming people aren't cutting in front of one another, it's like the printer question. If customers are placing orders ahead of time, and can arrive in any order, a hash table would be much better, with an order number or customer name as the key and the order details as the value)

    To store the genealogy information of biological species.
        Tree (look up phylogenic tree)
------------------------------------------------------------------------------------------
52. The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
https://stackoverflow.com/questions/185697/the-most-efficient-way-to-find-top-k-frequent-words-in-a-big-word-sequence
https://stackoverflow.com/questions/21565880/find-the-n-most-repeating-words-strings-in-a-huge-file-that-does-not-fit-in-me
https://stackoverflow.com/questions/17541983/find-the-10-most-frequently-used-words-in-a-large-book
https://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

MY SOLUTION:
    Approach 1:
        - First Hash all the words and compute a count of all the words. This can be done in O(n).
        - One approach would be to sort the hash list by values and return the top k.
          This will take O(n log n).

    Approach 2:
        - Instead we can traverse through the hash list and find the word with most frequency.
          Apply bucket sort algorithm. Create buckets and insert the elements into respective buckets.
          Then we can give all elements that have frequence over k.
        - Problem with this approach is, creating buckets of a size. This would take unnecessary space.

        - In case a new element get added to file, we can add it to hash table.
        - If the word is already in the hash, go to the bucket, pick the word and add to the correct bucket

    Approach 3:
        - IS ORDERING of top k elements important?
        - From the hash table, use quick sort partition algorithm to partition around k
        - With this you will get elements more than k. This can be done in O(n)

FROM ONLINE:
    Input: A positive integer K and a big text. The text can actually be viewed as word sequence. So we don't have to worry about how to break down it into word sequence.
    Output: The most frequent K words in the text.

    My thinking is like this.

        use a Hash table to record all words' frequency while traverse the whole word sequence. In this phase, the key is "word" and the value is "word-frequency". This takes O(n) time.

        sort the (word, word-frequency) pair; and the key is "word-frequency". This takes O(n*lg(n)) time with normal sorting algorithm.

        After sorting, we just take the first K words. This takes O(K) time.

    To summarize, the total time is O(n+nlg(n)+K)¿ Since K is surely smaller than N, so it is actually O(nlg(n)).

    We can improve this. Actually, we just want top K words. Other words' frequency is not concern for us. So, we can use "partial Heap sorting". For step 2) and 3), we don't just do sorting. Instead, we change it to be

    2') build a heap of (word, word-frequency) pair with "word-frequency" as key. It takes O(n) time to build a heap;

    3') extract top K words from the heap. Each extraction is O(lg(n)). So, total time is O(k*lg(n)).

    To summarize, this solution cost time O(n+k*lg(n)).

ANSWER:
    Solution 1:
        This can be done in O(n) time

        Steps:

            Count words and hash it, which will end up in the structure like this

            var hash = {
              "I" : 13,
              "like" : 3,
              "meow" : 3,
              "geek" : 3,
              "burger" : 2,
              "cat" : 1,
              "foo" : 100,
              ...
              ...

            Traverse through the hash and find the most frequently used word (in this case "foo" 100), then create the array of that size

            Then we can traverse the hash again and use the number of occurrences of words as array index, if there is nothing in the index, create an array else append it in the array. Then we end up with an array like:

              0   1      2            3                100
            [[ ],[ ],[burger],[like, meow, geek],[]...[foo]]

            Then just traverse the array from the end, and collect the k words.

    Solution 2:
        You're not going to get generally better runtime than the solution you've described. You have to do at least O(n) work to evaluate all the words, and then O(k) extra work to find the top k terms.

        If your problem set is really big, you can use a distributed solution such as map/reduce. Have n map workers count frequencies on 1/nth of the text each, and for each word, send it to one of m reducer workers calculated based on the hash of the word. The reducers then sum the counts. Merge sort over the reducers' outputs will give you the most popular words in order of popularity.

    Solution 3:
        After selecting the Kth smallest element, we partition the list around that element just as in quicksort. This is obviously also O(n). Anything on the "left" side of the pivot is in our group of K elements, so we're done (we can simply throw away everything else as we go along).

        So this strategy is:

            Go through each word and insert it into a hash table: O(n)
            Select the Kth smallest element: O(n)
            Partition around that element: O(n)

        If you want to rank the K elements, simply sort them with any efficient comparison sort in O(k * lg(k)) time, yielding a total run time of O(n+k * lg(k)).

        The O(n) time bound is optimal within a constant factor because we must examine each word at least once.

        The O(n + k * lg(k)) time bound is also optimal because there is no comparison-based way to sort k elements in less than k * lg(k) time.

WHAT IF THE DICTIONARY CAN'T FIT IN MEMORY
    Solution 4:
        Create an empty dictionary (hash map), keyed by word. The value is the count.
        for each file
            while not end of file
                read word
                if word in dictionary
                    update count
                else
                    if dictionary full
                        sort dictionary by word
                        output dictionary to temporary file
                        Clear dictionary
                    Add word to dictionary, with count 1
            end
        end
        if dictionary not empty
            sort dictionary by word
            output dictionary to temporary file

        You now have some number of temporary files, each sorted by word and containing one word/count pair per line. Like:

        aardvark,12
        bozo,3
        zebra,5

        Create a min-heap that you will use to hold your n largest items. Call it largest_items.

        Do a standard n-way merge of those temporary files. As you find each unique item (i.e. you merge all of the "aardvark" entries across the multiple files), you do this:

        if (largest_items.count < n)
            largest_items.add(word)
        else if (word.count > largest_items.peek().count)
        {
            // the count for this word is more than the smallest count
            // already on the heap. So remove the item with the
            // smallest count, and add this one.
            largest_items.remove_root()
            largest_items.add(word)
        }

        Complexity:

            Building the dictionaries is O(N), where N is the total number of individual words in the file.
            Sorting each temporary dictionary is O(k log k), where 'k' is the number of words in the dictionary.
            Writing each temporary dictionary is O(k)
            The merge is O(M log x), where M is the combined number of entries across all the temporary files, and x is the number of temporary files.
            Selecting the items is O(m log n), where m is the number of unique words, and n is the number of words you want to select.

        If you look at worst case behavior (i.e. all the words are unique), the complexity works out to (n is the total number of words):

            Building the dictionaries is O(n)
            Sorting and writing the temporary files is (n/m) * (m log m), where m is the dictionary size.
            The merge is n log (n/m).
            Selection is O(m + (k log k)), where k is the number of words you want to select and m is the number of unique words. Because all words are unique they have the same count, so you'll only do k inserts into the heap. The m term dominates when k is much smaller than m (which is usually the case in these situations). So selection turns out to be O(m).

        When you're working with data sets larger than memory, very often your bottleneck is file I/O. The algorithm I've outlined above tries to minimize the I/O. In the worst case (all words are unique), each word will be read twice and written once. But in the general case each word is read once and then each hash page is written once and read once. Plus, your sorts are on hash pages rather than raw words, and the total size of your temporary files will be much smaller than the original text.
------------------------------------------------------------------------------------------
53. How to count number of requests in last second, minute and hour
https://stackoverflow.com/questions/17562089/how-to-count-number-of-requests-in-last-second-minute-and-hour
https://stackoverflow.com/questions/11701008/efficient-way-to-compute-number-of-hits-to-a-server-within-the-last-minute-in-r

    Solution 1:
        If 100% accuracy is required:

        Have a linked-list of all requests and 3 counts - for the last hour, the last minute and the last second.

        You will have 2 pointers into the linked-list - for a minute ago and for a second ago.

        An hour ago will be at the end of the list. Whenever the time of the last request is more than an hour before the current time, remove it from the list and decrement the hour count.

        The minute and second pointers will point to the first request that occurred after a minute and a second ago respectively. Whenever the time of the request is more than a minute / second before the current time, shift up the pointer and decrement the minute / second count.

        When a new request comes in, add it to all 3 counts and add it to the front of the linked-list.

        Requests for the counts would simply involve returning the counts.

        All of the above operations are amortised constant time.

        If less than 100% accuracy is acceptable:

        The space-complexity for the above could be a bit much, depending on how many requests per second you would typically get; you can reduce this by sacrificing slightly on accuracy as follows:

        Have a linked-list as above, but only for the last second. Also have the 3 counts.

        Then have a circular array of 60 elements indicating the counts of each of the last 60 seconds. Whenever a second passes, subtract the last (oldest) element of the array from the minute count and add the last second count to the array.

        Have a similar circular array for the last 60 minutes.

        Loss of accuracy: The minute count can be off by all the requests in a second and the hour count can be off by all the requests in a minute.

        Obviously this won't really make sense if you only have one request per second or less. In this case you can keep the last minute in the linked-list and just have a circular array for the last 60 minutes.

        There are also other variations on this - the accuracy to space used ratio can be adjusted as required.

        A timer to remove old elements:

        If you remove old elements only when new elements come in, it will be amortised constant time (some operations might take longer, but it will average out to constant time).

        If you want true constant time, you can additionally have a timer running which removes old elements, and each invocation of this (and of course insertions and checking the counts) will only take constant time, since you're removing at most a number of elements inserted in the constant time since the last timer tick.

    Solution 2:
        To do this for time window of T seconds, have a queue data structure where you queue the timestamps of individual requests as they arrive. When you want to read the number of requests arrived during the most recent window of T seconds, first drop from the "old" end of the queue those timestamps that are older than T seconds, then read the size of the queue. You should also drop elements whenever you add a new request to the queue to keep its size bounded (assuming bounded rate for incoming requests).

        This solution works up to arbitrary precision, e.g. millisecond accuracy. If you are content with returning approximate answers, you can e.g. for time window of T = 3600 (an hour), consolidate requests coming within same second into a single queue element, making queue size bounded by 3600. I think that would be more than fine, but theoretically loses accuracy. For T = 1, you can do consolidation on millisecond level if you want.

        In pseudocode:
        queue Q

        proc requestReceived()
          Q.insertAtFront(now())
          collectGarbage()

        proc collectGarbage()
          limit = now() - T
          while (! Q.empty() && Q.lastElement() < limit)
            Q.popLast()

        proc count()
          collectGarbage()
          return Q.size()

    Solution 3:
        Why not just use a circular array? We have 3600 elements in that array.

        index = 0;
        Array[index % 3600] = count_in_one_second.
        ++index;

        if you want last second, return the last element of this array. if you want last minute, return the sum of last 60 elements. if you want last hour, return the sum of the whole array (3600 elements).

        Also How about using current time (e.g. System.currentTimeMillis()) instead of index?

    Solution 4:
        Use a circular buffer.

        Whenever you have to keep some current statistics with a built-in obsolescence, a ring buffer is a good candidate. In your case, you can easily keep count of the requests in the last minute by inserting new packets at the front of the circular buffer and keeping a one-minute-before-now pointer in the buffer, or performing a binary search on request time.