Friday, December 25, 2015

Amazon Interview 1: Problem 2

Problem 2: Given two linked lists. Each node stores a single digit. Each linked list this way represents a decimal number, with number of digits = number of nodes in the list. You need to add them to produce a third list which represents the sum of the numbers.

Problem statement would be complete only if we know the how decimal numbers are represented in the list.


To represent .123 the list is 1 -> 2-> 3


To add 2 numbers, you must consider the following scenario:


List 1 = 4 -> 5 -> 6

List 2 = 6 -> 9

Returned list should be 1 -> 1 -> 4 -> 6 (Though if this is considered only decimal number, it would be incorrect) but for time being let's consider this as a solution.


Solution 1: Modify the shorter list to append the '0' (Zero) to make both the lists size equal. For each list reach to ith location (1 <= i <= N ) starting from the Size of the list and add both the lists. If sum is greater than one use carry to add (i - 1) position.


List 1 => 4 -> 5 -> 6

List 2 => 6 -> 9 -> 0

When I = 3 (Iteration to reach 3rd position = 3)

List 3 => 6
Carry = 0

When I = 2 (Iteration to reach 3rd position = 2)

List 3 => 4 -> 6
Carry  = 1

When I = 1 (Iteration to reach 3rd position = 1)

List 3 => 1 -> 4 -> 6
Carry = 1

Exit the loop and add carry to list 3

List 3 => 1 -> 1 -> 4 -> 6

Time Complexity: 3 + 2 + 1 (N = 3)

Time Complexity for N elements: N + (N-1) + .... + 1 = N(N+1)/2 = O(N*N)

Time complexity of the above solution is O(N*N)


Solution 2: You can even reverse the lists and add them simply. But reversing the list would also require O(N*N) time complexity, and you would change the original structure of the input which is not desirable.


Solution 3: Here is another idea which performs better in normal circumstances, whereas in worst case it has same O(N*N) time complexity.




Logic
 method add start
  input list1 and list2
  minLength = find the smaller length of both the list
  assign a boolean array of len = minLength
  create a node with sum of list1 and list 2 digit mod 10
  array[0] = assign true if sum is greater than zero
  repeatTill = array[0] == true? 0:-1;
  for element from 1 to min length
   create a node with sum of list1 and list 2 digit mod 10
   array[element] = assign true if sum is greater than zero  
   repeatTill = array[element] == true? element:repeatTill;
  end for
  assign the remaining elements of the longer list to new list
  call recursive method to update the carries
 end
 
 method updateCarries start
  input list3, boolean[] array, repeatTill
  if repeatTill is negative then
   return list3
  end if
  if array[0] is true then
   add Node with digit 1 at front of the list
  end if
  for element from 1 to repeatTill
   if array[element] is true then
    assign repeatTill if array[element-1] is true
    update values
   end if
  end for
  return call updateCarries
 end



This solution's best case is O(N) when there is no carry in these two digits. For Example when 123 and 234 are added. In this case, loop is iterated only once.

Whereas in the worst case it will run for O(N*N). That would be most unusual addition. For Example when 9999 and 0001 are added. In this case, N*(N+1)/2 elements are accessed.

Java code for the solution is as following:

Java Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problem: Given two linked lists. Each node stores a single digit. Each linked
 * list this way represents a decimal number, with number of digits = number of
 * nodes in the list. You need to add then to produce a third list which
 * represents the sum of the numbers.
 * 
 * E.G. LinkedList 1 -> 2 -> 6 LinkedList 3 -> 8
 * 
 *
 */
public class SumDecimal {

 /**
  * This method reads the input and prepares the array and call the relevant
  * method.
  * 
  * @param args
  * @throws IOException
  */
 public static void main(String[] args) throws IOException {

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line = br.readLine();
  /**
   * N is the number of test cases.
   */
  int N = Integer.parseInt(line);
  for (int i = 0; i < N; i++) {
   String[] list1Values = br.readLine().split(" ");
   String[] list2Values = br.readLine().split(" ");
   Node list1 = null;
   for (int index = list1Values.length - 1; index >= 0; index--) {
    Node n = new Node(Integer.parseInt(list1Values[index]));
    n.next = list1;
    list1 = n;
   }
   Node list2 = null;
   for (int index = list2Values.length - 1; index >= 0; index--) {
    Node n = new Node(Integer.parseInt(list2Values[index]));
    n.next = list2;
    list2 = n;
   }
   Node list3 = add(list1, list2);
   System.out.println(list3);
  }
 }

 private static Node add(Node list1, Node list2) {
  int minLength = 1;
  Node l1 = list1;
  Node l2 = list2;
  while (l1.next != null && l2.next != null) {
   minLength++; // M or N whatever is smaller.
   l1 = l1.next;
   l2 = l2.next;
  }
  boolean[] carries = new boolean[minLength];
  Node list3 = new Node((list1.digit + list2.digit) % 10);
  Node list = list3;
  carries[0] = (list1.digit + list2.digit) / 10 == 0 ? false : true;
  int toMove = carries[0] ? 0 : -1;
  for (int index = 1; index < minLength; index++) {
   Node n = new Node((list1.next.digit + list2.next.digit) % 10);
   carries[index] = (list1.next.digit + list2.next.digit) / 10 == 0 ? false : true;
   list1 = list1.next;
   list2 = list2.next;
   list3.next = n;
   list3 = list3.next;
   toMove = carries[index] ? index : toMove;
  }
  if (list1.next != null) {
   list3.next = list1.next;
  } else {
   list3.next = list2.next;
  }
  list = updateCarries(list, carries, toMove);
  return list;
 }

 private static Node updateCarries(Node list3, boolean[] carries, int toMove) {
  if (toMove == -1)
   return list3;
  int nextMove = -1;
  Node list = list3;
  if (carries[0]) {
   Node n = new Node(1);
   n.next = list3;
   list = n;
   carries[0] = false;
  }
  for (int index = 1; index <= toMove; index++) {
   if (carries[index]) {
    int sum = list3.digit + 1;
    carries[index - 1] = sum == 10 ? true : false;
    list3.digit = sum % 10;
    carries[index] = false;
    nextMove = carries[index - 1] ? index - 1 : nextMove;
   }
   list3 = list3.next;
  }
  return updateCarries(list, carries, nextMove);
 }

 static class Node {
  int digit;
  Node next;

  Node(int digit) {
   this.digit = digit;
  }

  public String toString() {
   return (next == null) ? digit + "" : digit + " " + next.toString();
  }
 }

}



Input
7
1 2 3
2 3 4
3 4 5
3 4 5
9 9 9
0 0 1
9 0 0
1 9 9
9 8 1
1 2
1 2 6 8 9 6 7 8 9
9
1 2 6 8 9 6 7 8 9
9 8 4 2 1 4 3 8 7

Output
3 5 7
6 9 0
9 9 9
1 0 9 9
1 1 0 1
1 0 2 6 8 9 6 7 8 9
1 1 1 1 1 1 1 1 7 6

If you feel that something is not correct with the solution, let me know. I would try to fix the problem.

Thursday, December 24, 2015

Amazon Interview 1: Problem 1

This is not my interview question. It was conducted for my friend. He cleared his interview. Now I am sharing/solving all the questions asked to him.

Question 1: Given a sorted array of numbers, some of which may be repeating. Find the first occurrence of a given number.

Answer: In this case we use a binary search which is modified a bit to find min or max.

       If Binary search matches, get the minimum element in left subtree.
  Fetch Mid
  Check whether high is lower than low, return
  Element matches again, so check if next left subtree matches.
  Element does not matches, find if right subtree has the same element.
 Remaining is the binary search.

Following is the program for the solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problem: Given a sorted array of numbers, some of which may be repeating.
 * Find the first occurrence of a given number.
 * 
 * E.G. 1, 2, 2, 4, 8, 9, 10, 10, 10, 12
 * 
 * @author Praveen
 *
 */
public class FindFirstElement {

 /**
  * This method reads the input and prepares the array and call the relevant method.
  * @param args
  * @throws IOException
  */
 public static void main(String[] args) throws IOException {

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line = br.readLine();
  /**
   * N is the number of test cases.
   */
  int N = Integer.parseInt(line);
  for (int i = 0; i < N; i++) {
   String[] values = br.readLine().split(" ");
   int[] array = new int[values.length];
   for (int index = 0; index < values.length; index++) {
    array[index] = Integer.parseInt(values[index]);
   }
   String find = br.readLine();
   int element = Integer.parseInt(find);
   System.out.println(findIndexForElement(array, element, 0, array.length - 1));
  }
 }

 /**
  * Solution is to use a modified binary search.
  * 1. If Binary search matches, get the minimum element in left subtree.
  * 2. Remaining is the binary search.
  * @param array
  * @param element
  * @param low
  * @param high
  * @return
  */
 private static int findIndexForElement(int[] array, int element, int low, int high) {
  if (low > high) {
   return -1;
  }
  int mid = (low + high) / 2;
  if (array[mid] == element) {
   return getMin(array, element, low, mid - 1);
  } else if (array[mid] > element) {
   return findIndexForElement(array, element, low, mid - 1);
  } else {
   return findIndexForElement(array, element, mid + 1, high);
  }
 }

 /**
  * Finds the element that it first in the array.
  * Solution:
  * 1. Fetch Mid
  * 2. Check whether high is lower than low, return
  * 3. Element matches again, so check if next left subtree matches.
  * 4. Element does not matches, find if right subtree has the same element.
  * @param array
  * @param element
  * @param low
  * @param high
  * @return
  */
 private static int getMin(int[] array, int element, int low, int high) {
  int mid = (low + high) / 2;
  if (low > high) {
   return high + 1;
  } else if (array[mid] == element) {
   return getMin(array, element, low, mid - 1);
  } else {
   return getMin(array, element, mid + 1, high);
  }
 }

}

This program has been tested with the following test cases:
15
1 2 2 4 8 9 10 10 10 12
12
1 2 2 4 8 9 10 10 10 12
16
1 2 2 4 8 9 10 10 10 12
10
1 2 2 4 8 9 10 10 10 12
2
1 2 2 4 8 9 10 10 10 12
1
1 2 2 4 8 9 10 10 10 12
0
1 2 2 4 8 9 10 10 10 12
9
1 2 2 4 8 9 10 10 12
12
1 2 2 4 8 9 10 10 12
16
1 2 2 4 8 9 10 10 12
10
1 2 2 4 8 9 10 10 12
2
1 2 2 4 8 9 10 10 12
1
1 2 2 4 8 9 10 10 12
0
1 2 2 4 8 9 10 10 12
9
1 2 2 4 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13
10

If you think that I have still missed something during testing. Suggest me.

Wednesday, December 23, 2015

Design Patterns: Coffee Vending Machine

The question was asked in an interview to design a coffee vending machine.

Most importantly it is required for us to create the object with the help of creational design patterns. We would try to go through all the creational patterns which are widely known to us.

Let's start with Builder design pattern.
Builder design pattern is applied when the object constructed is huge and application would want to split the responsibility of object creation to various different objects. It can even give you the flexibility to sneak in the different implementations of a certain object based on need.

Does this DP fit to design the coffee vending machine?
Let's look over at the requirement. Coffee vending machine dispatches only few basic things i.e. various tea, various coffees, and hot water. None of the objects are really complex in nature. So it would be waste to invest so much efforts to apply builder pattern for the given problem.

Okay, let's take up another pattern i.e. Singleton design pattern.
Singleton design patterns knowing or unknowing have been in use for us. The idea behind this pattern to allow only one instance across the application. One instance must serve the need of all object requirement.

Instead analyzing this overly, we can conclude that single instance can not serve our purpose in this case. So we can not apply singleton design pattern for our application.

Moving on to Factory Abstract design pattern. (during the interview, I was using this design pattern to implement coffee vending machine)
Factory abstract design application build various different objects based on the requirement. Application would not really not know the product yet, the object created would serve the purpose of the operation. In this case application would require one class/product for each type of product type.

Does this DP fit to design the coffee vending machine?
If vending machine is used to get hot water, an object of hot water class must be returned. In this where the options could be unlimited Factory Abstract limits these options. To add another option, application would always need to introduce new class and add the application's main object which returns the output.

Could Factory Method design pattern suffice the need for this?
Based on my understanding abstract factory and factory method are almost the same. The difference lies between the responsibility of object creation. In case of factory method, object creation responsibility is designated to a factory method.

So applying this method would also be difficult in our scenario.

Let's look at the last known creational DP i.e. Prototype DP. In this design pattern we maintain a registry of object at some place and clone the object as per the need. It is very similar to on demand object creation. So in this DP also we would need to create as many classes as the options in the vending machine. Again, we would be writing way too much code for our work.

As we could not achieve the best design pattern mechanism with the help of creational design pattern. Let's move to other side of design patterns.

Let's look at the requirement in a different way.

Coffee Vending machine is using Coffee, Tea, Water, Milk, and Sugar to create all the available options. It might be needed that option might be needed to add lemon in the water and sugar to create lemon tea. In this case, we can use mix of two patterns. One abstract factory pattern and another is decorator patterns to decorate the object based on need.

Utilization of Abstract Factory pattern. Create 3 separate classes for Water, Coffee, and Tea. These 3 are the main component of the vending machine.

Now decorate the Coffee object with milk to make it milk coffee. Coffee object in itself can be utilized for espresso. Whereas in case tea, we can add various style based on the need.

milkCoffee = new Coffee(new Milk());
milkTea = new Tea(new Milk(new Masala()))
gingerTea = new Tea(new Milk(new Ginger()))
gingerMasalaTea = new Tea(new Milk(new Ginger(new Masala())))

Styling the tea and coffee can be solved with decorator pattern.

Why did we use different objects for tea and coffee?
Tea, Coffee, and Water are different products. So based on usual product understanding, we kept them separate and added styles later which are ginger to tea, masala to tea, and so on. Though it is possible to add the styles to the water to create coffee and tea also.
milkCoffee = new Water(Coffee(new Milk()));

If you think that your understanding deviates from mine. Let me know. We can discuss that in details.

Sunday, December 20, 2015

Daily Hunt: Interview Questions #3

As I have been part of rat race to find another Job. It was my 3rd interview with Daily Hunt.. It was mix of data structures and Java. I was asked 3 questions on Data Structures and various other questions related to Java.

Question 1: It is related to Data Structure. You have been given list of integers in an array and an another integer X. It is known that multiplication of 2 integers in the array is equal to X. Find the numbers from the array.

Solution 1: Solution I provided was to have 2 separate arrays. One contains the input as received and another to keep integers as Binary Search Tree.

We will iterate through the array to find the first multiplier, and once we found it we will try to find the remaining multiplier in the BST array. If the number is found is the BST, we found the else otherwise move to another integer in the input array.

Question 2: This question is on the design patterns. Design the coffee vending machine?
Coffee Vending machine is simple machine which are part of offices now a day. If you have to implement the coffee building machine, how would you do it?

Coffee vending machine can have options for various tea and various coffees. So what would be the best approach to design a software for such a coffee vending machine.

Now we have various design patterns available with us. What would be the best one for you?

The answer for the problem is the Decorator Pattern. We would discuss the same in the upcoming post in the details. Though I answered it with Abstract Factory and Abstract Method pattern. :-(

Question 3: Interviewer again moves to DS. An application is receiving the stream of strings. String may contain anagram. Application would need to detect those anagrams in the stream.
It is required to check the stream again to figure out if application has already received the string earlier in the stream to report it to be duplicate. But based on the question, 2 strings are duplicate when both of them are anagram to each other.

Simple answer for the question would be to read the string from the stream and sort the character string. Save the string in the Set, to maintain unique strings. If application tries to add the string in the set and it is already added to the set, set does not add it to array and returns false. In this case, the string can be marked as DUPLICATE.

Let's look at the example:
String a is not duplicate of ton of trings.
[String] => Set will contain {ginrst}
[a] => Set {ginrst, a}
[is] => Set {ginrst, a, is}
[not] => Set {ginrst, a, is, not}
[duplicate] => Set {ginrst, a, is, not, acdeilptu}
[of] => Set {ginrst, a, is, not, acdeilptu, of}
[ton] => Set {ginrst, a, is, not, acdeilptu, of} : No addition as 'not' already exists. It is considered as duplicate string.
[of] => Set {ginrst, a, is, not, acdeilptu, of} : No addition as 'of' already exists. It is considered as duplicate string.
[trings] => Set {ginrst, a, is, not, acdeilptu, of} : No addition as 'ginrst' already exists.

Question 4: So here comes a puzzle. 2 persons are landing on a straight line on a point A and B. Points A and B are not known to each of them. How would they find each other?
This one was interesting puzzle. I did not really have any clue about it. So I requested for the clue. Interviewer said that both the person can move in any direction. But it indicated that one of these two would move like a pendulum. So let's say that A moves but not B. So A moves to his left for half KM and later he moves to his right for 1Km. Next if could not find B yet, he moves to his left for 1.5KM, and so on.

Question 5: Here comes a DB cum Java question. An application has one table which contains only one column and one row. It maintains the user id of the users who are registering to the application. Database can only cater 10 update request per second, but number of user registering each second are 1000. How would you tackle the deadlock in this situation?
Now this was a tricky question. Initially I thought that it is required to look the solution at DB side, but rather the problem could have been solved at java side as well. My first thought was to think in terms of triggers. But triggers can not be the solution for this. Why did I think so? Trigger is a DB operation which will increase the count and save the count to database and return the value. In addition, triggers values are cached as well. It can also be a solution.

Java side we can fire the DB update after certain number of users have been created. So it is possible to maintain a static variable which will have the latest value.

I am now thinking, can we even use volatile or threadlocal variable in this? Please let me know if you have some better answer.

Question 6: What is serialization? Why do we use serialized version id for each class?
Serialization is to persist the Java memory object into file system in the form of file or database. readObject and writeObject methods are used to deserial and serial the object into the file file system.

To achieve serialization, it is required for class to implement Serializable interface.

serialVersionID is maintained to differentiate between 2 different version of classes. It helps loader to identify the class and deserial the specific object based on the version of the class. Serialization has been explained quite well in this blog.
http://exploreriddles.blogspot.in/2014/01/serialization-introduction.html

Question 7: On the deployed tomcat server, you have detected memory leak. How would you find the memory leak?
Okay, I assume that there is no fix to find the memory leak. In this case, we would need to first check in our application if something is possible leak. If it is not, it would be required to fetch the memory profile of the tomcat application and run through the profile to figure out the actual reason for the memory leak.
<!-- Notes to Me --> Learn more about Profiling.

Question 8: An application has a thread pool for 10 threads, but tasks provided to the threads are more than 10. How would you handle the situation programmatically?
Okay, I could not handle last 3 questions quite well. I was not to answer all simple questions of this interview. My assumption was that threadpool handles this scenario at it's own. As soon as, we submit a task to thread pool, it checks if there is any thread which is free. Threadpool assigns the task to the certain thread else if all threads are running, it send the task in the wait status to be notified once ny of the thread becomes free.

I am not an expert. I am also for the solution for the questions stated above. If you know some answers, let me know.

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

Tuesday, December 8, 2015

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.

Monday, January 5, 2015

Integrating a PostGreSql database to WAMP server

I am working with WAMP server for quite some time. For my production I have application compatible with PostGreSQL but WAMP was configured with MySQL. It was really a trouble some thing for me.

As I am quite new to PHP, so I was not aware about integrating PostGreSQL with WAMP server. But now I know that. Thanks to the post mentioned below, it helped me a lot to get it working.

http://toolkt.com/site/install-postgresql-and-phppgadmin-in-windows-with-wamp/

Sunday, January 19, 2014

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).

Friday, January 17, 2014

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.