Interview SQL queries

1.   Find the Duplicate records in table.
 
   1. SELECT email, COUNT(email) AS NumOccurrences
FROM T 
GROUP BY email HAVING ( COUNT(email) > 1 ) ;
  
 2. SELECT * FROM emp a
     WHERE rowid = ( SELECT max(rowid) FROM emp
                            WHERE empno = a.empno
                            GROUP BY empno HAVING count(*) >1)

2.   Delete Duplicate records from table.
    1.  DELETE FROM table_name A 
WHERE ROWID > (SELECT min(rowid) 
FROM table_name B  
WHERE A.key_val = B.key_val);


    2. 


1.   Find the Duplicate records in table.





















Consider the below DEPT and EMPLOYEE table and answer the below queries.
DEPT
DEPTNO (NOT NULL , NUMBER(2)),
DNAME (VARCHAR2(14)),
LOC (VARCHAR2(13)

EMPLOYEE
EMPNO (NOT NULL , NUMBER(4)),
ENAME (VARCHAR2(10)),
JOB (VARCHAR2(9)),
MGR (NUMBER(4)),
HIREDATE (DATE),
SAL (NUMBER(7,2)),
COMM (NUMBER(7,2)),
DEPTNO (NUMBER(2))

MGR is the EMPno of the Employee whom the Employee reports to.DEPTNO is a foreign key
1. List all the Employees who have at least one person reporting to them.</span><br /> 

SELECT ENAME FROM EMPLOYEE WHERE EMPNO IN (SELECT MGR FROM EMPLOYEE); 

2. List the highest salary paid for each job.

SELECT JOB, MAX(SAL) FROM EMPLOYEE GROUP BY JOB

3. In which year did most people join the company? Display the year and the number of Employees 
SELECT TO_CHAR(HIREDATE,'YYYY') "YEAR", COUNT(EMPNO) "NO. OF EMPLOYEES"
FROM EMPLOYEE
GROUP BY TO_CHAR(HIREDATE,'YYYY')
HAVING COUNT(EMPNO) = ( SELECT MAX(COUNT(EMPNO))
FROM EMPLOYEE
GROUP BY TO_CHAR(HIREDATE,'YYYY'));
  
4.  Write a correlated sub-query to list out the Employees who earn more than the average salary of their department. 
SELECT ENAME,SAL
FROM EMPLOYEE E
WHERE SAL &gt; (SELECT AVG(SAL)
FROM EMPLOYEE F
WHERE E.DEPTNO = F.DEPTNO);

5. Find the nth maximum salary.  
SELECT ENAME, SAL
FROM EMPLOYEE A
WHERE &N = (SELECT COUNT (DISTINCT(SAL))
FROM EMPLOYEE B
WHERE A.SAL <=B.SAL);  

6. Select the duplicate records (Records, which are inserted, that already exist) in the EMPLOYEE table.  
SELECT * FROM EMPLOYEE A
WHERE A.EMPNO IN (SELECT EMPNO                                        
FROM EMPLOYEE                                        
GROUP BY EMPNO                                          
HAVING COUNT(EMPNO)> 1)
AND A.ROWID!=MIN (ROWID));


7.  Write a query to list the length of service of the Employees (of the form n years and m months).
SELECT ENAME "EMPLOYEE",
        TO_CHAR(TRUNC(MONTHS_BETWEEN(SYSDATE,HIREDATE)/12))
||' YEARS '|| TO_CHAR(TRUNC(MOD(MONTHS_BETWEEN
(SYSDATE, HIREDATE),12)))||' MONTHS ' "LENGTH OF SERVICE"
FROM EMPLOYEE;

Joseph Problem...

Joseph likes taking part in programming contests. His favorite problem is, of course, Joseph's problem. It is stated as follows.

Problem : There are n persons numbered from 0 to n - 1 standing in a circle. The person number k, counting from the person number 0, is executed. After that the person number k of the remaining persons is executed, counting from the person after the last executed one. The process continues until only one person is left. This person is a survivor. The problem is, given n and k detect the survivor's number in the original circle.

  Solution: You can easily write a recursive write:
 Example:(20, 3) = 4+17-1 =20 Find J (20, 3), assume that you have to know the J (19, 3) = 17, then remove the number 3 20 people who left with 19 people, and this 19 starting from the number 4, 17 the last person is left, so J (20, 3) = 4 +17-1 = 20
 

public class JoshephProblem {
    public static void main(String[] args) {
        System.out.println(">>> " + J(5, 3));
    }

    public static int J(int n, int m) {
        if (n == 2) {
            if (m % 2 == 1)
                return 2;
            else
                return 1;
        } else {
            int temp = (J(n - 1, m) + m) % n;
            if (temp == 0)
                return n;
            else
                return temp;
        }
    }
}

Why Marker Interface ?

he main purpose to have marker interfaces is to create special types in those cases where the types themselves have no behavior particular to them. If there is no behavior then why to have an interface? Because the implementer of the class might only need to flag that it belongs to that particular type and everything else is handled/done by some other unit - either internal to Java (as in the case of Java supplied standard marker interfaces) or an app specific external unit.

Let's understand this by two examples - one in which we will discuss the purpose of a standard Java interface (Cloneable) and then another user-created marker interface.

When JVM sees a clone() method being invoked on an object, it first verifies if the underlying class has implemented the 'Cloneable' interface or not. If not, then it throws the exception CloneNotSupportedException. 
Assuming the underlying class has implemented the 'Cloneable' interface, JVM does some internal work (maybe by calling some method) to facilitate the cloning operation.
So, effectively marker interfaces kind of send out a signal to the corresponding external/internal entity (JVM in case of Cloneable) for them to arrange for the necessary functionality. 

public Object clone() throws CloneNotSupportedException {

 if (this implements Cloneable)

     return nativeCloneImpl();

 else

     throw new CloneNotSupportedException();

}

 
Can anyone tell why and when do we get 'CloneNotSupportedException' exception at compile-time itself? Well... that's no trick. If you see the signature of the 'Object.clone()' method carefully, you will see a throws clause associated with it. I'm sure how can you get rid of it: (i) by wrapping the clone-invocation code within appropriate try-catch (ii) throwing the CloneNotSupportedException from the calling method.

What purpose does a user-defined marker interface serve? It can well serve the same purpose as by any standard marker interface, but in that case the container (the module controlling the execution of the app) has to take the onus of making sure that whenever a class implements that interface it does the required work to support the underlying behavior - the way JVM does for Cloneable or any other standard marker interface for that matter.


user-defined marker interface in Java:-
to be continued........ 

DB Indexes

Q. What's DB indexes ?
A. basically used to sort data in a table.
There are basically 2 types of DB indexes:- Clustered and non-clusterd

Q. What's Mean By Cluster?
A. Oracle cluster supply an optional way of storing table data. In a cluster a group of tables share the same data blocks. The tables are grouped together because they share identical columns and are often used together. For example, the employee and department table use the depth no column. When you cluster the employee and department tables Oracle Database physically stores all rows for each department from both the employee and department tables in the same data blocks.
A cluster is used in database so that to keep all the rows of all data tables together and they can easily be accessed by the help of shared cluster key.

Because clusters store relevant rows of dissimilar tables together in the one data blocks, correctly used clusters offer two primary benefits:
■ Disk I/O is condensed and access time improves for joins of clustered tables.
■ The cluster key is the column, or collection of columns, that the clustered tables have
in same. You identify the columns of the cluster key when creating the cluster.
You next specify the same columns when creating every table added to the cluster. Each cluster key value is saved only single time each in the cluster and the cluster index, no concern how many rows of different tables hold the value.

Q. What's Cluster and Non-Cluster Indexes ?

A clustered Index sort the data in a table physically.
A non-clustered Index doesn't sort the data physically.

As clustered Index sort the data physically, So there can be only one Clustered index per table.
where as there can be many non-clustered index in table.
(with a maximum of 255 such indexes per table a very authentic possibility. i.e. every single column can be utilize for non-cluster indexing )

Q. when you can use a clustered or a non clustered index????
A. The clustered is a safe bet if you are working with a table having a large number of unique data, such as a table containing the employee IDs for the different members of an organization. These IDs are always unique, and using a clustered index is a good way of retrieving this large volume of unique data rapidly. On the other hand, a non clustered index is the best approach if you have a table that does not contain too many such unique values. These are just some of the differences between the two. You can read in detail about these differences by putting a search on the Internet for the differences between the two.

- - - - - -- - - - -- - - -

BST to Doubly Link List

To solve this problem, First we will analyze the different Cases :-
  Case 1: Leaf Node - left & right child is Null
  Case 2: No Left Subtree   - left Child is Null
  Case 2: No Right Subtree  - right Child is Null
  Case 2: No Left Subtree   - left Child is Null

Java 'ArrayList' Pseudocode ....

protected int modCount = 0;

ArrayList(int initialSize)

        IF  initialSize<0  THEN
                       Throw exception "Invalid Size"
       else
             arrayElement= new Object[initialSize];
        

ArrayList() 

  Call ArrayList(defaultSize); // default-size is 10

ArrayList(Collection<? extends E> C)
     arrayElement = C.toArray();
     size = arrayElement.length;
     IF arrayElement.getClass() != Object[].class THEN
                 arrayElement = Arrays.copyOf(arrayElement, size, Object[].class);

ensureCapacity(int newCapacity) 

   modCount++
   oldCapacity  = arrayElement.length;
    IF newCapacity > oldCapacity THEN
         Object[] oldData = arrayElement;
         newCap = (oldCap *3)/2 +1;
         IF newCap < newCapacity THEN
                   newCap=newCapacity;

         ENDIF
    END IF
  arrayElement =Arrays.copyOf(arrayElement, newCap); // My own implementation is at the end.

add(E data)
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = data;


add(int index, E element)
 IF index > size OR  index < 0 THEN
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
 ENDIF
 ensureCapacity(size+1);  // Increments modCount!!
 System.arraycopy(elementData, index, elementData, index + 1, size - index); //shifting the right hand side elements by 1.
 elementData[index] = element;
 size++;

RangeCheck(int index)
   IF index >= size THEN
        throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size);

 remove(int index)

  RangeCheck(index)
  modCount++;   // modification count
  Object oldVal = elementData.get(index);
  int numMoved = size - index - 1;

addAll(Collection<? extends E> c)

Object[] a = c.toArray();
length = a.length;
ensureCapacity(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
 size = size + numNew;
return numNew != 0;




  ........... to be continued (will add other details later)

Advantages of Iterator over forEach

1. Iterator is a design pattern and is a light-weight container.
2. Iterator doesnt need to know what the collection is (i.e. a List or sth else )
3. Using iterator ,we can remove the current element. The for-each loop hides the iterator, so you cannot call remove. Therefore, the for-each loop is not usable for filtering.
4. Similarly, forEach is not usable for loops where you need to replace elements in a list or array as you traverse it, but Iterator can be used.
5 .Finally, forEach is not usable for loops that must iterate over multiple collections in parallel.

finally Vs finilize

• finally – The finally block always executes when the try block exits, except System.exit(0) call. This ensures that the finally block is executed even if an unexpected exception occurs. But finally is useful for more than just exception handling — it allows the programmer to avoid having cleanup code accidentally bypassed by a return, continue, or break. Putting cleanup code in a finally block is always a good practice, even when no exceptions are anticipated.

• finalize() – method helps in garbage collection. A method that is invoked before an object is discarded by the garbage collector, allowing it to clean up its state. Should not be used to release non-memory resources like file handles, sockets, database connections etc because Java has only a finite number of these resources and you do not know when the garbage collection is going to kick in to release these non-memory resources through the finalize() method.

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+"";
}

}

intern() in java

We all know that string is the fundamental part of programming, every bit is as important as numbers. In java there is a string methos intern().

So what exactly is intern()? Well, as we know that in java there tow different ways of compare objects. You can use == or equals() method. The == operator compares the references of both objects, whereas equals() compares the data of both objects. So as part in first lesson we have learned that we should use equals() method, not == to compare string objects.

new String("Hello")==new String("Hello") will in fact return false because they are two different string objects. If we use equals() then it will return true. But equals() method can be fairly slow as it compares character-by-character.

Since the == compares identity, i.e. all it has to do is compare tow pointers to see if they are same or not. So it will be much faster then equals() method.

Thread.yeild() Vs Thread.Sleep() in java

I tried to find out this diff, bt no where its clearry given. All the details i found was jst bookies thing.
Finally i found this good answer, hope this will help you as well:-
yeild() : This allows other threads to execute which are in Runnable state and Our thread will also go in Runnable state. So that CPU Scheduler may choose other Thread from runnable pool torun . It may choose our thread too. Its not guranteed...
Sleep(): On call of this Our Thread goes to waiting state for specified time. So it gurantees that till that specified time CPU will not pick our thread. After time expires, it will be to Runnable State. Now it will be part of CPU allocation.

In JVM - Memory Type :)

Whenever we come across type of memory in JVM, it always reflects two.

• Heap Memory
• Non Heap Memory
  

all other memory jargon we hear about JVM, are logical part of these two.

Heap Memory (also called Shared Memory)
This is the place where multiple Thread will share the instances. So, all the Class Instances (Objects) and Arrays stored in this.

Non-Heap Memory
It comprises of 'Mehtod area' and other memory required for internal processing.

Mehtod area : As it is a part of non-heap area, it stores per-class structures, code for methods and constructors. Per-class structure means runtime constants and static fields.

So basically these above 3 type are the main jargon when it comes for JVM memory. But there are some other technical term also comes, whenever we talks about JVM.

Memory Pool : This is created by JVM Memory Manager at the runtime. It may belong to Heap or non-Heap.

Runtime Constant Pool : Its a per-class or per-interface run time representation of the constant_pool table in a class file. Its got allocated from JVM Method area.

Java Stack: This is created privately for each thread. Each Thread will have Program Counter (PC) and Java Stack. PC stores the intermediate value, dynamic linking, return value of any method and dispatched exception. This is basically used in place of register.

Memory Generation : JVM garbage collector uses these generation wise collection into mainly two category :- Young Genration and Old Generation.
Young Generation
-> Eden Space - Shortlived objects and any newly created objects will be available.
-> Survivor Space -When GC happens, if an object is still alive and it will be moved to survivor space.

Old Generation
-> Tenured Space - GC moves live objects from survivor space to tenured generation.
-> PermGen Space - This is called permanent generation. It contains meta data of the virtual machine, class and method objects.

Key TakeAways:-

• Local Variables are stored in Frames during runtime.
• Static Variables are stored in Method Area.
• Arrays are stored in heap memory.

Reference :-

• MemoryPoolMXBean provides you api to explore the memory usage, threshold notifications, peak memory usage and memory usage monitoring.
• Threads and Locks chapter of Java Language Specification talks lot about java memory
• Chapter 5 of Inside the Java Virtual Machine, The Java Virtual Machine by Bill Venners

BST(Binary Search Tree) to Doubly Link List

Merge two linked lists: Node* MergeList(Node *list1, Node* list2). Do not create a node in the function while merging the lists.

Struct Node{
int data;
struct node* p;
}

we are assuming that both the given list are sorted.
node mergeSort(node a, node b){
if(a == null) return b;
if(b == null) return a;
if(a.value <= b.value){
a.next = mergeSort(a.next, b);
retrun a;
}else{
b.next = mregeSort(a, b.next);
return b;
}
}

Most optimal way to find the sum of 2 numbers represented as linked lists

Solution 1:

1. reverse list-1
2. reverse list-2
3. find the sum and store it in a new list represented by list-3
4. reverse the list.

The complexity of this should be of the O(n+m). Is there anyway to reduce it, or do it better????

Solution2 :

You can do better without list reversal. WLOG(Without loss of generality) I'll assume that both lists h of equal length (prepend with 0 if necessary).

Start the addition from left right (from most significant to least significantple digit). You have 3cases, depending of the sum two digits:

1. = 9 : keep the nine and increase a counter
2. <>counter x nine, write sum, reset counter
3. > 9 : increase last digit, write counter x zero, write sum (modulo 10), reset counter

I'll work on the following example:



2 568 794 +
1 438 204
--------- =
4 006 998

Add 2 + 1 = 3: case 3.
list = (3), counter = 0
Add 5 + 4 = 9: case 1
list = (3), counter = 1
Add 6 + 3 = 9: case 1
list = (3), counter = 2
Add 8 + 8 = 16: case 3
list = (4, 0, 0, 6), counter = 0
Add 7 + 2 = 9: case 1
list = (4, 0, 0, 6), counter = 1
Add 9 + 0 = 9: case 1
list = (4, 0, 0, 6), counter = 2
Add 4 + 4 = 8: case 2
list = (4, 0, 0, 6, 9, 9, 8), counter = 0
 
Hope this will help to understand :)