Heap Sort

public class HeapSort {

public static void main(String[] args) {
int a[] = {1,2,3,4,5,6,7,8,9,11,10,13,12,11,10};
heapsort(a);
       for(int b :a)
      System.out.println(b);
}

public static void heapsort(int[] a){
int temp;
int currRoot = 0;
buildmaxHeap(a);
int heapSize = a.length-1;
for(int i = a.length-1;i>0;i--) {
temp = a[i];
a[i] = a[0];
a[0] = temp;
heapSize--;
maxHeapify(a,currRoot,heapSize);
}

}

public static void buildmaxHeap(int[] a){
for(int i = (int) Math.ceil((a.length-1)/2); i>=0;i--)
maxHeapify(a,i,a.length-1);
}


public static void maxHeapify(int[] a,int currRootIndex,int heapSize) {
int largest,temp;
int  leftIndex = 2* currRootIndex + 1;
int rightIndex = 2* currRootIndex + 2;
if(leftIndex <= heapSize && a[leftIndex] > a[currRootIndex])
largest = leftIndex;
else
largest = currRootIndex;
if(rightIndex <= heapSize && a[rightIndex] > a[largest])
largest = rightIndex;
if(largest != currRootIndex){
temp = a[currRootIndex];
a[currRootIndex] = a[largest];
a[largest] = temp;
maxHeapify(a, largest, heapSize);
}
}
}

Quick Sort

public class Quick {

  public static void main(String[] args) {
 
     int[] a = {3,2,5,1,7,8,10};
     quick(a,0,a.length-1);
     for(int b : a)
        System.out.println(b);
  }

  public static int partition(int[] a, int p, int q){
    int pivot = a[p];
    int temp;
    int i = p;
    for(int j = p+1;j<a.length;j++) {
       if(a[j]<=pivot){
         temp=a[i+1];
         a[i+1]=a[j];
         a[j] = temp;
         i++;
       }
    }
    temp = a[i];
    a[i] = a[p];
    a[p]=temp;
    return i;
  }

  public static void quick(int[] a, int p, int q) {
    if(p<q) {
      int r = partition(a,p,q);
      quick(a,p,r-1);
      quick(a,r+1,q);
    }
  }

  }

Insertion Sort

public static int[] insertion(int[] a){
int key;
for(int j=1;j<a.length;j++ ) {
key=a[j];
  int i=j-1;
while(i >= 0 && a[i] > key){
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
return a;
}

Abstract Class and Interface

What are the differences between Interface and Abstract class?

Abstract Class	Interfaces
An abstract class can provide complete, default code and/or just the details that have to be overridden.	An interface cannot provide any code at all,just the signature.
In case of abstract class, a class may extend only one abstract class.	A Class may implement several interfaces.
An abstract class can have non-abstract methods.	All methods of an Interface are abstract.
An abstract class can have instance variables.	An Interface cannot have instance variables.
An abstract class can have any visibility: public, private, protected.	An Interface visibility must be public (or) none.
If we add a new method to an abstract class then we have the option of providing default implementation and therefore all the existing code might work properly.	If we add a new method to an Interface then we have to track down all the implementations of the interface and define implementation for the new method.
An abstract class can contain constructors .	An Interface cannot contain constructors .
Abstract classes are fast.	Interfaces are slow as it requires extra indirection to find corresponding method in the actual class.

When should I use abstract classes and when should I use interfaces?

Use Interfaces when…

• You see that something in your design will change frequently.
• If various implementations only share method signatures then it is better to use Interfaces.
• you need some classes to use some methods which you don't want to be included in the class, then you go for the interface, which makes it easy to just implement and make use of the methods defined in the interface.

Use Abstract Class when…

• If various implementations are of the same kind and use common behavior or status then abstract class is better to use.
• When you want to provide a generalized form of abstraction and leave the implementation task with the inheriting subclass.
• Abstract classes are an excellent way to create planned inheritance hierarchies. They're also a good choice for nonleaf classes in class hierarchies

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

One solution is to use two priority heaps: a max heap for the values below the median, and a min heap for the values above the median. The median will be largest value of the max heap.
When a new value arrives it is placed in the below heap if the value is less than or equal to the median, otherwise it is placed into the above heap. The heap sizes can be equal or the below heap has one extra. This constraint can easily be restored by shifting an element from one heap to the other. The median is available in constant time, so updates are O(lg n).

1       private Comparator<Integer> maxHeapComparator, minHeapComparator;
2       private PriorityQueue<Integer> maxHeap, minHeap;
3       public void addNewNumber(int randomNumber) {
4              if (maxHeap.size() == minHeap.size()) {
5                      if ((minHeap.peek() != null) &&
6                               randomNumber > minHeap.peek()) {
7                               maxHeap.offer(minHeap.poll());
8                               minHeap.offer(randomNumber);
9                      } else {
10                              maxHeap.offer(randomNumber);
11                     }
12             }
13             else {
14                     if(randomNumber < maxHeap.peek()){
15                              minHeap.offer(maxHeap.poll());
16                              maxHeap.offer(randomNumber);
17                     }
18                     else {
19                              minHeap.offer(randomNumber);
20                     }
21             }
22      }
23      public static double getMedian() {
24             if (maxHeap.isEmpty()) return minHeap.peek();
25             else if (minHeap.isEmpty()) return maxHeap.peek();
26             if (maxHeap.size() == minHeap.size()) {
27                     return (minHeap.peek() + maxHeap.peek()) / 2;
28             } else if (maxHeap.size() > minHeap.size()) {
29                     return maxHeap.peek();
30             } else {
31                     return minHeap.peek();
32             }
33      }

Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

First, create a suffix tree for s. For example, if your word were bibs, you would create the following tree:
                                                             I               S
                                            B
                                     I                               B
                                                    S
                             B                                              S
                     S
Then, all you need to do is search for each string in T in the suffix tree. Note that if “B” were aword, you would come up with two locations.

1        public class SuffixTree {
2                SuffixTreeNode root = new SuffixTreeNode();
3                public SuffixTree(String s) {
4                         for (int i = 0; i < s.length(); i++) {
5                               String suffix = s.substring(i);
6                               root.insertString(suffix, i);
7                         }
8                }
9           
10               public ArrayList<Integer> getIndexes(String s) {
11                        return root.getIndexes(s);
12               }
13       }
14   
15       public class SuffixTreeNode {
16               HashMap<Character, SuffixTreeNode> children = new
17                                                                 HashMap<Character, SuffixTreeNode>();
18               char value;
19               ArrayList<Integer> indexes = new ArrayList<Integer>();
20            public SuffixTreeNode() { }
21        
22            public void insertString(String s, int index) {
23                   indexes.add(index);
24                   if (s != null && s.length() > 0) {
25                           value = s.charAt(0);
26                           SuffixTreeNode child = null;
27                           if (children.containsKey(value)) {
28                                   child = children.get(value);
29                           } else {
30                                   child = new SuffixTreeNode();
31                                   children.put(value, child);
32                           }
33                           String remainder = s.substring(1);
34                           child.insertString(remainder, index);
35                   }
36            }
37        
38            public ArrayList<Integer> getIndexes(String s) {
39                   if (s == null || s.length() == 0) {
40                           return indexes;
41                   } else {
42                           char first = s.charAt(0);
43                           if (children.containsKey(first)) {
44                                   String remainder = s.substring(1);
45                                   return children.get(first).getIndexes(remainder);
46                           }
47                   }
48                   return null;
49            }
50     }
51   
52     public class Question {
53            public static void main(String[] args) {
54                   String testString = “mississippi”;
55             String[] stringList = {“is”, “sip”, “hi”, “sis”};
56             SuffixTree tree = new SuffixTree(testString);
57                   for (String s : stringList) {
58                  ArrayList<Integer> list = tree.getIndexes(s);
59                  if (list != null) {
60                             System.out.println(s + “: “ + list.toString());
61                  }
62                   }
63            }
64     }

Write a function that adds two numbers. You should not use + or any arithmetic op- erators.

      int add_no_arithm(int a, int b) {
2            if (b == 0) return a;
3            int sum = a ^ b; // add without carrying
4            int carry = (a & b) << 1; // carry, but don’t add
5            return add_no_arithm(sum, carry); // recurse
6     }