[Ubuntu] Multiple launchers for each individual Eclipse installation

I have multiple Eclipse versions installed in my Ubuntu 12.04, so I wanted to have separate launcher icons in Launchpad. However I noticed it is not possible to create launch icons simply using:
"Right click -> Lock to Launcher" approach since the same launcher icon is used for all Eclipse installations; simply said there will be only one launcher icon for all Eclipse installations. 

It is quite easy to create multiple launcher icons for multiple installations. Below is the 4 steps you need to follow.

1. Create <eclipse-name>.desktop files for each installation

I created eclipse-jee-kepler.desktop file inside Kepler Eclipse installation folders, but you use any preferred location.

2. Update <eclipse-name>.desktop file with information

For "Eclipse JEE Kepler" installation, add the below content to eclipse-jee-kepler.desktop. You will have to change the path to the executable eclipse file.

[Desktop Entry]
Version=4.3.1
Name=Eclipse JEE Kepler
Comment=Eclipse JEE Kepler
Exec=/<path>/eclipse-jee-kepler-SR1-linux-gtk/eclipse
Icon=/<path>/eclipse-jee-kepler-SR1-linux-gtk/eclipse.ico
StartupNotify=false
Terminal=false
Type=Application
Categories=Development

You can create an eclipse.ico file to be displayed in the Launchpad yourself. As displayed here, I have created a simple file for my usage.

3. Grant permission to execute

Right click on this eclipse-jee-kepler.desktop file and select "Properties". Then go to the "Permissions" tab and select execute permission as shown in the image.

4. Run the eclipse installation

You can double click on the eclipse-jee-kepler.desktop file to start your eclipse installation. When this eclipse installation is started, the provided eclipse.ico will be displayed in the Launchpad. Now you can create a launch icon simply using "Right click -> Lock to Launcher".

Finally...

For each of your eclipse installations, you can create separate files with above 4 steps; then replace the property values to match with each eclipse installations (including a separate .ico).

If you are interested in finding more information about Unity Launchers and Desktop files, you can refer here.

[Java] String format against opening & closing characters

How to validate the format of a given string according to a given set of opening-closing character pairs? This has been raised as an interview question, so I thought of writing a simple program to solve this.

Let me elaborate the question. There are characters that are considered as opening characters and closing characters; when '(' is an opening character, the relevant closing character is ')' For example; ([]) is correctly formatted, but ([) is not. So your task is to find out whether all the starting characters are properly ended with a ending character.

Here, I am using a Stack (java.util.Stack) to solve the problem.

GroupingPair class

A simple class named GroupingPair is written to hold pair of opening and closing characters. For instance, '[' for starting and ']' for ending.

package com.digizol.interviews.string.format;

public class GroupingPair {

    private Character start;
    private Character end;

    public GroupingPair(Character start, Character end) {
        this.start = start;
        this.end = end;
    }

    public Character getStart() {
        return start;
    }

    public Character getEnd() {
        return end;
    }
}

FormatValidator class

This class has implemented the logic using a stack. This can be initialized with a list of GroupingPair objects. Then a given strings each character is compared against the GroupingPair objects to find out whether there is an opening or closing characters. If an opening character is found, related GroupingPair instance is pushed to the stack. Similarly, if a closing tag is found, the top GroupingPair is popped and compared with the character to see whether it matches with the expected.

package com.digizol.interviews.string.format;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class FormatValidator {

    private Map<Character, GroupingPair> openingChars;
    private Map<Character, GroupingPair> closingChars;

    public FormatValidator(GroupingPair[] pairs) {
        initOpeningCharacters(pairs);
        initClosingCharacters(pairs);
    }

    private void initClosingCharacters(GroupingPair[] pairs) {
        closingChars = new HashMap<Character, GroupingPair>();
        for (GroupingPair pair: pairs) {
            closingChars.put(pair.getEnd(), pair);
        }
    }

    private void initOpeningCharacters(GroupingPair[] pairs) {
        openingChars = new HashMap<Character, GroupingPair>();
        for (GroupingPair pair: pairs) {
            openingChars.put(pair.getStart(), pair);
        }
    }

    public boolean validate(String string) {
        return validate(string, false);
    }
    
    public boolean validate(String string, boolean validateOtherCharacters) {

        Stack<GroupingPair> stack = new Stack<GroupingPair>();

        char[] characterArray = string.toCharArray();

        for (Character c: characterArray) {

            if (openingChars.containsKey(c)) {
                stack.push(openingChars.get(c));
            } else if (closingChars.containsKey(c)) {
                if (!c.equals(stack.pop().getEnd())) {
                    return false;
                }
            } else if (validateOtherCharacters) {
                System.out.println("Unexpected character '" + c + "' found in string: " + string);
                return false;
            }
        }
        return stack.isEmpty();
    }
}

Test class

This is a simple class with the main method to test few examples. Character pairs (), '<'>' and [] are given for initialization.

package com.digizol.interviews.string.format;

public class Test {

    public static void main(String[] args) {

        FormatValidator validator = new FormatValidator(createPairs());

        String[] toTest = { "[(])", 
                            "([<>])", 
                            "([)", 
                            "()[]<>", 
                            "(()[]<>)",
                            "(mal [ formatted )",
                            "(this [ is < well > formatted ] text)"
                            };

        for (String string : toTest) {

            boolean valid = validator.validate(string, false);

            if (valid) {
                System.out.println(string + " \t-> well formatted");
            } else {
                System.out.println(string + " \t-> malformed");
            }
        }
    }

    private static GroupingPair[] createPairs() {
        GroupingPair[] pairs = new GroupingPair[] {
                                new GroupingPair('(', ')'), 
                                new GroupingPair('<', '>'), 
                                new GroupingPair('[', ']') 
        };
        return pairs;
    }
}

Following is the output you will get when this Test class is executed.

[(]) -> malformed
([<>]) -> well formatted
([) -> malformed
()[]<> -> well formatted
(()[]<>) -> well formatted
(mal [ formatted ) -> malformed
(this [ is < well > formatted ] text) -> well formatted

As you can see, the program has identified whether a string is well formatted or not. This eclipse project is available for download.

[Jenkins] Automatically retry a failed build

Are your Jenkins builds failing due to unavoidable reasons like unavailability of external databases, file systems etc? The only solution you might be having right now is to reschedule the build after fixing that external issue. In this post, I will be discussing on how you can automatically rerun a failed build.

Setup

For this, we are going to use a plugin named Naginator, version 1.8 is available here for download. As the first step, please install this plugin into your Jenkins.

When it is installed, there will be a new action named "Retry build after failure" added to the post-build action list in job configuration page (as shown).

Configuration

First create a new job. If you need to retry an existing job, please open the job configuration page. Then click on the "Add post-build action" button and select "Retry build after failure". This will add a new configuration section as shown in the below image.

There are 3 configuration settings (as numbered in above image). Let's discuss each in details below.

Setting 1 -> Rerun build for unstable builds as well as failures

This option is there to indicate whether you should be retrying the UNSTABLE state builds as well in addition to FAILURE state builds. Let's set it to true.

Setting 2 -> Delay before schedule

This allows you to define how long to delay a retrying build start-time from the time it was failed. There are two options to choose from; one is to provide a "fixed period" and the other is to provide an "increasing period". Let's use fixed period; and set 300 there (meaning 5 mins).

Setting 3 -> Max number of successive failed build

This is used to control the number of continuous failure builds. Jenkins will not automatically retry more than this maximum number of consecutive failures. So let's set 2 there so that it is retried only two times.

Conclusion

As expected, this is working without any issues and stops retrying as soon as the build is successful. Hope this will help you in avoiding manual retries.

[Log4j] How to integrate with your Java project

This is a quick guide on how to use log4j in your Java project. This task requires only five simple steps listed below. Each of these step is explained in details below.

1. Set up the project with log4j
2. Create log4j.properties file
3. Write a class to record log messages
4. Compile and run program
5. Check the log messages

1. Set up the project with log4j

As the first step, let's download the log4j 1.2.17 latest archive (tar or zip). When you extract the archive, log4j-1.2.17.jar file is available in the root of the directory.

Let's create a new project named say log4j-helloworld and copy the log4j-1.2.17.jar into a folder named lib inside the project.

2. Create log4j.properties file

Next task is to create a log4j.properties file (shown below) inside the project folder. This file is the configuration file that provides how, where, which etc instructions on generating log messages.

# root level configurations
log4j.rootLogger=INFO,console,file

# configuration for console outputs
log4j.appender.console=org.apache.log4j.ConsoleAppender
log4j.appender.console.layout=org.apache.log4j.PatternLayout

# configuration for file output (into a file named messages.log)
log4j.appender.file=org.apache.log4j.RollingFileAppender
log4j.appender.file.File=messages.log
log4j.appender.file.layout=org.apache.log4j.PatternLayout

# threshold for file output
log4j.appender.file.Threshold=ERROR

3. Write a class to record log messages

Let's write a simple class named Main (in src folder) with a main method to generate some log statements. Logger is added to the class as an attribute and used to write logs of different levels like debug, info and error.

package com.digizol.log4j.helloworld;

import org.apache.log4j.Level;
import org.apache.log4j.Logger;

public class Main {

    private static Logger log = Logger.getLogger(Main.class);

    public static void main(String[] args) {

        log.debug("This is debug method");
        log.info("This is info method");
        log.error("This is error method");

        log.log(Level.DEBUG, "This is debug from Level.DEBUG");
        log.log(Level.INFO, "This is info from Level.INFO");
        log.log(Level.ERROR, "This is error from Level.ERROR");

    }
}

4. Compile and run program

If you compile and run from command line, followings are the commands. Make sure to create classes folder inside project for generated class files before executing the commands.

# compile
javac -cp lib/log4j-1.2.17.jar -d classes -sourcepath src src/com/digizol/log4j/helloworld/Main.java

# run
java -cp lib/log4j-1.2.17.jar:./classes:./ com.digizol.log4j.helloworld.Main

If you are using an IDE like Eclipse, you can simply add log4j jar file into the build path before compiling. When running the Main class, you need to give the path to log4j.properties file in run configuration.

5. Check the log messages

In the Main class, we have added two debug level messages. However the rootLogger is configured in INFO level in log4j.properties file, so none of the debug level log messages are expected as outputs.

Console output as as below.

This is info method
This is error method
This is info from Level.INFO
This is error from Level.ERROR

Console has received both INFO and ERROR log messages, but not DEBUG.

However messages.log file has received only the ERROR level log messages as below.

This is error method
This is error from Level.ERROR

This is because the Threshold level of the file logging appender is set to ERROR which overrides the rootLogger configuration.

Hope this helps you to start using log4j in your next project. I have added this project here for your references.

Find which process holds a port number in Linux

Here is a simple tip to find out the process that has bounded a given port number. java.net.BindException: Address already in use - this is an error log message that software developers and deployment engineers encounter quite often since the same application or process is already running in the background occupying the port. Below we will locate a process based on the port.

1. Finding the process that holds the port

lsof -i <Internet address>

Let's find the process using the port "8080"

$ lsof -i :8080
COMMAND   PID  USER   FD   TYPE DEVICE SIZE/OFF NODE NAME
java        14124   kamal   35u   IPv4  18493      0t0    TCP   *:http-alt (LISTEN)

If needed, we can extract just the PID by leaving out all other information as shown below.

$ lsof -i :8080 -t
14124

PID above is the process id that uses the port 8080.

Using this PID, you can view the process details using following command.

ps u -p <PID>

Let's find the process details of PID 14124

$ ps u -p 14124
USER  PID  %CPU %MEM    VSZ   RSS  TTY  STAT START TIME COMMAND
kamal 14124  6.6   7.2   2399340  588220 pts/0  Sl+   10:39   1:01  /usr/lib/jvm/java-6-sun/bin/java

2. Terminating the process using the process id

A process can be terminated using the kill command.

kill -9 <PID>

Let's kill the above process as follows.

$ kill -9 14124

Hope this helps, also make sure you read details of "lsof" command for further details.

[Ubuntu] DeVeDe generated DVD menus not working

DeVeDe is a popular software for DVD creation, and I am using 3.21.0 version of that on Ubuntu 12.04 to generate DVDs from different files of .avi, .mpg and .mp4 types. However after the upgrade to Ubuntu 12.04, I was facing issues with the menus of generated DVD. Recently, I noticed that this is due to an incompatibility issue with ffmpeg solution provided by Ubuntu (detailed bug is found here).

Simplest workaround for this issue is to avoid the use of ffmpeg, and interestingly DeVeDe provides an option to do this.

Go to "Edit -> Preferences"

then uncheck "Use FFMPEG instead of Mencoder" as shown in the below image.

That setting will resolve this problem.

[Ubuntu] Troubleshoot USB Pen drives with powerful tools

My USB pen drive was not shown in Ubuntu 12.04 suddenly, so I tried it with Windows, but the result was same. That isolated the issue to the pen drive itself than the operating system. With Ubuntu, I used a lot of powerful tools to resolve this issue, and I am recording those below hoping that will help someone. However please note that there is no guarantee that these tools and instructions are going to resolve the issues you might face with your pen drives.

Steps I followed were:

1. Check whether your USB device is detected using "lsusb" command
2. Finding where the device is located (using fdisk)
3. Guess PC-type hard disk partitions using gpart
4. Manipulate partitions using gparted (Gnome partition editor)
5. Scan and repair disk partitions (using testdisk)
6. Finding bad blocks using badblocks
7. Copy zeros to starting locations (using dd)

Followings are the details those steps with the commands and the output of each.

1. Check whether your USB device is detected using "lsusb" command

lsusb is a command used to list all USB devices found in a system

$ lsusb
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
...
Bus 002 Device 008: ID 0930:6544 Toshiba Corp. Kingston DataTraveler 2.0 Stick (2GB)
...

Above command lists the connected USB devices, and my Kingston DataTraveler 2.0 Stick is also shown. So it is clear that the USB flash drive is correctly connected.

2. Finding where the device is located (using fdisk)

"fdisk" command can be used to find details about the device.

$ sudo fdisk -l
....
Disk /dev/sdc: 8010 MB, 8010194944 bytes
247 heads, 62 sectors/track, 1021 cylinders, total 15644912 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0xd0e2392f

Disk /dev/sdc doesn't contain a valid partition table

So this device size is correctly identified as 8010MB (8GB) and is located at /dev/sdc. Interestingly, fdisk has reported that this device is not having a valid partition table. So something has happened to the partition table and I wanted to fix it with the help of fdisk command as follows.

$ sudo fdisk /dev/sdc
Device contains neither a valid DOS partition table, nor Sun, SGI or OSF disklabel
Building a new DOS disklabel with disk identifier 0x4c9b7827.
Changes will remain in memory only, until you decide to write them.
After that, of course, the previous content won't be recoverable.

Warning: invalid flag 0x0000 of partition table 4 will be corrected by w(rite)

Command (m for help): w
The partition table has been altered!

Calling ioctl() to re-read partition table.

Error closing file

As shown above, fdisk has tried to alter the partition table, but failed. So I tried to add a partition as below, which again failed with the same error message.

# sudo fdisk /dev/sdc
...

Warning: invalid flag 0x0000 of partition table 4 will be corrected by w(rite)

Command (m for help): n
Partition type:
    primary (0 primary, 0 extended, 4 free)
    extended
Select (default p): p
Partition number (1-4, default 1): 1
First sector (2048-15644911, default 2048):
Using default value 2048
Last sector, +sectors or +size{K,M,G} (2048-15644911, default 15644911):
Using default value 15644911

Command (m for help): w
The partition table has been altered!

Calling ioctl() to re-read partition table.

Error closing file

So it seemed fdisk can not help further in resolving this issue.

3. Guess PC-type hard disk partitions using gpart

I used gpart to find details of the existing partitions, and following was the outcome.

$ sudo gpart /dev/sdc

Begin scan...
End scan.

Checking partitions...
Ok.

Guessed primary partition table:
Primary partition(1)
   type: 000(0x00)(unused)
   size: 0mb #s(0) s(0-0)
   chs:  (0/0/0)-(0/0/0)d (0/0/0)-(0/0/0)r

Primary partition(2)
   type: 000(0x00)(unused)
   size: 0mb #s(0) s(0-0)
   chs:  (0/0/0)-(0/0/0)d (0/0/0)-(0/0/0)r

Primary partition(3)
   type: 000(0x00)(unused)
   size: 0mb #s(0) s(0-0)
   chs:  (0/0/0)-(0/0/0)d (0/0/0)-(0/0/0)r

Primary partition(4)
   type: 000(0x00)(unused)
   size: 0mb #s(0) s(0-0)
   chs:  (0/0/0)-(0/0/0)d (0/0/0)-(0/0/0)r

As per the above findings, there is no correct partition in the device.

4. Manipulate partitions using gparted (Gnome partition editor)

I used "gparted" tool to add a partition table. As shown in above image, gparted shows this device at /dev/sdc with Partition=unallocated and FileSystem=unallocated, so it also identified that there was an issue. So I tried adding a partition table [by Device -> Create Partition Table...] of msdos type, but GUI displayed an error message as "Error while creating partition table". Command line also had some issues listed as below.

$ sudo gparted
======================
libparted : 2.3
======================
/dev/sdc: unrecognised disk label
/dev/sdc: unrecognised disk label
Input/output error during write on /dev/sdc
Error fsyncing/closing /dev/sdc: Input/output error
/dev/sdc: unrecognised disk label

So gparted also failed to resolve this for me.

5. Scan and repair disk partitions (using testdisk)

I tried "testdisk" tool to analyze and repair the disk. Following devices were identified by the tool.

$ sudo testdisk
TestDisk 6.13, Data Recovery Utility, November 2011
....
Select a media (use Arrow keys, then press Enter):
 ...
 Disk /dev/sdc - 8010 MB / 7639 MiB - Kingston DT 101 G2

Partition details of this /dev/sdc were shown as below.

Disk /dev/sdc - 8010 MB / 7639 MiB - CHS 1021 247 62
Current partition structure:
     Partition                  Start        End    Size in sectors
   P Unknown                  0   0  1  1021 150 18   15644912

Disk /dev/sdc - 8010 MB / 7639 MiB - CHS 1021 247 62
     Partition                  Start        End    Size in sectors

No partition found or selected for recovery

As per the above, there is no partitions in this disk.

Also I tried to use this tool to create a new MBR record, and the command resulted as below.

Write a new copy of MBR code, confirm ? (Y/N)
TestDisk exited normally.
You have to reboot for the change to take effect.

However even after reconnecting the device, the issue was not resolved.

6. Finding bad blocks using badblocks

Finally I suspected whether the pen drive was having bad blocks, so tried the badblocks utility to check for those as follows.

$ badblocks -vws /dev/sdc
Checking for bad blocks in read-write mode
From block 0 to 7822455
Testing with pattern 0xaa:   0.03% done, 34:50 elapsed. (0/0/0 errors)

However this tool was taking much longer time to run. As shown above only 0.03 was completely in 34.50 minutes, which means around 80 days to complete. Obviously, I was not going to wait that longer to fix the pen drive.

7. Copy zeros to starting locations (using dd)

I tried "dd" tool to write zeros to the device in case there were some inconsistency in the partition table creation space. So 8MB of zeros were written to pen drive successfully.

$ sudo dd if=/dev/zero of=/dev/sdc bs=8M count=1
1+0 records in
1+0 records out
8388608 bytes (8.4 MB) copied, 2734.83 s, 3.1 kB/s

However even after dd was successful, I tried to add a partition table with gparted as explained in step 4 above, but it continued to fail.

Summary

Finally after all these operations, partition table creation was not successful even though I was able to write some data into this pen drive with 'dd' tool. Hence it is not possible to boot and mount inside an operation system. I assumed this was due to a hardware failure of the device.

Hope these details will help someone (including me) when resolving issues with USB pen drives in future.

Thunderbird: Search by Attachment Name

Finding emails which included had a particular attachment is really important. Last week I happened to digg through my email box to find a number of emails that contained a particular document as an attachment. The only information I know about those emails is; those contained this particular attachment. So how can I find the email?

It is quite simple; since the filename is already known, search box on top right-hand side can be used. As shown in the below image, you need to type the filename inside inverted comma.

In this example, I am searching for a file named "Digizol.com Thunderbird Article.doc".

To summarize, three simple steps are;
1. Press 'Ctrl + k'
2. Type filename inside inverted commas
3. Press Enter

Hope this helps.

Minimum difference in two sorted arrays

Given two sorted arrays of same length, find pairs of numbers (one from each array) which has the minimum distance between those two numbers. This is the last weeks Thursday Coding Puzzle. Since both arrays are sorted, binary search is going be really useful in searching the values in arrays.
Even though this problem is not related to finding the exact matches as in binary search, it is easy to solve this problem with the same approach used in binary search. As a preparation for this puzzle, it is really useful if you can try and write binary search yourself without referring to internet for help.

This problem can be simplified into two steps and implemented incrementally. Initially, we can simplify this problem to use only one array out of the two; then use one value from the other array rather than the second array itself. Then enhance that solution to use all values in second array against the first array to complete the answer for the problem.

One Array against One Value problem

In this problem, it is required to find a value within the array such that it is the closest to the given value. There can be one of multiple values that are the closest to a given value; so that has to be supported.

Test Cases

As usual, test cases are written first before writing any production code. Followings are the four test cases.

1. shouldReturnEmptyForAnEmptyArray
     > If the array is empty, result has to be empty

2. shouldReturnSameValueIfFoundAnywhereInGivenArray
     > If the given array contains the given value, the distance is zero (0). So it has to be returned from the array other than any value.
     e.g.: For an array with 1, 4, 7, 11 against value 4, then number pair has to be (4,4)

3. shouldReturnCorrectIfOneClosestValueIsAnywhereInGivenArray
     > If the given array contains one closest value, then that is the minimum distance. So it has to be returned with the given value.
     e.g.: For an array with 1, 4, 7, 11 against value 5, then minimum distance is 1 for the number pair (4,5) which has to be returned.

4. shouldReturnCorrectIfMultipleValuesAreTheClosest
     > If the given array contains multiple values closest to the given value, then those has to be returned with the given value.
     e.g.: For an array with 1, 4, 8, 11 against value 6, then minimum distance is 2 for the number pairs (4,6) and (6,8) which has to be returned.

Above test cases are implemented in the following manner with JUnit4.

package com.digizol.puzzle;

import static org.junit.Assert.assertEquals;
import java.util.*;
import org.junit.Test;

public class MinimumDifferencesTest {

    private MinimumDifferences sut;

    public MinimumDifferencesTest() {
        sut = new MinimumDifferences();
    }

    @Test
    public void shouldReturnEmptyForAnEmptyArray() {
        assertEquals(0, sut.getMinPair(new int[] {}, 1).length);
    }

    @Test
    public void shouldReturnSameValueIfFoundAnywhereInGivenArray() {
        int[] sorted = { 1, 4, 7, 11, 15, 19, 26, 30, 33, 40 };
        for (int i = 0; i < sorted.length; i++) {
            int[] result = sut.getMinPair(sorted, sorted[i]);
            assertEquals(1, result.length);
            assertEquals(sorted[i], result[0]);
        }
    }
    
    @Test
    public void shouldReturnCorrectIfOneClosestValueIsAnywhereInGivenArray() {
        int[] sorted = { 1, 4, 7, 11, 15, 19, 26, 30, 33, 40 };
        int[] result = sut.getMinPair(sorted, sorted[0] - 1);
        assertEquals(1, result.length);
        assertEquals(sorted[0], result[0]);

        for (int i = 0; i < sorted.length; i++) {
            result = sut.getMinPair(sorted, sorted[i] + 1);
            assertEquals(1, result.length);
            assertEquals(sorted[i], result[0]);
        }
    }

    @Test
    public void shouldReturnCorrectIfMultipleValuesAreTheClosest() {
        int[] sorted = { 1, 4, 7, 11, 15, 19, 26, 30, 33, 40 };
        int[] result = sut.getMinPair(sorted, 28);
        assertEquals(2, result.length);
        List<Integer> expected = new ArrayList<Integer>();
        expected.add(26);
        expected.add(30);

        for (int i = 0; i < result.length; i++) {
            expected.remove(Integer.valueOf(result[i]));
        }
        assertEquals(0, expected.size());
    }
}

Production Code

By simply tweaking the binary search code, it is really easy to implement this expected functionality. You can compare the below implementation code with the binary search code; specially look at the three comments shown in both .

package com.digizol.puzzle;

public class MinimumDifferences {

    public int[] getMinPair(int[] sorted, int value) {
        if (sorted.length == 0) {
            return new int[] {};
        }
        return getMinPair(sorted, value, 0, sorted.length - 1, new int[]{});
    }

    private int[] getMinPair(int[] sorted, int value, 
                             int leftIndex, int rightIndex, int[] minValues) {

        // 1. index check
        if (leftIndex > rightIndex) {
            return minValues;
        }

        // 2. middle index
        int middleIndex = (leftIndex + rightIndex) / 2;

        if (minValues.length == 0) {
            minValues = new int[] { sorted[middleIndex] };
        } else {
            int oldDiff = diff(value, minValues[0]);
            int newDiff = diff(value, sorted[middleIndex]);
            
            if (newDiff < oldDiff) {
                minValues = new int[] { sorted[middleIndex] };
            } else if (newDiff == oldDiff)  {
                int[] temp = minValues;
                minValues = new int[temp.length + 1];
                for (int i = 0; i < temp.length; i++) {
                    minValues[i] = temp[i];
                }
                minValues[minValues.length - 1] = sorted[middleIndex];
            }
        }

        // 3. recursive invoke
        if (sorted[middleIndex] > value) {
            return getMinPair(sorted, value, leftIndex, middleIndex - 1, minValues);
        } else if (sorted[middleIndex] < value) {
            return getMinPair(sorted, value, middleIndex + 1, rightIndex, minValues);
        } else {
            return minValues;
        }
    }

    private int diff(int value, int currentValue) {
        
        int diff = currentValue - value;
        if (diff < 0) {
            diff = -diff;
        }
        return diff;
    }
}

Two Arrays Problem

Now we have got the minimum distance number pairs against a given value. Now the enhancement is quite simple, just need to invoke the above "getMinPair(int[] sorted, int value)" method with each value in the second array of the problem and find the smallest minimum of those.

Test Cases

Following is one of the test cases to check this two array based implementation.

    @Test
    public void shouldReturnMultiplePairsIfFoundInGivenArrays() {
        int[] first = { 1, 10, 20, 30, 40};
        int[] second = { 6, 14, 25, 35, 45};
        int[][] result = sut.getMinPair(first, second);
        assertEquals(2, result.length);
        
        for (int i = 0; i < result.length; i++) {
            if (result[i][0] == 6) {
                assertEquals(10, result[i][1]);
            } else if (result[i][0] == 10) {
                 if (result[i][1] != 6 && result[i][1] != 14) {
                     assert false;
                 }
            } else if (result[i][0] == 14) {
                assertEquals(10, result[i][1]);
            }
        }
    }

You can insert the following method into the above implemented MinimumDifferences class to complete the implementation for the puzzle.

    public int[][] getMinPair(int[] first, int[] second) {
        int[][] pairs = new int[0][];
        
        int diff = Integer.MAX_VALUE;
         
        for (int i = 0; i < second.length; i++) {

            // invoke modified binary search method
            int[] mins = getMinPair(first, second[i]);
            
            if (mins.length != 0) {
                int localDiff = mins[0] - second[i];
                if (localDiff < 0) {
                    localDiff = -localDiff;
                }
                if (diff > localDiff) {
                    diff = localDiff;
                    pairs = new int[mins.length][2];
                    for (int j = 0; j < mins.length; j++) {
                        int[] value = new int[]{mins[j], second[i]};
                        pairs[j] = value;
                    }
                } else if (diff == localDiff) {
                    int[][] temp = pairs;
                    pairs = new int[temp.length + mins.length][2];
                    for (int j = 0; j < temp.length; j++) {
                        pairs[j] = temp[j];
                    }
                    for (int j = 0; j < mins.length; j++) {
                        int[] value = new int[]{mins[j], second[i]};
                        pairs[j + temp.length] = value;
                    }
                }
            }
        }
        return pairs;
    }

Hope this helps you to understand how binary search can be modified to solve two sorted arrays based problem.

Related Articles

• Java: Binary Search (recursive) & TestCases
• Java Sorting: Comparator vs Comparable Tutorial

Java: Binary Search (recursive) & TestCases

Test cases for Binary search might not be something you have already written, but the implementation must be an old exercise you may have done in your algorithm lessons. May be it is easy for you to write it yourself without referring to examples or helping materials? I think it's time for you to try it yourself if you have not done it for a long time.

Since I wanted to solve a puzzle with binary search, I decided to write binary search myself. If you can not remember what the binary search is; a given value must be searched in a sorted array with the aim of minimizing the number of operations by limiting the search into the left or right half of the array by dividing it into two parts.

Test Cases

Test cases for this is not that specific to binary search, but mostly for any search. However as this search is executed in half by half approach, I wrote a number of test cases to search for the values in first, last, middle indexes followed by an all index search. Also since the array division is changing based on whether array length is odd or even, two test cases are added for that.

Here are the names of the test cases.

1. shouldReturnFalseIfArrayIsEmpty()
2. shouldReturnFalseIfNotFoundInSortedOddArray()
3. shouldReturnFalseIfNotFoundInSortedEvenArray()
4. shouldReturnTrueIfFoundAsFirstInSortedArray()
5. shouldReturnTrueIfFoundAtEndInSortedArray()
6. shouldReturnTrueIfFoundInMiddleInSortedArray()
7. shouldReturnTrueIfFoundAnywhereInSortedArray()
8. shouldReturnFalseIfNotFoundInSortedArray()

Above names are a bit self-explanatory, please see the following code for details.

package com.digizol.algorithms;

import static org.junit.Assert.*;
import org.junit.*;

public class BinarySearchTest {

    private BinarySearch sut;

    @Before
    public void setUp() throws Exception {
        sut = new BinarySearch();
    }

    @Test
    public void shouldReturnFalseIfArrayIsEmpty() {
        assertEquals(false, sut.find(new int[] {}, 1));
    }

    @Test
    public void shouldReturnFalseIfNotFoundInSortedOddArray() {
        assertEquals(false, 
                sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 9));
    }

    @Test
    public void shouldReturnFalseIfNotFoundInSortedEvenArray() {
        assertEquals(false,
                sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 }, 9));
    }

    @Test
    public void shouldReturnTrueIfFoundAsFirstInSortedArray() {
        assertEquals(true,
                sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 0));
    }

    @Test
    public void shouldReturnTrueIfFoundAtEndInSortedArray() {
        assertEquals(true,
                sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 16));
    }

    @Test
    public void shouldReturnTrueIfFoundInMiddleInSortedArray() {
        assertEquals(true,
                sut.find(new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 }, 8));
    }

    // covers the 'true' cases above
    @Test
    public void shouldReturnTrueIfFoundAnywhereInSortedArray() {
        int[] sorted = new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 };

        for (int i = 0; i < sorted.length; i++) {
            assertEquals(true, sut.find(sorted, sorted[i]));
        }
    }

    // covers the 'false' cases above
    @Test
    public void shouldReturnFalseIfNotFoundInSortedArray() {
        int[] sorted = new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16 };

        assertEquals(false, sut.find(sorted, sorted[0] - 1));    
        for (int i = 0; i < sorted.length; i++) {
            assertEquals(false, sut.find(sorted, sorted[i] + 1));
        }        
    }
}

Production Code

I want to stress the importance of you trying yourself to complete the code yourself rather than directly going to the code below.

I wrote below recursion based production code which passes against above test cases. There are three comments in the code, which helps you to remember the logic easily.

package com.digizol.algorithms;

public class BinarySearch {

    public boolean find(int[] sortedValues, int value) {
        return search(sortedValues, value, 0, sortedValues.length - 1);
    }

    private boolean search(int[] sorted, int value, int leftIndex, int rightIndex) {

        // 1. index check
        if (leftIndex > rightIndex) {
            return false;
        }

        // 2. middle index
        int middle = (rightIndex + leftIndex) / 2;

        // 3. recursive invoke
        if (sorted[middle] > value) {
            return search(sorted, value, leftIndex, middle - 1);
        } else if (sorted[middle] < value) {
            return search(sorted, value, middle + 1, rightIndex);
        } else {
            return true;
        }
    }

}

If you reached here after writing the program yourself, you deserve a round of applause. Congratulation!!!

Related Articles

• Java Sorting: Comparator vs Comparable Tutorial
• Minimum difference in two sorted arrays

Google Calendar: Add Country Holidays

Google Calendar with holidays of your country; is this something you are not quite familiar? Does colleagues from other countries schedule meetings on holidays of your country? If it is, no one else is there to blame (other than you); they are not aware of those holidays unless otherwise you notify them. The simplest way is to mark those days as holidays in your calendar, but it is not practical to add all of those manually. 

Importing Holiday Calendars

You are not required to add each of those manually. With few clicks, you can import the holiday calendars of your country into your Calendar. Out of the box, Google supports a number of country holiday calendars; 41 countries as of today, hopefully it will grow further.



You must open your Google calendar from a browser, and click on the
'Other calendars' - > 'Browse Interesting Calendars' on left panel as shown above.

This shows a page with holidays of each country, and you can subscribe to any number of those as per your interest. After you subscribe, those will be shown in your calendar. If you are working with colleagues in multiple countries, I suggest you to subscribe to their country calendars so that you will no longer be scheduling meetings on their holidays as well.

My County is not there in Holiday Calendars

If your country is not found in holiday calendars, we need to use an alternative approach. As you can see from the above screen, there is another item named 'Import Calendar'. When you click on that, Google Calendar allows you to upload iCalender or CSV file which has events. You will have to search the internet and find such an event file with holidays and upload.

2013 Sri Lankan Holiday Calendar

You can find the 2013 - Sri Lankan holiday Calendar here, click on the 'Download' link on top of that page and save the calendar2013sl.ics.txt file on to your disk, then import using the above popup window. It will add 26 events into your calendar, and following is how you will see the holidays.

As Google Calendar has become the defacto standard of meeting schedules in many organizations, my belief is that it is the right time for you to spend 2-3 minutes to import holiday calendars into yours (if you have not done it yet). The advantage is obvious, meeting organizers always notice if you are not available.