Oracle Interview - Telephonic Round - Continues

We did not solve the last problem that I was asked in the interview. So let's put together the solution for the same.

• Algorithm Problem: A random string is provided to you, you must find the minimum number of elements to be inserted in the string to make it palindrome.
• String is ABA, then method must return 0.
• String is ABC, then method must return 2 to form ABCBA.
• String ABCDA, then method must return 2 to form ABCDCBA.
• String ASD3D5, then method must return 3 to form AS5D3D5SA.

It has been difficult for me to find the solutions for the problem within the specified timeframe as it requires quite a good understanding to achieve such an efficient answers.

When I first heard the question, I felt that this would round would not be difficult as I thought, as I could come up with the algorithm within some time. But I was wrong. It was not the case there.

First Solution

 public class Palindrome {  
      String element;  
      public Palindrome(final String elem) {  
           element = elem;  
      }  
      public int makePalindrome() {  
           if (element.length() <= 1) {  
                return 0;  
           } else {  
                char[] dst = new char[element.length()];  
                int endIndex = element.length() - 1;  
                int index = 0;  
                element.getChars(0, element.length(), dst, 0);  
                while (dst[index] == dst[endIndex]) {  
                     index++;  
                     endIndex--;  
                }  
                return endIndex - index;  
           }  
      }  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           Palindrome p = new Palindrome("ABCA");  
           System.out.println("Chars to be added are: " + p.makePalindrome());  
      }  
 }  

Oh wow, that's it. But it is really worth the question.

What I did?
I solved for ABA, and it would return 0 but it was not the smallest palindrome. After discussion with interview a bit more, I can to know that this code would really not work for "ASD3D5". It was true, the code did not really work as per the question. Hell broke lose here. Now interviewer is already agitated with the time that I have taken.

I have to rework the solution with the closed mind. Stupid mind was still contemplating me to write some code on the same line, and it was not able to think something different at that time. However I failed the interview at that time only, but it was required for me to find the answer for the questions that are asked.

I tried little more and found the following answer.

Solution 2
It is simple, we have to use the dynamic programming to solve the issue that we have in hand. First we cut the corners of the string. In case of ABCDA, we use string BCD for the dynamic programming. Now we find the maximum number of elements which matches between original string and reversed string. Count of minimum non matching characters are the solution for the puzzle.

1:  package com.oracle;  
2:  import java.util.Collections;  
3:  import java.util.List;  
4:  public class Palindrome {  
5:       String element;  
6:       public Palindrome(final String elem) {  
7:            element = elem;  
8:       }  
9:       public int makePalindrome() {  
10:            if (element.length() <= 1) {  
11:                 return 0;  
12:            } else {  
13:                 char[] dst = new char[element.length()];  
14:                 int endIndex = element.length() - 1;  
15:                 int index = 0;  
16:                 element.getChars(0, element.length(), dst, 0);  
17:                 while (dst[index] == dst[endIndex]) {  
18:                      index++;  
19:                      endIndex--;  
20:                 }  
21:                 String substring = element.substring(index, endIndex + 1);  
22:                 System.out.println("New String is: " + substring);  
23:                 return Math.min(substring.length(),  
24:                           minCharForPalindrome(substring.toCharArray(), 0));  
25:            }  
26:       }  
27:       private int minCharForPalindrome(char[] substringArray, int compare) {  
28:            if(compare > substringArray.length){  
29:                 return compare;  
30:            }  
31:            int count = 0;  
32:            for (int index = compare, last = substringArray.length - 1; 

                   index < substringArray.length; index++, last--) {  
33:                 if (substringArray[index] != substringArray[last]) {  
34:                      count++;  
35:                 }  
36:            }  
37:            count += compare;  
38:            System.out.println("When Compare = " + compare + " Count= " + count);  
39:            return Math.min(count,  minCharForPalindrome(substringArray, ++compare));  
40:       }  
41:       /**  
42:        * @param args  
43:        */  
44:       public static void main(String[] args) {  
45:            Palindrome p = new Palindrome("ABCDEFG");  
46:            System.out.println("Chars to be added are: " + p.makePalindrome());  
47:       }  
48:  }  

This solution is based on the dynamic programming where starting from the first point string is compared with the another string. The solution is general should take O(N*N) time to compute the result.

1:  New String is: ABCDEFG  
2:  When Compare = 0 Count= 6  
3:  When Compare = 1 Count= 7  
4:  When Compare = 2 Count= 6  
5:  When Compare = 3 Count= 7  
6:  When Compare = 4 Count= 6  
7:  When Compare = 5 Count= 7  
8:  When Compare = 6 Count= 6  
9:  When Compare = 7 Count= 7  
10:  Chars to be added are: 6  

1:  New String is: ASD3D5  
2:  When Compare = 0 Count= 6  
3:  When Compare = 1 Count= 3  
4:  When Compare = 2 Count= 6  
5:  When Compare = 3 Count= 5  
6:  When Compare = 4 Count= 6  
7:  When Compare = 5 Count= 5  
8:  When Compare = 6 Count= 6  
9:  Chars to be added are: 3  

Now the problem with the solution is the time complexity. Can we do anything better?

Okay few people says yes. There is one solution which uses Knuth-Morris-Pratt Algo to find the solutions more efficiently.I have not implemented it yet, but I would surely try to implement and understand it. If you have understood the same, please suggest me the same.

Links for the reference are as following:
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
http://stackoverflow.com/questions/18732020/add-the-least-amount-of-characters-to-make-a-palindrome

Hope it helps

Oracle Interview - Telephonic Round

It was a telephonic discussion session for the post of senior software developer. Though I could not clear the round yet it would be best place to share the questions so that I can discuss whether there can be other solutions for the problems asked.

• What are the differences between JDK, JRE, and JVM?

JDK (Java Development Kit): Development Kit which is actually required for the developers. It is not required to run the Java dependent applications. It is rather required at the development.

JRE (Java Runtime Environment): Java Runtime environment is required to run the java application. It computer does not JRE, No Java application can run on it.

JVM (Java Virtual Machine): JVM is part of JRE, it reads byte code and execute them on the Hardware. It is the reason which causes JAVA applications to run on various platforms without changing much at the program level.

• Design Problem: You have to build a data/class model for a website. It has users i.e. People and it has group. A User can belong to multiple groups and a Group can have multiple users. Each group maintains an individual account. All the transactions are saved with the person who made the expenses and each person's share is calculated on each transaction. Person vice credit/debit history should also be maintained. Build the data structure for the same.

Design problems are some problem when interviewer and interviewee both do not have same understanding of the requirement. Such problems must only be discussed when you are speaking face to face. It not only gives more confidence but also provides more error correction while writing the code.

For this specific design problem, I had assumed that group is the prime information that system has, whereas Interviewer was expecting that Person should be the prima facie of the complete system. Though it was not difficult both the ways, but it is planned in separate way for both entities.

First Design

Application would have four classes as following

1:   public class Group{  
2:   List<Person> members;  
3:   List<Transaction> transactions;  
4:   List<Share> shares;  
5:   double totalExpenditure;  
6:   //Methods  
7:   addPerson  
8:   addTransaction  
9:   settleAmount  
10:   getShare for a person  
11:   }  
12:   public class Person{  
13:   String name;  
14:   List<Group> groups;  
15:   double credit;  
16:   double debit;  
17:   //Method  
18:   addToCredit  
19:   addToDebit  
20:   addGroup  
21:   }  
22:   public class Share{  
23:   double credit;  
24:   double debit;  
25:   Person belongsTo;  
26:   //Changes with each transaction.  
27:   }  
28:   //Transaction once added, it would be required it to modify.  
29:   public final class Transaction{ //Immutable class  
30:   final String type;  
31:   final String expenseReason;  
32:   final double amount;  
33:   final Person spentBy;  
34:   public Transaction(final String t, final String r, final double amount, final Person p){  
35:    type = t;  
36:    expenseReason = r;  
37:    this.amount = amount;  
38:    spentBy = p;  
39:   }  
40:   }  

Now when the system is designed from group point of view, it is considered that group is self managed and everyone part of the group would really be part of all the transactions relevant to group.

All the classes are self explanatory. Why did I make Transaction as immutable? Transaction is once done, it can not be altered later. Though there can be people who would say that 'What if user inputs the wrong data?' Oh yes, user has rights to enter wrong data, but it would be atmost 1% times.

It is best to solve the problems which are essential rather increase the complexity of the system by solving trivial problems.

However interviewer wanted to run things with the user perspective. As per him, A group is an entity based on users. User may or may not be the part of group's particular transactions. So it was required to rewrite the classes again based on the following assumption.

  //Transaction once added, it would not be required to modify it.  
  public final class Transaction{  
  final String type;  
  final String expenseReason;  
  final double amount;  
  final Person spentBy;  
  final List<Person> sharedAmong;  
  public Transaction(final String t, final String r, final double amount, final Person p, final List<Person> shared){  
   type = t;  
   expenseReason = r;  
   this.amount = amount;  
   spentBy = p;  
   sharedAmong = Collections.unmodifiableList(shared);  
  }  
  }  

However when things are user's point, then it is required to provide administrative work to someone who can create group, assign group, and perform group related works. It is required to add few fields and methods in other classes as well.

  public class Group{  
  List<Person> admins;  
         .....  
  }  
  public class Person{  
         ....  
  createGroup  
  addAdminToTheGroup  
  invitePeople  
  }  

However we can add more to it, but till this point we discussed.

• Algorithm Problem: A random string is provided to you, you must find the minimum number of elements to be inserted in the string to make it palindrome.
• String is ABA, then method must return 0.
• String is ABC, then method must return 2 to form ABCBA.
• String ABCDA, then method must return 2 to form ABCDCBA.
• String ASD3D5, then method must return 3 to form AS5D3D5SA.

It would be best to save to Algorithm Problem for the next blog. I could not solve the problem at the time of interview, but I have a solution with O(n*n) complexity. If there is solution available which is better than this, please suggest me.

If you think that above design problem can be designed better, please suggest.

Interview Question: Database Query: Find nth maximum salaried employee.

This question was asked to me in an screening process of a product based company.

Oracle database has employee table having EMPLOYEE_ID and SALARY as columns. Identify all the employee who get 3rd best salary in the company.

My instant answer was as follows:

SELECT * FROM EMPLOYEE WHERE ROW_NUMBER = 3 ORDER BY SALARY DESC

There was instant reaction, this query is wrong. Yes, it is. It will give me the 3rd most earning employee of the company but it will give me the THIRD BEST salary of the company.

So I modified my query a little bit and answered as follows:

SELECT * FROM EMPLOYEE WHERE SALARY = (SELECT DISTINCT(SALARY FROM EMPLOYEE WHERE ROW_NUMBER = 3 ORDER BY SALARY DESC) )


This query will work fine on oracle database but will not run on any other database. Interviewer was right. Now I did not know the way to figure out the third best salary. I did some Google search and found following options.

SELECT * FROM (SELECT EMPLOYEE_ID, SALARY, RANK() OVER (ORDER BY SALARY DESC) RANKSAL FROM EMPLOYEE) WHERE RANKSAL = 3;


SELECT * FROM EMPLOYEE E WHERE 3=(SELECT COUNT(DISTINCT SALARY) FROM EMPLOYEE WHERE E.SALARY<= SALARY);

SELECT LEVEL,MAX(SALARY) FROM EMPLOYEE WHERE LEVEL =3 CONNECT BY PRIOR SALARY > SALARY GROUP BY LEVEL;

So there are few ways to to figure out the third best salary.

Now during interview this question can be twisted in the following manner.

• Find the 3rd Minimum Salary.
• Find 10th Maximum/Minimum Salary.
• Find nth Maximum/Minimum salary of the Employee.
• Find all employees having salary less than 3rd best salary.