Donation

If you found the contents in this blog useful, then please make a donation to keep this blog running. You can make donations via Skrill with email address shazin.sadakath@gmail.com

Saturday, September 29, 2012

Google Code Jam 2012 Practice - Reverse Words

In order to improve my algorithm skills I wanted to try out some practice challenges offered by Google Code Jam 2012. I wrote the following code to solve Reverse Words challenge. I verified the output by submitting them to Google Code Jam page and there are correct.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

/**
 * 
 * @author Shazin Sadakath
 *
 */
public class CodeJamSolution2 {
    private File inFile;
    private File outFile;
    
    public static void main(String[] args) {
        if(args.length < 2) {
            System.out.println("Usage : java CodeJamSolution2 <In File> <Out File>");
            return;
        }
        CodeJamSolution2 cjs2 = new CodeJamSolution2(args[0], args[1]);
        cjs2.start();
    }
    
    public CodeJamSolution2(String inFile, String outFile) {
        this.inFile = new File(inFile);
        this.outFile = new File(outFile);
    }
    
    public void start() {
        BufferedReader br = null;
        BufferedWriter bw = null;
        try {
            br = new BufferedReader(new FileReader(inFile));
            bw = new BufferedWriter(new FileWriter(outFile));
            int count = Integer.parseInt(br.readLine());
            String[] words = null;
            for(int i=0;i<count;i++) {
                words = br.readLine().split(" ");
                reverse(words);
                bw.write(String.format("Case #%d: %s\n", i+1, output(words)));
            }
        } catch(Exception e) {
            e.printStackTrace();
        } finally {
            if(br != null) {
                try {
                    br.close();
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            if(bw != null) {
                try {
                    bw.close();
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
    }
    
    /**
     * Method to reverse a word array
     * works at O(N / 2) 
     * 
     * @param words
     */
    public void reverse(String[] words) {
        int i=0;
        int j=words.length - 1;
        String temp = null;
        while(i < j) {
            temp = words[i];
            words[i] = words[j];
            words[j] = temp;
            i++;
            j--;
        }
    }
    
    /**
     * method to append all the elements in the array together
     * 
     * @param words 
     * @return appended words sentence
     */
    private String output(String[] words) {
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<words.length;i++) {
            sb.append(words[i]);
            if(i != words.length - 1) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}

Wednesday, September 26, 2012

Google Code Jam 2012 Practice - Store Credit

In order to improve my algorithm skills I wanted to try out some practice challeges offered by Google Code Jam 2012. I wrote the following code to solve Store Credit challenge. I verified the output by submitting them to Google Code Jam page and there are correct.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Store Credit solution 
 * 
 * @author Shazin Sadakath
 *
 */
public class CodeJamSolution1 {
    private File inFile;
    private File outFile;
    
    public static void main(String[] args) {
        if(args.length < 2) {
            System.out.println("Usage : java CodeJamSolution1 <In File> <Out File>");
            return;
        }
        CodeJamSolution1 cjs1 = new CodeJamSolution1(args[0], args[1]);
        cjs1.start();
    }
    
    public CodeJamSolution1(String inFile, String outFile) {
        this.inFile = new File(inFile);
        this.outFile = new File(outFile);
    }
    
    public void start() {
        BufferedReader br = null;
        BufferedWriter bw = null;
        try {
            br = new BufferedReader(new FileReader(inFile));
            bw = new BufferedWriter(new FileWriter(outFile));
            int totalRecords = Integer.parseInt(br.readLine());
            int credit = 0;
            int items = 0;
            Map<String, List<Integer>> map = new HashMap<String, List<Integer>>();            
            for(int i=0;i<totalRecords;i++) {
                credit = Integer.parseInt(br.readLine());
                items = Integer.parseInt(br.readLine());
                int[] values = new int[items];
                String line = br.readLine();
                int j=0;
                List<Integer> indexes = null;                
                for(String value:line.split(" ")) {
                    values[j] = Integer.parseInt(value);                    
                    indexes = map.get(value);
                    if(indexes == null) {
                        indexes = new ArrayList<Integer>();
                    }
                    indexes.add(j);
                    map.put(value, indexes);
                    j++;
                }                
                insertionSort(values);
                int[] result = findSum(values, credit);    
                int[] finalValues = null;
                if(result[0] == result[1]) {
                    indexes = map.get(String.valueOf(result[0]));
                    finalValues = new int[] { indexes.get(0) + 1, indexes.get(1) + 1};
                } else {
                    finalValues = new int[] { map.get(String.valueOf(result[0])).get(0) + 1, map.get(String.valueOf(result[1])).get(0) + 1};
                    insertionSort(finalValues);
                }                
                bw.write(String.format("Case #%d: %d %d\n", i+1, finalValues[0], finalValues[1]));
                map.clear();                
            }
            
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if(br != null) {
                try {
                    br.close();
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            if(bw != null) {
                try {
                    bw.close();
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
         
    }
    
    /**
     * Method to find sum
     * uses O(N) in worse case given a sorted array
     * 
     * @param values - int Array
     * @param sum - Sum
     * @return int Array with values which add to sum 
     */
    public int[] findSum(int[] values, int sum) {
        int[] result = null;        
        int i = 0;
        int j = values.length - 1;
        while(i <= j) {            
            if((values[i] + values[j]) == sum) {
                result = new int[] { values[i], values[j] };
                break;
            } else if ((values[i] + values[j]) < sum) {
                i += 1;
            } else if ((values[i] + values[j]) > sum) {
                j -= 1;
            }
        }        
        return result;
    }
    
    /**
     * insertion sort algorithm 
     * uses O(N ^ 2) is worse case
     * 
     * @param values - int Array to be sorted
     */
    public void insertionSort(int[] values) {
        int iHole = 0;        
        int item = 0;
        for(int i=1;i<values.length;i++) {
            item = values[i];
            iHole = i;
            while(iHole > 0 && values[iHole - 1] > item) {
                values[iHole] = values[iHole - 1];
                iHole -= 1;
            }
            values[iHole] = item;
        }        
    }    
}

Monday, September 24, 2012

Vulnerability in Opencart based shopping carts

I found a vulnerability which exposes the sensitive information stored in error log file of opencart web application to public. An unprotected web site will cause the log file to be crawled by legitimate bots and will be indexed in search engine result pages. For example if you want to what are the web sites which uses opencart web application as their main shopping cart application just use the following query in google and search.

PHP Warning:  unlink(system/cache/cache.currency [<a href='function.unlink'>function.unlink</a>]: No such file or directory in public_html/system/library/cache.php

This is common warning message logged by almost all of the opencart web applications in their log file. Along with this log file you can find usernames, directory structures etc which are sensitive. An unprotected system and system/log directory in opencart causes this vulnerability. This can be fixed by performing the following step as mentioned in sitefixit.

Securing The /system/ Folder

Certain files are wide-open by default. If you have installed OpenCart in your root directory, just go to http://www.yourdomain.com/system/logs/error.log and you should be able to download your error log, even if you’re a public user. You should protect these files, so create a .htaccess with the following code:


     <Files *.*>
    Order Deny,Allow
    Deny from all
    </Files> 

Then put that .htaccess file in the following 2 directories:
  1. /system/
  2. /system/logs/

Wednesday, September 12, 2012

How I didn't get the Amazon.com Job

Well I was informed by Kristin yesterday (12/09/2012) that there are pursuing with other candidates but I might be considered for future opportunities. Well I am not sad because I took out of good experience through these interviews on what to expect, where should I improve myself on.

One of the main problems I think that got me out of the interview process is that, I didn't ask enough questions from the interviewer. I was trying to find the solution to the problem as quickly as possible. As I think the two algorithms I wrote are in first and last phone screens were not what the interviewers were expecting. Amazon is a company working with millions of records and transactions per day so they might expect their algorithms to be much more efficient than O(n^2). The interviewer never told me this but I guess it is my fault I should have asked.

But I am pretty sure that I did really well during the second phone screen and wrote a very effient solution for the take home question given to me by Pascal. Pascal himself replied to me commending about the cleaness of the code.I am happy and proud about that.

But there are a lot of skills that I should master and this was a good wake up call. Hopefully I work hard on my weaknesses and become good in the future. Anyway as always thank god for giving me the opportunity.