Finding max and min

Q: Given an array of n elements, find the min and max in 3n/2 comparisons even in worst case.

We usually think of the following approach as soon as we see the question

One scan through the array with two extra variables to store current min and max.
In this approach the worst case number of comparisons = 2n

Can we change the approach slightly to make sure that even the worst case number of comparisons is 3*n/2

Following is the approach..

1) take 2 number at a time ....

2) compare these 2 numbers .... (1st comparison)

3) compare the minimum of these two with current minimum  (2nd comparison)

4) compare the max of these two with current max (3rd comparison)

as there are (n/2) pairs ... and 3 comparisons per a pair .... total comparisons are 3n/2 ....

No of occurrences of a number

Q: Given a sorted array find number of occurrences of a given number

If the interviewer has mentioned that the given array is in sorted array then he is expecting the solution to be in log( n ) time.

We can solve this using binary search. To find the no of occurrences of the given number we can find the first occurrence of the number and the last occurrence of the number and return the difference between them.

To find the first occurrence of a number we need to check for the following condition. Return the position if any of the following is true.

(mid == low && A[mid] == data) || (A[mid] == data && A[mid-1] < data)

To find the last occurrence of a number we need to check for the following condition. Return the position if any of the following is true.

(mid == high && A[mid] == data) || (A[mid] == data && A[mid+1] > data)

Working Java Code:

public class NoOfOccurences {

    public static int findFirstOccurence(int A[],int low,int high,int data)
    {
        int mid;
       
        while(low <= high)
        {
            mid = low + (high-low)/2;
            if(( mid == low && A[mid] == data) || (A[mid] == data && A[mid-1] < data))
            {
                return mid;
            }else if(A[mid] >= data)
            {
                high = mid-1;
            }else
            {
                low = mid+1;
            }   
        }
       
        return -1;
       
    }
   
    public static int findLastOccurence(int A[],int low,int high,int data)
    {
        int mid;
       
        while(low <= high)
        {
            mid = low + (high-low)/2;
            if(( mid == high && A[mid] == data) || (A[mid] == data && A[mid+1] > data))
            {
                return mid;
            }else if(A[mid] <= data)
            {
                low = mid+1;
            }else
            {
                high = mid-1;
            }   
        }
       
        return -1;
    }
    
    
    public static void main(String[] args) {
        int a[] = {1,2,3,3,3,3,4,5,6};
        int firstCount = NoOfOccurences.findFirstOccurence(a,0,8,3);
        int lastCount = NoOfOccurences.findLastOccurence(a,0,8,3);
       
        int noOfOccur = (lastCount - firstCount) +1;
        System.out.print("No of occurences"+noOfOccur);

    }

}

SubArray With sum zero.

Q: An array contain positive and negative elements, find maximum subarray whose sum is equal to zero.

Algorithm:

Lets take input array as a[]={-3,2,4,-6,-8,10,11}

Make an array b [] such that b[i]=b[i-1]+a[i]; means b[i] = sum(a[0],..., a[i]);

So b[]={-3,-1,3,-3,-11,-1,10}

Now all those pairs at indexes (i,j)in array b[] having equal numbers are the indexes of subarrays from (i+1,j) having sum as zero.

we have to find some (i, j) so: a[i] + a[i+1] + ... + a[j] = 0. But a[i] + a[i+1] + ... + a[j] = b[j] - b[i-1].
when creating the map using b values, the key in map is the value from b and the value in map is the index of from b. if a new key exists, this means we found a solution.

Finding all pairs in O(n) can be done by using map.

Working JAVA Code
---------------------------
import java.util.Comparator;
public class Index implements Comparable{
Integer start;
Integer end;
public Integer getStart() {
    return start;
}
public void setStart(Integer start) {
    this.start = start;
}
public Integer getEnd() {
    return end;
}
public void setEnd(Integer end) {
    this.end = end;
}
public int compareTo(Object index1) {
    index1 = (Index) index1;
    Index index2 = (Index) this;
    Integer  index1Distance = ((Index) index1).getEnd().intValue() -  ((Index) index1).getStart().intValue();
    Integer index2Distance = ((Index) index2).getEnd().intValue() -  ((Index) index2).getStart().intValue();
    if (index1Distance > index2Distance)
        return 1;
    else if (index1Distance == index2Distance)
        return 0;
    else
        return -1;
}
}

import java.util.HashMap;
import java.util.Map;
public class SubarraywithSumZero {
    public Index findLongestSubArraywithSumZero(long[] inputArray) {
        // 1. Generate a cummulative array
        for (int i=1; i < inputArray.length; i++) {
            inputArray[i] += inputArray[ (i-1)];
        }
        //2. Read the array, store it in map
        // For a subraary with 0 there should + and - numbers
        // we need to figure the longest distance indexes which have same numbers
        // since our array is cummulative postives and negatives which sum to 0 will bring the
        // intermittent array back to same number where it started
        // eg intermittent array = -6, -8, -10, -6, -4, 1, 2, 3, 4, 1
        // now from -6 we again reach -6
        // and later from 1 back to 1 which implies these two arrays are summing to 0
        // we just need the longest one
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        Index maxIndex = null;
        for (int i=0; i < inputArray.length; i++) {
            Integer index = new Integer(i);
            Integer val = new Integer((int) inputArray[i]);
            if (indexMap.get(val) == null) {
                indexMap.put(val, index);
            }
            else {
                if (maxIndex == null) {
                    maxIndex = new Index();
                    //collosion found the subarray
                    maxIndex.setStart(indexMap.get(val));
                    maxIndex.setEnd(new Integer(i));
                }
                else  {
                    Index index1 = new Index();
                    index1.setStart(indexMap.get(val));
                    index1.setEnd(new Integer(i));
                    if (maxIndex.compareTo(index1) <= 0) {
                        maxIndex = index1;
                    }
                }
            }
        }
            return maxIndex;       
    }
    public static void main(String[] args) {
        long inputArray[] = {3,2,4,-6,-8,10,11};
        SubarraywithSumZero subarraywithSumZero = new SubarraywithSumZero();
        Index maxIndex = subarraywithSumZero.findLongestSubArraywithSumZero(inputArray);
        System.out.println("Longgest Subarray with sum starts at [" + maxIndex.getStart() + " ] and ends at [" + maxIndex.getEnd() + "]");
    }
}

Finding duplicates in an unsorted array

 

Q: You are given an array of elements. Some/all of them are duplicates. Find them in 0(n) time and 0(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

Algorithm:

1. Read input from startPos
2. If input is within the maxRange or it's not in correct place then it's a candidate to be   replaced else incrementStartPos
3. finalPosition for input is input[i]
4. if finalPosition < maxRange then swap input with finalPosition and increment finalPosition with MaxRange
5. else no need to swap as previous instances of this element are recorded at finalPos so just increment finalPosition with MaxRange to record another instance
6. if input at startPos is in correct place or reached zero then increment startPos++ till you go through end of Array
7. Iterate through the array and divide each element with maxRange. The divisor indicates how many times a element was repeated and 0 indicates a missing element

Eg: if an array had
(2, 3, 4, 3, 2}
1. n=5 after step1 we'll get
{3, 7, 4, 3, 2}
2. now a[0] = 3 so again in loop we'll get
{4, 7, 8, 3, 2}
3. now a[0] = 4 so again in loop we'll get
{3, 7, 8, 9, 2}
4. a[0] = 3 so again in loop we'll get { , 7, 13, 9, 2}
5. since a[0] is empty move to a[1] and in loop we find it's at the right place so move to next, 8, 9 are also in place so we move to last element and have the final array as
{ , 12, 13, 9, }

Now to find how many are duplicates divide every element by 5 and take the mod => m = (a[i] mod n) -1 this gives you how many times an element is repeated.

 

public static void main(String[] args) {       

        int[] inputArr1 = {0, 2, 3, 4, 3, 2};
        findDuplicates(inputArr1, 5);
        printDuplicatesAndMissingElements(inputArr1);
    }

    private static void findDuplicates(int[] inputArr, int maxRange) {
        // for simplicity reasons we will assume nothing is there in 0 index of array
        // and start from 1
        int i = 1;
        int maxArrLength = inputArr.length;
       
        while(true) {
            if ( i > maxArrLength - 1)
                break;
           
            int finalPos = inputArr[i];
            System.out.println(" Read :: " + inputArr[i]);
           
            if (finalPos > maxRange) {
                //this element is already in final position skip and move further looking for elements within maxRange
                i++;
                continue;
            }
            int finalPosElement = inputArr[inputArr[i]];
            int startPos = i;
            int startPosElement = inputArr[i];
           
            // if startPos element isn't in place and it's within the maxRange..
            // then candidate for swap or reaching final pos...
            if (inputArr[startPos] != i ||
                    inputArr[startPos] <= maxRange) {

                if (finalPosElement > maxRange) {
                    // if finalposElement > maxRange then no swapping required
                    // just add maxRange to denote multiple entry
                    inputArr[finalPos] += maxRange;   
                    //make startPosElement as 0
                    inputArr[startPos] = 0;
                    System.out.println("No swapping required incemented " + inputArr[finalPos] );
                }
                else {
                    //swap
                    int temp = startPosElement;
                    inputArr[startPos] = finalPosElement;
                    inputArr[finalPos] = temp + maxRange;
                    System.out.println("Swapped : " + startPosElement + " with " +finalPosElement);
                }
            }
            printArray(inputArr);
            // if the element in current evaluated position isn't still correct repeat the above again
            if (inputArr[startPos] == i ||
                    
                    inputArr[startPos] > maxRange) {
                System.out.println(" Read :: "+ inputArr[startPos] + " it's already in place");
                inputArr[startPos] += maxRange;
                i++;
            }
            else if (inputArr[startPos] == 0){
                i++;
                continue;
            }
            else {
                continue;
            }
               
        }
       
    }
   
    private static void printArray(int[] inputArr) {
        for (int i=1; i < inputArr.length; i++) {
            System.out.print(inputArr[i] +",");
        }
        System.out.println("");
    }
    private static void printDuplicatesAndMissingElements(int[] inputArr) {
        int maxRange = inputArr.length;
        for (int i=1; i < inputArr.length; i++) {
            if (inputArr[i] == 0) {
                System.out.println(" Element [" + i + "] is missing");
            }
            int input = inputArr[i];
            int mod = input / maxRange;
            if ( mod > 1) {
                System.out.println (" Element [" + i + "] is repeated + [" + mod + "] times");
               
            }
        }
    }

}

Ternary Search Tree implementation

The ternary search tree contains three types of links. First, there are pointers that correspond to links in the corresponding trie, shown as dashed down-arrows. Traversing a down-link corresponds to “matching” the character from which the arrow starts. The left- and right- links are traversed when the current character does not match the desired character at the current position. We take the left-link if the character we are looking for is alphabetically before the character in the current node, and the right-link in the opposite case.

Ternary tree data structure solves the memory problem of tries which we discussed in the earlier post in a more clever way. To avoid the memory occupied by unnecessary pointers, each trie node is represented as a tree-within-a-tree rather than as an array. Each non-null pointer in the trie node gets its own node in a ternary search tree.

Each node in a Ternary search tree could be implemented like this in java:

class TNode
{
    char m_char;
    TNode left, center, right;
    boolean wordEnd;

    public TNode(char ch, boolean wordEnd)
    {
        m_char = ch;
        wordEnd = wordEnd;
    }
}

Here is a Ternary search tree that stores words AB, ABBA, ABCD, and BCD. Nodes that terminate words are marked yellow:

Here is a simple Ternary search tree implementation in java:

public class TernarySearchTree {

    TNode root = null;
   
    public TernarySearchTree()
    {
        this.root = null;
    }

    private void insert(String key, int pos, TNode node)
    {
        char s[] = key.toCharArray();
        if (node == null) { node = new TNode(s[pos], false); }

        if (s[pos] < node.m_char) {
            insert(key, pos, node.left);
            }
        else if (s[pos] > node.m_char) {
            insert(key, pos, node.right);
            }
        else
        {
            if (pos + 1 == key.length()) { node.wordEnd = true; }
            else { insert(key, pos + 1, node.center); }
        }
    }

    public void insert(String s)
    {
        if (s == null || s == "") throw new IllegalArgumentException();

        insert(s, 0, this.root);
    }

    public boolean containsKey(String key)
    {
        if (key == null || key == "") throw new IllegalArgumentException();

        int pos = 0;
        TNode node = this.root;
        char s[] = key.toCharArray();
        while (node != null)
        {

            if (s[pos] < node.m_char) { node = node.left; }
            else if (s[pos] > node.m_char) { node = node.right; }
            else
            {
                if (++pos == key.length()) return node.wordEnd;
                node = node.center;
            }
        }

        return false;
    }
   
    public static void main(String[] args)
    {
        TernarySearchTree tree = new TernarySearchTree();
        tree.insert("AB");
        tree.insert("ABBA");
        tree.insert("ABCD");
        tree.insert("BCD");
       
        boolean found = tree.containsKey("AB");
       
        if(found)
            System.out.println("AB is found in the tree");
        else
            System.out.println("AB is not found");
       
        found = tree.containsKey("ABCD");
       
        if(found)
            System.out.println("ABCD is found in the tree");
        else
            System.out.println("ABCD is not found");

    }
}

class TNode
{
    char m_char;
    TNode left, center, right;
    boolean wordEnd;

    public TNode(char ch, boolean wordEnd)
    {
        m_char = ch;
        wordEnd = wordEnd;
    }
}

Trie implementation

A trie is a tree-like data structure in which each node contains an array of pointers, one pointer for each character in the alphabet. Starting at the root node, we can trace a word by following pointers corresponding to the letters in the target word.

Some of the uses of this Trie data structure is

1) Auto completion of the words or sentences like in Google Suggest.

2) Dictionary etc..

Each node in a trie could be implemented like this in java:

class Node {
    Node[] children;
    boolean isKey;

    public Node() {
        isKey = false;
        children = new Node[26];
    }

    public Node(boolean key) {
        isKey = key;
        children = new Node[26];
    }

}

 

Here is a trie that stores words AB, ABBA, ABCD, and BCD. Nodes that terminate words are marked yellow:

 

 

Here is a simple Trie search tree implementation in java:

public class Trie {

    Node root;

    public Trie() {
        this.root = new Node();
    }

    /**
     * Method to insert a string to Node and its children
     *
     * @param key
     *            the string to insert (the string is assumed to be uppercase)
     * @return true if the node or one of its children is changed, false
     *         otherwise
     */
    public boolean insert(String key) {
        return root.insert(key.toUpperCase());
    }

    /**
     * Returns whether key is a valid prefix for certain key in this trie. For
     * example: if key "hello" is in this trie, tests with all prefixes "hel",
     * "hell", "hello" return true
     *
     * @param prefix
     *            the prefix to check
     * @return true if the prefix is valid, false otherwise
     */
    public boolean containPrefix(String prefix) {
        return root.containPrefix(prefix.toUpperCase());
    }

    /**
     * Returns whether key is a valid key in this trie. For example: if key
     * "hello" is in this trie, tests with all prefixes "hel", "hell" return
     * false
     *
     * @param key
     *            the key to check
     * @return true if the key is valid, false otherwise
     */
    public boolean containKey(String key) {
        return root.containKey(key.toUpperCase());
    }
   
    public static void main(String[] args)
    {
       
        Trie trie = new Trie();
        trie.insert("AB");
        trie.insert("ABBA");
        trie.insert("ABCD");
        trie.insert("BCD");
       
        boolean found = trie.containKey("AB");
       
        if(found)
            System.out.println("AB is found in the trie");
        else
            System.out.println("AB is not found");
       
        found = trie.containPrefix("ABC");
       
        if(found)
            System.out.println("ABC prefix is found in the trie");
        else
            System.out.println("ABC prefix is not found");

    }
}

class Node {
    Node[] children;
    boolean isKey;

    public Node() {
        isKey = false;
        children = new Node[26];
    }

    public Node(boolean key) {
        isKey = key;
        children = new Node[26];
    }

    /**
     * Method to insert a string to Node and its children
     *
     * @param key
     *            the string to insert (the string is assumed to be uppercase)
     * @return true if the node or one of its children is changed, false
     *         otherwise
     */
    public boolean insert(String key) {
        // If the key is empty, this node is a key
        if (key.length() == 0) {
            if (isKey)
                return false;
            else {
                isKey = true;
                return true;
            }
        } else {// otherwise, insert in one of its child

            int childNodePosition = key.charAt(0) - 'A';
            if (children[childNodePosition] == null) {
                children[childNodePosition] = new Node();
                children[childNodePosition].insert(key.substring(1));
                return true;
            } else {
                return children[childNodePosition].insert(key.substring(1));
            }
        }
    }

    /**
     * Returns whether key is a valid prefix for certain key in this trie. For
     * example: if key "hello" is in this trie, tests with all prefixes "hel",
     * "hell", "hello" return true
     *
     * @param prefix
     *            the prefix to check
     * @return true if the prefix is valid, false otherwise
     */
    public boolean containPrefix(String prefix) {
        // If the prefix is empty, return true
        if (prefix.length() == 0) {
            return true;
        } else {// otherwise, check in one of its child
            int childNodePosition = prefix.charAt(0) - 'A';
            return children[childNodePosition] != null
                    && children[childNodePosition].containPrefix(prefix
                            .substring(1));
        }
    }

    /**
     * Returns whether key is a valid key in this trie. For example: if key
     * "hello" is in this trie, tests with all prefixes "hel", "hell" return
     * false
     *
     * @param key
     *            the key to check
     * @return true if the key is valid, false otherwise
     */
    public boolean containKey(String key) {
        // If the prefix is empty, return true
        if (key.length() == 0) {
            return isKey;
        } else {// otherwise, check in one of its child
            int childNodePosition = key.charAt(0) - 'A';
            return children[childNodePosition] != null
                    && children[childNodePosition].containKey(key.substring(1));
        }
    }

    public boolean isKey() {
        return isKey;
    }

    public void setKey(boolean key) {
        isKey = key;
    }
}

360 degree Viewer

Sample Application showing the 360 degree view of an image using paper vision 3d.

Demo here

Source code

<?xml version="1.0" encoding="utf-8"?>
<mx:Application xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute"
                xmlns:view="org.papervision3d.view.*" creationComplete="init();"
                width="622" height="504"
                backgroundGradientAlphas="[1.0, 1.0]" backgroundGradientColors="[#FFFFFF, #DEDEDE]">
    <mx:Script>
        <![CDATA[
            import mx.events.ItemClickEvent;
            import org.papervision3d.objects.primitives.Cylinder;
            import org.papervision3d.materials.BitmapFileMaterial;
            private var cylinder:Cylinder;
            //Initialization function
            private function init():void{
                // BasicView added to the Stage
                myUI.addChild( bv );
                bv.cameraAsCamera3D.x = 0;
                bv.cameraAsCamera3D.z = 0;
                bv.cameraAsCamera3D.y = 0;
                //Create object
                var mat:BitmapFileMaterial = new BitmapFileMaterial("DSC00020.jpg",true);
                mat.doubleSided = true;
                mat.precise = true;
                mat.smooth = true;
                cylinder = new Cylinder( mat , 80 , 100 , 100 , 100 , 80 , false , false );
                bv.scene.addChild( cylinder );
                //Rendering bv.startRendering();
                this.addEventListener(Event.ENTER_FRAME , onTimer );
            }
            //Rendering
            private function onTimer( e:Event ):void{
                bv.renderer.renderScene( bv.scene , bv.camera , bv.viewport );
                cylinder.rotationY += (myUI.width - myUI.mouseX )/ 100;
            }
            private function onClick(e:ItemClickEvent):void{
                cylinder.rotationY = e.item.angle;
            }
        ]]>
    </mx:Script>
    <view:BasicView id="bv"/>
    <mx:UIComponent id="myUI" width="300" height="300"/>
    <mx:LinkBar id="link" x="263.5" y="6" labelField="label" itemClick="onClick(event)">
        <mx:Object label="a" angle="0"/>
        <mx:Object label="b" angle="90"/>
        <mx:Object label="c" angle="180"/>
        <mx:Object label="d" angle="270"/>
    </mx:LinkBar>
    <mx:Label x="280.5" y="476" text="360 Video"/>
</mx:Application>