Amazon Product API

Just enrolled into Amazon Product API which will help me in my next project involving books. The project plans to research on review, ratings and genre of the books. Excited to get started !

String : Anagrams or not

Question : Find if two words are anagrams or not.

Solution :
The best solution basically involves sorting the characters in the words and then comparing to check if they are same.


public static boolean isAnagram(String s1, String s2){
      
        if (s1.length() != s2.length() )
            return false;
      
        char s1array[] = s1.toLowerCase().toCharArray();
        char s2array[] = s2.toLowerCase().toCharArray();
      
        Arrays.sort(s1array);
        Arrays.sort(s2array);
      
        for (int i=0;i <s1.length();i++)
            if (s1array[i] != s2array[i])
                return false;
        return true;
    }

String : Remove duplicate characters

Question : Remove Duplicate characters from a string.

Solution :

Basically the solution involves counting the occurences of characters in the string .

First solution uses an in-built Hashtable :

    public static String removeDuplicateCharHash(String ip){
        Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();
        String op = new String("");
        for(int i=0;i<ip.length();i++){
            Character ch = ip.charAt(i);
            if (! ht.containsKey(ch))
            { op = op + ch; ht.put(ch, new Integer(1)); }
        }
        return op;
    }
   
Second Solution uses a bit vector which is used as a hastable:

    public static String removeDuplicateChar(String ip){
// Initialize the bit vector  
    int ht[] = new int[256];
        for (int i=0;i<256;i++)
            ht[i] = 0;
     
  String op = "";
       
        for (int i=0;i<ip.length();i++){
            char ch = ip.charAt(i);
            if (ht[ch] == 0)
            {op = op + ch; ht[ch]++;}
        }
       
        return op;
    }

Increase EBS Image Size

Increase EBS Image Size

Scenario : Lets say you wanted to make your own image based on the stock Amazon AMI. But after you are done with the painful customization , you realize you started of with a EBS size of 6GB !
You need more than that !

You would have 2 options now :
1. Restart with a bigger size AMI. (Good luck and have fun again.)
2. Resize the current one to a bigger size.

This post is about the second option.

Assuming your current instance name is INST1, the attached volume is VOL1SMALL.
It can be an easy task if you follow the steps shown below :

1. Stop the instance. (I have noticed the steps below complete a lot faster if the instance is stopped)
2. Create a snapshot of the attached volume . Let it be SNAP1.
3. Now create a new volume from the snapshot you just created. Let this be VOL2BIG (Choose your higher size while doing this )
4. Select the already attached volume, i.e. VOL1SMALL and notice the path where it is mounted. It should be most probably /dev/sda1 . Now Detach this volume.
5. Now right click on the newly created volume VOL2BIG and set the mount path to be the same "/dev/sda1".
6. Start the instance again. INST1.
7. Do the df -h and you'll STILL SEE 6GB ! What the Hell !! Don't panic :-)

All you gotta do is resize the partition. To do that :

1. run "fdisk -l"
Note the device name of the newly attached volume. In my case it was "/dev/xvde1"

2. run "resize2fs /dev/xvde1 SIZE"

Note SIZE should include the units as well. If you want it to grow to 15Gigs .. use 15G
Do man resize2fs for more details.

Thats it ... Running df -h will now show you the new size !

Enjoy !

Solve Sudoku

Question : Write a program to solve a Sudoku !

Thought Process :
I am not a very expert level sudoku solver. So I think I know only the basic rules and the basic methods to solve a Sudoku. Hence in real life I am able to solve the "Easy" levels , struggle with "Medium" and "Hard".

The solution I came up with employs only the basic strategies. The answer given by my algorithm is the max I can go manually. I am not able to solve any more than this algorithm. Others can expand on this and add more functions and strategies.

Code : Class describing each of the block in a Sudoku grid

public class Sudoku {
// 2D array to store the sudoku elements
 ArrayList<ArrayList<SudokuBlock>> sb;
// This variable stores the number of unsolved blocks
 int unsolved;
 
 public Sudoku(int arr[][]){
  // Initialize the sudoku by taking in an array of values 
  sb = new ArrayList<ArrayList<SudokuBlock>>();
  unsolved = 81;
  for(int i=0;i<9;i++)
   { 
   ArrayList<SudokuBlock> asb = new  ArrayList<SudokuBlock>();
   for(int j=0;j<9;j++)
   {
    if(arr[i][j] != 0){
     SudokuBlock sbb = new SudokuBlock(true,arr[i][j]);
     asb.add(sbb);
     unsolved--;
    }
    else {
     SudokuBlock sbb = new SudokuBlock();
     asb.add(sbb);
    }
   }
   sb.add(asb);
   }
 }
 
 public void print(){
  for(int i=0;i<9;i++)
   { if(i>0 && i%3==0) System.out.println("- - - - - - - - - - - -");
     for(int j=0;j<9;j++)
     {
      if(j>0 && j%3==0) System.out.print(" | ");
       System.out.print(sb.get(i).get(j).sv+" ");
     }
     System.out.println(); 
   }
 }
 
 public void print(int i, int j){
// Can be used to debug 
  if(sb.get(i).get(j).isSet)
   System.out.print(sb.get(i).get(j).sv+" ");
  else
      System.out.print(sb.get(i).get(j).sud_values.toString());
  
 }
 
 public void solve(){
 // Main function which triggers different algorithms to solve the sudoku 
// Check the smaller 3 * 3 blocks and try to fill the values 
  smallBlock();
// Check the row and column for solved entries and removes them from other blocks Set   
  inlines();
// Check 3 adjacent rows/columns at a time and attempt to fill values  
  triples();
// Check to complete a row/column  
  fillrow();
 }
 
 public int unsolved(){
  // Calculates the number of unsolved spaces left
  unsolved = 81;
  for(int i=0;i<9;i++)
   for(int j=0;j<9;j++)
    if(sb.get(i).get(j).isSet)
     unsolved--;
  
  return unsolved;
 }
 public void fillrow(){
  // Check for values to complete a row 
  for(int i=0;i<9;i++){
   for(int j=0;j<9;j++){
    if(!sb.get(i).get(j).isSet){
     HashSet<Integer> ms = (HashSet<Integer>) sb.get(i).get(j).sud_values.clone();
     for(int k=0;k<9;k++){
      if(sb.get(i).get(k).isSet && j!=k ){
       ms.removeAll(sb.get(i).get(k).sud_values);
      }
     }
     if(ms.size() ==1 && !sb.get(i).get(j).isSet){
      sb.get(i).get(j).isSet = true;
      sb.get(i).get(j).sv = (Integer) ms.toArray()[0];
      solve();
     }
    }
    if(!sb.get(i).get(j).isSet){
     // For columns
     HashSet<Integer> ms = (HashSet<Integer>) sb.get(i).get(j).sud_values.clone();
     for(int k=0;k<9;k++){
      if(sb.get(k).get(j).isSet && i!=k ){
       ms.removeAll(sb.get(k).get(j).sud_values);
      }
     }
     if(ms.size() ==1 && !sb.get(i).get(j).isSet){
      sb.get(i).get(j).isSet = true;
      sb.get(i).get(j).sv = (Integer) ms.toArray()[0];
      solve();
     } 
    }
   }
  }
 }
 
 public void triples(){
  // Check the 3 rows and columns to see if value should be set
   //check in the remaining columns in the set
     //if exists then check in remaining rows in the set
     //if exists then set it !
 // Attempt to find the row edges and column edges for a particular block   
  int row_min=0;
  int row_max=0;
  int col_min=0;
  int col_max=0;
 // Dividing up the entire sudoku into 9 3*3 blocks 
  for(int i=0;i<9;i++){
   
   int cal = i%3;
   row_min = (i/3)*3 ;
   row_max = row_min + 2;
   col_min = cal/3 + cal*3;
   col_max = col_min + 2;
   
   for(int a=row_min;a<=row_max;a++)
    for(int b=col_min;b<=col_max;b++)
    {
     if(!sb.get(a).get(b).isSet){
      // Not using iterator because we plan to change the values
      Object[] it = sb.get(a).get(b).sud_values.toArray();
      for(int iti=0;iti< it.length;iti++){
       // Variable which holds number of rows/column a particular value occurs
       int count_r=0;
       int count_c=0;
       Integer n = (Integer) it[iti];
      for(int k=0;k<9;k++){
       
       if(a!=row_min && n == sb.get(row_min).get(k).sv)
        count_r++;
       if(a!=(row_min+1) && n == sb.get(row_min+1).get(k).sv)
        count_r++;
       if(a!=(row_min+2) && n == sb.get(row_min+2).get(k).sv)
        count_r++;
       if(b!=col_min && n == sb.get(k).get(col_min).sv)
        count_c++;
       if(b!=(col_min+1) && n == sb.get(k).get(col_min+1).sv)
        count_c++;
       if(b!=(col_min+2)&& n == sb.get(k).get(col_min+2).sv)
        count_c++;
       
       if (count_c ==2 && count_r ==2)
        { sb.get(a).get(b).sv = n;
          sb.get(a).get(b).isSet = true;
          
         // Whenever we find a new value, reiterate from the beginning 
          solve();
        }
       else if (count_c ==2 && count_r !=2){
       int in1, in2;
       
       if(a==row_min)
       {in1=row_min+1;in2=row_min+2;}
       else if((a==row_min+1)){
        in1=row_min;in2=row_min+2;
       }
       else {
        in1=row_min;in2=row_min+1;
       }
      
       if(!sb.get(in1).get(b).sud_values.contains(n) && !sb.get(in2).get(b).sud_values.contains(n)){
        sb.get(a).get(b).isSet = true;
        sb.get(a).get(b).sv = n;
        
        solve();
        
       }
       
       
       }
       else if (count_c !=2 && count_r ==2){
        
        int in1, in2;
        if(b==col_min)
        {in1=col_min+1;in2=col_min+2;}
        else if((b==col_min+1)){
         in1=col_min;in2=col_min+2;
        }
        else {
         in1=col_min;in2=col_min+1;
        }
        
        if(!sb.get(a).get(in1).sud_values.contains(n) && !sb.get(a).get(in2).sud_values.contains(n)){
         sb.get(a).get(b).isSet = true;
         sb.get(a).get(b).sv = n;
         
         solve();
        }
        
        
        }
       
       
      }
      
      
      }
      
     }
    if(sb.get(a).get(b).isSet)
     sb.get(a).get(b).sud_values.clear();
    }
  
 
  }
 }
 public void inlines(){
    //Checks if a number exists in the row or column if yes then remove from the set
  for(int i=0;i<9;i++){
   for(int j=0;j<9;j++){
    for(int k=0;k<9;k++){
     if(!sb.get(i).get(j).isSet){
      sb.get(i).get(j).sud_values.remove(sb.get(i).get(k).sv);
      sb.get(i).get(j).sud_values.remove(sb.get(k).get(j).sv);
     }
    }
    if(!sb.get(i).get(j).isSet)
     if (sb.get(i).get(j).sud_values.size() == 1)
     {
      sb.get(i).get(j).sv = (Integer) (sb.get(i).get(j).sud_values.toArray()[0]);
      sb.get(i).get(j).isSet = true;
      // If any new value is found recurse !
      solve();
     }
    
   }
   
  }
 }
 public void smallBlock(){
  // Compare with the smaller block and fill possible values
   
  
  int row_min=0;
  int row_max=0;
  int col_min=0;
  int col_max=0;
  
  for(int i=0;i<9;i++){
   HashSet<Integer> hs_np_val = new HashSet<Integer>();
   for(int j=1;j<10;j++)
    hs_np_val.add(j);
   
   int cal = i%3;
   row_min = (i/3)*3 ;
   row_max = row_min + 2;
   col_min = cal/3 + cal*3;
   col_max = col_min + 2;
   
   for(int a=row_min;a<=row_max;a++)
    for(int b=col_min;b<=col_max;b++)
    {
     if(sb.get(a).get(b).isSet){
      hs_np_val.remove(sb.get(a).get(b).sv);
     }
    }
  
   //Fill the blocks with possible values
    
   for(int a=row_min;a<=row_max;a++)
    for(int b=col_min;b<=col_max;b++)
     if(!sb.get(a).get(b).isSet)
       { //sb.get(a).get(b).sud_values = hs_np_val;
      sb.get(a).get(b).sud_values.clear();
      sb.get(a).get(b).sud_values.addAll(hs_np_val);
      if(sb.get(a).get(b).sud_values.size() ==1){
       sb.get(a).get(b).sv = (Integer) (sb.get(a).get(b).sud_values.toArray()[0]);
       sb.get(a).get(b).isSet = true;
       solve();
      }
       }
   
    
  }
 }
 
 private class SudokuBlock {

  // Variable to hold possible set of values
  public HashSet<Integer> sud_values;
  // Variable which identifies if the value is found or not
  boolean isSet;
  // Variable value
  public int sv;
  
  public SudokuBlock(){
   isSet = false;
   sv =0;
   sud_values = new HashSet<Integer>();
   for(int i=1;i<=9;i++)
    sud_values.add(new Integer(i));
  }
  
  public SudokuBlock(boolean is, int isv){
   isSet = is;
   sv =isv;
   sud_values = new HashSet<Integer>();
  }

}

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  /*
  // Easy Level 
  int arr[][] = {{0,0,0,1,0,5,0,0,0},
        {1,4,0,0,0,0,6,7,0},
        {0,8,0,0,0,2,4,0,0},
        {0,6,3,0,7,0,0,1,0},
        {9,0,0,0,0,0,0,0,3},
        {0,1,0,0,9,0,5,2,0},
        {0,0,7,2,0,0,0,8,0},
        {0,2,6,0,0,0,0,3,5},
        {0,0,0,4,0,9,0,0,0}};
  */
  // Medium
   int arr[][] = 
      {{4,0,0,0,1,0,0,0,0},
       {0,0,0,3,0,9,0,4,0},
       {0,7,0,0,0,5,0,0,9},
       {0,0,0,0,6,0,0,2,1},
       {0,0,4,0,7,0,6,0,0},
       {1,9,0,0,5,0,0,0,0},
       {9,0,0,4,0,0,0,7,0},
       {0,3,0,6,0,8,0,0,0},
       {0,0,0,0,3,0,0,0,6}};
  
  Sudoku sd = new Sudoku(arr);
  System.out.println("Original. Unsolved : "+sd.unsolved());
  sd.print();
  
  sd.solve();
  
  
  System.out.println("After.  Unsolved : "+sd.unsolved());
  sd.print();
  
 }
}

The code has all the comments included in it ! I don't think it should be hard to decipher that. This code obviously cannot solve all the sudokus. The result of this code is the maximum level I can go manually. I'll hone my own skills and add functions accordingly ! Till then here it is.

String : has Unique characters.

Question: Implement a function to find if a string has all unique characters.

Thought Process : Basically, you have to note if any character has been repeated or not. So a list of used character has to be maintained. So we can utilize a Hash table for such a purpose. However, in this particular case, we can emulate a hash table by using an array (the characters value can be the index and the value can be 1 or 0) ! So two solutions :

public static boolean unique_chars(String s){
int ht[] = new int[256];
for(int i=0;i<256;i++)
   ht[i] = 0;
  
  for(int j=0;j 0){
return false;
}
ht[(int)s.charAt(j)]++;
}
return true;
}

public static boolean unique_chars_hash(String s){
Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();

for(int j=0;j<s.length();j++){
if(ht.containsKey(s.charAt(j))){
return false;
}
ht.put(s.charAt(j), new Integer(1));
}
return true;
}

Complexity :
Time : O(n) : where n is the number of characters.
Space: O(1) : You would need extra storage for an array to emulate the hashtable but that will be constant. You can even reduce that space by using a bit vector.

public static boolean unique_chars_bv(String s){
  // Assuming all lowercase characters
  int bv =0;
  
  for(int j=0;j<s.length();j++){
   if((bv & (1<<(int)s.charAt(j))) > 0){
    return false;
   }
   bv |= (1<<(int)s.charAt(j));
  }
   return true;
 }

String : Count Words

Question : (Asked to me during a phone interview)

Write a function to count the words in a string. (without using any in-built split functions. The only delimiter is space).

My Thought Process :

Right of the bat , Start counting space characters. But realized that this would fail if all the characters are spaces. Alright, rethink. Make $word_count =0; Start reading characters, if space, skip till next character not a space. Increment the $word_count. But this was also flawed (for input " some word "). So finally after a 2nd rethink. Here's my answer :

public static int word_count(String s1){
// Function to calculate number of words in a string
int count = 0;

if(s1 == null)
return count;

int i= 0 ;
while(i < s1.length()){

while(i <s1.length() && s1.charAt(i) == ' ')
i++;
if(i == s1.length())
break;
else
{
count++;
while(i<s1.length() && s1.charAt(i) != ' ')
i++;
}

}

return count;
}

Complexity :

Time : O(n) : n being number of characters.

Space: O(1) : Just one variable space needed.