Loop detection in Singly Linked List.

Floyd’s Cycle Detection Algorithm (The Tortoise and the Hare) :

In Brief : How do you determine if your singly-linked list has a cycle?
In the late 1960s, Robert W. Floyd invented an algorithm that worked in linear (O(N)) time. It is also called Floyd’s cycle detection algorithm or The Tortoise and the Hare

 tortoise = top
 hare = top
  
 forever:
      if hare == end :
          return 'No Loop Found'
      hare = hare.next
  
      if hare == end :
         return 'No Loop Found'
     hare = hare.next
 
     tortoise = tortoise.next
 
     if hare == tortoise:
         return 'Loop Found'	

hare

The easiest solution to the cycle detection problem is to run through the list, keeping track of which nodes you visit, and on each node check to see if it is the same as any of the previous nodes. It’s pretty obvious that this runs in quadratic (O(N^2)) time… not very efficient, and actually more complicated than this one.

The Tortoise and the Hare is possibly the most famous cycle detection algorithm, and is surprisingly straightforward. The Tortoise and the Hare are both pointers, and both start at the top of the list. For each iteration, the Tortoise takes one step and the Hare takes two. If there is a loop, the hare will go around that loop (possibly more than once) and eventually meet up with the turtle when the turtle gets into the loop. If there is no loop, the hare will get to the end of the list without meeting up with the turtle.

Why can’t you just let the hare go by itself? If there was a loop, it would just go forever; the turtle ensues you will only take n steps at most.

Note : Most of the part of this post is taken from http://www.siafoo.net/algorithm/10

A case of using constant file in javaScript Appliactions :Reducing coupling between frontend and backend

Problem :
If we have a REST “getBookInfo” and its response was :

{
    "book": {
        "name": "Ramayan",
        "author": "Valmiki"
    }
}

Now it’s changed to (note first the capital letters ):

{
    "Book": {
        "Name": "Ramayan",
        "Author": "Valmiki"
    }
}

So where ever we were accessing the response like below it would stop working :

_implGetBookInfoSuccess : function(data, response) {
                     var varBookInfo = response.book;
                     if (!_.isUndefined(varBookInfo)) {
                                         this._implInvokeGetBookPrice(varBookInfo.name, varBookInfo.author);
                     }
              },

Sometimes we deal with the same REST response in many files so in above scenario we had to change every file which was dealing with response and it is very difficult.

Suggested Solution :

Create a constant mapper file BookInfoResponseMapper.js :

		
define([], function() {
       var BookInfoResponseMapper = {
                     
              //CheckCoverage REST response object attribute
              Book : 'book',
                     
              //CheckCoverage REST response object attribute
              Book_Name: 'name',
                     
              //CheckCoverage REST response object attribute
              Book_Author: 'author',
       };
       return BookInfoResponseMapper;
});

Access the response attribute like below :

_ implGetBookInfoSuccess: function(data, response) {
                     var varBookInfo = response[BookInfoResponseMapper.Book];
                     if (!_.isUndefined(varBookInfo)) {
                            this._ implInvokeGetBookPrice(varBookInfo[BookInfoResponseMapper.Book_Name],
                                 varBookInfo[BookInfoResponseMapper.Book_Author]);
                           }
              }

It would reduce the coupling between FE and REST response and changing only the constant file will be sufficient in the case of any changes in REST response.

Note : Please note that all the examples above are with require.js and Backbone. But the concept can be used with any application.

Java Hash Collision in HashMap

How does get(Key key) method works internally in HashMap:

Here are steps, which happens, when you call get() method with key object to retrieve corresponding value from hash based collection

a) Key.hashCode() method is used to find the bucket location in backing array. (Remember HashMap is backed by array in Java) Though hashcode() is not used directly, but they are passed to internal hash() function.

b) In backing array or better known as bucket, key and values are stored in form of a nested class called Entry. If there is only one Entry at bucket location, than value from that entry is returned. Pretty straightforward right?

Things get little tricky, when Interviewer ask second question, What happens if two keys has same hashCode? If multiple keys has same hashCode, than during put() operation collision had occurred, which means multiple Entry object stored in a bucket location. Each Entry keep track of another Entry, forming a linked list data structure there. Now, if we need to retrieve value object in this situation, following steps will be followed :

1) Call hashCode() method of key to find bucket location.

2) Traverse thought linked list, comparing keys in each entries using keys.equals() until it return true.

So, we use equals() method of key object to find correct entry and than return value from that.

Example

package algo.hashmap;

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

public class HashCollision {

	public static void main(String[] args) {

		Map<MyInnerClass, String> myMap = new HashMap<MyInnerClass, String>();
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode same equals
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode different equals
		myMap.put(new MyInnerClass("ABC", "D"), "Second");
		
		System.out.println(myMap);
	}
}

class MyInnerClass {
	private String StrA;
	private String StrB;

	public MyInnerClass(String strA, String strB) {
		super();
		StrA = strA;
		StrB = strB;
	}

	@Override
	public int hashCode() {
		return (StrA + StrB).length();
	}

	@Override
	public boolean equals(Object obj) {
		if (StrB.length() == StrA.length()) {
			return true;
		}
		return false;
	}
}

Same hashCode Same equals :


public static void main(String[] args) {

		Map<MyInnerClass, String> myMap = new HashMap<MyInnerClass, String>();
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode same equals
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode different equals
		//myMap.put(new MyInnerClass("ABC", "D"), "Second");
		
		System.out.println(myMap);
	}

HashCollisionSameEquals

Same hashCode different equals


public static void main(String[] args) {

		Map<MyInnerClass, String> myMap = new HashMap<MyInnerClass, String>();
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode same equals
		//myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode different equals
		myMap.put(new MyInnerClass("ABC", "D"), "Second");
		
		System.out.println(myMap);
	}

HashCollisionDifferentEquals

Greatest Sum of Sub-Arrays…


Question : Given an integer array containing positive and negative numbers, how do you get the maximum
sum of its sub-arrays? Continuous numbers form a sub-array of an array.For example, if the input array is {1, -2, 3, 10, -4, 7, 2, -5}, the sub-array with the maximum sum is {3, 10, -4, 7,2} whose sum 18.

Let’s accumulate each number in the sample array from beginning to end. Our solution initializes sum
as 0. In the first step, it adds the first number 1, and sum becomes 1. And then if it adds the second
number -2, sum becomes -1. At the third step, it adds the third number 3. Notice that the previous sum is
less than 0, so the new sum will be 2 and it is less than the third number 3 itself. Therefore, the previous
accumulated sum -1 should be discarded.
The key point here is that when the sum becomes a negative number or zero, adding this sum to the
following array element will not be greater than the element itself, so the new sub-array will start from
the next element.
It continues accumulating from the next number with sum 3. When it adds the fourth number 10,
sum becomes 13, and it decreases to 9 when it adds the fifth number -4. Notice that the sum with -4 is
less than the previous sum 13 because of the negative number -4. It saves the previous sum 13 since it
might be the max sum of sub-arrays.
At the sixth step, it adds the sixth number 7 and sum becomes 16. Now sum is greater than the
previous max sum of sub-arrays, so the max sum is updated to 16. It is similar when it adds the seventh
number 2. The max sum of sub-arrays is updated to 18. Lastly it adds -5 and sum becomes 13. Since it is
less than the previous max sum of sub-arrays, the final max sum of sub-arrays remains 18, and the subarray
is {3, 10, -4, 7, 2} accordingly.


int getGreatestSumOfSubArray(int[] numbers) {
   int curSum = 0;
   int greatestSum = Integer.MIN_VALUE;
   for(int i = 0; i < numbers.length; ++i) {
     if(curSum <= 0)
        curSum = numbers[i];
     else
        curSum += numbers[i];

     if(curSum > greatestSum)
     greatestSum = curSum;
   }
   return greatestSum;
}

(Apress.Coding.Interviews.Questions.Analysis.and.Solutions)

Finding minimum and maximum value in Array in single pass…

To find the minimum value into an array of items, take the first item and to compare its value against the values of all other elements. Once we find a smaller element we continue the comparisons with its value. Finally we find the minimum.

We pass through the array with n steps and we need exactly n-1 comparisons.

Finding the maximum is identical to finding the minimum and requires n-1 comparisons!

Since they both are O(n) and need n-1 comparisons it’s natural to think that combining the two tasks will be O(n) and 2n – 2 comparisons. However we can reduce the number of comparisons!

Instead of taking only one item from the array and comparing it against the minimum and maximum we can take a pair of items at each step. Thus we can first compare them and then compare the smaller value with the currently smallest value and the greater item with the currently greatest value. This will make only 3 comparisons instead of 4.

The complexity of finding both minimum and maximum is O(n). Even after combining the both algorithms in one single pass the complexity remains O(n). However in the second case we can reduce the number of comparisons to 3 * ceil(n/2) instead of 2n – 2!

Finding duplicates in array…


An array contains n numbers ranging from 0 to n-1. There are some numbers duplicated in the
array. It is not clear how many numbers are duplicated or how many times a number gets duplicated. How do you
find a duplicated number in the array? For example, if an array of length 7 contains the numbers {2, 3, 1, 0, 2, 5,
3}, the implemented function (or method) should return either 2 or 3.

Indexes in an array with length n are in the range 0 to n-1. If there were no duplication in the n
numbers ranging from 0 to n-1, we could rearrange them in sorted order, locating the number i as the ith
number. Since there are duplicate numbers in the array, some locations are occupied by multiple
numbers, but some locations are vacant.
Now let’s rearrange the input array. All numbers are scanned one by one. When the ith number is
visited, first it checks whether the value (denoted as m) is equal to i. If it is, we continue to scan the next
number. Otherwise, we compare it with the mth number. If the ith number equals the mth number,
duplication has been found. If not, we locate the number m in its correct place, swapping it with the mth
number. We continue to scan, compare, and swap until a duplicated number is found.
Take the array {2, 3, 1, 0, 2, 5, 3} as an example. The first number 2 does not equal its index 0, so it is
swapped with the number with index 2. The array becomes {1, 3, 2, 0, 2, 5, 3}. The first number after
swapping is 1, which does not equal its index 0, so two elements in the array are swapped again and the
array becomes {3, 1, 2, 0, 2, 5, 3}. It continues to swap since the first number is still not 0. The array is {0,
1, 2, 3, 2, 5, 3} after swapping the first number and the number with index 3. Finally, the first number
becomes 0.
Let’s move on to scan the next numbers. Because the following three numbers, 1, 2 and 3, are all
equal to their indexes, no swaps are necessary for them. The following number, 2, is not the same as its
index, so we check whether it is the same as the number with index 2. Duplication is found since the
number with index 2 is also 2.


int duplicate(int numbers[]) {
int length = numbers.length;
for(int i = 0; i < length; ++i) {
if(numbers[i] < 0 || numbers[i] > length - 1)
throw new IllegalArgumentException("Invalid numbers.");
}
for(int i = 0; i < length; ++i) {
while(numbers[i] != i) {
if(numbers[i] == numbers[numbers[i]]) {
return numbers[i];
}
// swap numbers[i] and numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
throw new IllegalArgumentException("No duplications.");
}

Finding the second highest value in array

// Initialize these to the smallest value possible
int highest = Integer.MIN_VALUE;
int secondHighest = Integer.MIN_VALUE;

// Loop over the array
for (int i = 0; i < array.Length; i++) {

    // If we've found a new highest number...
    if (array[i] > highest) {

        // ...shift the current highest number to second highest
        secondHighest = highest;

        // ...and set the new highest.
        highest = array[i];
    } else if (array[i] > secondHighest)
        // Just replace the second highest
        secondHighest = array[i];
    }
}

// After exiting the loop, secondHighest now represents the second
// largest value in the array<br />