Given two sorted arrays, develop logic to merge them into a third sorted array. Ideally, with O(n) complexity.

There are two ways to attack this problem.

The first-cut solution, which comes almost instantaneously to our minds, is

    1. append the two arrays [ O(n) ]
    2. sort the resulting array [ O(nlogn) ]

The complexity for this solution will be O(nlogn). Not so impressive, given the fact that we already have two re-sorted arrays.

The second approach uses the following logic:

1. First array is denoted by a1. a1[i] denotes an element in a1[i]
   Second array is denoted by a2. a2[j] denotes an element in a2[j]
2. create a new array with length = len(a1) + len(a2). Let us call this array m. An element in m is denoted by m[k].
3. if (a1[i] < a2[j]):
        m[k]=a1[i]
        m[++k]=a2[j]
        i++
   else if (a1[i] > a2[j]):
        m[k]=a2[j]
        m[++k]=a1[i]
        j++
   else :
        m[k]=a1[i]
        m[++k]=a2[j]
        i++
        j++
4. if (i==len(a1)):
        append elements j to len(a2)-1 of a2 to m
   else if (j==len(a2)):
        append elements i to len(a1)-1 of a1 to m
   else :
        goto step 3

Since the two given arrays are iterated over only once in this solution, the complexity is O(n). Where n is the length of the resulting merged array.

Efficiency.

I was writing code for Base64 encoder today. I was able to.
And then it occurred to me – “How about writing a function which can theoritically encode file of any arbitrary size.”

So I proceeded, to read bytes, encode them, write them to a file.
And then came in the second challenge – breaking the BIG base64 string into fixed-width lines (doesn’t sound challenging ? Try it!)
I was successful after burning out some brain cells.

But the joy of flexibility did not last long … read on to know why …

• Target : encode 80 MB binary file.
• My code takes 4.3 seconds (average)
• GNU base64 took only 2.5 seconds
• 

A lag of 1.8 seconds, not as efficient as ‘The Gurus’ …

Note: The programming language I used was Java. Say … how about trying out the same in Python ??

Designing Filters

The other day me and my friends were discussing ways to implement filters. The things we focussed on were :

• Pluggable – The design should enable developers to add or remove filters as plug-ins
• Sequence – The order in which filters are applied should be configurable
• Testing – If adding a new filter, the developer should only be able to write a test case for the new filter and be done with it

Finally we agreed upon what is described best by the following UML ( disclaimer: we are not UML Gods, but use uml just to convey the idea):

• There should be an interface which exposes the filtering function, for example, the Filter interface above exposes the doFilter() function. This function takes a sequence of results as input.
• There may be n implementations of the Filter interface, each providing – ideally – a unique filtering functionality.
• The class which performs filtering (in this case the FilterEnforcer class)
  • should be aware of the Filter interface and not of any implementations of the same.
  • The member variable filters is an Array or List of filters, thereby determining the sequence in which the filters will be applied.
  • The function which applies the these filters to the result-set will simply iterate over the filters and invoke the doFilter() function of each filter.

This design is already a widely used one – and if I am not wrong – I have seen this being implemented somewhere in Tomcat and Spring-Framework codebase.

MEMCACHED telnet syntax reference

Quick and Handy MEMCACHED telnet syntax reference:

http://blog.elijaa.org/index.php?post/2010/05/21/Memcached-telnet-command-summary

UBUNTU: Reset Compiz from command line

I assume that you completly fucked-up gnome while fingering compiz (exactly like I did) .
Open a terminal (ctrl+alt+F1 if you are all-fucked) and type away the following :

$ gconftool-2 --recursive-unset /apps/compiz
$ sudo /etc/init.d/gdm restart

Works like magic !

Ssh without password

1. Run the following command on the client
   • -> ssh-keygen -t dsa
2. File id_dsa and id_dsa.pub will be created inside $HOME/.ssh
3. Copy the id_dsa.pub to the server’s .ssh directory
   • -> ssh-copy-id -i ~/.ssh/id_dsa.pub user@server
4. You can try ssh to the server from the client and no password will be needed
   • -> ssh user@server

Source:  http://linuxwave.blogspot.com/2007/07/ssh-without-password.html

Why do we write any servlet initialization code in init() and not in servlet’s constructor ?

I was asked this question and I found this here when I googled for the same:

The init() method is typically used to perform servlet initialization–creating or loading objects that are used by the servlet in the handling of its requests. Why not use a constructor instead? Well, in JDK 1.0 (for which servlets were originally written), constructors for dynamically loaded Java classes (such as servlets) couldn’t accept arguments. So, in order to provide a new servlet any information about itself and its environment, a server had to call a servlet’s init() method and pass along an object that implements the ServletConfig interface. Also, Java doesn’t allow interfaces to declare constructors. This means that the javax.servlet.Servlet interface cannot declare a constructor that accepts a ServletConfig parameter. It has to declare another method, like init(). It’s still possible, of course, for you to define constructors for your servlets, but in the constructor you don’t have access to the ServletConfig object or the ability to throw a ServletException.

I started digging deep into java code where Servlet classes are loaded and found the code in org.apache.catalina.core.StandardWrapper.loadServlet().
It goes like this:

• A servlet class is loaded
• An instance of the the servlet class is created using default (zero argument) constructor of the class by reflection
• The method init(ServletConfig config) is called on this instance which passes all context related configuration to the servlet
• The method init(ServletConfig config) then calls method init()
• The servlet is now loaded and the instance created !

So if you put in any servlet initialization code in servlet’s default constructor, it should not use ServletConfig and ServletContext objects. This will throw NullpointerException, since ServerConfig information is not initialized the Servlet till this point. However, if you want to perform any initialization which does not refer to ServletContext / ServletConfig, you can safely do so in the default constructor.

Note: Any constructor other than the default constructor is useless as it is never called by the servlet-container.

Write a function to remove the duplicate items in-place

Write a function to remove the duplicate items in-place (return the new size of the array)

Solution:

1. Sort the array, complexity of this step depends on algo used.
2. loop over array till index < len(array)-1
3. check if current element == next element
4. if true, delete next element, else increment index

Complexity:
Complexity = complexity(sort()) + Complexity(remove_duplicates())
= O(N) + Complexity(remove_duplicates())
Hence depending on whether you use Bubble Sort or Merge Sort (?) the
overall complexity is going to be O(N^2) or O(NlogN)

Python Code:

#!/usr/bin/python

# Simple bubble sort for demo, O(N^2)
# You can use a better sorting algo
def sort( arr ):
    L=len(arr)-1
    for i in range(L,0,-1):
        for j in range (0,i):
           if arr[j] > arr[j+1]:
                t = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = t
    return arr
        
# Complexity O(N)
def remove_duplicates( arr ):
    length = len(arr)
    i=0;

    while i < (length-1):
        
        # check if two consequtive 
        # elements are equal ...
        if arr[i] == arr[i+1] :
            #delete next element
            arr.pop(i+1)
            #get new size of array
            length = len(arr)
        else:
            # else move on to next
            # element
            i = i + 1
    return arr

# Execute
a = [1,3,6,1,5,5,0,9,6,8,9,7]
arr = remove_duplicates(sort(a))
print arr

How to multiply a number by 7 most efficiently

This is an easy one.
For machines it is always simpler to do bit-shifting than multiply.

What is bit-shifting one place to left, physically ?
Bit shifting one place right means multiplication by 2.
Example:

0010 << 1 = 0100, ( 2 * 2 = 4 )
0100 << 1 = 1000, ( 4 * 2 = 8 )
0011 << 1 = 0110, ( 3 * 2 = 6 )

Similarly, bit-shifting one place right means diuvision by 2.

Now what if you shit each bit 2 places ? It is simply bitshiting each bit by 1, 2 times – right ? Which is nothing but multiplying by 2 twice!
Hence, bit-shifting a number 2 places left multiplies it by 4.

That’s ok, but how is it related to multiplication by 7 ?
Elementary Watson!
For any given number N,

N*7 = N*( 1 + 2 + 4)
    = N + N*2 + N*4
    = N + N<<1 + N<<2

Where << is the bitwise left shift operator.

Here is example python code:

>>> def multiply_by_seven( n ):
...     return (n<<1) + (n<<2) +n;
... 
>>> multiply_by_seven(2)
14
>>> multiply_by_seven(3)
21
>>> multiply_by_seven(7)
49
>>> 

Similarly you can break multiplication by any number into powers of 2 and perform an efficient multiplication.

NOTE: Akshay just walked past me and said “Well, just multiply by 8 and subtract 1″

How do you efficiently right-shift an array with the least memory usage?

How do you efficiently right-shift an array with the least memory usage?
For example, the original array could be 2 3 4 5 6. after right-shift two positions, it should be 5 6 2 3 4. The function prototype is shift_right (int[] arret, int shiftCount).
OR
Algorithm to right-shift an array M places, where M < length(array)

Solution 1:

Here is the exact solution as given in “Programming Pearls, 2nd Edition” :
“Swap all the numbers M times”
For example: Say you have an array[1,2,3,4] and you have to shift
it right 2 places. The

---   Start    ---
[1,2,3,4]
--- First Pass ---
[1,2,3,4]
 ^ ^
[2,1,3,4]
   ^ ^
[2,3,1,4]
     ^ ^
[2,3,4,1]

--- Second Pass ---
[2,3,4,1]
 ^ ^
[3,2,4,1]
   ^ ^
[3,4,2,1]
     ^ ^
[3,4,1,2]

---   Result   ---
[3,4,1,2]

Complexity:
Not good! Take the worstcase. Say you have an array of length `n` and you have to shift all elements `n-1` places.
The complexity becomes `O(N*(N-1)) ≈ O(N^2)` as `n -> ∞`.
In average case it will be O(mN), where `m` is the number of places to shift.

Solution 2:
Yet another solution.
Step 1: reverse the array by swapping all the elements (single pass, O(N))
Step 2: reverse all the elements from 0 to `M-1`
Step 3: reverse all the elements from `M` to `L-1` (where L is the length of the array)

Array       : [1,2,3,4,5], M=3
First pass  : [5,4,3,2,1] (all elements swapped reversing the array)

Second pass : [3,4,5,2,1] (reverse array from 0 to 3-1=2)
               ^ ^ ^
Third Pass  : [3,4,5,1,2] (reverse elements 3 to 5)
                     ^ ^
Result      : [4,5,1,2,3]

As simple as that !!

Java Code: [ source: sun java fourums ]

int[] reverse(int[] a, int i, int j) { // reverse elements i, i+1 ... j-1
   for (; --j > i; i++) {
      int t= a[i]; a[i]= a[j]; a[j]= t;
   }
   return a; // convenience.
}

int[] shiftRight(int[] a, int i) {
   return reverse(reverse(reverse(a, 0, a.length), 0, i), i, a.length);
}

Complexity: O(N)
Basically you traverse over the array twice, hence the complexity turns out to be O(2N) ≈ O(N)` as `n -> ∞`.