MindSpace

A randomized divide-and-conquer algorithm

There is nothing new here. My Java code to find the 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.

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));
    }
}

Hackerrank

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();
    }
}