What is the smallest integer greater than 95555 in which there will be 4 identical numbers?

Ans: 96666? nope, its 95999 :-)

Direct Memory Access (DMA)

Reference:

If IO device (such as disk controller) needs data to be written or read from the memory, it used to to through the CPU like below.

In the above image, if IO can talk to/access memory directly, the number of cycles will reduce drastically. To achieve this direct memory access by an IO device, a special called DMA controller is needed.

Now, there are 4 components involved in DMA theory. Picture below.

YOUTUBE LINK: https://www.youtube.com/watch?v=Xkpu8BXi3aI

Here is how it works:
1. 

Bubble Sort

Pseudocode:

for j = 0 to n -2 // no need till n-2 as it will validate already properly aligned values(see code)
    if a[j] > a[j+1]
        swap (a[j], a[j+1])
 After the above pass, the largest element will come at the end.

Perform the above pass for each of the elements in the array.

Code
#include <stdio.h>

#define NELEMS(x) (sizeof (x) / sizeof (x[0]))

void display(int arr[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);

    printf("\n");
}

void swap(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}

void bubble(int arr[], int n)
{
    int i, j;
    int swapped = 0;
    for (i = 0; i < n - 1; ++i) { // no need of <n as bigger will find its way anyway
        swapped = 0;
        for (j = 0; j < n - i - 1; ++j) { // j < n-2 also works, but this is not needed
            if (arr[j] > arr[j + 1]) {
                swap(arr + j, arr + j + 1);
                swapped = 1;
                display(arr, 8);
            }
        }
        if (swapped == 0) break; // if no swap happened, no need to continue any further
    }
}

int main()
{
    int arr[] = { 17, 21, 19, 15, 5, 99, 1, 0 };
    /* int arr[] = { 17, 21, 19, 98, 99, 100, 101, 102 }; // almost sorted (usage of swapped flag helps here) */

    printf("Unsorted: ");
    display(arr, NELEMS(arr));

    bubble(arr, NELEMS(arr));

    printf("Sorted: ");
    display(arr, NELEMS(arr));
}

Output:

Unsorted: 17 21 19 15 5 99 1 0

17 19 21 15 5 99 1 0

17 19 15 21 5 99 1 0

17 19 15 5 21 99 1 0

17 19 15 5 21 1 99 0

17 19 15 5 21 1 0 99

17 15 19 5 21 1 0 99

17 15 5 19 21 1 0 99

17 15 5 19 1 21 0 99

17 15 5 19 1 0 21 99

15 17 5 19 1 0 21 99

15 5 17 19 1 0 21 99

15 5 17 1 19 0 21 99

15 5 17 1 0 19 21 99

5 15 17 1 0 19 21 99

5 15 1 17 0 19 21 99

5 15 1 0 17 19 21 99

5 1 15 0 17 19 21 99

5 1 0 15 17 19 21 99

1 5 0 15 17 19 21 99

1 0 5 15 17 19 21 99

0 1 5 15 17 19 21 99

Sorted: 0 1 5 15 17 19 21 99

Time Complexity: O(n^n)

Selection Sort

Pseudocode:

• Take element in 0th position
• From 1st to (n-1)th position, find the smallest element and its index.
• If we found a smallest element, swap it with 0th position
• Repeat the above for all the positions
• NOTE: Selection sort basically means, fill the position of each index (starting from 0) by it's appropriate value (by choosing the minimum amount in the remaining indexes in each loop)

Psuedocode flow:

SelectionSort (A, n)

{

    for i = 0 to n -1 // we can do it till n-2, as n-1 will automatically have biggest element in its position

    {

        iMin = i
        for j = i+1 to n-1

         {

            if (A[j] < A[iMin])

                iMin = j
           }

            swap (A[iMin], A[i])

    }

}

C Code:

#include <stdio.h>

#define NELEMS(x) (sizeof (x)/sizeof(x[0]))

void swap(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}

void display(int arr[], int size)
{
    int i;
    for (i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void selection(int arr[], int n)
{
    int i, j, iMin;

    for (i = 0; i < n - 1; ++i) { // no need for last iteration, as the biggest number will be there anyways (due to previous operation)
        iMin = i; // find the right element for this position
        for (j = i + 1; j < n; ++j) {
            if (arr[j] < arr[iMin]) {
                iMin = j;
            }
        }
        swap(arr + iMin, arr + i);
        display(arr, 7); // NELEMS wont' work as it will be converted as pointer _here_
    }
}

int main()
{
    int arr[] = { 21, 5, 22, 74, 0, 99, 18 };

    printf("UnSorted: ");
    display(arr, NELEMS(arr));

    selection(arr, NELEMS(arr));

    printf("Sorted: ");
    display(arr, NELEMS(arr));
    return (0);

}

Output:

UnSorted: 21 5 22 74 0 99 18

0 5 22 74 21 99 18

0 5 22 74 21 99 18

0 5 18 74 21 99 22

0 5 18 21 74 99 22

0 5 18 21 22 99 74

0 5 18 21 22 74 99

Sorted: 0 5 18 21 22 74 99

[NOTE that, each index starting from 0 (referred by iMin), will pull the appropriate value, by going through the loop]

Sorting Basics

Sorting

http://www.youtube.com/playlist?list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U

Sorting is basically essential to do the searching.

Linear Search:
If we are to search a data in an unsorted pool of data, we call the search as Linear Search.
If the number of data in the pool is 'n', and we are to search for a data 'd', then we need to compare 'd' against (n-1) elements.
If n is 2^64, and if each comparison takes 1 ms, then we will need 2^64 ms (worst-case) to find the data.

size = n
n = 2^64 => 2^64 comparisons

Sorted:
If we the pool is sorted, then we can use Binary search.
size = n
And if n = 2^64 => 64 ms

Number of Sorting algorithms:

1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort
7. Counting Sort
8. Radix Sort
9. [And many more]

Classification of these algorithms is based on:

1. Time Complexity (Big O Notation)
2. Space Complexity or Memory Usage [Merge sort, uses temporary storage]
3. Stability (already sorted items in the input, will be preserved in the sorted list). For ex, cards of 6heart and 6clubs along with other cards, will remain in same order even in sorted list
4. Internal (RAM) or External Sort (data in Disc or tapes)
5. Recursive (Quick and Merge) and Non-Recursive

Angle between Hour and Minute Hands

Question: Find the angle between hour and minute hands when the time is 3.27.
Answer: 58.5
Solution:

1. First, find the angle at minute hand is, from 12'o clock
2. Next, find the angle of hour hand is, from 12'o clock
3. The difference between them is the answer.

Angle of minute hand from 12'o clock:

Minute hand is showing 27 minutes (see the question).

For 60 mins, the minute handle will move 360 degree.

So, for 1 min, how much degree it will move? 

((1 * 360)  / 60) => 6 degree.

So, for 27 mins, the minute handle will be at, 27 * 6 degrees from 12'o clock.

Which is, 162 degree.

Angle of hour hand from 12'o clock:

The angle between each hour is 30 degree.

So, at 3'o clock, the hour handle will be exactly at 90 degree (from 12'o clock).

Now, the time has past 27 mins from 3'o clock (see question).

So, we need to find the hour handle moves for each minute.

For 60 mins, the hour handle moves 30 degree.

So, for 1 min, the hour handles moves: 

((1* 30)/60) => 0.5 degree.

So, for 27 mins, the hour handle would have moved, 27 * 0.5 degree,

which is 13.5 degree.

So, the total degree of hour handle from 12'o clock => 90 + 13.5 degrees.

It is 103.5 degree.

The difference between minute handle and hour handle => 162 - 103.5 => 58.5 degree.

58.5 degree is the answer.

Simple formula: 30 * hours - 5.5 * mins

For same question (3:27) => (30 * 3) - (5.5 * 27) => 90 -  148.5 => -58.5 (degree don't have signs)

Big O Notation With Sample codes

Table of Summary:

Examples

O(1) - Constant Time Examples:

• Algorithm 1:

Algorithm 1 prints hello once and it doesn't depend on n, so it will always run in constant time, so it is O(1).

print "hello";

• Algorithm 2:

Algorithm 2 prints hello 3 times, however it does not depend on an input size. Even as n grows, this algorithm will always only print hello 3 times. That being said 3, is a constant, so this algorithm is also O(1).

print "hello";
print "hello";
print "hello";

O(log(n)) - Logarithmic Examples:

• Algorithm 3 - This acts like "log_2"

Algorithm 3 demonstrates an algorithm that runs in log_2(n). Notice the post operation of the for loop multiples the current value of i by 2, so i goes from 1 to 2 to 4 to 8 to 16 to 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• Algorithm 4 - This acts like "log_3"

Algorithm 4 demonstrates log_3. Notice i goes from 1 to 3 to 9 to 27...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• Algorithm 5 - This acts like "log_1.02"

Algorithm 5 is important, as it helps show that as long as the number is greater than 1 and the result is repeatedly multiplied against itself, that you are looking at a logarithmic algorithm.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O(n) - Linear Time Examples:

• Algorithm 6

This algorithm is simple, which prints hello n times.

for(int i = 0; i < n; i++)
  print "hello";

• Algorithm 7

This algorithm shows a variation, where it will print hello n/2 times. n/2 = 1/2 * n. We ignore the 1/2 constant and see that this algorithm is O(n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O(n*log(n)) - nlog(n) Examples:

• Algorithm 8

Think of this as a combination of O(log(n)) and O(n). The nesting of the for loops help us obtain the O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

• Algorithm 9

Algorithm 9 is like algorithm 8, but each of the loops has allowed variations, which still result in the final result being O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O(n^2) - n squared Examples:

• Algorithm 10

O(n^2) is obtained easily by nesting standard for loops.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

• Algorithm 11

Like algorithm 10, but with some variations.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O(n^3) - n cubed Examples:

• Algorithm 12

This is like algorithm 10, but with 3 loops instead of 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";

• Algorithm 13

Like algorithm 12, but with some variations that still yield O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";




Big O Notation

https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly
O(log(N))

O(log N) basically means time goes up linearly while the n goes up exponentially. So if it takes 1second to compute 10 elements, it will take 2 seconds to compute 100 elements, 3 seconds to compute 1000 elements, and so on.

​It is O(log n) when we do divide and conquer type of algorithms e.g binary search. Another example is quick sort where each time we divide the array into two parts and each time it takes O(N) time to find a pivot element. Hence it N O(log N)

Phone Book example:

• O(1) (best case): Given the page that a business's name is on and the business name, find the phone number.
• O(1) (average case): Given the page that a person's name is on and their name, find the phone number.
• O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.)
• O(n): Find all people whose phone numbers contain the digit "5".
• O(n): Given a phone number, find the person or business with that number.
• O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.

For the below examples, we're now at the printer's office. Phone books are waiting to be mailed to each resident or business, and there's a sticker on each phone book identifying where it should be mailed to. Every person or business gets one phone book.

Horse Loop:

Ok let's try and fully understand what a logarithm actually is.

Imagine we have a rope and we have tied it to a horse. If the rope is directly tied to the horse, the force the horse would need to pull away (say, from a man) is directly 1.

Now imagine the rope is looped round a pole. The horse to get away will now have to pull many times harder. The amount of times will depend on the roughness of the rope and the size of the pole, but let's assume it will multiply one's strength by 10 (when the rope makes a complete turn).

Now if the rope is looped once, the horse will need to pull 10 times harder. If the human decides to make it really difficult for the horse, he may loop the rope again round a pole, increasing it's strength by an additional 10 times. A third loop will again increase the strength by a further 10 times.

We can see that for each loop, the value increases by 10. The number of turns required to get any number is called the logarithm of the number i.e. we need 3 posts to multiple your strength by 1000 times, 6 posts to multiply your strength by 1,000,000.

3 is the logarithm of 1,000, and 6 is the logarithm of 1,000,000 (base 10).

Expect script

Link: https://likegeeks.com/expect-command/

Important GIT tricks

1. To view the diff of the files using vimdiff, 
1. Open ~/.gitconfig and append the following lines
   [diff]
     external = git_diff_wrapper

NOTE: you can also do it, by issuing "git config --global diff.tool vimdiff", but I have not tried.

References: https://technotales.wordpress.com/2009/05/17/git-diff-with-vimdiff/

https://stackoverflow.com/questions/3713765/viewing-all-git-diffs-with-vimdif

2. To ignore the cscope files showing from "git status [-s]", do the following.
- go to the working directory
- and add cscope file(s) in .gitignore file