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.

Flipkart Interview 1: Data Structure and Algorithm

It was a telephonic discussion with Flipkart, as per its reputation, its interview throws questions to provide algorithms for them. In the first telecon, I was asked 2 questions (though the interviewer wanted to discuss 3), and those are following 2 questions.

A Binary tree is there, root of the binary tree is provided. It is asked to search a node and find all the nodes that are at a K distance from the tree.

Binary Tree - Not BST

 Consider the tree provided in the figure above.

Root of the tree is A, and it is required to find all the elements at distance 3 from Node D.

Answer should be C, J and K.

Root of the tree is A, and it is required to find all the elements at distance 2 from Node D.

Answer should be A, E, P, Q, R, and S.

Root of the tree is A, and it is required to find all the elements at distance 4 from Node D.

Answer should be T, U, V, F and G.

Solution

It is possible to create the graph where starting node of the graph is D as the starting node of the graph. Search Node along with its path. Create a graph with the help of path that was retained while searching the node, find all the nodes at distance K using BFS.

Algorithm for this as follows:

List 1
Find the element using recursion and store all the elements in a stack.
(Time complexity O(n))
Create the graph such that all the parents, catered in the stacks,
points in the other direction. i.e. D -> B-> A
(Time complexity O log(n) + Space Complexity o(Log n))
Now run the Breadth First Search algorithm to for iterations.
(Time complexity O(n))

Total time complexity for the solution is O(n + log n) = O(k*n) = O(n)

Space Complexity is O(log n). 

Let’s look at the alternative approach, as we have to change the linking, so it might not be feasible to change the DS.

List 2
Find the element using recursion and store all the elements in a stack, 
along with the side of the side of the traversal (Left or Right). 
(Time complexity O(n))
Find all downward elements that are at distance K from the node specified.
For each element pop the stack and maintain a count
From the node popped, find all the elements at (K – count) distance 
at the other side of tree.
End for each 

Let’s write a program for the method mentioned above.

We will need 2 classes for complete DS and solution.

Tree.java
class Tree {  
  char data;
  Tree left;
  Tree right;
  public Tree(char data) {
   this.data = data;
  }
  public char getData() {
   return data;
  }
  public void setData(char data) {
   this.data = data;
  }
  public Tree getLeft() {
   return left;
  }
  public void setLeft(Tree left) {
   this.left = left;
  }
  public Tree getRight() {
   return right;
  }
  public void setRight(Tree right) {
   this.right = right;
  }  
  public String toString(){
   return "" + data;
  }
 }

PathElement.java 
class PathElement {
  int direction;
  Tree node;
  public PathElement(Tree node, int dir) {
   this.node = node;
   direction = dir;
  }
  public int getDirection() {
   return direction;
  }
  public void setDirection(int direction) {
   this.direction = direction;
  }
  public Tree getNode() {
   return node;
  }
  public void setNode(Tree node) {
   this.node = node;
  }
  public String toString(){
   return ("Node:" + node.toString() + " Direction: " + direction  + "\n");
  }
 }

Search the path for element requested, and Keep the PathElement object with the stack.

List 3
 Stack path = new Stack();
 private boolean searchElement(Tree root, char search, int direction) {
  if( root == null ) return false;
  if( root.data == search ){
   path.push(new PathElement(root, direction));
   return true;
  }else{
   path.push(new PathElement(root, direction));
   boolean isInLeftTree = searchElement(root.getLeft(), search, 1);
   boolean isInRightTree = !isInLeftTree? searchElement(root.getRight(), search, 2) : false;
   if(!isInLeftTree && !isInRightTree ){
    path.pop();
    return false;
   }
   return true;
  }
 }

Read the downward element and create for these downward element.

List 4
 private List downwardElements(PathElement elem, int distance) {
  List chars = new LinkedList();
  return readElementAtDistanceK(chars, elem.node, distance);
  //Following method is listed further.
 }

Read the upward elements and add them to the list created above.

List 5
 private List upward(Stack path, PathElement pathElem, int distance) {
  PathElement prevElement = pathElem;
  PathElement element;
  int count = 1;
  List chars = new LinkedList();
  try{
   while( ( element = path.pop() ) != null){
    readElementsInDifferentDirection(chars, element, distance - count, prevElement.direction);
    prevElement = element;
    count++;
   }
  }catch(EmptyStackException ese){
  }
  return chars;
 }

 private List readElementsInDifferentDirection(List chars, PathElement element, int i, int direction) {
  Tree root = element.node;
  if( i == 0 ){
   chars.add(root.data);
  }
  if( direction == 1 ){
   readElementAtDistanceK(chars, root.right, i - 1 );
  }else{
   readElementAtDistanceK(chars, root.left, i - 1 );
  }
  return chars;
 }

Module to Read all the elements at a distance K from a node.

List 6
 private List readElementAtDistanceK(List chars, Tree root, int distance) {
  if( root == null ) return chars;
  if( distance == 0 ){
   chars.add(root.data);
   return chars;
  }
  readElementAtDistanceK(chars, root.left, distance - 1 );
  readElementAtDistanceK(chars, root.right, distance - 1 );
  return chars;
 }

Java representation to call the module is as followed.

List 7
  tp.searchElement(root, search, 0);
  PathElement pathElem = tp.path.pop();
  List<Character> chars = tp.downwardElements(pathElem, distance);
  chars.addAll(tp.upward(tp.path, pathElem, distance));  
  System.out.println("All the Characters:" + chars);

It will contain few generic related warnings and errors, please modify them to compile and run the program.

This approach has space complexity of log(n) and time complexity as defined below.
Search the node and path = O(n) //Worst case scenario.
Search the downward and upward elements = O(n) //Worst case scenario.
Time complexity of algorithm is O(n).

Interview: Java along with Algorithm 3

First F2F was followed with another rounds of F2F. Though first round was 90 minutes long but this round did not last longer than 40 minutes.

1. How to save key and list of Integers in the HashMap?
2. How is it possible to reduce the size of this map?
3. Implement HashMap?
4. Implement LRU with the help of Map?
5. Find all possible strings of a Given String?

I have got few more interviews lined up for next couple of days. So I will try to remember post those interview question.

In addition to posting new questions, I will surely post the answers these questions.

Interview: Java along with Algorithm 2

After clearing questions in the first round, I was asked to face the interviewer in F2F rounds. I was nervous to face the interviewers after a long long time.

It all started with the general introductory question and followed with the following questions.

1. Difference between Restful and Soap web services?
2. What is Soap WS?
3. Which different XML parsers we have?
4. Write code for stream parser?
5. Tell me the class loader heirarchy?
6. What is serialization?
7. What is SerialVersionUID?
8. How does Hashmap work?
9. What are the differences between SynchronizedHashMap and ConcurrentHashMap?
10. Implement stack using 2 queues?
11. Implement stack using 1 queue?
12. Sort an array containing numbers 0,1,2?
13. Difference between abstraction and encapsulation?
14. where will you categories the private method?
15. How to stop subclass from serializing if super-class is serializable?

I will try to post answers to following question within some time.

Interview: Java along with Algorithm

Few days back, I faced a telephonic interview with a Product based company in Gurgaon. It was quite a quick interview round for me. Here I am mentioning the questions asked by interviewer.

Q1: What are the advantages of Arrays over Lists?

Q2: What are the advantages of Lists over Arrays?

So Linked list provides following two advantages over arrays

1)         Dynamic size

2)         Ease of insertion/deletion

Linked lists have following drawbacks:

1)         Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.

2)         Extra memory space for a pointer is required with each element of the list.

3)         Arrays have better cache locality that can make a pretty big difference in performance. 

Q3. Suggest the best possible data structure in these 2 conditions?

A. DS must have add, delete, search operations, where search is most used functions of the DS?

DS based on hashing technique.

B. DS must have add, delete, rangeSearch operations, where search is most used functions of the DS?

DS based on Tree technique.

Q4. What do you mean by Hashing?

Q5. What are the different algorithms to resolve hash collision?

Q6. Is it possible to call static method within a constructor?

Q7. What is synchronization?

Q8. What are the different ways of implementing Threads?

Q9. What is the difference between creating threads by implementing runnable Interface or extending thread class implementation?

Implements Runnable is the preferred way to do it, IMO. You're not really specializing the thread's behaviour. You're just giving it something to run. That means composition is the philosophically "purer" way to go.

In practical terms, it means you can implement Runnable and extend from another class as well.

Q10. What is the difference between Callable and Runnable interfaces?

The Callable interface is similar to Runnable, in that both are designed for classes whose instances are potentially executed by another thread. A Runnable, however, does not return a result and cannot throw a checked exception.

Q11. What is garbage collection?

Q12. What is the difference between notify and notifyAll()?

Q13. What are practical scenarios where notify and notifyAll work?

Algorithm: Find smallest contiguous array containing K 0's in array of 1's and 0's

I was thinking to improve my algorithmic fundamentals, so I planned to make few notes for myself that will assist me in future (Obviously at the time of Interviews). Following questions and answers have been taken from stackoverflow.com. This post is a sticky notes post for me. Please do not use the answers for reference purpose.

Following question was asked to me in an telephonic discussion with some interviewer. I had posted the question on stackoverflow where people provided me a satisfactory and efficient solution.

Problem Statement
I have array of 1's and 0's only. Now I want to find smallest contiguous subset/subarray which contains at least K 0's.

Example:

1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0

K(6) is either 0 0 1 0 1 1 0 0 0 or 0 0 0 0 1 0 1 1 0.

We have to come up with the solution where algorithm must minimize the number of iterations.

Algorithm

• In the given array, find the first occurance of 0 (say at index i).
• Keep on scanning until you've k 0's included in your window (say, the window ends at index j) Record the window Length(say j-i+1=L).
• Discard the left-most 0 at index i, and keep scanning till you get next 0 (say at index i').
• Extend the right-end of the window situated at j to j' to make the count of 0's = k again.
• If the new window-length L'=j'-i'+1 is smaller update it.

Following algorithm does not take care about the boundary conditions and all, but this can be applied to the example mentioned above.

Iteration

1. i = 3, String for K(6) 0 1 1 0 1 1 0 0 0 0, so j = 12, and l = 10.
2. i = 6, String for K(6) 0 1 1 0 0 0 0 1 0, so j = 14, and l = 9. Update
3. i = 9, String for k(6) 0 0 0 0 1 0 1 1 0, so j = 17, and l = 9. Donot update
4. i = 10, string for k(6) 0 0 0 1 0 1 1 0 0, so i = 18, and l = 9. Do not update
5. i = 11, String for k(6) 0 0 1 0 1 1 0 0 0, so I = 19, and l = 9; Do not update
6. i = 12, String for K(6) 0 1 0 1 1 0 0 0 1 1 0, so I = 22, and l = 11, do not update
7. i = 14, String for K(6) 0 1 1 0 0 0 1 1 0 0, so I = 23, and l = 10, do not update
8. i = 17, String for K(6) 0 0 0 1 1 0 0 1 0, so I = 25, and l = 9, do not update
9. i = 18, String for K(6) 0 0 1 1 0 0 1 0 0, so I = 26, and l = 9, do not update
10. i = 19, String for K(6) 0 1 1 0 0 1 0 0 0, so I = 27, and l = 9, do not update

No more iteration is available. So first string which has 6 o's and has the minimum length is selected from the array set.

Java Program

package com.number;

public class MinimumStringContainingKZeros {
 
 public String minStrHavingKZeros(String str, int k){
  int i = find(str, 1, 0);
  int j = find( str, k - 1, i + 1 );
  System.out.println( i + " && " + j);
  if( i == -1 || j == -1 ) return "";
  int i1 = i;
  int j1 = j;
  while(true){
   i1 = find(str, 1, i1 + 1);
   j1 = find(str, 1, j1 + 1);
   if( j1 == -1 ) break;
   if( j1 - i1 < j - i ){
    i = i1;
    j = j1;
   }
  }
  return str.substring(i, j + 1);
 }
 
 int find(String str, int count, int start){
  int index = start;
  while( index < str.length() ){
   if( str.charAt(index) == '0'){
    count --;
    if( count == 0 ){
     return index;
    }
   }
   index++;
  }
  return -1;
 }
}

Time Complexity

Appllication has to run through the whole characters twice, once to find the first element and another to last element.

O(n) is the time complexity of the application.

Space Complexity

No additional space is required in this algorithm.

Time Complexity of the Solution

Could you suggest me time complexity of the following solution:

02.// import java.math.*;

03.class Solution {

04. 

05.int sum = 0;

06.int sumTillCurrentIndex = 0;

07.int sumFromBack = 0;

08.int equi ( int[] A ) {

09.for(int i : A){

10.sum += i;

11.}

12. 

13.if(sum - A[0] == 0 ){

14.return 0;

15.}

16.if((sum - A[A.length -1]) == 0){

17.return(A.length -1);

18.}

19.sumFromBack = sum - A[0];

20.for(int index = 1; index < A.length - 1; index++){

21.sumTillCurrentIndex += A[index - 1];

22.sumFromBack -= A[index];

23.System.out.println("" + sum + ":"

24.+ sumTillCurrentIndex + ":" + sumFromBack );

25.if(sumFromBack == sumTillCurrentIndex){

26.return(index);

27.}

28.}

29.return -1;

30.}

31.}