Median and Order statistics

Finding kth median in linear time

The idea is to partition the array we do in quick sort.  Assuming a 0 based index the item that you are looking for is positioned at k-1  if the array is ordered. Here is how we can find that element. First partition the array using a pivot (the pivot partitions the array into two parts; the elements on the left are smaller than the pivot element and elements on the right are greater than the pivot element).  Lets say the pivot index is i. if i equals k-1 then it is your median. Otherwise check if k-1 is less than  i. If it is  then repeat the same process for elements from 0 to i - 1 else repeat the process for elements from i + 1 to the end of partition that you are working on. As we chose the pivot randomly this algorithm would take expected linear time.

Here is the code that implements the above algorithm.

int find_kth_median(int x[],int start, int end, int k) {

 int pivot =  start + ((float)rand() - 1)/INT_MAX * (end - start +1);
 int a = x[pivot];

 int up = end, down = start;
 while(down < up) {

  while(x[down] <= a && down <= end)
   down++;
  while(x[up] > a)
   up--;
  if(down < up) {
   std::swap(x[up], x[down]);
  }
 }

 x[start] = x[up];
 x[up] = a;

 if (up == k-1)
  return x[up];
 else if (up < k-1) 
  return find_kth_median(x,up+1, end, k);
 else
  return find_kth_median(x, start, up -1, k);
}

Here are some of the questions that are similar to the above question:

Given an algorithm that finds median in linear time. How would you find kth element ?

Use the technique above. The idea is simple: find the median of the whole array ( the array will be partitioned around the media). Say the median index is i. Then if k is greater than i repeat the process on the right side of the array else repeat on the left side. Continue until you find the median.

Given a set of elements divide the set into k equal parts

The idea is to find the median of the whole set and then find median of the set at the left and right of the median and then continue so on. This requires O (n log k).

Java Language Concepts

What's the difference between abstract classes and interface?

interface can only have method signatures on it. It can't have implementations(body of methods) but abstract classes can have implementations. A class can be labeled as abstract even if no methods in the class are abstract. Abstract classes cannot be instantiated. If all the methods in a class are abstract it behaves like interface. Is it? Then why do we need interface? Only limitation of abstract classes is that they are classes which means we cannot extend from more than one abstract class.

What is the difference between static and not static methods?

Static methods can be accessed using class name while non static method requires instance of the class to access it. Both static and non static methods have single copy in the application. So under the hood what is the difference? One important distinction is that static methods cannot be virtual. Other is that static methods don't have access to this pointer. Non static methods take the object (on which it is called as argument). Static and non static methods look like this:

class X {

public static void staticMethod() {

//do sth
}

public void nonStaticMethod() {
//do sth
}
}

Under the hood the compiler generates method like this:

public void staticMethod() {
//do sth
}

public void nonStaticMethod(X this) {
//do sth
}

What is the difference between Comparable and Comparator ?

Comparable can be implemented by any class that requires ordering. compareTo method of the Comparable interface takes another object to which the current object is compared. For example you might have Person object and you have implemented Comparable to compare those objects using the first name and last name. But later your need changes and you have to order person objects based on their address. In this case, with Comparable, you have to change the implementation. You might not want to do that because you might need sorting using first name and last name in other places.So in that case you can always use Comparator interface. The sort method of Collections class can also take Comparator as argument. This helps you sort objects based on your needs. With comparable you are stuck to one implementation.

When do you have to override hashcode method?

When you will be using a hashed container to put your objects in, you need to override hashcode. If you override equals it's always good to override hashcode too. The hashcode provided by Object class in Java Language takes memory address of the object as hashcode. This is not what we want with our objects. For example consider following example:

class Person {

private String name;
private String dob;

public Person(String name, String dob) {
   this.name = name;
   this.dob = dob;
}
public boolean equals(Object obj) {
//implementation
}

//..


public static void main(String[] args) {

   Set<Person> persons = new HashSet<Person>();
  Person p1 = new Person("Person1", "12/12/2008");
  
   
  persons.add(p1);

 Person p2 = new Person("Person1", "12/12/2008");
  if(persons.contains(p2)) {
     //do sth
   }
    
}   
}

I am assuming here that person with same name and Date of Birth are equal. Do you think the condition will be true? Not necessarily. It's because the two person objects might get mapped into two different buckets in the hashset. Unless we return same hashcode for two equal objects there is no guarantee that the objects can be located in the hashed containers. So keep in mind that whenever you override equals you should override hashcode and two equal objects should always return same hashcode.

finally in C/C++

If you have programmed in C/ C++ you know there is no such thing as finally in C/C++. If you have used Java you know how convenient it is with finally to handle resources in code that is exception prone. There is a pretty nice and clean way to simulate finally in C++ (using destructors) but C doesn't have nice and clean way to do it. I am not sure if it is the recommended approach as it utilizes goto keyword. Since I started programming, I have been told not to use goto. Even while I read books i find authors ranting about use of goto. But here is a technique in C that simulates finally using goto.

void do_sth() {

   int *arr1 = 0,*arr2 = 0, * arr3 = 0;

   //calling function on will return error code, 0 being success
   // and other values a failure
   arr1 = (int *)malloc(100 * sizeof(int));
   if(!arr1)
      goto finally; // u wud have free(arr1) without finally
  
   arr2 =(int*) malloc(100 * sizeof(int));
 
   if(!arr2)
     goto finally; //u wud have free(arr1) and free(arr2) without finally

   arr3 =(int*) malloc(100 * sizeof(int));

   if(!arr3)
      goto finally; //u wud have free(arr1) and free(arr2) and free(arr3) without finally

 //do sth here 

   finally:
     free(arr1);
     free(arr2);
     free(arr3);
}

This is a simple example showing how you can handle exceptions in memory allocation. This makes sure that everything is freed when function exists and makes code lot cleaner. The resource allocation used here was simple. For example if you were opening 3 files instead. How would the code ? You would probably check if the file handle is valid in finally and if it is valid you would close them. The main advantage of this approach is that your resource handling code is localized. it's not spread over places and also you would write less code with this approach.

Now how would you do same thing in C++? Well C++ has facility for destructor which can do the job for you. When the object goes out of scope, the resource is cleaned up. There are lots of examples in C++ standard library. For example, instead of using dynamic arrays as shown above in C code, you could use std::vector in C++ which takes care of freeing the resources itself. Also there is std::auto_ptr which can be used for exception prone code. Of course auto_ptr doesn't support arrays.For supporting arrays you can use equivalent of boost's scoped_array.

Producer Consumer Problem

Well this is one of the frequently asked questions. It's a good way to see how much you understand multithreading. The solution is pretty simple but it's always good to understand the subtleties. The code would look something like this:

 
public void produce() {

  synchronized(queue) {

      while(queue.isFull()) {
      queue.wait();
      }

  //produce
  queue.enqueue(someObj);

  queue.notifyAll();
  }
}




public void consume() {

  synchronized(queue) {
 
     while(queue.isEmpty()) {
     queue.wait();
     }

  //consume
  someObj = queue.dequeue();
  //do something with the object

  queue.notifyAll();
  }

}

The code is pretty simple but even there are things where people get confused easily. First of all both the producer and consumer should synchronize on same object. Beginners tend to forget that. Also notice the use of while loop, when required conditions haven't been met threads are made to wait. A while loop is needed because we are using notifyAll here.notifyAll wakes up all the threads waiting on an object but only one thread will be able to obtain the lock. So in this case only one thread is allowed to proceed and others go back to wait. Another question arising in the context is the placement of notifyAll. Does it have to be the last statement inside synchronize block? The answer is no. It doesn't matter where you keep the notifyAll till it is inside synchronize block. The lock will only be released when synchronize block is escaped.

Recommendation

Never try to do produce consumer problem this way in production code. Always try to use the concurrent collections or facilities provided by the Java Language. For example, you could have used BlockingQueue rather than hand coding the program above.

Conversion from infix to postfix

Converting a given infix expression to postfix expression is used when numerical expressions are evaluated. Given an expression like A+B*C, the problem is to convert it into expression ABC*+. This is quite a simple problem and involves use of a stack. The idea is to add every digit encountered into postfix string. A stack is used to store operators. Whenever an operator is encountered, if it is of lower precedence than the operator on top of stack then the stack is popped and the operator is added to the postfix string. The popping is continued until the stack is empty. This is a pretty simple problem and the code is given below:

//returns true if stk precedes infix
bool precedes(char stk, char infix) {

 //declare an array of operators in precedence order
 //considers only 4 operators now
 static char prec[] ={'/','*','+','-'};

 //check for precedence
 for(int i = 0; i <4; i++) {
  if(prec[i] == stk)
   return true;
  if(prec[i] == infix)
   return false;

 }
}

//convert to postfix
std::string postfix(const std::string &infix) {

 int i = 0;

 //operator stack
 std::stack<char> op_stack;
 std::string post_fix;
 while(i < infix.length()) {

  //if it is a digit add it to postfix 
  if(isdigit(infix[i]))
   post_fix.append(1,infix[i]);
  else {

   //if operator at the top of stack 
   //precededs current operator
   //pop the operator and add it to 
   //the post fix string
   //repeat this until stack is empty
   //or operator at top of stack 
   //doesn't have higher precedence
   while(!op_stack.empty() && 
    precedes(op_stack.top(),infix[i])) {
    post_fix.append(1, op_stack.top());
    op_stack.pop();
   }
   
   //push the current operator
   op_stack.push(infix[i]);
  }
  i++;
 }

 //add everything to the post fix string
 while(!op_stack.empty())
 { 
  post_fix.append(1, op_stack.top()); 
  op_stack.pop();
 }
 return post_fix;
}

Number base conversion and arithmetic

Perhaps most of us came across base conversions when we were in high school. It's pretty easy to convert numbers from and to decimal if we remember 2 simple rules. If we desire to convert from/to base b to/from decimal we can use following rules:

Conversion from decimal to base b

Divide the given decimal number by b and store the remainder in a string. Keep on dividing until we the number can be divided no more.

num be the given decimal number

digit[i] = (num /b ^ (i+1)) % b.

resulting number in base b is digit[0] digit[1] ...digit[n-1].

Conversion from base b to decimal

num be the given number in base b and n be the number of digits

decimal = digit[n - 1] * b ^ (n -1)+...+digit[i] * b ^ (i) + digit[1] * b^1 + digit[0] * b^0


These 2 techniques are sufficient to convert between numbers in any bases.
Lets say you want to convert a number from base x into base y. To solve this you can convert base x into decimal and then convert the decimal into base y. These 2 techniques are easily transformed into programs. But it might not be a good idea to use these techniques when bases are power of 2. If bases are power of 2, bit manipulation techniques can be applied to convert. For example for converting from decimal to hex, it's always lot faster to take 4 bits at a time and convert them to hexadecimal. For example if given number is 35 (00100011, take 4 rightmost bits (0011) which is 3 and again take next 4 bits(0010) which is 2. Thus the Hex number for this is 23. This is likely to be faster than division.

Arithmetic

How would you add/subtract or do some other arithmetic operations on 2 numbers in base b? The simple idea is to convert the numbers into decimal and do the operation and then convert the resulting number back to b. The operation can be implemented for the given base itself but requires significant effort than the conversion technique.

Web Application Performance Improvement

When a web application is accessed by few users the performance may not be a huge problem but as the numbers of users grow it might bring your application to a halt if not designed properly with scalability in mind.It's always good to start out by profiling the application first. The profiling can give you insight on the piece of code that is expensive. A piece of code that is expensive might not necessarily be the main culprit. Always look for the piece of code that is extensively called. For example you might have one method that takes 2 seconds to run and then the other method that takes 200 ms. First intuition might be to make the first method efficient. But it might be the case that your application calls the method 1 or 2 times whereas it calls the second method thousands of time. In this case it's always good to optimize the second method.

Connection Pooling

If your application accesses database a lot make sure you are using connection pooling. And also consider using Stored Procedure if you need to filter results or make multiple requests to the database in the same code path.

Caching

If results can be reused across multiple requests, it's always a good idea to employ cache.

Compression

Make sure server supports compression and is using it to send results. This decrease communication time.


Clustering

Use server cluster for your application.

Resource contention

Minimize resource contention because if lot of requests are competing for same resource they degrade performance and hinder scalability. For example servlet is a shared resource and having synchronized method in servlets may cause scalability problems.

Memory Usage

Watch memory usage of your applications and try to reduce unnecessary memory usage.Use of large amount of memory might trigger garbage collector frequently which uses precious CPU time which could have been used for serving users.