Algo #122 : ATOI

Problem Statement : 
        Implement atoi to convert string into integer.

Solution : 

Below is atoi implementation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

public static int atoi(String in) { int radix = 10; int limit = Integer.MAX_VALUE; int multiplicationLimit = limit / radix; if(in==null || (in=in.trim()).equals("")) return 0; int result=0, i =0 , len = in.length(); boolean isPositive=true; if (in.charAt(0) == '-') { i++; isPositive = false; } else if (in.charAt(0) == '+') i++; while(i<len){ char c = in.charAt(i++); if(c >= '0' && c <= '9') { int digit = (c - '0'); if(result < multiplicationLimit) result = result * radix + digit; else //result overflowing { if(isPositive) return Integer.MAX_VALUE; else return Integer.MIN_VALUE; } } else break; } if(!isPositive) result=-result; return result; } public static void main(String[] args) { System.out.println(atoi(" -88297 248252140B12 37")); System.out.println(atoi(" 75 6 ")); System.out.println(atoi("+349A756")); }

Please post comments and suggestions if any.
Happy Coding !! :)

Algo #121 : Quick Select Algorithm

Problem Statement : 
         Find the kth smallest element in an unsorted array.

Input : 
Array : [ 7 , 5 , 4 , 3, 2, 8 , 1 ]
and k= 3  (kth smallest element)

Output: 3

PS: No duplicate elements in the array

Solution : 

One of the simplest method to solve the above problem would be to sort and then find the kth smallest element. But sorting would take O(nlogn) and again O(n) to find the kth smallest element.

Now the question is can we do better than this ? Yes we can.

We can use even Min-heap to store the elements and pop k-times to get the k-th smallest element.

Quick Select Algorithm : 
In this post we will discuss Quick Select Technique which is very much similar to Quicksort.
We know that elements to the left of pivot are smaller and elements to the right of pivot are greater than pivot.

Lets take an example to demonstrate this
Array : [ 7 , 5 , 4 , 3, 2, 8 , 1 ] and k= 3
Below i will walk you through changes happening in the array , which will finally return kth-smallest element. Note we are considering the last element of the array (coloured green ) as pivot

Fig1 : Demonstration the steps on Quick Select

Below is the code implementation :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public int findKSmallest(int[] arr, int k, int l, int r) { int len = arr.length; if (k > 0 && k <= len) { int index = partition(arr, l, r); if (index + 1 == k) return arr[index]; else if (index < k) return findKSmallest(arr, k, index + 1, r); else return findKSmallest(arr, k, l, index - 1); } return -1; } private int partition(int[] arr, int l , int r){ int pivotValue = arr[r]; int storeIndex=l,i=l; for (;i < r; i++ ) { if (arr[i] <= pivotValue) swap(arr, i, storeIndex++); } if(arr[storeIndex] > arr[r]) swap(arr, r, storeIndex); //System.out.println(Arrays.toString(arr)); return storeIndex; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = {7,5,4,3,2,8,1}; int k = 3; KQuickSelect sortObj = new KQuickSelect(); int data = sortObj.findKSmallest(arr, k, 0, arr.length-1); System.out.println(data); }

PS: The above code will work fine for non-duplicate elements. For duplication elements you can use Min-Heap technique.

Please post your suggestions and comments.
Happy Coding !! :)

Algo #120 : Pallindrome Check

Problem Statement : 
         Check if a number is palindrome without extra space O(1) .

Solution : 

      One of the common ways i have seen interviewees approach to this problem is by converting it into a string , but the constraint of the problem doesn't allow you to use extra space.

Here we will use pointers to check for palindrome but without converting it into a string.

Iterative Implementation :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

boolean isPalindrome(int num) { int div = 1; if(num < 0) num = -num; for(;num/div>=10;div *=10); //div which will help in dividing below, [Note : dont Miss ';'] while (num != 0) { int leftDigit = num / div; int rightDigit = num % 10; if (leftDigit != rightDigit) return false; num %= div ; //removes left most digit num /= 10 ; //removes right most digit div /= 100; } return true; }

 Recursive Implementation :
 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/** * Recursive apporach to check if a number is pallindrome without extra space * @author prathore2 */ public class PallindromeCheck { private static int dummy = 0; public static boolean isPallindrome(int num) { dummy = num; return isPallindrome1(num); } private static boolean isPallindrome1(int num) { if (num == 0) return true; if (isPallindrome1(num / 10) && (num % 10 == dummy % 10)) { dummy /= 10; return true; } return false; } public static void main(String[] args) { System.out.println(isPallindrome(12321)); } }

Please post your comment and suggestions if any.
Happy Coding !! :)

Algo #119 : Dutch National Flag

Problem Statement: 
            Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
                                     
                                                               OR

Sort a given array consisting of 0s,1s and 2s.

Input : [ 1,2,0,2,0,1,0,2 ]
Output: [ 0,0,0,1,1,2,2,2 ]

Solution: 

  This problem is very known problem and is commonly asked in interviews and is also known as Dutch National Flag Algorithm, another variant of this problem consists of only 0s and 1s.

In this problem we will be taking up 3 pointers, the strategy behind solving this problem is to divide the array into three regions. The mid pointer traverses over the array , if  '0' is encountered swap mid and low pointer elements , if  '1' is encountered skip, if '2' is encountered swap mid and high pointer elements.

Below is the Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

int[] sort(int[] arr) { if (arr != null) { int len = arr.length; int low = 0; int mid = 0; int high = len - 1; while (mid <= high) { switch (arr[mid]) { case 0: swap(arr, mid++, low++); break; case 1: mid++; break; case 2: swap(arr, mid, high--); break; } } } return arr; } void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

Time Complexity : O(n)
Space Complexity: O(1)

Please comment and post suggestions if any.
Happy Coding :)

Algo #118: Trailing Zeros in a Factorial

Problem Statement : 
    Find the total trailing zeros in factorial of a number

Example :
Input : 5
Output = 1
Explanation:
  5! = 120 , clearly 1 trailing zero.

Solution : 
   Simple method is to calculate factorial and count number of zeros, but here calculating factorial value would overflow for larger numbers.

We can do better than this approach, since we just have to calculate the trailing zeros and we need not calculate the factorial of the number, factorial can be obtained by multiplying prime numbers and prime number 2 and 5 produces product 10.

Therefore , if we count total number of 5's we are done because we can see 2's are always in excess.
For number like 5, 10 ,15 ... they have only single 5 in them,
but for numbers like 25, 50,25 , they have double 5's in them
Similarly for numbers like 125, 250,375 will have triple 5's in them.

Therefore totals number of 5's which also equal to trailing zeros of n!
       = n/5 + n/(5^2) + n/(5^3) + .....

1 2 3 4 5 6 7

private static int trailingZeroCount(int num) { int count = 0; if(num > 0) for(int i=5;i>=1;i*=5) count += num / i; return count; }

Input : 33
Output : 7

Please comments and post suggestions if any :)
Happy Coding :)