Pages

Wednesday 25 April 2012

Redirections and Pipes

1) http://mywiki.wooledge.org/BashFAQ/055
2) http://mywiki.wooledge.org/BashGuide/InputAndOutput#Redirection
3) http://stackoverflow.com/questions/818255/in-the-bash-shell-what-is-21

Friday 20 April 2012

Fail fast and Fail safe in Java

http://www.certpal.com/blogs/2009/09/iterators-fail-fast-vs-fail-safe/
http://javarevisited.blogspot.co.uk/2012/02/fail-safe-vs-fail-fast-iterator-in-java.html

Thursday 19 April 2012

Internal and External Commands to the Unix Shell

Some commands that you type are internal , built into the shell. For example, the cd command is built-in. That is, the shell interprets that command and changes your current directory ( 1.21 ) for you. The ls command, on the other hand, is an external program stored in the file /bin/ls .

The shell doesn't start a separate process to run internal commands. External commands require the shell to fork and exec ( 1.11 ) a new subprocess ( 38.3 ) ; this takes some time, especially on a busy system. (Article 7.4 shows an example where extra speed can be important.)

Reference : http://docstore.mik.ua/orelly/unix/upt/ch01_10.htm

Tuesday 17 April 2012

Autoboxing and Unboxing in Java

Excerpts from the reference :

Definition : You can’t put an int (or other primitive value) into a collection. Collections can only hold object references, so you have to box primitive values into the appropriate wrapper class (which is Integer in the case of int). When you take the object out of the collection, you get the Integer that you put in; if you need an int, you must unbox the Integer using the intValue method. All of this boxing and unboxing is a pain, and clutters up your code. The autoboxing and unboxing feature automates the process, eliminating the pain and the clutter.

Advantages : The result of all this magic is that you can largely ignore the distinction between int and Integer, with a few caveats.Use them only when you have to put code in collections.

Disadvantages :
1)  An Integer expression can have a null value.
2) If your program tries to autounbox null, it will throw a NullPointerException.
3) The == operator performs reference identity comparisons on Integer expressions and value equality comparisons on int expressions.
4) There are performance costs associated with boxing and unboxing, even if it is done automatically.

Example :
You can write Integer i = 5; instead of Integer i = Integer.valueOf(5); or Integer i = new Integer(5);  

Reference :
1) http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html

Tip : This feature was introduced in JDK 5.

 Java supplies built-in reference types known as wrapper types, one for each of the primitive types:
Java automatically converts from primitive types to wrapper types (autoboxing) and back (auto-unboxing) when warranted

Monday 16 April 2012

Java Generics


Previous Code :  
// Removes 4-letter words from c. Elements must be strings
static void expurgate(Collection c) {
    for (Iterator i = c.iterator(); i.hasNext(); )
      if (((String) i.next()).length() == 4)
        i.remove();

Disadvantage of this approach : 
When we declare c to be of type Collection<String>, this tells us
something about the variable c that holds true wherever and whenever
it is used, and the compiler guarantees it (assuming the program compiles
without warnings).
 
New Code :
// Removes the 4-letter words from c
static void expurgate(Collection<String> c) {
    for (Iterator<String> i = c.iterator(); i.hasNext(); )
      if (i.next().length() == 4)
        i.remove();
}
 
Advantages of this approach :  
A cast, on the other hand, tells us something the programmer thinks is true at a single point in the code, and the VM checks
whether the programmer is right only at run time.
 
Defining Simple Generics : 
public interface List<E> { void add(E x);
Iterator<E> iterator();
}public interface Iterator<E> { E next();
boolean hasNext();
}

You might imagine that List<Integer> stands for a version of List where E has
been uniformly replaced by Integer:
public interface IntegerList { void add(Integer x)
Iterator<Integer> iterator();
}
 
This might be misleading. 

Type parameters are analogous to the ordinary parameters used in methods or constructors.
Much like a method has formal value parameters that describe the kinds of
values it operates on, a generic declaration has formal type parameters. When a method
is invoked, actual arguments are substituted for the formal parameters, and the method
body is evaluated. When a generic declaration is invoked, the actual type arguments
are substituted for the formal type parameters.

Generic Subtyping : 
If Foo is a subtype (subclass or subinterface) of Bar, and G is some
generic type declaration, it is not the case that G<Foo> is a subtype of G<Bar>.




Best Resources :
1) http://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.pdf
2) http://www.ibm.com/developerworks/java/library/j-jtp01255/index.html
3) http://docs.oracle.com/javase/1.5.0/docs/guide/language/generics.html

Tip :
Generics was introduced in Java 1.5.

Sunday 15 April 2012

Poisson Distribution

Wikipedia definition : The Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time and/or space if these events occur with a known average rate and independently of the time since the last event.


The major difference between Poisson and Binomial distributions is that the Poisson does not have a fixed number of trials. Instead, it uses the fixed interval of time or space in which the number of successes is recorded.


Ex.1.  On an average Friday, a waitress gets no tip from 5 customers. Find the probability that she will get no tip from 7 customers this Friday.The waitress averages 5 customers that leave no tip on Fridays: λ = 5.
Random Variable : The number of customers that leave her no tip this Friday.
We are interested in P(X = 7).


Ex. 2 During a typical football game, a coach can expect 3.2 injuries. Find the probability that the team will have at most 1 injury in this game.A coach can expect 3.2 injuries : λ = 3.2.
Random Variable : The number of injuries the team has in this game.


 Ex. 3. A small life insurance company has determined that on the average it receives  6 death claims per day. Find the probability that the company receives at least seven death claims on a randomly selected day.
                                                       P(x ≥ 7) = 1 - P(x ≤ 6) =  0.393697



Ex. 4. The number of traffic accidents that occurs on a particular stretch of road during a month follows a Poisson distribution with a mean of  9.4. Find the probability that less than two accidents will occur on this stretch of road during a randomly selected month.
                                         P(x < 2) = P(x = 0) + P(x = 1) =  0.000860

         



Friday 13 April 2012

StringBuilder vs StringBuffer vs String in Java

String : immutable
StringBuffer : mutable + threadsafety
StringBuilder : mutable + without thread-safety

References : 
1) http://javarevisited.blogspot.co.uk/2011/07/string-vs-stringbuffer-vs-stringbuilder.html

Difference between HashMap and HashSet and HashTable

Hashtable
Hashtable is basically a datastructure to retain key-value pairs.
  • It doesn’t allow null for both key and value. You will get NullPointerException if you add null value.
  • It is synchronized. So it comes with its cost. Only one thread can access at a time
HashMap
Like Hashtable it also accepts key value pairs.
  • It allows null for both key and value
  • It is unsynchronized. Hence, it comes up with better performance than HashTable
  • Implements the map interface
HashSet
HashSet does not allow duplicate values. It provides add method rather put method. You also use its contain method to check whether the object is already available in HashSet. HashSet can be used where you want to maintain a unique list.
Implements the set interface.

Concurrent HashMap :
A concurrentHashMap is thread-safe implementation of Map interface. In this class put and remove method are synchronized but not get method. This class is different from Hashtable in terms of locking; it means that hashtable use object level lock but this class uses bucket level lock thus having better performance.

References :
1) http://docs.oracle.com/javase/tutorial/collections/index.html
2) http://www.amazon.com/dp/0596527756/?tag=stackoverfl08-20

Remove Duplicates from a String

Problem : Remove duplicates from string given " bananas " Return "bans"
Write code for both O(n) and O(n2) solutions


Solution using BitSet:  
public class RemoveDuplicatesFromString {
    public static void main(String args[]){
       
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        str = str.toLowerCase();
        BitSet bitset = new BitSet(26);
        for(int i=0;i<str.length();i++)
        {
            if(!bitset.get(str.charAt(i)))
            {
                bitset.set(str.charAt(i));
                System.out.print(str.charAt(i));
            }
        }
       
    }
}

Solution using HashSet:  
public class RemoveDuplicatesFromString {
    public static void main(String args[]){
       
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        str = str.toLowerCase();
   
        HashSet<Character> bitset=new HashSet<Character>(); 
        for(int i=0;i<str.length();i++)
        {
            if(!bitset.contains(str.charAt(i)))
            {
                bitset.add(str.charAt(i));
                System.out.print(str.charAt(i));
            }
        }
           
    }
}

References :
1) http://docs.oracle.com/javase/1.5.0/docs/api/java/util/class-use/BitSet.html
2) http://docs.oracle.com/javase/1.4.2/docs/api/java/util/BitSet.html

Wednesday 11 April 2012

Colorful Numbers

Problem : Determine whether a number is colorful or not. 263 is a colorful number because (2,6,3,2x6,6x3,2x3x6) are all different whereas 236 is not because (2,3,6,2x3,3x6,2x3x6) have 6 twice. So take all consecutive subsets of digits, take their product and ensure all the products are different

Solution :  
public class ColorfulNumbers {
    public static void main(String args[]){
        Scanner input = new Scanner(System.in);
        String number = input.nextLine();
        Set<Integer> set = new HashSet<Integer>();
        for(int i=1;i<=number.length();i++)
        {
            for(int j=0;j+i<=number.length();j++)
            {
                int k =j;
                int prd = 1;
               
                while(k<j+i)
                {
                    prd = prd * (number.charAt(k)-'0');
                    k++;
                }
               
                if(set.contains(prd))
                {
                    System.out.println("Not colorful");
                    System.exit(0);
                }
                else
                {
                    set.add(prd);
                }
               
               
            }
        }
        System.out.println("Colorful");
       
    }
}

Print continuous alphabets from a sequence of arbitrary alphabets
For example:
Input: abcdefljdflsjflmnopflsjflasjftuvwxyz
Output: abcdef; mnop; tuvwxyz
Input: AbcDefljdflsjflmnopflsjflasjftuvWxYz
Output: abcdef; mnop; tuvwxyz



public class ContinuousAlphabets {
    public static void main(String args[])
    {
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        System.out.println(str);
       
        if(str==null || str.length()<=1)
            return;
        str = str.toLowerCase();
        StringBuffer temp = new StringBuffer();
        for(int i =0;i<str.length();i++){
            if((temp.length()==0) || ((temp.length()>0) && (str.charAt(i) - temp.charAt(temp.length()-1) == 1)))
                temp.append(str.charAt(i));
            else{
                if(temp.length()>1){
                    System.out.println(temp);
                }
                temp.delete(0, temp.length());
                temp.append(str.charAt(i));
            }   
        }
        if(temp.length()>1){
            System.out.println(temp);
        }
    }
  
}

Monday 9 April 2012

Saddle Point

1) Find the minimum in each row
2) Find the maximum in each column, and put these in separate arrays.
3) Print the minimum value of the column maxima (-10), and the maximum value of the row minima(-10)

import java.util.Scanner;


public class saddlepoints {
    public static void main(String args[])
    {
        int m,n;
        int arr[][] = new int[10][10];
        int rowMinima[] = new int[10];
        int colMaxima[] = new int[10];
        Scanner scanner = new Scanner(System.in);
        System.out.println("Input the number of rows");
        m = Integer.parseInt(scanner.nextLine());
        System.out.println("Input the number of columns");
        n = Integer.parseInt(scanner.nextLine());
       
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(scanner.nextLine());
            }
        }
       
        for(int i=0;i<m;i++){
            int min = Integer.MAX_VALUE;
            for(int j=0;j<n;j++){
                if(arr[i][j]<min)
                    min = arr[i][j];
            }
            rowMinima[i] = min;
        }
       
        for(int j=0;j<n;j++){
            int max = Integer.MIN_VALUE;
            for(int i=0;i<n;i++){
                if(arr[j][i]>max)
                    max = arr[j][i];
            }
            colMaxima[j] = max;
        }
       
        int max=Integer.MIN_VALUE;
        for(int i=0;i<m;i++)
        {   
            if(rowMinima[i]>max)
                max = rowMinima[i];
        }
       
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++)
        {   
            if(rowMinima[i]<min)
                min = rowMinima[i];
        }
       
        if(min == max)
            System.out.println("Saddle Point is "+min);
               
    }
}
 

Generate all substrings of a string

static void ListCombination(String str){
  if(str != null && str.length()!=0)
   RecCombine("",str);
 }
 
 static void RecCombine(String prefix,String rest){
  if(rest.length() == 0)
   System.out.print(prefix + " ");
  else{
   RecCombine(prefix + rest.charAt(0),rest.substring(1));
   RecCombine(prefix,rest.substring(1));
   
  }
 }

Related Questions :
  1.  You will also need to find out all substrings of a string in the subset sum problem http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

Generate all permutations of a string in Java

public  static void permutation(String str) { 
    permutation("", str); 
 }

 private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
           permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

Sunday 8 April 2012

Reverse words of a String

Solution in Java :

import java.util.*;
public class ReverseWords{
public static void main(String[] args){
  System.out.print("Enter the string: ");
  Scanner input=new Scanner(System.in);
  String str=input.nextLine();
  StringBuffer buffer = new StringBuffer(str);
  StringTokenizer st = new StringTokenizer(buffer.reverse().toString()" ");
  System.out.print("Reversed Words: ");

  while(st.hasMoreTokens()){
    StringBuffer sb= new StringBuffer(st.nextToken());
    System.out.print(" "+sb.reverse());
  }
}
}
References : 

The string tokenizer class allows an application to break a string into tokens. The tokenization method is much simpler than the one used by the StreamTokenizer class. The StringTokenizer methods do not distinguish among identifiers, numbers, and quoted strings, nor do they recognize and skip comments.
The set of delimiters (the characters that separate tokens) may be specified either at creation time or on a per-token basis.
An instance of StringTokenizer behaves in one of two ways, depending on whether it was created with the returnDelims flag having the value true or false:
  • If the flag is false, delimiter characters serve to separate tokens. A token is a maximal sequence of consecutive characters that are not delimiters.
  • If the flag is true, delimiter characters are themselves considered to be tokens. A token is thus either one delimiter character, or a maximal sequence of consecutive characters that are not delimiters.
A StringTokenizer object internally maintains a current position within the string to be tokenized. Some operations advance this current position past the characters processed.
A token is returned by taking a substring of the string that was used to create the StringTokenizer object.
The following is one example of the use of the tokenizer. The code:
StringTokenizer st = new StringTokenizer("this is a test");
     while (st.hasMoreTokens()) {
         System.out.println(st.nextToken());
     }
 
prints the following output:
this
     is
     a
     test
 
StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.
The following example illustrates how the String.split method can be used to break up a string into its basic tokens:
String[] result = "this is a test".split("\\s");
     for (int x=0; x<result.length; x++)
         System.out.println(result[x]);
 
prints the following output:
this
     is
     a
     test
 
A thread-safe, mutable sequence of characters. A string buffer is like a String, but can be modified. At any point in time it contains some particular sequence of characters, but the length and content of the sequence can be changed through certain method calls.
String buffers are safe for use by multiple threads. The methods are synchronized where necessary so that all the operations on any particular instance behave as if they occur in some serial order that is consistent with the order of the method calls made by each of the individual threads involved.
The principal operations on a StringBuffer are the append and insert methods, which are overloaded so as to accept data of any type. Each effectively converts a given datum to a string and then appends or inserts the characters of that string to the string buffer. The append method always adds these characters at the end of the buffer; the insert method adds the characters at a specified point.
For example, if z refers to a string buffer object whose current contents are "start", then the method call z.append("le") would cause the string buffer to contain "startle", whereas z.insert(4, "le") would alter the string buffer to contain "starlet".
In general, if sb refers to an instance of a StringBuffer, then sb.append(x) has the same effect as sb.insert(sb.length(), x).
Whenever an operation occurs involving a source sequence (such as appending or inserting from a source sequence) this class synchronizes only on the string buffer performing the operation, not on the source.
Every string buffer has a capacity. As long as the length of the character sequence contained in the string buffer does not exceed the capacity, it is not necessary to allocate a new internal buffer array. If the internal buffer overflows, it is automatically made larger. As of release JDK 5, this class has been supplemented with an equivalent class designed for use by a single thread, StringBuilder. The StringBuilder class should generally be used in preference to this one, as it supports all of the same operations but it is faster, as it performs no synchronization.


 Solution in C :
void ReverseWords(char *str)
{
    int start, end, length;

    length=strlen(str);
    ReverseString(str, 0, length-1);

    start=end=0;
    while (end < length)
    {
        if (str[end] ! = ' ')
        {
            start=end;
            while (str[end] != ' ' && end < length)
                  end++;        
            end--;
            ReverseString(str, start, end);
        }
        end++;
    }
}
void ReverseString(str, start, end)
{
    char *temp;
    while (start < end)
    {
        temp=str[start];
        str[start]=str[end];
        str[end]=temp;
        start++;
        end--;
    }
}