Programming Interview - Mathematics Problems

Find all factors of the number ?

A number is always divisible by 1 and itself. The smallest factor a number can have is 2, while largest factor would be n/2. But as a * b = number n, were a and b are co-efficient, the pairs of numbers will be duplicated after a = b, i.e. square-root of n. Hence we only need to loop till square-root of n, and add both i and n/i to the list of factors.

Verify if number is a prime number ?

To verify a prime number we only need to loop through from 2 to square-root of number n. As the number n to be non-prime there must be factors "a" and "b" such that a = n / b, i.e. a * b = n. As we observe for example number 36, the factor pairs {1,36} {2,18} {3,12} {4,9} {6,6} {9,4} {12,3} {18,2} {36,1} are repeated after {6,6} which is after square-root of 36, i.e. 6. Hence after square-root of n, the numbers would be either repeated factor-pairs, multiple of other prime numbers.

Also 1 is not regarded as a prime number. 

Fibonacci Sequence

F(n) = { F(n - 1) + F(n - 2)   if n > 1

           {  n                             if n = 0,1 }

0  1  1  2  3  5  8  ...

The first two terms of the series are 0, 1.

Using Recursion: if(n <= 1)  return n;   return fibonacci(n-1) + fibonacci(n-2)

Recursion: Exponential Time

Fibonacci Sequence Recursion: O(2^n)

Iteration: Here we need three variables, the previousNumber, the currentNumber and a temp Number as we cannot assign the new value to currentNumber directly because, we have to first move currentNumber's value to previousNumber.

    System.out.print(previousNumber + ", ");

    for (int i = 1; i < n; i++) {

        newNumber = currentNumber + previousNumber;
        previousNumber = currentNumber;
        currentNumber = newNumber;

        System.out.print(currentNumber + ", ");
    }
  

Modular Exponentiation

Calculate: x^n mod M

Since integer is 32 bit, with 1 bit reserved for sign, the range of integer is -2^31 to 2^31, hence calculating x^n directly will not fit many cases within integer range.

Since (a * b) % M = {(a % M) * (b % M)} % M

x^n % M = (x * x^n-1) % M

        = {(x % M) * (x^n-1 % M)} % M

When n is even,  {(x^n/2 % M) * (x^n/2 % M)} % M

Time complexity is O(log n)

Power(x,n) i.e. x^n

x^n = { x^n/2 * x^n/2  if n is even

        x * x^n-1      if n is odd

        1              if n=0       }

To calculate the time complexity, use the variance of the number being updated and passed to the recursive function.

T(n) = T(n/2) + C

T(n) = T(n/2^k) + K*C    assuming this is done k times.

Hence k is log2(n) which is the time complexity.

Find all factors of the number:

12 = {1,2,3,4,6,12}

Trial Division were we try to divide the number with all the numbers from 1 to n itself.

But 1 and the number itself are its factors. Also since the smallest factor of the number is 2 and largest factor is n/2, there are no factors of the number above n/2. Also if a * b = n, assuming a.b are factors, then when a > sqrt n, then b < sqrt n. Further when a = sqrt n, then a = b = sqrt n. Hence only search factor till square root of number, as remaining are just number/factor.

Divide all the numbers starting from 2 to square-root of n, and add [current-no] with (n / [current-no]) to the factors list. Numbers 1 and n are already added to factors list.

Time complexity is O(sqrt n)

Prime Factorization of a number n

24 = 3 * 2 * 2 * 2

Start dividing the number n by smallest number (starting with 2) such that the remainder is 0. Continue dividing the quotient from previous division until the remainder is non-zero, then select the next number for division of the quotient. The loop continues selecting next smallest number (i) until the (i) becomes greater than square-root of quotient, which indicates that the quotient is a prime number. Since we already know that there cannot be any factors for a number (quotient here) after square-root of that number.

Time complexity is O(sqrt n)

How do implement Sieve of Eratosthenes Algorithms for Prime Number?

How to check if a given year is a leap year in Java?

How to convert a decimal number to binary in Java?

How to reverse given Integer in Java?

How to find the largest prime factor of a given integral number?

How to print Floyd’s triangle?

How to print Pascal’s triangle? (solution)

How to calculate the square root of a given number?

Programming Interview - Core

Binary Search

1. Sorted array is pre-condition for binary Search. Take two pinter with start = 0, end = n-1 where n is length of the array.
2. Search a sorted array by repeatedly dividing the search interval in half. 
3. mid = (start + end) / 2
4. Case 1:  x == A[mid]   return mid
5. Case 2:  x < A[mid]    end = mid - 1    (x lies before the mid element, so shift end)
6. Case 3:  x > A[mid]    start = mid + 1    (x lies after the mid element, so shift start)
7. Continue till start <= end, (because even when start == end, we have 1 element to check)

If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

  int binarySearch(int array[], int start, int end, int numberToFind);
  

Complexity: (n / 2^k) = 1, were k is no of steps to reach result, while n is length of array. This gives k = log n. Hence the time complexity is O(log n).

Recursive Version:

• binarySearch(array, start, end, numberToFind)
• When start > end, then return -1
• mid = (start + end) / 2
• Case 1: x == array[mid], then return mid
• Case 2: x < array[mid],   then call binarySearch(array, start, mid-1, numberToFind)
• Case 3: x > array[mid],   then call binarySearch(array, mid+1, end, numberToFind)

Binary Search - First Occurrence of the element

We have a sorted array with duplicate elements to find the first occurrence of the element.

Modify the Case1 as below:

result = -1  (initialize the result with -1 indicating that no match found)

Case 1:  x == A[mid]   then  

              result = mid;     (capture the result i.e. the position of the matched element) 

              end = mid - 1    (to find first occurrence of the element x, check if there is one more occurrence of x before matched mid element, hence we shift end before mid)

Finally return result

Binary Search - Last Occurrence of the element

Similar to above we modify the Case1 as below:

Case 1:  x == A[mid]   then  

              result = mid;     (capture the result i.e. the position of the matched element) 

              start = mid + 1    (to find last occurrence of the element x, check if there is one more occurrence of x after the matched mid element, hence we shift start after mid)

Finally return result

Time complexity of both these variations of binary search is O(log n).

Count number of occurrences of element in sorted array

Strategy 1: Loop through the sorted array until there is a match and count until there is no match.

Strategy 2: Find the element in the sorted array using binary search, then first shift left and then shift right to count all the occurrences of the element.

Strategy 3: Find the first occurrence of element using binary search and then the last occurrence of element using binary search, using that determine the count of occurrences since the array is sorted i.e. (Last - First + 1).

Search element in a circular sorted array

Given a sorted circular array were the start element followed by end element lies somewhere in the middle of the array. 

E.g. 12,  14,  18,  21,  3,  6,  8,  9

      low               mid                high

The start element in the above array is 3. 

In the below code, x is the input element to be searched and we need to determine the position of x in the array.

mid = (low + high) / 2

Case1: A[mid] == x, return mid

Case2: A[mid] <= A[high]         // Right half is sorted

2A:    x > A[mid] && x <= A[high]

        low = mid + 1                   // search in right sorted half

Else

       high = mid - 1                    // search in left half

Case 3: A[low] <= A[mid]         // Left half is sorted

3A: x >= A[low] && x < A[mid]

       high = mid - 1                    // search in left sorted half

Else

        low = mid + 1                   // search in right half

Precedence of Operators

(high + low) / 2 is same as low + ((high - low)/2), as low + high can overflow if range exceeds integer.

Memoization

Memoization is an optimization technique used to speed up programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Sorting

Quick Sort

It is in place sorting.

Average case: O(n log n)

Worst case: n pow 2

1) Select a Pivot.

2) Move the elements lower than pivot to left side, while move elements higher than pivot to right side.

In below example we select the pivot always as the last element.

QuickSort(A, start, end) { 

  if (start < end) {

    pIndex = Partition(A, start, end)

    QuickSort(A, start, pIndex-1)

    QuickSort(A, pIndex+1, end)

  }

}

Partition(A, start, end) {

 pivot = A[end]             // Pivot is always the last element of list

 pIndex = start

 for i=start to end-1 {

   if(A[i] <= pivot) {

     swap(A[i], A[pIndex])

     pIndex = pIndex + 1

   }

 }

 swap(A[pIndex], A[end])

 return

}

Merge Sort

1) Split the list into half, at the mid point. Continue to split the 2 lists each recursively further until only 1 element is present. 

2) Now merge all the splitted list earlier recursively from bottom up such that, the final list at each step is sorted. Note here while merging two lists, we first take original list which was splitted in those two lists in the first place. Loop through both the Left and Right splitter list to check which is greater/less and place them elements in sorted fashion into the original list. Repeat this for all list in each recursive step.

Merge(Left, Right, A) {

  sizeLeft = length(Left)

  sizeRight = length(Right)

  i = j = k = 0

  while(i < sizeLeft && j < sizeRight) {

    if( Left[i] <= Right[j] )  {

       

       A[k] = Left[i]

       k = k + 1

       i = i + 1

    }

    else {

       A[k] = Right[j]

       k = k + 1

       j = j + 1

    }

  }

  // If there are elements remaining in either Left or Right list then simply append to result list

  while(i < sizeLeft) {

     A[k] = Left[i]

     i = i + 1

     k = k + 1

  }

  while(j < sizeRight) {

     A[k] = Right[j]

     j = j + 1

     k = k + 1

  }

}

MergeSort(A) {

  n = length(A)

  if(n < 2) return

  mid = n/2

  left = array of size(mid)

  right = array of size(n - mid)

  for i = 0 to mid - 1

     left[i] = A[i]

  for i = mid to n - 1

     right[i-mid] = A[i]

  MergeSort(left)

  MergeSort(right)

  Merge(left, right, A)

}