Wednesday, December 9, 2015

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

No comments:

Post a Comment