Sample Programs for Java Interviews-Series 1

Bubble Sort:

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

Sample Program:

package sortings.BubbleSort;  
 public class BubbleSortExample {  
      public static void main(String a[]) {  
           int i;  
           int array[] = { 12, 9, 4, 99, 120, 1, 3, 10 };  
           bubble_srt(array, array.length);  
           System.out.print("Values after sorting: ");  
           for (i = 0; i < array.length; i++)  
                System.out.print(array[i] + " ");  
      }  
      public static void bubble_srt(int a[], int n) {  
           int i, j, t = 0;  
           for (i = 0; i < n; i++) {  
                for (j = 1; j < (n - i); j++) {  
                     if (a[j - 1] > a[j]) {  
                          t = a[j - 1];  
                          a[j - 1] = a[j];  
                          a[j] = t;  
                     }  
                }  
           }  
      }  
 }  

Output:

Values after sorting: 1  3  4  9  10  12  99  120


Fibonacci Series:

The Fibonacci sequence is a set of numbers that starts with a one or a zero, followed by a one, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers. If the Fibonacci sequence is denoted F ( n ), where n is the first term in the sequence, the following equation obtains for n = 0, where the first two terms are defined as 0 and 1 by convention


F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Sample Program:

package ramesh.programming;  
 public class FibonocciExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           int n = 15;  
           int f1, f2 = 0, f3 = 1;  
           System.out.println(f2);  
           for (int i = 1; i <= n; i++) {  
                System.out.print(" "+f3);  
                f1 = f2;  
                f2 = f3;  
                f3 = f1 + f2;  
           }  
      }  
 }  

Output:  1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Fibonacci using recursive method:

package ramesh.programming;  
 public class FibonocciRecursive {  
      /**  
       * @param args  
       */  
      public static long fib(long num) {  
           if (num <= 1) {  
                return num;  
           }  
           return fib(num - 1) + fib(num - 2);  
      }  
      public static void main(String[] args) {  
           long n = 15;  
           for (int i = 1; i <= n; i++) {  
                System.out.print(fib(i)+"");  
           }  
      }  
 }  

Output: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 

Reverse a Number:

This is a sample program to reverse a given integer number

package ramesh.misc;  
 /**  
  * @author RameshM  
  * A sample program for reversing a given integer number  
  */  
 public class ReverseIntegerNumber {  
      public int reverseNumber(int number) {  
           int reverse = 0;  
           while (number != 0) {  
                reverse = (reverse * 10);  
                reverse = reverse + (number % 10);  
                number = number / 10;  
           }  
           return reverse;  
      }  
      public static void main(String a[]) {  
           ReverseIntegerNumber reverse = new ReverseIntegerNumber();  
           // Not handling the cases where the number is less than or equal to zero  
           // for brevity purposes.  
           System.out.println("Number after reversing: "  
                     + reverse.reverseNumber(14789));  
      }  
 }  

Output:

98741


Thanks for visiting my blog!!!!!!!!!

Select nth highest salary

This is very popular interview question asked for beginners to experienced programmers.

I will explain how we can find the nth highest salary using Oracle row_number() analytic function.

Let me first explain what is row_number() analytic function.

row_number() assign a unique number to each row to which it applied based on the order by clause(either descending order or ascending order).

By nesting a subquery using ROW_NUMBER inside a query that retrieves the ROW_NUMBER values for a specified range, you can find a precise subset of rows from the results of the inner query.

Query:

SELECT *
FROM
  ( SELECT employee.*,
           row_number() over (
                              ORDER BY employee.salary DESC) rownumber
   FROM employee employee)
WHERE rownumber=n;

As you see the above query, first we are using the inner query which assign a number for each row starting from 1. Since we are doing order by desc for the salary, the salaries will be order by highest to smallest.

Since the rows are arranged in descending order, the row with the highest salary will have a 1 for the row number.Since we know the row numbers we just pass the row number(n) and it will compare and return the result.

That's all about selecting the nth highest salary.

Thanks for visiting my blog!!!!!

Binary Search-Sample program in Java

What is Binary Search by the way?

A binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value.[1][2] For binary search, the array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.
(Source: WikiPedia)

The requirement for binary search algo is the array should be sorted.We can use Quick Sort or Merge Sort for sorting the array.First we need to take mid element(if low=0 and high=array.length-1 then mid=low+high/2).If the middle element is the one which we are searching we return the index or we just print the element is found in the array at a specified index.

Lets say the element we are searching is less than the middle element then we will take the sub array by specifying high=mid-1 or if the searching element is greater than the middle element then our sub array becomes low=mid+1.This process will continue until we found the element we are searching.

Code:

/**
 * @author RameshM
 * 
 *         Sample program for Binary Search
 */
public class BinarySearchTest {

 public static boolean searchKey(int[] intArray, int element) {

  int low = 0;
  int high = intArray.length - 1;

  while (low <= high) {
   int middle = (low + high) / 2;
   if (element > intArray[middle]) {
    low = middle + 1;
   } else if (element < intArray[middle]) {
    high = middle - 1;
   } else {
    return true;
   }
  }
  return false;
 }

 public static void main(String args[]) {

  int[] intArray = { 2, 4, 5, 8, 9, 22, 44, 55, 66, 88, 100 };

  int element = 44;

  boolean result = searchKey(intArray, element);

  if (result) {
   System.out.println("The element found in the Array");
  } else {
   System.out.println("The element is not found in the Array");
  }

 }
}

Output:

The element found in the Array