Minimum no. of comparisons required for finding 2nd minimum element

second smallest of n elements can be found with n + logn -2 in worst case..

Lets check out how?

See the pair-wise comparison below

1  2  3  4  5  6  7  8
 \/    \/    \/    \/
 1      3    5      7
   \  /        \  /
     1          5
        \   /
          1

1 is the smallest, it took n-1 = 7 comparisons. Now compare all the numbers which 1 was compared to (compare 2,3,5).

2  3   5
 \/   /
  2  /
   \/
   2

2 is the second smallest. It took lg(n)-1 = 2 comparisons.

So total is (n-1)+(logn-1) = n+logn-2 comparisons.

Why manhole cover are round

• A round manhole cover cannot fall through its circular opening, whereas a square manhole cover could fall in if it were inserted diagonally in the hole.
• Circular covers don’t need to be rotated or precisely aligned when placing them on the opening.
• A round manhole cover is easily moved and rolled.
• Human beings have a roughly circular cross-section.
• Round tubes are the strongest shape against the compression of the earth around them, so the cover of the tube would naturally be round as well.
• It’s easier to dig a circular hole.
• Round castings are much easier to manufacture using a lathe.

read in detail

Thread vs Process

Processes are the abstraction of running programs: A binary image, virtualized memory, various kernel resources, an associated security context, and so on. Threadsare the unit of execution in a process: A virtualized processor, a stack, and program state. Put another way, processes are running binaries and threads are the smallest unit of execution schedulable by an operating system's process scheduler.

A process contains one or more threads. In single-threaded processes, the process contains one thread. You can say the thread is the process—there is one thing going on. In multithreaded processes, the process contains more than one thread—there's more than one thing going on.

The two primary virtualized abstractions in modern operating systems are virtualized memory and a virtualized processor. Both afford the illusion to running processes that they alone consume the machine's resources. Virtualized memory gives processes a unique view of memory that seamlessly maps back to physical RAM or on-disk storage (swap space). A virtualized processor lets processes act as if they alone run on a processor, when in fact multiple processes are multitasking across multiple processors.

Virtualized memory is associated with the process and not the thread. Thus, threads share one memory address space. Conversely, a distinct virtualized processor is associated with each thread. Each thread is an independent schedulable entity.

What's the point? We obviously need processes. But why introduce the separate concept of a thread and allow multithreaded processes? There are four primary benefits to multithreading:

• Programming abstraction. Dividing up work and assigning each division to a unit of execution (a thread) is a natural approach to many problems. Programming patterns that utilize this approach include the reactor, thread-per-connection, and thread pool patterns. Some, however, view threads as an anti-pattern. The inimitable Alan Cox summed this up well with the quote, "threads are for people who can't program state machines."
• Parallelism. In machines with multiple processors, threads provide an efficient way to achieve true parallelism. As each thread receives its own virtualized processor and is an independently-schedulable entity, multiple threads may run on multiple processors at the same time, improving a system's throughput. To the extent that threads are used to achieve parallelism—that is, there are no more threads than processors—the "threads are for people who can't program state machines" quote does not apply.
• Blocking I/O. Without threads, blocking I/O halts the whole process. This can be detrimental to both throughput and latency. In a multithreaded process, individual threads may block, waiting on I/O, while other threads make forward progress. Asynchronous & non-blocking I/O are alternative solutions to threads for this issue.
• Memory savings. Threads provide an efficient way to share memory yet utilize multiple units of execution. In this manner they are an alternative to multiple processes.

The cost of these benefits of threading are increased complexity in the form of needing to manage concurrency through mechanisms such as mutexes and condition variables. Given the growing trend toward processors sporting multiple cores and systems sporting multiple processors, threading is only going to become a more important tool in system programming.

C Operator Precedence Table

 Refer to precedance table

Max XOR of two numbers

Question:Suppose we're given two numbers l and r and that we want to find max(i⊕j) for l≤i,j≤r.

Answer:
Common solution is to proceed with O(n^2) time.

but, It is possible to do it in O(log r) time.

The maximum possible XOR of any two integers from an interval [l,r] can be determined from l⊕r, assuming l,r to be integers. This value is equal to 2p−1, where p is the smallest value such that 2p is larger than l⊕r.

Here is an implementation in C++

int maximumXOR(int l, int r) {
    int q = l ^ r, a = 1;
    while(q){
        q /= 2;
        a <<= 1;
    }
    return --a;
}

Trailing Zeros in 100 Factorial

Ok, let’s look at how trailing zeros are formed in the first place. A trailing zero is formed when a multiple of 5 is multiplied with a multiple of 2. Now all we have to do is count the number of 5′s and 2′s in the multiplication.

Let’s count the 5′s first. 5, 10, 15, 20, 25 and so on making a total of 20. However there is more to this. Since 25, 50, 75 and 100 have two 5′s in each of them (25 = 5 * 5, 50 = 2 * 5 * 5, …), you have to count them twice. This makes the grand total 24. For people who like to look at it from a formula point of view

Number of 5′s = 100/5 + 100/25 + 100/125 + … = 24 (Integer values only)

Moving on to count the number of 2′s. 2, 4, 6, 8, 10 and so on. Total of 50 multiples of 2′s, 25 multiples of 4′s (count these once more), 12 multiples of 8′s (count these once more) and so on… The grand total comes out to

Number of 2′s = 100/2 + 100/4 + 100/8 + 100/16 + 100/32 + 100/64 + 100/128 + … = 97 (Integer values only)

Each pair of 2 and 5 will cause a trailing zero. Since we have only 24 5′s, we can only make 24 pairs of 2′s and 5′s thus the number of trailing zeros in 100 factorial is 24.

Non recursive fibonnaci program

Q:

int main() {   int f = 0, g = 1;   int i;   for(i = 0; i < 15; i++)   {     printf("%d \n", f);     f = f + g;     g = f - g;   }   getchar();   return 0; }

Answer: The function prints first 15.