Interesting Programming Puzzle - Separate Engineers and Managers

There are n people of which more than half are engineers and the rest are managers. An engineer always tells the truth. A manager may  or may not speak the truth. to every ith guy, you can ask whether the jth guy is an engineer.
Find out a way to separate out engineers and managers in the most efficient way.

Solution :

Here's an n-1 query solution
1. Maintain three sets of people: UNSEEN, STACK, and DISCARD.
2. Initialize the process by picking one arbitrarily to be the STACK, everything else is UNSEEN.
3. Repeat the following step until UNSEEN is empty:
        a. Pick an UNSEEN element x, remove it from UNSEEN.
        b. Ask the top of the STACK y about x. If y says "manager" pop y off the stack and DISCARD both x and y. If it says "engineer" add x to the top of the STACK.

After all elements have been processed in this way (n-1 comparisons), the top of the stack must be an engineer. Once we get an engineer, we can separate out engineers and managers by asking the engineer since an engineer always speaks truth.

Why does this work? 

First observe that whenever we discard a pair, at least one of them is a manager(If you don't understand this, check by taking various cases). So among the rest of them (STACK and UNSEEN) a majority must still be engineers. So at the end,when UNSEEN is empty, there must be an engineer in the stack, therefore the top of the stack must be an engineer.

This can be improved to n-2 simply by stopping one earlier. When there's one UNSEEN left, if the stack is empty, that UNSEEN one is an engineer. Otherwise, the top of the stack must be an engineer. If is n is even and n>=4, as a first step we can just throw out one person, and apply this algorithm to the remaining n-1 obtaining n-3 comparisons. This gives the optimal algorithm.

Birthday Paradox

This is one of the very interesting problems in Probability theory. So here it goes. Birthday Paradox concerns  the probability, that in a set of n randomly chosen people, some pair of them will have the same birthday.

Consider the following example: Assuming for a moment that birthdays are evenly distributed throughout the year, if you're sitting in a room with forty people in it, what are the chances that two of those people have the same birthday? For simplicity's sake, we'll ignore leap years. A reasonable, intelligent person might point out that the odds don't reach 100% until there are 366 people in the room (the number of days in a year + 1)... and forty is about 11% of 366... so such a person might conclude that the odds of two people in forty sharing a birthday are about 11%. In reality, due to Math's convoluted reasoning, the odds are about 90%. This phenomenon is known as the Birthday Paradox.

It turns out that this phenomenon is very useful in cryptography and hashing algorithms. The birthday paradox is strange, counter-intuitive, and completely true. It’s only a “paradox” because our brains can’t handle the compounding power of exponents. We expect probabilities to be linear and only consider the scenarios we’re involved in (both faulty assumptions, by the way). So, without diverging away lets dive into the main part.

Lets work with some numbers. Suppose there are 23 people in a room. What are the chances that 2 people share a birthday ?

Lets list down all the possible ways, 23 people can have birthdays and count the ways where at least 2 people share a birthday. After this calculating this, the required probability is a cake walk. But since the number of ways are huge, this is hard to do. Lets flip the problem. Instead of finding all the ways where at 2 people share a birthday, lets find all the ways where no 2 people share a birthday. Then we can easily compute the probability that at least 2 people share a birthday by subtracting from 1. 

With 23 people, we have 253 combinations. 

(23 X 22) / 2 = 253

The chance of 2 people having different birthdays is :

1 - (1/365)  = (364 / 365) = 0.997260  --> This should be pretty easy to understand

Makes sense. 364 out of 365 days are Ok.

Now, all the 253 pairs should be different. We use exponents to find the probability. So, the probability that all the 253 pairs have different birthdays is 

(364 / 365) ^ 253 = 0.4995

Now the chances that out of 23 people in a room, no 2 people share a birthday is 1 - 0.4995 = 0.5005 = 50.05%

The generalized formula is :

P(n) = 1 - (364 / 365)^C(n,2), where n is the count of people in the room.

There is another way to look at this problem which may seem easier for some people:
Let's say you have a big wall calendar with all 365 days on it. You walk in and put a big X on your birthday. The next person who walks in has only a 364 possible open days available, so the probability of the two dates not colliding is 364/365. The next person has only 363 open days, so the probability of not colliding is 363/365. If you multiply the probabilities for all 23 people not colliding, then you get:
364/365 × 363/365 × … 365-23+1/365 = Chances of no collisions

Catastrophic Backtracking

Lets start off with a small puzzle.

Here is the code :
What would be the output of the above code ? Here are the options :
a) 99
b) 100
c) Throw an exception
d) None of the above

As clear from the code, the regular expression will match "no" odd number strings of "a". Most the people would think that the answer is 99 since we have 99 even number strings of a's, but Oups !! Wait a minute !!

The correct answer is d option. Strange !! Isn't it ??
Well to add more to your confusion, the above program runs for more than 10^15 years before printing anything. How is this possible ?

This is due to "Catastrophic BackTracking" which is caused by our regex. Lets take a close look at it : (aa|aab?)+

Lets say we are matching a string that does not below to the pattern specified, example "aaaaa". Here is the DFA for this :

As seen from the DFA in the image above, the DFA engine traverses the "whole tree". The time complexity of the above code is exponential in the length of string : O(2^(n/2)) to be precise.

How can we fix it ?

The solution is simple. While nesting repetition operators, make sure that "there is only one way to match the same match". 

In our code, there are multiple ways to match a string. For example, both "aa" pattern is matched by both "aa" and "aab?". So, lets change our code to use a regular expression which adheres to the above principle :

The regex"(aab?)+" matches exactly the same strings as "(aa|aab?)+", but doesn't exhibit "catastrophic backtracking". The above code does produce an output and it prints 99.

Java Garbage Collection

Garbage Collection is the process of looking at the heap memory, identifying which objects are in use and which are not, and deleting the unused objects. When we say that an object is in use, we mean that some part of our program still has a pointer to that object. An unused object on the other hand, is no longer referenced by any part of our program. Hence the memory used by the unused object can be reclaimed. This is what garbage collection does.

Java does not explicitly allocate and deallocate memory in the program code like in C or C++. Some developers set the object references to null or call System.gc() to free the memory explicitly. Explicitly nulling of object references is not a big deal  since modern Java compilers are smart enough to interpret when an object becomes out of scope in "almost all" the cases. But System.gc() would affect the system performance drastically and should not be called. In Java, the developer does not explicitly free the memory in the program code. The garbage collector takes care of it. The Java garbage collector is based on the following 2 hypotheses which are called the weak generation hypotheses:

1. Most objects become unreachable soon.
2. References from old objects to new objects only exist in small numbers.

In HotSpot JVM, the heap space is divided into 3 regions :

1. Young Generation : Most of the newly created objects are located in this region. Since according to the above hypotheses most objects become unreachable soon, most objects die here. When we say objects die here, we mean to say that they are collected by minor GC. The objects which survive this generation are transferred to the old generation.
2. Old Generation : The objects which survive the young generation are copied here. It is "generally" larger than the young generation. Since it is bigger in size, GC is less frequent than in the young generation. It should be noted that the size of the generations is configurable and is tuned based on the application requirement, but most of the times old generation is bigger than the young generation. When objects die in the old generation we say that a major GC has occurred.
3. Permanent Generation : The permanent generation is for methods and classes. A GC can occur is this as well and it is counted as a major GC. This generation is populated by the JVM at runtime based on the classes in use by the application. In addition, Java SE library classes and methods may be stored here.

The following figure makes it clear.

Why Java uses different generations in the Heap ?

JVM used Mark and Sweep algorithm for garbage collection. The first step in this process is called marking. In this step, garbage collector identifies which objects are in use and which are not. This can be a time consuming process since we need to scan all the objects. The second step is the deletion step. In this step, unreferenced objects are removed, leaving behind referenced objects and pointers to free space. The following figures explain the 2 steps :

To improve the performance, in addition to removing the unreferenced objects, we compact the remaining referenced objects by moving them together. This makes new memory allocations easier and faster. Having to mark all objects in JVM is inefficient. As more and more objects are allocated, list of objects grows leading to longer garbage collection times. Instead, we can make use of the weak generation hypothesis as explained previously. That is why Java uses Generational Garbage Collection.

Composition of Young Generation :

The young generation is composed of 3 spaces : one Eden space and two Survivor spaces. The majority of the newly created objects are created in the Eden space. After one GC in the Eden space, surviving objects are moved to one of the survivor spaces. Once this survivor space is full, surviving objects are moved to the other survivor space. And surviving objects from this survivor space are moved to the old generation.

Some Garbage Collectors in JVM :

Some types of garbage collectors:

1. Serial GC
2. Parallel GC
3. Concurrent Mark & Sweep (CMS) GC

Serial GC : 

This GC first marks the surviving objects in the old generation. It then sweeps the heap leaving only the surviving objects behind. It then moves the survived objects to one part. Serial GC causes stop-the-world i.e. the application becomes inactive during Serial GC.

Parallel GC : 

This GC also causes stop-the world. While Serial GC uses only one thread for GC, Parallel GC uses multiple threads for GC and is hence efficient than Serial GC. It makes sense to use this GC when we have multiple cores.

Concurrent Mark & Sweep GC : 

This GC uses only one thread. This GC performs the following steps :

• Initial Mark
• Concurrent Marking
• Remark
• Concurrent Sweeping

As clear from the below figure that Concurrent Mark Sweep GC stops the world only during the initial mark and remark phases. During the concurrent marking and sweeping phases, this GC runs along with application thread. We can parallelize this with concurrency in HotSpot JVM. This GC is used when the response time is very crucial.

JVM options for different GC algorithms :

• Serial generational collector (-XX:+UseSerialGC).
• Parallel for young space, serial for old space generational collector (-XX:+UseParallelGC).
• Parallel young and old space generational collector (-XX:+UseParallelOldGC).
• Concurrent mark sweep with serial young space collector (-XX:+UseConcMarkSweepGC -XX:-UseParNewGC).
• Concurrent mark sweep with parallel young space collector (-XX:+UseConcMarkSweepGC -XX:+UseParNewGC).
• G1 garbage collector (-XX:+UseG1GC).

Does Explicit nulling help garbage collection

Here I would be discussing whether explicit nulling of variables helps garbage collection in any significant way. For those who are not up to date with HotSpot GC, let me throw some light on that. The heap is divided into several spaces: Eden space, 2 survivor spaces and an old generation space. The Eden space and the 2 survivor spaces make up the young generation. When an object is created, it is created in the Eden space. Most objects die there (become out of scope) and are collected by the garbage collector. If an object  remains in the Eden space till the next minor GC runs, it is promoted to the 1st survivor space and then to the next survivor space. If an object becomes too old or the young generation becomes full, objects get promoted to the old generation space.

Now, lets get back on the topic: Does nulling variables explicitly help garbage collector ?
The answer is it depends. If the Eden space is full and an object is being created then if sufficient space could be created in Eden, then no more work is required. But if sufficient space can't be freed in Eden then existing objects in Eden space have to be promoted to the 1st survivor space before new objects can be created. There might be some objects in the Eden space that the application doesn't need now. But those objects have still not gone out of scope and hence can't be garbage collected. Explicitly nulling the variables holding the references to those objects would make a difference and those objects can now be garbage collected.

One thing that is to be noted here is that compiler can make object references null even if you don't make them null explicitly. Only in cases where the compiler can't prove that the object is no longer used, it doesn't make them null. Explicitly nulling can help GC in rare cases such as the one discussed above. All the following conditions should be true if you are explicitly nulling object references :

• The variable is the only weak reference to the object.
• The variable will stay in scope for an extended period of time.
• The compiler is not able to prove that the object is no longer used but you are able to prove that the object is no longer needed.

In general, explicitly nulling is not required because the Java compiler is smart enough to do that. One very important use case of explicitly nulling is when you have a map having some entries that you no longer need. The objects to which the map entries point to are not eligible for garbage collection. Making them null explicitly does help. But something like the following won't help since the object would anyhow go out of scope and would be garbage collected in the next GC run. We should never do this :

Bit Manipulation : Find 2 numbers which are repeated odd number of times in an array in which all other numbers are repeated even number of times

Today I would be sharing a problem which can be very efficiently solved using bit manipulations.

Problem :

Given an array containing integer numbers containing numbers which are repeated even number of times except two numbers which are repeated odd number of times. The range of integer numbers is not given. Find the two numbers which are repeated even odd number of time.

Solution :

It can be solved in O(n) time and O(1) space. The basic concept here is x ^ x = 0. Here's the algorithm :

1) XOR all the elements in the array. This would nullify all the elements which are repeated even number of times. So, we would get the XOR of elements which are repeated odd number of times.

2) Now divide the set of numbers into 2 sets such that numbers which are repeated odd number of times go into different sets. To divide the set in this way is quite easy given that the set bits in the XOR of two numbers are the bits in which the two numbers differ. From step 1, we got the XOR of the numbers which are repeated odd number of times. Divide all the elements of the array into 2 sets depending on any of the set bits in the XOR output of step 1.

3) XOR all the elements within each set and we would get the elements which are repeated odd number of times since the elements which are repeated even number of times would have nullified  each other.

Here is the code snippet :

Now result1 and result2 would hold the numbers which are repeated odd number of times.

There is a trick to find the lowest bit position set. Suppose x is a number and we wish to find the lowest bit position which is set. We can do so by :
x |= x & (x-1);
The above code snippet can be made more efficient by employing the above rule.

David Shaw's Supercomputer - Anton

Things have been quite on the blog, but not because there has not been a lot to say. In fact, there has been so much happening that I have had not the idle cycles to write about them.

Recently got a chance to meet one of the D.E.Shaw Research scientists and got an insight into what they are doing. Prior to forming D.E. Shaw Research, David Shaw founded D.E. Shaw & Co., a hedge fund which is one of the most successful quantitative analysis shops. Since 2001, David Shaw has been doing full time research as part of D.E.Shaw Research. D.E. Shaw Research develops both algorithms and customized machine architectures for molecular dynamic simulations such as protein folding. The result is the Anton Supercomputer, a heavily customized machine with 512 specialized computing nodes specifically designed for particle interaction simulations.

Basically, each of the 512 nodes consists of a heavily pipelined special-purpose ASIC that is designed to compute the particle force interactions (using an algorithm called the NT method), along with a general-purpose processor that supports a limited instruction set. Communication is heavily optimized to reduce the amount of data exchanged between nodes. The processors are connected into a 3D toroidal hypercube and each processor "owns" a set of particles corresponding to a particular cube of space. One of these is to be hosted at the Pittsburgh Supercomputing Center.

The ability to perform long, accurate Molecular Dynamics (MD) simulations involving proteins and other biological macro-molecules could in principle provide answer to some of the most important outstanding questions in the field of biology, chemistry and medicine.