Saturday, 28 May 2016

Implement Berlin Clock


This question is asked in UBS bank Interview.

Problem:-

Berlin Clock represent time in the form of Lamps. Each Row representation of Lamps involves a
different logic. On the top of the clock there is a yellow lamp that blinks on/off every two seconds.The time is calculated by adding rectangular lamps.
  
The top two rows of lamps are red. These indicate the hours of a day. In the top row there are 4 red     lamps. Every lamp represents 5 hours. In the lower row of red lamps every lamp represents 1 hour.So if two lamps of the first row and three of the second row are switched on that indicates                 5+5+3=13h or 1 pm.
  
The two rows of lamps at the bottom count the minutes. The first of these rows has 11 lamps, the       second 4. In the first row every lamp represents 5 minutes. In this first row the 3rd, 6th and 9th lamp are red and indicate the first quarter, half and last quarter of an hour. The other lamps are yellow. In the last row with 4 lamps every lamp represents 1 minute.
  
  For example:-

   Input       Result
  00:00:00     Y
                   OOOO
                   OOOO
                   OOOOOOOOOOO
                   OOOO


Sample TimeConverter Class


import java.util.regex.Matcher;  
 import java.util.regex.Pattern;  
 /**  
  * This class contains the business logic to convert time into Berlin Clock  
  *   
  * @author Dixit  
  *   
  */  
 public class TimeConverterImpl implements TimeConverter {  
 /**  
       * Method validates and convert the time(hh:mm:ss) into Berlin Clock(in the form of Lamps)  
       * For example: 00:00:00 is converted into   
       * Y  
       * OOOO  
       * OOOO  
       * OOOOOOOOOOO  
       * OOOO  
       *   
       * @param aTime consist of String in the form of hh:mm:ss.  
       * @return String consisting of Lamps value.  
       */  
      @Override  
      public String convertTime(String time) {  
           // Input time needs to validated first before performing conversion.  
           if (!validateInputTime(time)) {  
                return TimeConverterConstants.INVALID_TIME;  
           }  
           int timeUnitDivisibleByFive;  
           int timeUnitModulusOfFive;  
           int timeUnitValue;  
           // Input time is split using String split method providing ":" as  
           // argument  
           String[] splitTime = time.split(TimeConverterConstants.COLON);  
           StringBuffer convertedTime = new StringBuffer();  
           // first Seconds Lamp(First Row) is appended to StringBuffer.  
           convertedTime.append(getLamps(Integer.parseInt(splitTime[2])));  
           // line separator is added  
           convertedTime.append(TimeConverterConstants.LINE_SEPARATOR);  
           timeUnitValue = Integer.parseInt(splitTime[0]);  
           timeUnitDivisibleByFive = timeUnitValue  
                     / TimeConverterConstants.MULTIPLE_OF_FIVE;  
           timeUnitModulusOfFive = timeUnitValue  
                     % TimeConverterConstants.MULTIPLE_OF_FIVE;  
           // append second row of Hour Lamps  
           convertedTime.append(getLamps(timeUnitValue, timeUnitDivisibleByFive,  
                     TimeConverterConstants.RED_LAMP));  
           convertedTime.append(TimeConverterConstants.LINE_SEPARATOR);  
           // append third row of Hour Lamps  
           convertedTime.append(getLamps(timeUnitValue, timeUnitModulusOfFive,  
                     TimeConverterConstants.RED_LAMP));  
           convertedTime.append(TimeConverterConstants.LINE_SEPARATOR);  
           timeUnitValue = Integer.parseInt(splitTime[1]);  
           timeUnitDivisibleByFive = timeUnitValue  
                     / TimeConverterConstants.MULTIPLE_OF_FIVE;  
           timeUnitModulusOfFive = timeUnitValue  
                     % TimeConverterConstants.MULTIPLE_OF_FIVE;  
           // append fourth row of Minute Lamps.  
           convertedTime.append(getLamps(timeUnitValue, timeUnitDivisibleByFive,  
                     TimeConverterConstants.RED_LAMP,  
                     TimeConverterConstants.YELLOW_LAMP));  
           convertedTime.append(TimeConverterConstants.LINE_SEPARATOR);  
           // append fifth row of Minute Lamps.  
           convertedTime.append(getLamps(timeUnitValue, timeUnitModulusOfFive,  
                     TimeConverterConstants.YELLOW_LAMP));  
           return convertedTime.toString();  
      }  
      /**  
       * Method Validates the Time It checks for following things:- 1) Checks for  
       * Null and empty value of inputTime. 2) Checks for proper valid pattern of  
       * time in the form of (hh:mm:ss) and also check for limit value allowed in  
       * HH ,MM and SS. For example: 00:00:00 is valid time but 00:00 is not.  
       *   
       * @param inputTime  
       *      consist of time in the form of hh:mm:ss.  
       * @return true if input is correct and false if input is not correct.  
       */  
      private boolean validateInputTime(String inputTime) {  
           try {  
                if (inputTime != null && !inputTime.isEmpty()) {  
                     Pattern timeRegexPattern = Pattern  
                               .compile(TimeConverterConstants.TIME_REGEX_PATTERN);  
                     Matcher timeMatcher = timeRegexPattern.matcher(inputTime);  
                     if (!timeMatcher.matches()) {  
                          return false;  
                     }  
                } else {  
                     return false;  
                }  
           } catch (Exception e) {  
                System.out.println("Exception occured in validation method :-"  
                          + e.getMessage());  
           }  
           return true;  
      }  
      /**  
       * Method checks if timeUnitValue modulus of 2 is 0 then it returns YELLOW  
       * Lamp else it returns OFF Lamp.  
       *   
       * @param timeUnitValue  
       *      consist of SS value.  
       * @return String consist of Single Lamp.  
       */  
      @Override  
      public String getLamps(int timeUnitValue) {  
           if (timeUnitValue % TimeConverterConstants.MULTIPLE_OF_TWO == 0) {  
                return TimeConverterConstants.YELLOW_LAMP;  
           } else {  
                return TimeConverterConstants.OFF_LAMP;  
           }  
      }  
      /**  
       * This method returns Eleven Lamps based on the numericValue passed  
       * to it. The lamps result may consist of RED,YELLOW,OFF and combination of  
       * (RED and OFF)Lamps or (YELLOW and OFF) Lamps.  
       *   
       * @param timeUnitValue  
       *      consist of MM value.  
       * @param numericValue  
       *      consist of integer value divisible by five.  
       * @param strRedLamp  
       *      consist of RED lamp value.  
       * @param strYellowLamp  
       *      consist of YELLOW lamp value.  
       * @return String consist of Eleven Lamps.  
       */  
      @Override  
      public String getLamps(int timeUnitValue, int numericValue,  
                String strRedLamp, String strYellowLamp) {  
           StringBuilder lamps = new StringBuilder(  
                     TimeConverterConstants.ELEVEN_OFF_LAMPS);  
           for (int i = 0; i < numericValue; i++) {  
                if ((i + 1) % TimeConverterConstants.MULTIPLE_OF_THREE == 0) {  
                     lamps.replace(i, i + 1, strRedLamp);  
                } else {  
                     lamps.replace(i, i + 1, strYellowLamp);  
                }  
           }  
           return lamps.toString();  
      }  
      /**  
       * This method returns four Lamps based on the numericValue passed to  
       * it. The lamps result may consist of RED,YELLOW,OFF and combination of  
       * (RED and OFF)Lamps or (YELLOW and OFF) Lamps.  
       *   
       * @param timeUnitValue  
       *      consist of either HH or MM value.  
       * @param numericValue  
       *      consist of integer which may be divisible of five or modulus  
       *      of five.  
       * @param strLamp  
       *      lamp value passed to the function. It can be either RED or  
       *      YELLOW.  
       * @return String consist of four Lamps.  
       */  
      @Override  
      public String getLamps(int timeUnitValue, int numericValue, String strLamp) {  
           StringBuilder lamps = new StringBuilder(  
                     TimeConverterConstants.FOUR_OFF_LAMPS);  
           for (int i = 0; i < numericValue; i++) {  
                lamps.replace(i, i + 1, strLamp);  
           }  
           return lamps.toString();  
      }  
 }  



To get the full code,please hit this link Berlin Clock

Enjoy Programming :)

JDK 1.8 Compiler Compliance is not available in Eclipse Kepler


Most of the time we encounter this issue that jdk 1.8 Compiler compliance is not available in Eclipse .Mostly this issue seen in Kepler.

Steps to resolve this issue:-

  1. Go to Help in Eclipse and Oper Eclipse Market Place option.
  2. Search for jdk 1.8 for kepler
  3. Install the required plugin.
  4. Restart the eclipse.

Enjoy Coding :)

Write Comparator for Student class, assuming student class has name and roll number.


Question:-

Write comparator for Student class, assuming student class has name and roll number.

           Conditions:

                   If the name is same, check of roll number

                   If the name is different, check only for name



Sample Program:-


import java.util.Comparator;  
 /**  
  * Comparator for Student class which uses following field for comparison  
  *   
  * 1.Name ,If name are same, then it uses Roll Number.  
  *   
  * If Name are different , then it checks for name only.  
  *   
  * @author   
  *  
  */  
 public class StudentComparator implements Comparator<Student> {  
   @Override  
   public int compare(Student student1, Student student2) {  
    if (student1 != null && student2 != null) {  
      String name1 = student1.getName().trim();  
      String name2 = student2.getName().trim();  
      if (name1.equals(name2)) {  
       return student1.getRollNumber() - student2.getRollNumber();  
      }  
      return name1.compareTo(name2);  
    }  
    return 0;  
   }  
 }  

Enjoy Programming :)

How to implement an ArrayList


Sample Program:-


/**  
  * @author Dixit  
  *  
  */  
 public class CustomArrayListImpl {  
      private static final int LIST_SIZE = 5;  
      private Object data[];  
      private int index;  
      private int size;  
      public CustomArrayListImpl() {  
           this.data = new Object[LIST_SIZE];  
           this.size = LIST_SIZE;  
      }  
      public void add(Object obj) {  
           System.out.println("index:" + this.index + " list size:"  
                     + this.data.length);  
           if (this.index == this.size - 1) {  
                increaseSize();  
           }  
           data[this.index] = obj;  
           this.index++;  
      }  
      private void increaseSize() {  
           this.size = this.size + LIST_SIZE;  
           Object newData[] = new Object[this.size];  
           for (int i = 0; i < data.length; i++) {  
                newData[i] = data[i];  
           }  
           this.data = newData;  
           System.out.println("index:" + this.index + " List size:"  
                     + this.data.length);  
      }  
      public Object get(int i) throws Exception {  
           if (i > this.index - 1) {  
                throw new Exception("ArrayIndexOutOfBound Occurs");  
           }  
           if (i < 0) {  
                throw new Exception("Negative Value Provided");  
           }  
           return this.data[i];  
      }  
      public void remove(int i) throws Exception {  
           if (i > this.index - 1) {  
                throw new Exception("ArrayIndexOutOfBound Occurs");  
           }  
           if (i < 0) {  
                throw new Exception("Negative Value Provided");  
           }  
           System.out.println("Object getting removed:" + this.data[i]);  
           for (int x = i; x < this.data.length - 1; x++) {  
                data[x] = data[x + 1];  
           }  
           this.index--;  
      }  
      /**  
       * @param args  
       * @throws Exception  
       */  
      public static void main(String[] args) throws Exception {  
           CustomArrayListImpl list = new CustomArrayListImpl();  
           list.add("0");  
           list.add("1");  
           list.add("2");  
           list.add("3");  
           list.add("4");  
           System.out.println("After resizing :-");  
           list.add("5");  
           list.remove(4);  
           System.out.println(list.get(3));  
      }  
 }  


 Output:  
 index:0 list size:5  
 index:1 list size:5  
 index:2 list size:5  
 index:3 list size:5  
 index:4 list size:5  
 index:4 List size:10  
 After resizing :-  
 index:5 list size:10  
 Object getting removed:4  
 3  

Explanation:-
List initial size is set to 5 and it is increased dynamically every time with more 5 indexes.                        
Limitations:-
In Object array we need to provide the size at the time of initialization which is not required for ArrayList. ArrayList automatically assigns its size to 10.

If List is used in Multithreading environment, where two threads are operating on it. One Thread is iterating over it and another thread is adding element to it, then in that case it will throw ConcurrentModificationException.

In order to avoid ConcurrentModificationException, we need to work on the clone of original ArrayList.


Enjoy Programming:)

Write program to sort map by value


Sample Program:-


import java.util.ArrayList;  
 import java.util.Collections;  
 import java.util.Comparator;  
 import java.util.HashMap;  
 import java.util.List;  
 import java.util.Map;  
 import java.util.Map.Entry;  
 import java.util.Set;  
 /**  
  * @author Dixit  
  *  
  */  
 public class SortMapByValues {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           // Suppose map contains roll number as key and Name as values  
           Map<Integer, String> studentMap = new HashMap<Integer, String>();  
           studentMap.put(1, "Satish");  
           studentMap.put(2, "Ashish");  
           studentMap.put(3, "Manish");  
           studentMap.put(4, "Rajnish");  
           studentMap.put(5, "Kavita");  
           Set<Map.Entry<Integer, String>> set = studentMap.entrySet();  
           List<Map.Entry<Integer, String>> list = new ArrayList<Map.Entry<Integer, String>>(  
                     set);  
           Collections.sort(list, new Comparator<Map.Entry<Integer, String>>() {  
                @Override  
                public int compare(Entry<Integer, String> o1,  
                          Entry<Integer, String> o2) {  
                     return o1.getValue().compareTo(o2.getValue());  
                }  
           });  
           for (Map.Entry<Integer, String> entry : list) {  
                System.out.println(entry.getKey() + " " + entry.getValue());  
           }  
      }  
 }  


Output:  
 2 Ashish  
 5 Kavita  
 3 Manish  
 4 Rajnish  
 1 Satish  


Explanation:-
In above program, I have created HashMap which contains key as roll number and values as name. First I get the entryset from the map and store it into Set. Then I convert the Set into the list so that I can sort it using custom comparator .I have used Collections utility class sort method for sorting and I have provided custom comparator to it.

Enjoy Programming :)

Sort a stack using temporary stack


Stack is a data structure which is based on first-in ,last-out algorithm.It basically means the element which is added first will be removed at last.There are various ways available to sort the stack of which one of them is using temporary stack.

Sample Program:-


 import java.util.Stack;  
 /**  
  * @author Dixit  
  *  
  */  
 public class StackSorting {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           Stack<Integer> stack = new Stack<Integer>();  
           stack.add(1);  
           stack.add(5);  
           stack.add(10);  
           stack.add(9);  
           stack.add(2);  
           Stack<Integer> tempStack = new Stack<Integer>();  
           while (!stack.isEmpty()) {  
                int value = stack.pop();  
                while (!tempStack.isEmpty() && tempStack.peek() > value) {  
                     stack.push(tempStack.pop());  
                }  
                tempStack.push(value);  
           }  
           for (int i = 0; i < tempStack.size(); i++) {  
                System.out.println(tempStack.get(i));  
           }  
      }  
 }  


Output:  
 1  
 2  
 5  
 9  
 10  



Enjoy Programming:)

Find sum of each digit in a number using recursion


Recursion is a technique which allows to define something in terms of itself which means recursion allows a method to call itself repeatedly.Finding sum of digit using for loop is easy but using recursion it is bit tricky.

Sample Program:-


 /**  
  * @author Dixit  
  *  
  */  
 public class SumOfDigitUsingRecursion {  
      private static int sum = 0;  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           String number = "7214";  
           if (number != null && !number.trim().isEmpty())  
                System.out  
                          .println("Sum of Digit of given number " + number  
                                    + " is :-"  
                                    + getSumOfDigit(Integer.parseInt(number.trim())));  
           else  
                System.out.println("Either String is empty or null");  
      }  
      private static int getSumOfDigit(int num) {  
           if (num == 0)  
                return sum;  
           else {  
                sum = sum + (num % 10);  
                getSumOfDigit(num / 10);  
           }  
           return sum;  
      }  
 }  


Limitations:
  • If your number is larger, then it will occupy more memory space as well as time.


Enjoy Programming:)

Find the middle node of linked list in one pass


Linked List is data structure which consist of nodes.Each node consist of data,previous node pointer and next node pointer.Previous node pointer points to previous node and next node pointer points to next node.Finding a middle node of linked list is one of important question asked in interview for experienced professionals.

Sample Program:-


 public class FindMiddleNodeInLinkedList {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           LinkedList linkedList = new LinkedList();  
           LinkedList.Node head = linkedList.head();  
           linkedList.add(new LinkedList.Node("10"));  
           linkedList.add(new LinkedList.Node("9"));  
           linkedList.add(new LinkedList.Node("8"));  
           linkedList.add(new LinkedList.Node("7"));  
           linkedList.add(new LinkedList.Node("6"));  
           LinkedList.Node current = head;  
           int length = 0;  
           LinkedList.Node middle = head;  
           while (current.next() != null) {  
                length++;  
                if (length % 2 == 0) {  
                     middle = middle.next();  
                }  
                current = current.next();  
           }  
           if (length % 2 == 1) {  
                middle = middle.next();  
           }  
           System.out.println(" Middle element of LinkedList is : " + middle);  
      }  
 }  
 class LinkedList {  
      private Node head;  
      private Node tail;  
      public LinkedList() {  
           this.head = new Node("head");  
           tail = head;  
      }  
      public Node head() {  
           return head;  
      }  
      public void add(Node node) {  
           tail.next = node;  
           tail = node;  
      }  
      public static class Node {  
           private Node next;  
           private String value;  
           public Node(String value) {  
                this.value = value;  
           }  
           public String value() {  
                return value;  
           }  
           public void setValue(String value) {  
                this.value = value;  
           }  
           public Node next() {  
                return next;  
           }  
           public void setNext(Node next) {  
                this.next = next;  
           }  
           public String toString() {  
                return this.value;  
           }  
      }  
 }  


Corner Cases:-
  • If only one node is present, then it will return the node.
  • If even number of nodes are present, then it will return middle element as the node which is exactly divisible by 2.


Enjoy Programming:)

Find first non repeated character in a string



String is most important topic in Java.There are many programming question on String which are important from interview perspective.This is one of the problem where we need to find the first non repeated character in the String.There can be multiple solutions for this problem.One of the solution is as follows:-

Sample Program:-


import java.util.Hashtable;  
 public class FirstUnRepeatedCharacter {  
      private static Character getFirstUnRepeatedCharacterUsingHashTable(  
                char[] charArray) {  
           Hashtable<Character, Integer> hashtable = new Hashtable<Character, Integer>();  
           for (Character character : charArray) {  
                if (!hashtable.containsKey(character))  
                     hashtable.put(character, 0);  
                else  
                     hashtable.put(character, hashtable.get(character) + 1);  
           }  
           for (Character character : charArray) {  
                if (hashtable.get(character) == 0)  
                     return character;  
           }  
           return 0;  
      }  
      private static char getFirstUnRepaedtedCharacterUsingLoops(String str) {  
           int count;  
           for (int i = 0; i < str.length(); i++) {  
                count = 0;  
                for (int j = 0; j < str.length(); j++) {  
                     if (i != j && str.charAt(i) == str.charAt(j)) {  
                          count = count + 1;  
                          break;  
                     }  
                }  
                if (count == 0) {  
                     return str.charAt(i);  
                }  
           }  
           return 0;  
      }  
      public static void main(String[] args) {  
           String str = "daabbcc";  
           System.out.println("First Un repeated Character Using For loops:-"  
                     + getFirstUnRepaedtedCharacterUsingLoops(str));  
           System.out.println("First Un repeated Character Using HashTable:-"  
                     + getFirstUnRepeatedCharacterUsingHashTable(str.toCharArray()));  
      }  
 }  



The Time Complexity in case of First approach i.e. using for loops is O(n2) because each character is compared with remaining characters and 2 for loops are used for that to iterate over all the characters.
And The time Complexity for other approach i.e. using HashTable is O(2n) because first loop is used to insert the character in HashTable along with the count of character and Second loop is used to get the first unrepeated character.
First approach is preferable if given string is small and in case of large String we can use Second approach.



Enjoy Programming :)