Red-Black Tree

May 29, 2014 Leave a comment

I will refine this post as I code more methods. This is an attempt to learn this data structure and explain what I think I understand using pictures drawn using TEX. I use the tikz editor.

The algorithm code is based on pseudo-code from “Introduction to Algorithms” by Thomas H. Cormen et al. I use Java language features like enums etc. wherever possible.

Sample TEX code

[->,>=stealth',level/.style={sibling distance = 5cm/#1,
  level distance = 1.5cm}] 
\node [arn_n] {3}
    child{ node [arn_r] {2} 
 				child{ node [arn_nil] {NIL}}
    }
    child{ node [arn_r] {4}
							child{ node [arn_nil] {NIL}}
	}
;

Insert

public class RedBlack {

    private final Node SENTINEL= new Node();
    private Node root= new Node();

    public RedBlack() {
        root = SENTINEL;
    }

    enum Color {
        BLACK,
        RED};

    class Node{

        public void setColor(Color color) {
            this.color = color;
        }

        private Color color = Color.BLACK;

        Node left,right,p;
        int key;
    }

    public void insert( RedBlack tree,
                        Node z){
        
        Node y =  SENTINEL;
        Node x =  tree.root;
        
        while( x != SENTINEL){
            y = x;
            if ( z.key < x.key){
                x = x.left;
            }else
                x = x.right;
        }
        
        z.p = y;
        
        if( y == SENTINEL){
            tree.root = z;
        }else if ( z.key < y.key){
                z = y.left;
        }else{
                z = y.right;
        }
        z.left = z.right = SENTINEL;
        z.setColor(Color.RED);
    }
}

I check the colors like this.

    public void inOrder(Node x){

        if( x != SENTINEL){
            inOrder(x.left);
            System.out.println(x.key + "[" + x.color + "]");
            inOrder(x.right);
        }
    }

Now this tree has to be fixed so that it conforms to the rules that govern a Red-Black tree. So I code a method to fix it. This method is based on the pseudo-code from the same book. But I think there is a bug which I haven’t found. This tree after it is fixed looks like this.

Screen Shot 2014-06-01 at 1.17.01 PM

The black height property is 2.

The black height property for the left branch is 2 but it is 3 for one of the paths on the right.

I may have to read some other book because finding this bug is going to be hard.

Actually the tree should be like this.

Filed under Algorithms, Java

Hackerrank’s Service Lane

May 29, 2014 Leave a comment

I am again posting code without asymtotic analysis. There is no standard algorithm used here. I believe this problem pertains to Range Minimum Query algorithm which I hope to explore.

It is ridiculous that the code to parse the input values is more complex than the actual brute-force algorithm. Should Hackerrank parse it for us ?

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    private int noOfTestCases;

    private ArrayList<Integer> widths = new ArrayList<>();
    private ArrayList<Segment> tests = new ArrayList<>();

    OutputStream outputStream = System.out;
    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));


    public void  getInput(BufferedReader br) throws IOException {
        Scanner s = null;
        int lengthHighway = 0;
        try {
            s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

            if (s.hasNextLine()) {
                String[] s1 = s.nextLine().split("\\s+");
                lengthHighway = Integer.parseInt(s1[0]);
                noOfTestCases = Integer.parseInt(s1[1]);
            }
            if (s.hasNextLine()) {
                String[] s1 = s.nextLine().split("\\s+");
                for( int i = 0 ; i < s1.length ; i ++){
                    widths.add( Integer.parseInt(s1[i]) );
                }
            }
            while (s.hasNextLine()) {
                String[] s1 = s.nextLine().split("\\s+");
                tests.add( new Segment(Integer.parseInt(s1[0]), Integer.parseInt(s1[1]) ));
            }
        } finally {
            s.close();
        }
    }

    class Segment{

        public final int entry,exit;

        public Segment(int entry, int exit) {
            this.entry = entry;
            this.exit = exit;
        }
    }

    public static void main( String... argv ) throws IOException {
        Solution rm = new Solution();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        rm.getInput(br);
        rm.fit();

    }

   private void fit() {
        int[] vehicle = new int[]{1,2,3};

        try {
            for( Segment test : tests){
                Integer[] a  = Arrays.copyOfRange(widths.toArray(new Integer[widths.size()]), test.entry, test.exit+1);
                Arrays.sort(a);
                pw.println(vehicle[a[0]-1]);
                pw.flush();
            }
        }finally{
            pw.close();
        }
    }

}

Filed under Java

A randomized divide-and-conquer algorithm

May 26, 2014 1 Comment

There is nothing new here. My Java code to find the k^{th} smallest element in an array(Algorithms book by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani). The code is written based on the pseudo-code.

I am using Google guava here.

Ints.toArray( less )

This is the algorithm definition.

selection(S,k) = \begin{cases} selection(S_L,k), & \mbox{if } k\le |S_L|\\ v, & \mbox{if } |S_L| < k \le |S_L| + |S_v|\\ selection(S_R,k-|S_L|-|S_v|, & \mbox{if } k\ge |S_L|+|S_v| \end{cases}

import com.google.common.primitives.Ints;

import java.util.ArrayList;
import java.util.Random;

import static java.util.Arrays.sort;

public class KThLargestSelection {

    private Random r = new Random();

    static int[] a1 = new int[]{ 0,2,7,3,4,9};

        public int findKThLargest(  int[] a, int k ){

                int pivot = getPivot(a);

                ArrayList<Integer> less = new ArrayList<>();
                ArrayList<Integer> equal = new ArrayList<>();
                ArrayList<Integer> great = new ArrayList<>();

                for( int value : a ){
                        if ( value < pivot){
                            less.add( value );
                        } else if ( value == pivot){
                            equal.add( value );
                        }else if ( value > pivot){
                            great.add( value );
                        }
                }
                        if (k <= less.size()) {
                            return findKThLargest (Ints.toArray( less ), k);
                        }else if (k <= less.size() + equal.size()){
                            return  pivot;
                        }else
                            return   findKThLargest (Ints.toArray( great  ), k - less.size() - equal.size());

        }

    private int getPivot( int[] data ){
        int[] highLow = new int[0];

            System.out.println("getPivot [" + data.length + "] " + toStringArray(data));
            highLow = new int[] { data[0],data[data.length - 1] };

        if( data.length >= 3){
            sort(new int[]{data[r.nextInt(2)],
                           data[r.nextInt(2)],
                           data[r.nextInt(2)]});
        }
        return highLow[ 1 ];
    }

    private String toStringArray(int[] data){
        StringBuilder sb = new StringBuilder();
        for( int i = 0 ; i < data.length ; i ++ ){
            sb.append( data[i] + " ");
        }
        return sb.toString();
    }
    
    public static void main( String... s){
        KThLargestSelection l = new KThLargestSelection();
        System.out.println( l.findKThLargest(a1, 1));
    }
}

Filed under Java

Hackerrank

May 23, 2014 Leave a comment

I know it is embarassing to post code like this without asymptotic analysis. After taking a strenuous 10 week Machine learning course I am again coding java. This is the Utopia problem which can be solved in one line.

package com.hackerrank;

import java.io.*;
import java.util.ArrayList;


public class Solution {

    private int noOfTestCases;

    private ArrayList<Integer> tests = new ArrayList<>();

    OutputStream outputStream = System.out;
    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));

    protected void parseStdin(String[] data){

        int test = Integer.parseInt( data[0] );
        assert( test >= 1 && test <= 10);
        noOfTestCases = test;
            for( int i = 1 ; i < data.length ; i ++ ){
                int d = Integer.parseInt( data[i] );
                assert( d >= 0 && d <= 60);
                tests.add( d );
            }
        assert( tests.size() == noOfTestCases );
    }


    public ArrayList<String>  getInput(BufferedReader br) throws IOException {
        String line = null;
        ArrayList<String> arguments = new ArrayList<>();
        while( (line = br.readLine()) != null ){
            arguments.add(line);
        }
        br.close();
        return arguments;
    }

    public static void main( String... argv ) throws IOException {

        Solution utopia = new Solution();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<String> arguments = utopia.getInput( br );
        utopia.parseStdin( arguments.toArray(new String[arguments.size()]));
        utopia.test();


    }

    protected void test() {
        assert( 0 != noOfTestCases );
        assert( tests.size() == noOfTestCases );
        for( Integer test : tests)   {
            if( test != 0 ){
               if(test % 2  == 0){
                   growEvenly(test);
               }else{
                   growOddly(test);

               }
            }else{
                pw.println(1);
            }
        }
        pw.close();
    }

    private void growOddly(int test) {
        int odd = 1;
        if(test == 1 ){
            pw.println(test + 1);
        }else{
            for(int j = 0,k = test - 1 ; j < k; j = j + 2 ){
                odd = odd + odd + 1;
            }
            pw.println(odd * 2); pw.flush();
        }

    }

    private void growEvenly(int test) {
        int even = 1;
        for(int j = 0,k = test / 2 ; j < k ; j ++){
            even = even * 2 + 1;

        }
        pw.println(even);  pw.flush();
    }
}

Easymock

I have to expect 4 calls to readLine to accomodate null.

package com.hackerrank;

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

import java.io.BufferedReader;
import java.io.IOException;

import static org.easymock.EasyMock.createMock;
import static org.easymock.EasyMock.expect;
import static org.easymock.EasyMock.replay;

public class UtopiaTest {

    String[] argv;

    Solution solution;

    @Before
    public void sendInput() throws IOException {
        BufferedReader mockInputStream = createMock(BufferedReader.class);
        expect(mockInputStream.readLine()).andReturn(String.valueOf(2));
        expect(mockInputStream.readLine()).andReturn(String.valueOf(0));
        expect(mockInputStream.readLine()).andReturn(String.valueOf(1));
        expect(mockInputStream.readLine()).andReturn(null);
        replay(mockInputStream);
        solution = new Solution();
        argv = solution.getInput(mockInputStream).toArray(new String[3]);
        Assert.assertTrue(argv.length == 3);
    }

    @Test
    public void parse(){
        solution = new Solution();
        solution.parseStdin( argv );
    }

    @Test
    public void test(){
        solution = new Solution();
        solution.parseStdin( argv );
        solution.test();
    }
}

Filed under Java

Octave code example

May 19, 2014 Leave a comment

This is one of the simpler code tasks I worked on. I use ‘R’ but since this is Octave my first attempt wasn’t generic. The for loop assumes that there are 2 columns in the matrix shown below. There is a way to modify it to be more generic but this an example to show my Octave skills !!

I have a matrix with 2 columns and a vector which has repeating sets of the numbers 3,2 and 1. The task is to calculate the mean of all values in each column of the matrix rows that are grouped by the numbers 3, 2 and 1. So I decided to add the vector as the 3rd column of the matrix.

Matrix

\begin{pmatrix} 0.5403023 & -0.9576595 \\ -0.4161468 & -0.2751633 \\ -0.9899925 & 0.6603167 \\ -0.6536436 & 0.9887046 \\ 0.2836622 & 0.4080821 \\ 0.9601703 & -0.5477293 \\ 0.7539023 & -0.9999608 \\ -0.1455000 & -0.5328330 \\ -0.9111303 & 0.4241790 \\ -0.8390715 & 0.9912028 \\ 0.0044257 & 0.6469193 \\ 0.8438540 & -0.2921388 \\ 0.9074468 & -0.9626059 \\ 0.1367372 & -0.7480575 \\ -0.7596879 & 0.1542514 \end{pmatrix}

Vector

\begin{pmatrix} 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 1 \\ 2 \\ 3 \\ 1 \end{pmatrix}

Add the vector as the 3rd column.

centroids = zeros(K, n);%Declare matrix to store the result
X(:,end + 1 ) = idx;

\begin{pmatrix} 0.5403023 & -0.9576595 & 2.0000000 \\ -0.4161468 & -0.2751633 & 3.0000000 \\ -0.9899925 & 0.6603167 & 1.0000000 \\ -0.6536436 & 0.9887046 & 2.0000000 \\ 0.2836622 & 0.4080821 & 3.0000000 \\ 0.9601703 & -0.5477293 & 1.0000000 \\ 0.7539023 & -0.9999608 & 2.0000000 \\ -0.1455000 & -0.5328330 & 3.0000000 \\ -0.9111303 & 0.4241790 & 1.0000000 \\ -0.8390715 & 0.9912028 & 2.0000000 \\ 0.0044257 & 0.6469193 & 3.0000000 \\ 0.8438540 & -0.2921388 & 1.0000000 \\ 0.9074468 & -0.9626059 & 2.0000000 \\ 0.1367372 & -0.7480575 & 3.0000000 \\ -0.7596879 & 0.1542514 & 1.0000000 \\ \end{pmatrix}

Find the unique values of the 3rd column. The decimals do not matter here.

uidx = unique(X(:,3),"columns");

Vector with unique elements

\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}

I use find to get all the row numbers(j) of the values in the matrix where the 3rd column matches each of the unique values(uidx)

for i = 1:size(uidx,1)
 [j,k]=find(X(:,3) == uidx(i) );
 s = X(j,1);
 t = X(j,2);
 centroids(i,:) = [mean(s);mean(t)]
end

Mean of each column for all the grouped rows

\begin{pmatrix} -0.171357 & 0.079776 \\ 0.141787 & -0.188064 \\ -0.027364 & -0.100211 \end{pmatrix}

Filed under Octave