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.

Designing Cache

Cache is one very important concept in computer science. It is one design technique that is likely to help you when your system is thwarted by performance problems. Give this it is highly likely that at some point in your life as a Software Guy you have to design a cache. Cache generally employs multiple data structures for efficiency. Cache has limited space to store data so depending on your application you might have to chose a replacement policy. Ideally you would want to throw the element that would be unused to make room for new elements. But our world is not perfect and we have no way of knowing which element is likely to be unused in the future. The best thing we can do is to make a guess based on our application or may be log the usage statistics and fine tune the cache. Based on the replacement policy we can design caches in different ways.

LRU Cache

LRU cache is the simple cache where the least recently used item is thrown off the cache to make room for new one. As cache requires fast lookup we can always rely on hashtable for fast lookup. But how can we find least recently used item in Hashtable? We can't. So we need to find some other data structure that does it effectively. Why not use a queue? Whenever element is accessed put it on the tail. So front of the queue will be the least recently used one. Cool but we cannot access elements randomly from the queue. Queue is a data structure where you can remove element from the front and put the element from the back. To be able to access element anywhere we can use LinkedList. This solves the problem pretty effectively. SO here is the simple design: Create Node class that holds cache key and data. This node will be node of the linked list and also based on the key, it is inserted into hastable. We can use pointers so that both hashtable and Linked List point to same node. Lookup will require looking up in the hastable, if the data is not there and cache is full then remove the first element from the linked list and fetch new element and put it in back of the list. If cache is not full and data is there simply put the Node to the back of the list. The operations are quite simple.

MRU Cache
The neeed of this kind of cache may not arise that often but it can be implemented similarly as before but you can remove the tail of the list to remove most recently used item.

LFU cache
Least frequently used cache. This is quite difficult to design because we need to keep count of the accesses of each entry in cache. Here is my idea: Use Binary Search Tree with frequency of access as key and Hashtable for fast lookup. For lookup, if entry is in the cache, take the entry Node , delete it from the BST, increase its frequency and reinsert it into BST. While replacing the entry chose the leftmost element.

There are different other schemes. I would also like to hear from readers about these schemes and their solution.

Reversing a Linked List

I heard this is one of the most frequently asked questions in an interview. It seems to be asked quite a lot in phone screens. May be because it's simple, gives a good idea whether you have grasp of pointers and whether you have an idea of basic data structure (Of course linked list). There are 2 ways to approach this problem. The first one is recursive. But you might not want to come up with recursive solution during interview unless interviewer explicitly directs you to do so. Why? Because recursion is slow and takes up lot of memory if linked list is long. The second solution is also obvious. You go through each node in the list and adjust the pointers. Before proceeding it might be wise to ask the interviewer whether it's an singly or doubly linked list. Here we assume it's a singly linked list. The code is given below.

Node* reverse_list(Node *head) {
if(head == NULL)
return;

Node *current = head, *temp, *new_list = 0;

while(current != 0) {
temp = current->next;
current->next = new_list;
new_list = current;
current = temp;
}

//return new head
return new_list;

}

Young Tableau

Young tableau consists of rows and columns of numbers in the form of a matrix. The special property of young tableau is that its rows and columns are sorted. Young tableau can also function as a min heap. There are different interesting algorithms relating to young tableau.

Example of young tableau.

1 2 3
4 6 7
5 7 12

It's clear from the example that each row and column is sorted.

Here is one interesting problem on Young Tableau: How to find an element in an Young Tableau?

Naive search on the table would require O(mn) time. Where m is the number of rows and n is the number of columns. Can we do bit better? Turns out we can. The trick is to start from the top right corner> if the element we are searching for is greater we move down in the column. If the element we are searching for is smaller we move left in the row. We repeat the procedure until we find the element or we end up in a row or column beyond the table. This would translate to a simple code below:

The example assumes 3 X 3 matrix for simplicity. row is the number of rows and col is the number of columns in the matrix and n is the element being looked for.

int find_n(int x[][3],int row, int col, int n) {

 int r =0 , c = col -1;
 while( r < row && col >=0) {
  if(x[r][c] == n)
   return n;
  else if ( x[r][c] > n)
   c--;
  else
   r++;
 }
 return -1;
}

Another problem in Young Tableau is extracting minimum element. The minimum element is the element in (0,0) position. The main problem is replacing the spot (0,0) after minimum element has been removed. The code is given below (sorry that i have it in Java because I did these two things separately but still i believe it is simple enough so i thought it was not necessary to put both of these in same language)

/*
a is young tableau, i and j are current position in the tableau that we are filling
m and n are number of rows and column
*/
void youngify(int[][] a, int i, int j, int m, int n) {
  if (i > m || j > n)
   return;

  int x = -1, y = -1;

  if (i + 1 < m && a[i + 1][j] < a[i][j]) {
   a[i][j] = a[i + 1][j];
   x = i + 1;
   y = j;

  }
  if (j + 1 < n && a[i][j + 1] < a[i][j]) {
   a[i][j] = a[i][j + 1];
   x = i;
   y = j + 1;
  }

  if (x != -1) {
   //the empty space is filled with marked
   //by maximum value a integer can hold
   a[x][y] = Integer.MAX_VALUE;
   youngify(a, x, y, m, n);
  }

 }

Inserting an element into non full young tableau follows the similar process as extracting minimum element. The idea is to put the element into last row and column and move it upto the position where is should be.

Sorting can also be implemented for n X n young tableau in O(n ^3) time by using the operation by which we extract minimum element. The idea is to extract minimum element which takes O(n+n) = O(n) time, IF we repeat this for n^2 element it will take O (n ^3)time.

Finding overflows during arithmetic operations

We know that data in computers have limited size. For example, integer may be limited to 4 bytes. So, while writing programs sometimes we might need to check for overflows to make sure that the resulting value fits the size. But finding overflows are easy.

Finding overflow during addition

Lets say you are adding number a and b. Lets say maximum value that the types of a and b can hold be MAX. Then we can check for overflow using following condition:

if ( (MAX - a) < b then the result overflows else not.

Finding overflow during multiplication

One example of its use is while computing factorial. Lets say you want to compute n!. But you also want to make sure that appropriate error is thrown when it overflows. This is also quite simple. Lets say again that the maximum value a data type can hold be MAX and you are multiplying a and b. The result overflows if MAX/a < b.

Finding median or Kth element in Binary Search Tree (BST)

Finding kth element in BST is quite simple. We know that all the elements in left subtree is smaller than all the elements in right subtree. If we count the number of elements in left and right subtree then we know in which subtree the required element exists and then we move to this subtree and repeat the same steps again. For example starting from root we are looking for 11th element. Lets say left subtree has 7 elements and right subtree has 6 elements.Then as the number 11 is greater than 7 we know that the 11th median exists in the right subtree. Now in the right subtree we look for (11 - 7 -1 = 3)rd element (Why?? because we have discarded left subtree). We proceed similarly in the new subtree until we get the kth median as the root.

The example described above can very well be described in recursive form. The code below is a complete program in recursive form.

  
 //find kth element in a BST recursively
Node * find_kth_element(Node *tree, int &k) {

 if(tree == 0)
  return 0;

 int count = 0;

 //count the nodes in left subtree
 count_nodes(tree->left_, count);

 //check if the root is median
 if( k == count + 1)
  return tree;

 //check if median falls on left subtree
 else if (count >= k) {

  return find_kth_element(tree->left_,k);
 }
 //the median falls on right subtree
 else {
  k = k - (count + 1);
  return find_kth_element(tree->right_, k);
 }
}

Iterative Solution

We know that recursive solutions are not that efficient and it's always good to avoid it if it's possible. The problem however is equally simple in iterative form as well. The code below translates recursive form into iterative form.

  
 

//find kth element iteratively
Node * find_kth_element_iterative(Node *tree, int &k) {
 if(tree == 0)
  return 0;

 Node *node = tree;
 int count = 0;
 int pos = k;


 while(node != 0) {
  count = 0;

  //count nodes on the left subtree
  count_nodes(node->left_, count);

  //check if root is the median
  if( pos == count + 1)
   return node;

  //check if median falls on left subtree
  else if (count >= pos)
   node = node->left_;

  //median falls on right subtree
  else {
   pos -= (count + 1);
   node = node->right_;
  }

 }
 return 0;
}

Complexity

What's the complexity of above algorithms? While finding median You are moving along a path in the tree, so in the worst case it can be height of the tree (h) and also you are counting the number of nodes in left subtree at each step. Which requires O(n) time in the worst case. Thus the overall algorithm is O(nh).

Is there a way to improve it? Yes, of course ( at least one technique I know of). If you need to keep on computing the kth median on a single tree many times, then you can construct a tree with a count of elements in its subtree. If you do this the counting of number of nodes in left subtree takes O(1) time. Effectively the algorithm will reduce to O(h) algorithm. In case tree is balanced this is just O(log n). Not bad :).