Permutations of a given string

In outline form,algorithm looks like :

If you're past the last position
Print the string
Return
Otherwise
For each letter in the input string
If it's marked as used, skip to the next letter
Else place the letter in the current position
Mark the letter as used
Permute remaining letters starting at current position + 1
Mark the letter as unused

Recursive Implementation :
Java code:

public class Permutations {

 public static void main(String[] args) {
  permutation("", "abc");
 }

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

Method 2:

import java.util.ArrayList;
import java.util.List;

public class Permutations {

 public static void main(String[] args) {
  List<String> permutations = getPermutations("abcd");
  System.out.println(" size " + permutations.size());
  for (int i = 0; i < permutations.size(); i++) {
   System.out.println(permutations.get(i));
  }
 }

 public static List<String> getPermutations(String word) {
  if (word == null || word.length() == 0)
   throw new NullPointerException();
  ArrayList<String> result = new ArrayList<String>();
  if (word.length() == 1) {
   result.add(word);
   return result;
  }
  List<String> temp = getPermutations(word
    .substring(0, word.length() - 1));
  for (String s : temp) {
   List<String> joined = joinCharToString(s, word
     .charAt(word.length() - 1));
   result.addAll(joined);
  }
  return result;
 }

 public static List<String> joinCharToString(String ori, char aChar) {
  if (ori == null || ori.length() == 0)
   throw new NullPointerException();
  List<String> result = new ArrayList<String>();
  StringBuilder sb;
  for (int i = 0; i < ori.length() + 1; i++) {
   sb = new StringBuilder(ori);
   sb.insert(i, aChar);
   result.add(sb.toString());
  }
  return result;
 }
}

Print all permutations with repetition of characters : 
Given a string of length n, print all permutation of the given string. Repetition of characters is allowed. Print these permutations in lexicographically sorted order
Examples:
Input: AB
Ouput: All permutations of AB with repetition are:
      AA
      AB
      BA
      BB

Java Code : 

public class Permutations {
 public static void main(String[] args) {
  String str = "abc";
  char[] chars = str.toCharArray();
  getPermutations(chars, "", str.length());
 }

 private static void getPermutations(char[] chars, String target, int length) {
  if (length == 0) {
   System.out.println(target);
   return;
  }

  for (int i = 0; i < chars.length; i++) {
   getPermutations(chars, target + chars[i], length - 1);
  }
 }
}

Gmail Multiple User Names...

Many of you might not be knowing that if you have 1 gmail id … you have infinte gmail ids…

Seems to be a joke.. It’s not actually…

for e.g  if you have gmail id:

venuhyd@gmail.com

then the mail sent to following ids will also be received by your mailbox:

venu+hyd@gmail.com  8char can be any valid charcter set of max 8 characters

venu.hyd@googlemail.com

venu.hyd@gmail.com

v.e.n.u.h.y.d@gmail.com

venuhy.d@gmail.com

As gmail ignores .’s in its username...

An alias made by mixture of various such alias is also an alias for your id. 

like  my.i.d+love@googlemail.com will alsodirect uts mail to your inbox.

You can use it to filter your e-mails from some sources by giving them alias id and then using a filter with to field..

Just Check this out...

Regrads 

Venu.

Find Kth largest and smallest number in BST

How to find kth smallest element in BST. you cannot use static/global variable and you cannot pass value of k to any function ?

Solution : Make in order traversal and out put the kth element.

Let each node in the BST have a field that returns the number of elements in its left and right subtree. Let the left subtree of node T contain only elements smaller than T and the right subtree only elements larger than or equal to T.

Now, suppose we are at node T:

1.       k == num_elements(left subtree of T), then the answer we're looking for is the value in node T

2.       k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.

3.       k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

This is O(log N) on average (assuming a balanced tree).

Java code:

public int ReturnKthSmallestElement1(int k)
    {
        Node node = Root;

        int count = k;

        int sizeOfLeftSubtree = 0;

        while(node != null)
        {

            sizeOfLeftSubtree = node.SizeOfLeftSubtree();

            if (sizeOfLeftSubtree + 1 == count)
                return node.Value;
            else if (sizeOfLeftSubtree < count)
            {
                node = node.Right;
                count -= sizeOfLeftSubtree+1;
            }
            else
            {
                node = node.Left;
            }
        }

        return -1;
    }

Refer : 

Find Kth largest and smallest number in BST

Algorithm : 

find(node, k) {

  if (count(node->left) + 1 == k) result = node;

  else if (count(node->left) < k) result = find(node->right, k - count(node->left) - 1);

  return find(node->left, k);

For largest element use node->right

struct tree* findkthsmallest(struct tree* t,int k)
    {
        int left_size=0;

        if(t->left!=NULL) left_size=t->left->size;

        if(left_size+1==k) return t;

        else if(k<=left_size) return findkthsmallest(t->left,k);

        else return findkthsmallest(t->right,k-left_size-1);//find k-left_size-1 smallest in right subtree.
    }

struct tree* findkthlargest(struct tree* t,int k)
    {
        int right_size=0;

        if(t->right!=NULL) right_size=t->right->size;

        if(right_size+1==k) return t;

        else if(k<=right_size) return findkthlargest(t->right,k);

        else return findkthlargest(t->left,k-right_size-1);
    }

Trie Data structure

Refer : http://linux.thai.net/~thep/datrie/datrie.html


 "Why use tries if set <string> and hash tables can do the same?" There are two main reasons:

• The tries can insert and find strings in O(L) time (where L represent the length of a single word). This is much faster than set , but is it a bit faster than a hash table.
• The set <string> and the hash tables can only find in a dictionary words that match exactly with the single word that we are finding; the trie allow us to find words that have a single character different, a prefix in common, a character missing, etc.

Refer for java program : http://www.technicalypto.com/2010/04/trie-data-structure-part-2-node-and.html

http://flexaired.blogspot.com/2009/12/flex-email-client-for-google-app-engine_13.html

http://www1bpt.bridgeport.edu/~dichter/cs201/Trie.Handout.doc



Q)best way , Memory-wise, to store 10 Crores mobile numbers ?
a trie can be considered as a tree with 26 child nodes, i.e. from 'a' to 'z'....where each node consists of a character.E.g. to represent sachin, we create a trie which has s->a->c->h->i->n,  i.e. 6 nodes. Now when we want to add sachim into the database, we just create another child node of i, which would be m. Now there are two nodes going out from i.This way we keep on adding nodes as and when required. Now to detect each word, we end the word with a spl character, which will be inserted after the last child node so that whenever we  encounter that character, we know that we have reached the end of a word.


Trie is better in terms of scalability and performance.With Hashtable,There is a problem of rehashing when all buckets are full and rehashing takes O(N).Although it happens once in a blue moon.That can impact the performance in a production environment.Trie doesn't have this problem. 
http://www.youtube.com/watch?v=uhAUk63tLRM

Difference between Tree Map and Hash Map

HashMap

HashMap allows null as both keys and values. HashMap is useful when we need to access the map without cosidering how they are added to the map (means, unordered lookup of values using their keys). HashMap is synchronized while it is being looked up. HashMap doesn’t allow duplicated entries.

The performance of HashMap is based on two optional parameter which we can specify during the creation of the HashMap. Initial capacity & load factor. Initial capacity is the bucket size assigned to a HashMap during it’s creation. Load factor decides when the HashMap needs to be expanded. If the load factor is 0.75, the size will be increased when the current size of the map crosses 75% of its capacity.

TreeMap

The basic difference between HashMap & TreeMap is that, in a TreeMap the elements are stored in a tree. TreeMap allows us to retrieve the elements in some sorted order defined by the user. So we can say that TreeMap is slower than HashMap. This is the only implementation based onSortedMap interface.

TreeMap allows us to specify an optional Comparator object during its creation. The keys should be compatible with the comparator specified. This comparator decides the order by which the keys need to be sorted.

If we are not specifying the comparator, TreeMap will try to sort the keys in the natural order. Means will consider them as instances of Comparable interface.

A common mistake that everyone does is not to override the hashcode(). If we are failing to do so, map.get(new MyCustomKey(<value>)); may not give you what you were expecting. So it is always adviced to override the hashCode() if objects of that class is being used as a key.

Shell sort

Refer : http://education.cdacmumbai.in/education/pgdst/dsalfac/notes/ShellSort.pdf


Shellsort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared.

Shellsort makes multiple passes through a list and sorts a number of equally sized sets using the insertion sort.

Shellsort improves on the efficiency of insertion sort by quickly shifting values to their destination.

Shellsort is also known as diminishing increment sort.

The distance between comparisons decreases as the sorting algorithm runs until the last phase in which adjacent elements are compared

After each phase and some increment   hk, for every i, we have a[ i ] ≤ a [ i + hk ] all elements spaced hk apart are sorted.

The file is said to be hk – sorted.

Advantages :

Advantage of Shellsort is that its only efficient for medium size lists. For bigger lists, the algorithm is not the best choice. Fastest of all O(N^2) sorting algorithms.

5 times faster than the bubble sort and a little over twice as fast as the insertion sort, its closest competitor.

Disadvantages :

Disadvantage of Shellsort is that it is a complex algorithm and its not nearly as efficient as the merge, heap, and quick sorts.

The shell sort is still significantly slower than the merge, heap, and quick sorts, but its relatively simple algorithm makes it a good choice for sorting lists of less than 5000 items unless speed important. It's also an excellent choice for repetitive sorting of smaller lists.

Best Case: The best case in the shell sort is when the array is already sorted in the right order. The number of comparisons is less.

Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour

Bucket sort works as follows:

1. Set up an array of initially empty "buckets."
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

Optimizations         

A common optimization is to put the elements back in the original array first, then run insertion sort over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.

Comparision with other sorting techniques:

1.Bucket sort can be seen as a generalization of counting sort; in fact, if each bucket has size 1 then bucket sort degenerates to counting sort.

2.Bucket sort with two buckets is effectively a version of quicksort where the pivot value is always selected to be the middle value of the value range. While this choice is effective for uniformly distributed inputs, other means of choosing the pivot in quicksort such as randomly selected pivots make it more resistant to clustering in the input distribution.

3.The n-way mergesort algorithm also begins by distributing the list into n sublists and sorting each one; however, the sublists created by mergesort have overlapping value ranges and so cannot be recombined by simple concatenation as in bucket sort. Instead, they must be interleaved by a merge algorithm. However, this added expense is counterbalanced by the simpler scatter phase and the ability to ensure that each sublist is the same size, providing a good worst-case time bound.

4.Top-down radix sort can be seen as a special case of bucket sort where both the range of values and the number of buckets is constrained to be a power of two. Consequently, each bucket's size is also a power of two, and the procedure can be applied recursively. This approach can accelerate the scatter phase, since we only need to examine a prefix of the bit representation of each element to determine its bucket.

Java code :

import java.util.ArrayList;
import java.util.Arrays;


public class BucketSort {


public static void main(String args[]) {


Double[] array = { 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0 };


ArrayList<Double> masterlist = new ArrayList<Double>(Arrays
.asList(array));


// all of the doubles will be 0.0 <= x < 100.0
double rangeOfBucket = 100.0 / masterlist.size();


// creating a new ArrayList of n buckets
ArrayList[] buckets = new ArrayList[masterlist.size()];
buckets = fillBuckets(buckets);


double d;
for (int i = 0; i < masterlist.size(); i++) {
d = (Double) masterlist.get(i);
// this mess discovers the appropriate bucket and dumps d in it
buckets[(int) (d / rangeOfBucket)].add(d);
}


masterlist = new ArrayList<Double>();


for (int m = 0; m < buckets.length; m++) {
buckets[m] = insertionSort(buckets[m]); // sort the bucket
for (int n = 0; n < buckets[m].size(); n++) {
masterlist.add((Double) buckets[m].get(n));// reading the
// numbers back into
// the original list
// in order
}
}


System.out.println(masterlist.toString());


}


/**
* Modified version of InsertionSort found at
* http://www.samspublishing.com/articles/article.asp?p=31526&seqNum=4&rl=1
* 
* @param a
*            The ArrayList to be sorted
* @return A sorted ArrayList
*/
public static ArrayList insertionSort(ArrayList a) {


int in, out;


for (out = 1; out < a.size(); out++) {
double temp = (Double) a.get(out); // remove marked item


in = out; // start shifts at out


// until one is smaller,
while (in > 0 && (Double) a.get(in - 1) >= temp) {
a.set(in, a.get(in - 1));// shift item right
in--; // go left one position
}


a.set(in, temp); // insert marked item
}


return a;
}


/**
* Helper method to fill an array of ArrayLists with _unique_ ArrayLists,
* something that Arrays.fill() does not do.
* 
* @param b
*            The array of ArrayLists to be filled
* @return The original array filled with empty ArrayLists
*/
private static ArrayList[] fillBuckets(ArrayList[] b) {
for (int i = 0; i < b.length; i++) {
b[i] = new ArrayList();
}
return b;
}


}