Equilibrium index of an Array

Ques :What is "Equilibrium index of an Array" ?
Ans:   Equilibrium index of an Array is an index of Array, such that the sum of elements at lower indices is equal to the sum of elements at higher indices. Value of element at the index is not taken into account.
For example, In the below Array:
Array A  -7   1    5   2  -4    3   0
Index        0   1    2   3   4    5   6
So here Index 3 and 6 are equilibrium index.
3 is an equilibrium index, because:     A[0]+A[1]+A[2]  = A[4]+A[5]+A[6]
6 is also an equilibrium index, because: A[0]+A[1]+A[2]+A[3]+A[4]+A[5] = 0

Method-1: Brute-Force method
 This method uses two loops to find the leftSum and rightSum for each index while traversing the array. 

void printEquilibriumIndexes(int arr[], int n){
    for (int i = 0; i < n; ++i){
        int leftSum = 0, rightSum = 0;
        for (int j=0; j<i; j++)
            leftSum += arr[j];
        for(int j=i+1; j<n; j++)
            rightSum += arr[j];       
        if (leftSum == rightSum)
           System.out.println("Index : "+i);
    }
}

Time complexity: O(n^2) 
Method-2: In this more efficient method where we keep track of the sum of all the elements in the Array and hence do not calculate the leftSum and rightSum from scratch but just update them based on the current index.

/**
 * This function will print all the Equilibrium Indexes in array arr
 */
void printEquilibriumIndexes(int arr[], int n){
    int rightSum = 0;   // Sum of all the Elements to the right of an Element
    int leftSum = 0; // Sum of all the Elements to the left of an Element

    for (int i=0; i<n; ++i)
        rightSum += arr[i];

    for (int i = 0; i < n; ++i){
        rightSum -= arr[i];
        if (leftSum == rightSum)
           System.out.println("Index: "+i);

        leftSum += arr[i];
    }
}

Rotate an array by K Position left.

We have to rotate an a sorted Array by k points. For example, if k=3, for the below array
A ={2, 4, 7, 9, 10, 12, 28, 30, 34, 50}
then after rotation the final array will be A ={9, 10, 12, 28, 30, 34, 50, 2, 4, 7}.

Solution:
 Method 1: Brute Force method : Rotate by one position at a time

/** Rotate the Array k places by rotating by one position at a time
 */
void rotate(int *arr, int n, int k){
    for (int cnt = 0; cnt < k; cnt++){
        int temp = arr[0];
        int i=0;
        for (; i < n-1; i++)
            arr[i] = arr[i+1];
        arr[i] = temp;
    }
}

Method 1: Swapping & Reversing the Sub-array method: 

For i= 0 to k-1
swap a[i], a[n-i-1]
// arr: 50, 34, 20,
9, 10, 12, 18, 7, 4, 2

Reverse elements from k to n-k-1.        // arr: 50, 34, 20, 18, 12, 10, 9, 7, 4, 2

Reverse elements from 0 to n-k-1.       // arr: 9, 10, 12, 18, 20, 34, 50, 7, 4, 2
Reverse elements from n-k to n-1.       // arr: 9, 10, 12, 18, 20, 34, 50, 2, 4, 7

/**
 * Function to rotate the array arr of size n by k positions
 * We will examine the state of array after each step for following input values
 * arr: 2, 4, 7, 9, 10, 12, 18, 20, 34, 50
 *   n: 10
 *   k: 3
 *
 * Expected Output: 9, 10, 12, 18, 20, 34, 50, 2, 4, 7
 */
void rotate(int *arr, int n, int k){
 for(int i=0; i < k; i++)
        swap(arr,i,n-i-1);
    // arr: 50, 34, 20, 9, 10, 12, 18, 7, 4, 2
    reverse(arr,k,n-k-1);
    // arr: 50, 34, 20, 18, 12, 10, 9, 7, 4, 2
    reverse(arr,0,n-k-1);
    // arr: 9, 10, 12, 18, 20, 34, 50, 7, 4, 2
    reverse(arr,n-k, n-1);
    // arr: 9, 10, 12, 18, 20, 34, 50, 2, 4, 7
}

/**
 * Swap two elements at position a & b of Array arr.
 */
void swap(int *arr, int a, int b){
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
}

/**
 * Reverse all the elements of array arr between positions a & b (both inclusive)
 */
void reverse(int *arr, int a, int b){
    for(int i=0; i<=(b-a)/2; i++)
        swap(arr, a+i, b-i);
}

/**
 * Function to print the array
 */
void printArray(int arr[], int size){
    for(int i = 0; i < size; i++)
        cout<<arr[i]<<" ";
}

Method-4: Using an Auxiliary Array

If we use a separate array to store the result then things becomes easy. I am sure you can write the function for this one :)

void rotateUsingExtaArray(int arr[], int n, int k){
    for(int i=0; i < n; i++)
        b[i] = arr[(i+k)%n];
}

Time complexity: O(n).   Space Complexity: O(n)

Method-6: Juggling Algorithm
In this method, the array is divided into M sets, where M = GCD(n, k), and rotate the corresponding elements in each set: For Example: If we want to rotate the below array by 2 points

1 2 3 4 5 6

M = GCD(6, 2) = 2;

First Set Moves:

3 2  5 4  1 6

Second Set Moves:

3 4 5 6 1 2

/**
 * Rotate the array arr of size n by k places
 */
void rotateJuggling(int *arr, int n, int k){

    int i, j, p, temp;
    for (i = 0; i < gcd(k, n); i++){

        // moving i'th
        temp = arr[i];
        j = i;
        while(1){

            p = j + k;
            if (p >= n)
                p = p - n;
            if (p == i)
                break;
            arr[j] = arr[p];
            j = p;
        }
        arr[j] = temp;
    }
}

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

Find the N-th largest element in the array of positive integers.. unsorted array

Sort the array in decreasing order then loop through the sorted array while counting unique elements then stop when the count is equal to (n). In the code below we will assume the array is already sorted. You can refer to the following post for more information about merge sort which you can use to efficiently sort the array in O(nlogn) time complexity.

public int NthMaxumum(int[] A){
   int s = A.length;
   //Let us assume we need to find the 3d. maximum which is 4
   int n = 3;
   //Counter
   int c = 1;
   //Initialize n(th) max
   int nmax = A[0];
   //Loop in the array while the count is less than (n)
   for (int i = 0; i < s && c < n; i++){
  //If the current array element is different from the current n(th) max increment the counter
 if (A[i] != nmax) c++;
 //Update n(th) max
 nmax = A[i];
}

x^n algorithm with logN complexity

Question : Write a function to compute (x) to the power of (n) where (x) and (n) are positive integers. Your algorithm should run in O(logn) time complexity.
Answer : Use divide and conquer technique. For even values of (n) calculate x^(n/2) and return the square of that as the final result because x^n = x^(n/2) * x^(n/2). For odd values of (n) calculate x^(n-1) and return it multiplied by (x) because x^n = x * x^(n-1). The first base case for recursion is n = 0 in this case you return 1. The second base case for recursion is n = 1 in this case you return (x). This algorithm runs in O(logn) because the problem size (n) is divided by (2) every time we call the recursive function. For odd values of (n) one extra call is executed before the number becomes even again which does not impact the overall performance of the algorithm for large values of (n). Please take a look at the code below for more details.

//Imports
using System;

//Test class
class Test
{
    public int RecursiveExp(int x, int n){
        //First base case
        if (n == 0){
            return 1;
        }
        //Second base case
        if (n == 1){
            return x;
        }
        //Even values of (n)
        if (n % 2 == 0){
            int y = RecursiveExp(x, n / 2);
            return y * y;
        }else{
            int y = RecursiveExp(x, n - 1);
            return x * y;
        }
    }
}


public static void main(string[] args)
    {
        //Create a test object
        Test tst = new Test();
        //Examples
        Console.Out.WriteLine(tst.RecursiveExp(2, 0));
        Console.Out.WriteLine(tst.RecursiveExp(2, 1));
        Console.Out.WriteLine(tst.RecursiveExp(2, 3));
        Console.Out.WriteLine(tst.RecursiveExp(2, 4));
    }
}

The Next Palindrome Number.

I recently came across a problem to find the Next Palindrome Number. For example, the next palindrome after 2133 is 2222. 
Palindrome: is a word, phrase, number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words is generally permitted(.
The common way to solve this problems is brute-force approach where we keep increment the integer until we hit palindrome.

public static String bruteForce(String s){
  BigInteger i = new BigInteger(s) ;
  while(true){
    i = i.add(BigInteger.ONE);
    final String result = i.toString();
    if(isPalindrome(result)){
      return result;
    }
  }
}

This approach is VERY slow for large numbers! A faster way is "mirroring" the number about its centre. For example, the mirror of 65432 is 65456, which is the next palindrome. The following method mirrors a string:

public static String mirror(String s) {
  final char[] arr = s.toCharArray();
  int midpoint = arr.length / 2;
  int i=arr.length%2==0?midpoint:midpoint+1;
  while (i < arr.length) {
    arr[i] = arr[midpoint - 1];
    i++;
    midpoint--;
  }
  return new String(arr);
}

BUT sometimes a mirrored number might be smaller than the original. For example, the mirror of 12345 is 12321, which is smaller. In this case, we need to increment the original number from the middle and then mirror it. So when 12345 is incremented from the middle, you get 12445 which mirrors to 12421, the next palindrome. Incrementing from the middle can get tricky if there is a 9 in the middle. For example, 12945 increments to 13045 which then mirrors to 13031. The following method increments a number from the middle:

public static String incrementFromMiddle(String s) {
  final char[] arr = s.toCharArray();
  final int midpoint = arr.length / 2;
  int currPoint=arr.length%2==0?midpoint-1:midpoint;
  boolean found = false;
  while (currPoint >= 0 && !found) {
    char c = arr[currPoint];
    char inc;
    if (c == '9') {
      inc = '0';
    }
    else {
      inc = (char) (c + 1);
      found = true;
    }
    arr[currPoint] = inc;
    if (!found) {
      currPoint--;
    }
  }

  if (!found) {
    // we have fallen off the start of the string
    // example 999 has become 009. Add a one on to give: 1009
    final char[] newarr = new char[arr.length + 1];
    newarr[0] = '1';
    System.arraycopy(arr, 0, newarr, 1, arr.length);
    return new String(newarr);
  }
  else {
    return new String(arr);
  }
}

Question :Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

Answer: most of the time i get people who give answers like “the most senior pirate takes half and divides the rest up among the least senior pirates.” um, you missed the whole point to begin with. sorry.

any answer without a specific logic behind it is invalid. if i ask you why pirate 5 gave x coins to pirate 1, please don’t say “because he’s nice”.

now for the real solution. pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. so who can he get to vote for him, and why would they choose to vote for him? if you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. but it gets more complicated.

lets consider if there were only 1 pirate. obviously he would take it all for himself and no one would complain.

if there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he’s obviously going to keep all the money for himself.

if there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. so who can he convince and how? here is the leap that needs to be made to solve this problem. pirate 3 realizes that if his plan is not adopted he will be executed and they will be left with 2 pirates. he already knows what happens when there are 2 pirates as we just figured out. pirate 2 takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says, well, 1 is better than none, and since i know if i don’t vote for pirate 3, i get nothing, i should vote for this plan.

now we know what happens when there are 3 pirates. so what happens with 4? well pirate 4 has to convince 1 other person to join in his plan. he knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather not part with 2 whole coins. he realizes that if he gets executed, then pirate 3’s scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.

a common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. but that is why i said that the pirates are extremely intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn’t want to die and we just showed that 3 has a winning proposal.

so lets sum up at this point

Pirate   1   2   3   4    5
    5.      ?   ?   ?   ?     ?
    4.      0  1   0   99   -
    3.      1  0  99   -    -
    2.     0  100 -   -   -
    1.    100

once you see the pattern it becomes very clear. you have to realize that when a pirate’s plan does not succeed then that means you are in the same situation with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. pirate 2 needs 0 other people to vote for him. so he votes for himself and takes all the money. pirate 1 gets 0. 3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1 other person to vote for him. he gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote for him. its clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. so he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.

Pirate    1   2   3   4   5
          5. 1   0   1   0  98

what happens if there are 15 pirates? pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.

hope you enjoyed this one. its my favorite interview question of all. it really allows the candidate to ask a lot of interesting questions and its really amazing when they reach the solution all by themselves.

Customize Iterator

"In Computer Science, an iterator is an object that allows a programmer to traverse through all the element collection, regardless its implementation"


In java, along with the introduction of Collection, the Iterator is also been provided for all collection type. But sometimes we come across the scenario where we need to loop through the list of User defined object and if we want to utilize the iterator for that then we need customized Iterator for that Object(to utilize the new FOR loop as well). Here is a simple example for the same:-

public class MyClass{
int id;
String name;
String sal;

public MyClass(int i, String name) {
super();
this.i = i;
this.next = next;
}

public int getI() {
return i;
}

public void setI(int i) {
this.i = i;
}

public SampleNode getNext() {
return next;
}

public void setNext(SampleNode next) {
this.next = next;
}

public String toString() {
return i+"";
}

}