Algorithms, Coding and Java

[eipicode-blog]

EclEmma - Code Coverage Tool that just works

I came across this Code Coverage tool for Java called EclEmma. http://www.eclemma.org

If you use eclipse then I would highly recommend this. Just install it from the marketplace

Then Go to Run->Coverage choose a single test, a package or the whole project (as test suite) and click coverage. 

And, there you go - the results. 

It does a great job of showing you what's covered and what's not!

[eipicode-blog]

Memory Usage of Java Data Types and References

Primitive Data Types

byte - 1 Byte

short, char - 2 Bytes

int, float - 4 Bytes

double,long - 8 Bytes

Overheads

To calculate the memory usage you will also find the following information useful. 

Overhead for Single Dimension Array - 24 bytes

Object Overhead - 16 bytes

Object Reference Overhead - 8 bytes

Padding - Each object uses memory which is a multiple of 8 bytes. So pad up the calculated size of your object. 

For the type boolean the specification is platform dependent - empirical evidence suggests its close to 1 Byte(what a colossal waste!)

Reference:

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

[eipicode-blog]

Sequence Generator

This is really a toy example with the use of the synchronized keyword. 

The Sequence Generator is supposed to maintain a counter and return its value and increment it by 1 every time the getNext method is called.

One might use the ++ operator and carelessly fail to put the synchronized keyword for the method. The problem is that the ++ operator is not atomic so the following scenario is possible. 

Thread A  Read Counter as 10   Increment counter to 11   Update counter as 11  

Thread B        Read Counter as 10              Increment counter to 11          Update counter as 11

So, in the end we see that the counter has been incremented only once after two calls to getNext, and of course both the calls have returned the same value. 

This problem is easily fixed by including the synchronized keyword in the method. 

This example also demonstrates how to run a crude test for concurrency. If you leave out the synchronized keyword and run it the final counter value may not be what is expected. But the test is not guaranteed to detect problems. 

https://github.com/eipione/java-algos/blob/master/src/main/java/com/ephipi/threads/demo/SequenceGen.java

[eipicode-blog]

Implement a Queue with two Stacks

Here we need to use two stacks. 

We use the first stack (the mainStack) to push all the elements as they come in.

We use the second stack (the reverseStack) to empty out all elements of the mainStack when we are called upon to dequeue an element. 

So, the operations are implemented like this

Enqueue: Push the element in the mainStack. 

Dequeue: Check the reverseStack, if it is not empty pop an element. If it empty then pop out all elements in the mainStack and keep pushing them in the reverseStack (thereby reversing the order). Then pop an element from the reverseStack. 

Source Code

[eipicode-blog]

Implementing a Queue

Here we need to keep track of two nodes - the first and the last. 

Enqueue : Allocate a new node, and point the next of the last node to the new node. Make new node as the last. 

Dequeue: Return the data from the first element and make the next of the first element as the new first. 

Source Code

[eipicode-blog]

Implementing a Stack

A Stack just needs to a keep a pointer to the top of the stack.

For a push operation - allocate a new Node, point it's next to the existing top and, make this new node the top. 

For the pop operation - just return the data from the top node and make top's next the new top. 

Source Code

[eipicode-blog]

Java Profiling

A nice tool for getting started on Java profiling is jvisualvm which ships with the standard SDK. 

Through this you can monitor processes running on the local machine very easily and remote processes with some more configuration. 

It can be launched from the command line with the command 'jvisualvm' 

This is what you will see when you launch, choose the process you want to probe. 

Let's say we choose the ExplodeExtractConvert Process. 

The "Overview" tab tells you basic details about the process including the JVM parameters and System properties which are good as a quick reference and (sometimes) sanity checks. 

The "Monitor" tab can help you identify bottlenecks e.g.

CPU usage is constantly very high

Memory constantly climbing and not being released after GC to come to a base level

Number of threads constantly growing or not being idle even when the application is at rest (like in a web server with no load)

Look at the live threads. Here I have just the main thread as the relevant one. On web server processes you will see a number of threads and looking at their behavior can tell you whether you need to increase/decrease the number. 

It is instructive to filter the methods by your methods in your custom code and look at the methods that take up the most CPU. You may see a methods taking up a lot of time which you did not expect. Fix it :)

Memory Profiling. Again, filtering by custom classes can sometimes be useful. Its normal to have lots of primitives and strings here. If you are looking for a memory leak here - you usually find a clue for it in the first few classes which are not strings or primitives 

Here's the sampler output for memory. 

[eipicode-blog]

Blocking Thread Pool Executor

The Java Executor Framework gives a number of choices for thread pool executors where you can control the number of threads that are run simultaneously, the queue size, how long idle threads live and so on. 

And it also gives you an option to specify what to do with the jobs that are submitted when the thread pool and the queue are full. By default it throws a RejectedExecutionException. However typically this is not a great way to handle excess load.

One way that is adequate in some situations it to let the caller run the rejected job. This also prevents the caller from submitting more jobs. Look at CallerRunsPolicy. 

However, in this case it is possible that while the caller is running the rejected threads the ThreadPool has available slots again which are not immediately utilized. This is sub-optimal in most situations.

What we need is a mechanism for blocking the job submission itself till slots become available so that the job submission can resume as soon as a slot becomes available. This can be accomplished by using a semaphore with number of permits equal to the number of threads + queue size that you wish to allow. 

The job submission method acquires a permit just before submitting the job and releases it in the finally block of the method execution. 

This ensures that , the process gets blocked when no permits are available. 

One catch with this method is this - we release the permit in the finally block of the thread that is running (ideally we would have wanted this to happen after the thread has been returned to the pool - but there is no clean way of doing that). 

What this means is that, in the worst case we will see our queue size growing to the queue size we intended + number of threads allowed. However they clear up very quickly so I have found this approach to be acceptable in most circumstances. 

Source Code

[eipicode-blog]

Detect Cycles in Linked List

This is a classic problem in Linked Lists. You are given a list which contains a cycle. One way of thinking about a cycle is this - the "last" node instead of pointing to NULL points to some previous element in the list thereby creating a cycle. 

The first task is to detect whether there is  a cycle. Class problems often have classic solutions. As does this one - the "Floyd's cycle-finding algorithm". 

You take a hare and a tortoise and the hare moves along twice as fast as the tortoise. So, for every one node move by the tortoise the hare jumps two. If either of them reach a NULL node there is no cycle, and if they meet then we have detected a cycle. 

So far so good, but now we have to find the start of the loop. Here is how we set up the problem. 

Node Position of the start the Loop = K (i.e. if you move K nodes from the head you will be at the start of the loop)

Size of the Loop = M (i.e. if you move M nodes from the start of the loop then we come back at the start of the loop)

Number of iterations when the hare and tortoise meet = I (i.e. the tortoise has moved I steps and the hare has moved 2I steps)

Tortoise's position from the loop start = (I - K) mod M

Hare's position from the loop start = (2I - K) mod M

Since they have met, we have 

(2I - K) mod M = (I-K) mod M

Now, simplifying this using simple modulo arithmetic we have 

[(2I -K) - (I-K) ] mod M = 0

this gives us,

I Mod M = 0 ( this makes intuitive sense, since the additional steps taken by the hare are a multiple of M i.e. the extra distance travelled by the hare is just a multiple of the size of the loop - so the hare and the tortoise are obviously at the same point)

Now let's change the rules of the hare and tortoise game.

We know that the tortoise it at the position (I-K) mod M. So, if it takes K more steps it will be at the position (I-K+K) mod M which is I mod M (this we know is 0 i.e. the loop start)

So now we send back the hare to the start of the loop and slow it down to one step per iteration and let the tortoise continue one step per iteration. 

In exactly K iterations the hare and tortoise will meet again, at the start of the loop. 

When they meet we have the Node that is the start of the loop. 

Source Code

You can read more about this on Wikipedia 

[eipicode-blog]

Linked List Kth to Last Element

Find the Kth to last element of a given LinkedList

Use two pointers. 

Advance the first pointer by K -1 steps.

If the list is exhausted before K -1 steps then return there is  no Kth to last element. 

Otherwise start the second pointer,and keep moving both the pointers. When the first pointer reaches the last element, then the second pointer points to the Kth to last element.

Source Code

[eipicode-blog]

Test for String Rotations

Given two Strings s1 and s2 test to see if one is a rotation of the other without using any additional space. 

The key idea is to iterate over s1 and look for matches of s2, but match characters in s2 with characters of s1 modulo s1.length. 

Source Code

[eipicode-blog]

Reverse a Linked List

I have come across this question often - reverse a link list in place and in one pass. 

The code is pretty crisp but is take a while to get your head around - especially if its been a while since you last looked at linked lists. 

Source Code

The key intuition is that you keep track of two pointers - one pointing to the head of the list you have already reversed and one pointing to the head of the remaining unreversed list. 

So to start, the head of the unreversed list is the head of the reversed list you are given

and, 

the head of the reversed list is NULL 

Then, as you traverse the list -

1.  Store the pointer to the next element in the unreversed list, call it "current"

2. Point the head of the unreversed list to the head of the reversed list. 

3. Make the previous head of the unreversed list as the new head of the reversed list. 

4. Make "current" stored in step 1 as the new head of the unreversed list. 

Do this till the head of the unreversed list becomes NULL. 

In the end,

Return the head of the reversed list.