Removing duplicates from array using Binary Search Tree

Problem : given an array e.g. [3,5,4,2,1,2,3,1]

Need : filter the array such as to remove duplicates ( reference : http://www.careercup.com/question?id=3515013)

Approach: There are many ways to do this

a.) sort the array and compare elements in sequential fashion and remove duplicates : Complexity – O(nlogn)

b.) create a hash and based on hash function put values in hash only once, if you encounter duplicates, ignore them : Complexity - O(n)

c.) another approach is to do it with using Binary Search Tree, pick one element at a time, search if it exists in tree, if not, create node, set pointers and if you encounter duplicates, just ignore them by not creating tree nodes: Complexity - O(n)

I tried doing this using Java, took a long time to get it right, but finally it worked. The program also prints the three traversal techniques that we can run on a tree – PreOrder, PostOrder and InOrder

Please note that in code, left=true means ” left child” and left=false means “right child”.

Program is as follows:

BSTNode.java

     /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */

    package careercup.google;

    /**
     *
     * @author Harit
     */
    public class BSTNode {
        private int value;
        private int leftChild;
        private int rightChild;

        public BSTNode(int v){
            value = v;
            leftChild = -1;
            rightChild = -1;
        }

        public int getValue(){
            return this.value;
        }

        public int getChild(boolean left){
            if(left){
                return this.leftChild;
            }
            else{
                return this.rightChild;
            }
        }
        public void setChild(int child, boolean left){
            if(left){
                this.leftChild = child;
            }else{
                this.rightChild = child;
            }
        }
    }

RemDupArrayBST.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

import java.util.ArrayList;

/**
 *
 * @author Harit
 */
public class RemDupArrayBST {
    /* Output Array of Nodes */
    private static ArrayList<BSTNode> nodes = new ArrayList<BSTNode>();
    private static int parent = -1;
    private static boolean left = false;

    public static void main(String args[]){
        /* Sample Input Array */
        //int[] input_array = new int[]{3,1,2,1};
        int[] input_array = new int[]{3,5,4,2,1,2,3,1};
        //int[] input_array = new int[]{1,2,3,2,4,4};
        /* end sample input */

        for(int i=0; i<input_array.length; i++){
            if(nodes.size() == 0){
                /* tree is empty, add root */
                BSTNode node = new BSTNode(input_array[i]);
                nodes.add(node);
            }else{
                /* search if node already exists */
                if(!contains(input_array[i])){
                    BSTNode node = new BSTNode(input_array[i]);
                    nodes.add(node);
                    nodes.get(parent).setChild(nodes.size()-1, left);
                }else{
                    System.out.println(input_array[i] + " : already exists - ignoring");
                }
            }
        }

        /* final print */
        System.out.print("Inorder Traversal: ");
        inOrderTraverse(nodes.get(0));

        System.out.println("");

        System.out.print("PostOrder Traversal: ");
        postOrderTraverse(nodes.get(0));

        System.out.println("");

        System.out.print("PreOrder Traversal: ");
        preOrderTraverse(nodes.get(0));

        System.out.println("");
    }

    private static boolean contains(int value){
        int index = 0;
        while(index >= 0){
            if (nodes.get(index).getValue() == value){
                return true;
            }
            if (nodes.get(index).getValue() > value){
                parent = index;
                left = true;
                index = nodes.get(index).getChild(true);
            }else{
                parent = index;
                left = false;
                index = nodes.get(index).getChild(false);
            }
        }
        return false;
    }

    private static void inOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        if(node.getChild(true) != -1){
            inOrderTraverse(nodes.get(node.getChild(true)));
        }
        System.out.print(node.getValue() + " ");
        if(node.getChild(false) != -1){
            inOrderTraverse(nodes.get(node.getChild(false)));
        }
    }

    private static void postOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        if(node.getChild(true) != -1){
            postOrderTraverse(nodes.get(node.getChild(true)));
        }
        if(node.getChild(false) != -1){
            postOrderTraverse(nodes.get(node.getChild(false)));
        }
        System.out.print(node.getValue() + " ");
    }

    private static void preOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        System.out.print(node.getValue() + " ");
        if(node.getChild(true) != -1){
            preOrderTraverse(nodes.get(node.getChild(true)));
        }
        if(node.getChild(false) != -1){
            preOrderTraverse(nodes.get(node.getChild(false)));
        }
    }
}

Output:

2 : already exists – ignoring

3 : already exists – ignoring

1 : already exists – ignoring

Inorder Traversal: 1 2 3 4 5

PostOrder Traversal: 1 2 4 5 3

PreOrder Traversal: 3 2 1 5 4

search and replace (tr command) in perl

Its been such a long time that I never wrote a single program in one of the language I love : Perl. So I was going through questions posted on Microsoft interview list and I decided to write the program in Perl.

The question was  : “Write an efficient C code for ‘tr’ program. ‘tr’ has two command line arguments. They both are strings of same length. tr reads an input file, replaces each character in the first string with the corresponding character in the second string. eg. ‘tr abc xyz’ replaces all ‘a’s by ‘x’s, ‘b’s by ‘y’s and so on.”

And the code in Perl is as follows (comments for prints are suppressed and can be used for debugging purposes) :

#!/usr/bin/perl

my %hash = ();

if($#ARGV + 1 != 3){

print “usage : ./tr.pl <search> <replace> <file>\n”;

exit;

}

if(length($ARGV[0]) != length($ARGV[1])){

print “search and replace pattern have to be os same length\n”;

exit;

}

my($search) = $ARGV[0];

my($replace) = $ARGV[1];

my($file) = $ARGV[2];

#print “$search : $replace : $file\n”;

prepareHash();

modifyHash($search, $replace);

readFile($file);

sub prepareHash(){

my(@array) = (a .. z);

#print “@array\n”;

foreach(@array){

$hash{$_} = $_;

}

#while(my($key,$value) = each %hash){

#       print “$key => $value, “;

#}

}

sub modifyHash(){

my(@search) = split(//,$_[0]);

my(@replace) = split(//,$_[1]);

#print “@search\n”;

#print “@replace\n”;

foreach($i = 0; $i < scalar(@search); $i ++){

$hash{$search[$i]} = $replace[$i];

}

#while(my($key,$value) = each %hash){

#       print “$key => $value, “;

#}

#print “\n”;

}

sub readFile(){

print “opening file ..\n”;

my($buf,$data,$n);

open(FILE,”$file”) or die “couldn’t open the file : $!”;

while(($n = read FILE,$data,1) != 0){

#print “$data:$hash{$data}, “;

print “$data”;

if(!$hash{$data}){

$buf .= $data;

}else{

$buf .= $hash{$data};

}

}

print “\nAfter replacement ..\n”;

print “$buf”;

}

output :

./tr.pl abcmno xyzpqr text

opening file ..

a b c d e f g h i j k l m n o p q r s t u v w x y z

After replacement ..

x y z d e f g h i j k l p q r p q r s t u v w x y z