Home » Posts filed under Interviews

Find the angle between the hour and minute hands in Java

in - on 13:05:00 - No comments

Find the angle between the hour and minute hands on an analog clock.

Given the time, calculate the smaller angle between the hour and minute hands on an analog clock in Java.

Java Program to find angle between hour and minute hand.

In 60 mins, clock minute hand takes 360 degree. so for 1 min = 360/60 = 6 degree.
In 12 hours, clock hour hand takes 360 degree. so for 1 hour = 360/12 = 30 degree 

But when it is 1.20, hour hand doesn't be on exact 1, and would be slightly crossed 1 (when it is 1.30, hour hand would be in between 1 and 2.) 
So we need to find out the exact position of the hour hand and the angle it covered, that is you need to find the angle hour hand makes for each minute passes. 

We already know 1 hour angle = 30 degree 
In 1 hour, we have 60 minutes, so in each minute, how much angle hour hand makes = 30/60 = 1/2.
 
package javabypatel.misc;

public class FindAngle {
    public static void main(String[] args) {
        System.out.println(findAngle(12, 25));
    }

   public static double findAngle(int hour, int minute) {
        // in 60 mins, it takes 360 degree. so for a 1 min = 360/60 = 6 degree
        double minAngle = minute * 6;

        // in 12 hours, it takes 360 degree. so for 1 hour = 360/12 = 30 degree
       double hourAngle = hour * 30;

        //but when it is 1.20, hour hand doesn't be on exact 1, and would be slightly crossed 1 (when it is 1.30, hour hand would be in between 1 and 2.)
        //So you need to find out the exact position of the hour hand and the angle it covered between a single hour.
        //that is you need to find the angle hour hand makes for each minute passes.
        //we already know 1 hour angle = 30 degree
        //In 1 hour, we have 60 minutes, so in each minute, how much angle hour hand makes = 30/60 = 1/2.
        double hourAngleForEachMinute = minute/2.0; //minute * 1/2; (divided by 2.0 to make it divide in double context)

        //Final hour angle would be hourAngle + hourAngleForEachMinute
        double finalHourAngle = hourAngle + hourAngleForEachMinute;

        double angle = Math.abs(finalHourAngle - minAngle);

        //analog clock is round, so clock hands make two angles, one in interior and one is exterior, Since we are told to return smaller angle we return minimum one.
        return Math.min(angle, 360-angle);
    }
}
Read more
Categories:

Write your own Integer to String (itoa) implementation in Java

in , - on 00:28:00 - No comments

Write your own Integer to String (itoa) converter.

Implement your own Integer to ASCII (itoa) method which converts an Integer to String.

Input 1: 123
Output: "123" (as String)

Input 2: 0
Output: "0" (as String)

Input 3: 8
Output: "8" (as String)

Algorithm

Before we look into the algorithm, lets understand the ASCII ranges for 0-9.

ASCII  Char 
--------------- 
 48   0    
 49   1    
 50   2    
 51   3    
 52   4    
 53   5    
 54   6    
 55   7    
 56   8    
 57   9 

so if we have integer 4 and we want to get the char representation of 4, we can get by
char number = '0' + 4 which would be 48 + 4 = 52 and when we do ((char) 52) we get '4'.

similarly, if we have integer 7 and we want to get the char representation of 7, we can get by
char number = '0' + 7 which would be 48 + 7 = 55 and when we do ((char) 55) we get '7'.

Lets jump to original problem, if given the number 123

Mod and Divide the number by 10 to read each digits from end, once we have the digit convert it in the way shown below and put in StringBuilder.

Java Program to convert Integer To Ascii.

package javabypatel;

public class IntegerToASCII {
    public static void main(String[] args) {
        System.out.println(integerToAscii(10));
    }

    private static String integerToAscii(int num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            int lastDigit = num % 10;
            char ch = (char) ('0' + lastDigit);

            // since we are processing the last digit first(reverse order),
            // inserting at 0th position so that output is not in reverse order.
            sb.insert(0, ch);
            num /= 10;
        }
        return sb.toString();
    }
}
Read more
Categories: ,

Write your own String to Integer (atoi) implementation in Java

in , - on 00:07:00 - No comments

Write your own String to Integer (atoi) converter.

Implement your own ASCII to Integer (atoi) method which converts a string to an integer.

Input 1: "123"
Output: 123 (as int)

Input 2: "0"
Output: 0 (as int)

Input 3: "8"
Output: 8 (as int)

Algorithm

Before we look into the algorithm, lets understand the ASCII ranges for 0-9.

ASCII  Char 
--------------- 
 48   0    
 49   1    
 50   2    
 51   3    
 52   4    
 53   5    
 54   6    
 55   7    
 56   8    
 57   9 

so if we have char '4' and we want to get the Integer representation of '4', we can get by

int number = '4' - '0' which would be 52 - 48 = 4 (an integer 4), 

similarly, if we want to get the integer representation of char '7', just subtract it by '0'.
int number = '7' - '0' which would be 55 - 48 = 7 (an integer 7), similarly

Lets jump to original problem, if given the String "123"

Iterate the String, get the first character '1', convert it to Integer as shown above.
Similarly for all the characters of the String.

For getting the integer number, we will use the technique, 

sum = 0 initially.
sum = (sum * 10) + (str.charAt(i) - '0') 

Java Program to convert Ascii To Integer.

    

package javabypatel;

public class ASCIIToInteger {
    public static void main(String[] args) {
        System.out.println(asciiToInt("10"));
    }

    private static int asciiToInt(String num) {
        int result = 0;
        for (int i = 0; i < num.length(); i++) {
            char ch = num.charAt(i);
            result = (result * 10) + (ch - '0');
        }
        return result;
    }
}
Read more
Categories: ,

Merge all overlapping intervals in Java

in - on 17:22:00 - No comments

Merge overlapping intervals in Java.

Given a N pairs of intervals. merge all overlapping intervals..

You are given a pair of intervals in a format (start time, end time), Merge intervals that overlaps with each other.

Consider this problem as asking someone availability in their calendar, and if the person calendar is like below,
Meeting from [[1,2],[2,3],[3,4],[10,12]] what the person will say?
I am busy from [1-4] and [10-12], it is like merging intervals that overlaps.

Example of Merging overlapping intervals

merge overlapping intervals

Let see some more input and output:

Example 1: Input: intervals = [[1,2],[2,3],[3,4],[10,15]]
Output: [[1,4],[10,15]]

Example 2: Input: intervals = [[1,5],[3,5],[2,6],[10,15]]
Output: [[1,6],[10,15]]

Example 3: Input: intervals = [[1,4],[2,6]]
Output: [[1,6]]

Algorithm

Lets say we are given below time intervals

(1, 4), (7, 9), (3, 6), (8, 10)

If we sort the time intervals based on start time,

(1, 4), (3, 6), (7, 9), (8, 10)

If we see the first two interval, end time of first interval is greater than start time of second interval which means there is overlap of (end time - start time).

Our task is to Iterate all the intervals and compare, if there is overlap, just Merge the both intervals into one and expand the endInterval window by comparing endTime of both intervals and consider the one which is highest.

(1, 4), (3, 6), 

Merged Interval = (1, 6)

(7, 9)

totally new range, doesn't overlap with the Merged Interval till now (1, 6)

Put it in our Merged Interval list [(1, 6), (7, 9)] 

(8, 10)

Compare the top interval from merged interval list that is compare (7, 9) with (8, 10)

there is overlap, update the window (7, 10), update the merged interval list (1, 6) (7, 10).

Java Program to Merge overlapping intervals.

    
package javabypatel

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class MergeOverlappingIntervals {

    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
                new Interval(1, 2),
                new Interval(2, 3),
                new Interval(3, 4),
                new Interval(10, 15));

        Stack<Interval> mergedIntervals = new MergeOverlappingIntervals().mergeOverlappingIntervals(intervals);
        System.out.println(mergedIntervals);
    }

    public Stack<Interval> mergeOverlappingIntervals(List<Interval> intervals) {
        if (intervals == null) {
            return null;
        }

        Stack<Interval> stack = new Stack<>();
        if (intervals.size() < 2) {
            stack.addAll(intervals);
            return stack;
        }

        Collections.sort(intervals);

        //We can take any data structure which can help us compare the top element.
        stack.add(intervals.get(0));

        for (int i = 1; i < intervals.size(); i++) {
            Interval nextInterval = intervals.get(i);
            Interval resultInterval = stack.peek();

            //Check if Interval overlaps? If yes, increase the end time
            //example (1, 3) (2, 6) -> Intervals overlaps,
            //end time will be max of both end time = 6
            //since the array is sorted by startTime, no need to update the startTime as smallest will be at top.
            if (resultInterval.endTime >= nextInterval.startTime) {
                //update the peek endTime
                resultInterval.endTime = Math.max(resultInterval.endTime, nextInterval.endTime);
            } else {
                //if no overlaps then this is the new range, add it in stack.
                stack.add(nextInterval);
            }
        }

        return stack;
    }
}
Interval.java 
package javabypatel;

public class Interval implements Comparable<Interval>{
    public int startTime;
    public int endTime;

    public Interval(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Interval interval) {
        if (startTime < interval.startTime) {
            return -1;
        } else if (startTime == endTime) {
            return 0;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Interval{" +
                "startTime=" + startTime +
                ", endTime=" + endTime +
                '}';
    }
}
Read more
Categories:

Find overlapping interval among a given set of intervals.

in - on 22:44:00 - No comments

Find overlapping interval among a given set of intervals.

Given a N pairs of intervals. Identify interval that overlap with other interval.

You are given a pair of intervals in a format (start time, end time), find interval that overlaps with other interval.

Example of overlapping intervals

find overlapping time intervals

Let see some more input and output:

Example 1:
Input: (1, 3) (3, 5) (5, 7)
Output: No overlapping Intervals.

Example 2: (2, 3) (3, 5) (1, 6)
Output: (1, 6) overlaps with (2, 3)
Though (3, 5) also overlaps with (1, 6) we are mainly looking for one of them. Given solution below find one of them. 

Algorithm

Lets say we are given below time intervals

(1, 4), (7, 9), (3, 6), (8, 10)

If we sort the time intervals based on start time,

(1, 4), (3, 6), (7, 9), (8, 10)

If we see the first two interval, end time of first interval is greater than start time of second interval which means there is overlap of (end time - start time) in this case it is (4 - 3) = overlap of 1 unit.

Our task is to just find the overlapping intervals.

Java Program to find overlapping intervals among a given set of intervals.

package javabypatel;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class OverlappingIntervals {
    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
                new Interval(1, 3),
                new Interval(6, 8),
                new Interval(2, 4),
                new Interval(5, 6));
        List<Interval> interval = new OverlappingIntervals().findOverlappingIntervalApproach1(intervals);
        System.out.println("Overlapping intervals :" + interval);

        boolean isOverlappingIntervals = findOverlappingIntervalApproach2(intervals);
        System.out.println("Is overlapping intervals :" + isOverlappingIntervals);
    }

    //Sort the intervals by start time and compare the endtime of first interval with the start time of next interval.
    //If the endTime of first interval is > then startTime of next interval means there is overlap
    //Example: [(1, 3) (2, 4)]
    //time complexity: (n log n) + n = (n log n)
    public List<Interval> findOverlappingIntervalApproach1(List<Interval> intervals) {
        Collections.sort(intervals); //(n log n)
        List<Interval> overlappingInterval = new ArrayList<>();

        for (int i = 0; i < intervals.size()-1; i++) { //n
            if (intervals.get(i).endTime > intervals.get(i+1).startTime) {
                overlappingInterval.add(intervals.get(i));
                overlappingInterval.add(intervals.get(i+1));
            }
        }
        return overlappingInterval;
    }

    //Another approach which just says there is overlap or not.
    //time complexity:
    // O(n) = to find the max element in array
    // O(m) = where m is the max element in array
    // Total = O(m + n)
    // this approach works well when the range is small
    public static boolean findOverlappingIntervalApproach2(List<Interval> intervals){
        //find the highest end time within list of all intervals
        int highestTime = intervals.get(0).endTime;
        for (int i = 1; i<intervals.size(); i++) {
            int endTime = intervals.get(i).endTime;
            if(highestTime < endTime)
                highestTime = endTime;
        }

        int[] count = new int[highestTime + 1];
        //Mark the count[startTime] to +1 and count[endTime] to -1
        for (int i = 0; i<intervals.size(); i++) {
            Interval current = intervals.get(i);
            count[current.startTime]++;
            count[current.endTime]--;
        }

        //Iterate count array and sum the values
        //if at any point sum is > 1 that means interval overlaps.
        boolean isOverlappingIntervals = false;

        int sum = 0;
        for (int i = 0; i <count.length; i++) {
            sum += count[i];
            if(sum > 1){
                isOverlappingIntervals = true;
                break;
            }
        }

        return isOverlappingIntervals;
    }
}
Interval.java 
package javabypatel;

public class Interval implements Comparable<Interval>{
    public int startTime;
    public int endTime;

    public Interval(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Interval interval) {
        if (startTime < interval.startTime) {
            return -1;
        } else if (startTime == endTime) {
            return 0;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Interval{" +
                "startTime=" + startTime +
                ", endTime=" + endTime +
                '}';
    }
}
Approach 2

In this approach, we are going to take a count array and for each given interval start time we will do count[startTime]++ and for end time, do count[endTime]--.

After filling the count array, iterate count array and do the sum of counts, If at any given index we find 
sum > 2 it means there is overlapping intervals. 

How this approach is working? say if we have intervals as (1, 3) and (2, 5), and count array for this will be. array size will be 5(highest end time in given intervals)
(1, 3) = [0, 1, 0, -1, 0,  0]
(2, 5) = [0, 1, 1, -1, 0, -1]

Whenever we see adjacent one's, it means there is y interval(in this case (2,5)) which has starting time before the end of x interval(1,3).
 
Read more
Categories:

Serialize and Deserialize N-ary tree in Java

in , , - on 16:17:00 - No comments

Serialize and Deserialize N-ary tree in java

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, serialize and deserialize it.

Example of N-ary tree Serialization-Deserialization.

Serialize and Deserialize N-ary Tree

Algorithm

Serialization and Deserialization of N-ary tree is very similar to Serialization and Deserialization of Binary tree.

I would recommend to visit the Serialization/Deserialization post if not visited before: Serialize and Deserialize a Binary Tree

In Binary tree since there are only 2 child, we can get where is the start and end of the child of a particular Node from the serailized key, but in N-ary tree a Node can have n children, so we need some method to identify the start and end of a child nodes.

In this approach we will do a preorder traversal of N-ary tree and place the length of child nodes next to Node value as shown in example below,
 
serialize and deserialize n-ary tree implementation


In Deserialization process, it is exactly reverse now, we know first key in the String is the actual node and next key is the length of child nodes of a key.

Java Program to Serialize Deserialize N-ary tree

package javabypatel;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class SerializeDeserializeNAryTree {

    public static void main(String[] args) {
        NAryNode root = new NAryNode(1,
                Arrays.asList(
                        new NAryNode(2, Arrays.asList(
                                new NAryNode(5),
                                new NAryNode(6),
                                new NAryNode(7, Arrays.asList(
                                        new NAryNode(11),
                                        new NAryNode(12))))),
                        new NAryNode(3),
                        new NAryNode(4, Arrays.asList(
                                new NAryNode(8),
                                new NAryNode(9),
                                new NAryNode(10)))
                ));

        String str = serializeTree(root, new StringBuilder());
        System.out.println(str);
        NAryNode deserializeRoot1 = deserializeApproach1(str == null? null : str.split(","), new int[1]);
        NAryNode deserializeRoot2 = deserializeApproach2(str);

        System.out.println(deserializeRoot1);
        System.out.println(deserializeRoot2);
    }

    //In this approach, we need to take a separate index array of size 1 to remember the next element in array to pick
    //or we can take a static integer to remember the state.
    private static NAryNode deserializeApproach1(String[] arr, int[] index) {
        if (arr == null || index[0] >= arr.length || arr[index[0]] == null) {
            return null;
        }

        NAryNode n = new NAryNode(Integer.parseInt(arr[index[0]++]));
        int size = Integer.parseInt(arr[index[0]++]);
        n.child = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            n.child.add(deserializeApproach1(arr, index));
        }
        return n;
    }

    //In this approach, we are converting serialized tree to Queue, so that when we do
    //queue.poll it will remove the element and we don't need to keep track of the next element to process.
    private static NAryNode deserializeApproach2(String str) {
        if (str == null) {
            return null;
        }
        return deserializeHelper(new LinkedList<String>(Arrays.asList(str.split(","))));
    }

    private static NAryNode deserializeHelper(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }

        NAryNode n = new NAryNode(Integer.parseInt(queue.poll()));
        int size = Integer.parseInt(queue.poll());
        n.child = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            n.child.add(deserializeHelper(queue));
        }
        return n;
    }

    private static String serializeTree(NAryNode root, StringBuilder sb) {
        if (root == null) {
            return null;
        }

        sb.append(root.data);
        sb.append(",");

        if (root.child != null) {
            sb.append(root.child.size());
            sb.append(",");
            for (int i = 0; i<root.child.size(); i++) {
                serializeTree(root.child.get(i), sb);
            }
        } else {
            sb.append(0);
            sb.append(",");
        }
        return sb.toString();
    }
}
NAryNode.java
package javabypatel;

import java.util.List;

public class NAryNode {
    public int data;
    public List<NAryNode> child;

    public NAryNode(int data, List<NAryNode> child) {
        this.data = data;
        this.child = child;
    }
    public NAryNode(int data) {
        this.data = data;
    }
}
Read more
Categories: , ,

N-ary tree preorder traversal in java

in , , - on 14:52:00 - No comments

N-ary tree preorder traversal in java

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, print preorder traversal of its nodes values.

Example of N-ary tree preorder traversal below:

n-ary tree preorder traversal example

Algorithm

Preorder traversal: To traverse a Binary Tree in Preorder, following operations are carried-out 
  1. Visit the root node and print data of that node. 
  2. Traverse the left subtree, and 
  3. Traverse the right subtree.

Preorder traversal of N-ary tree is very similar to that of Binary tree preorder traversal, only difference is instead of two children in Binary tree here we have N children.

Preorder traversal of Binary tree: Binary Tree Preorder Traversal

Considering the example above, 
we will first visit the root Node 1, then instead of directly going Left and then Right that is what we do in Binary tree preorder traversal because there is only 2 children, here we don't know the number of child, so what we are going to do is loop for all the child and then do a Preorder traversal for each child.
 
Visit Root Node 1, 
loop for all the children [Node 2, Node 3, Node 4]  (i = 0, i<3; i++) i=0

Visit Node 2, 
Iterate all its children [Node 5, Node 6, Node 7]  (i = 0, i<3; i++) i=0

Visit Node 5,
Iterate all its children []

Node 5 has no children so we came back to Node 2, now i = 1

Came back to Node 2, 
Iterate all its children [Node 5, Node 6, Node 7], (i = 0, i<3; i++), i =2 do for Node 6. 

and it continues.

Java Program to print N-ary tree preorder traversal

package javabypatel;

import java.util.Arrays;

public class NAryTreeTraversal {
    public static void main(String[] args) {
        NAryNode root = new NAryNode(1,
                Arrays.asList(
                        new NAryNode(2, Arrays.asList(
                                    new NAryNode(5),
                                    new NAryNode(6),
                                    new NAryNode(7, Arrays.asList(
                                                new NAryNode(11),
                                                new NAryNode(12))))),
                        new NAryNode(3),
                        new NAryNode(4, Arrays.asList(
                                    new NAryNode(8),
                                    new NAryNode(9),
                                    new NAryNode(10)))
                ));

        preOrderTraversal(root);
    }

    private static void preOrderTraversal(NAryNode start) {
        if (start == null) {
            return;
        }

        System.out.print(start.data + ",");
        if (start.child != null) {
            for (int i = 0; i < start.child.size(); i++) {
                preOrderTraversal(start.child.get(i));
            }
        }
    }
}
NAryNode.java
package javabypatel;

import java.util.List;

public class NAryNode {
    public int data;
    public List<NAryNode> child;

    public NAryNode(int data, List<NAryNode> child) {
        this.data = data;
        this.child = child;
    }
    public NAryNode(int data) {
        this.data = data;
    }
}
Read more
Categories: , ,

Find longest binary gap in binary representation of integer number.

in - on 01:22:00 - No comments

Find longest length bi-valued slice in an array in java

This is a popular interview question asked in Tier-1 companies.

You are given a positive integer n, find the longest distance between two consecutive 1's in the binary representation of n.

Example:
1. Input: 9
Output: 2
9 binary representation is 1001 and there are two 0 in between 1's. so answer is 2

2. Input: 1041
Output: 5
1041 binary representation is 10000010001 and there are 5 consecutive 0's in first gap and 3 consecutive 0's in second binary gap. so answer is 5 as the highest gap among both.

3. Input: 15
Output: 0
15 binary representation is 1111 and there are no 0's in between 1's. so answer is 0

4. Input: 20
Output: 10
20 binary representation is 10100 and contains only one 0 in between 1's. so answer is 1

Algorithm

we will take 3 variables 
maxGap: for storing the result
tempGap: for storing temporary gap
oneFlag: a flag for indication that we have encountered 1 before or not.

Example: 101001, in this example when we encounter first binary gap of size 1 which would be in tempGap but later we encountered another binary gap of size 2 which is higher than before, so we need to store previous value of tempGap, that is where maxGap will be used to store whichever is highest among previous binary gaps.

Java Program to find longest binary gap in binary representation of an integer number.


package javabypatel;

public class BinaryGap {
    public static void main(String[] args) {
        System.out.println(new BinaryGap().findLongestBinaryGap(20));
    }

    public int findLongestBinaryGap(int number) {
        int maxGap = 0;
        int tempGap = 0;
        boolean oneFlag = false;

        while (number > 0) {
            int remainder = number % 2;
            number = number / 2;
            System.out.print(remainder);
            if (oneFlag) {
                if (remainder == 1) {
                    maxGap = Math.max(tempGap, maxGap);
                    tempGap = 0;
                } else {
                    tempGap ++;
                }
            } else if (remainder == 1) {
                oneFlag = true;
            }
        }
        System.out.println();
        return maxGap;
    }
}
Read more
Categories:

Find longest length bi-valued slice in an array

in , , - on 00:26:00 - No comments

Find longest length bi-valued slice in an array in java

This is a popular interview question asked in Tier-1 companies.

You are given a sequence of n integers and the task is to find the maximum slice of the array which contains no more than two different numbers.

Example:
1. Input: [1, 2, 1, 2, 2, 3, 3, 2, 3]
Output: 6
Max slice is [2, 2, 3, 3, 2, 3] which contains only two numbers 2 and 3 and the length is 6 

2. Input: [1, 2, 3]
Output: 2
Max slice is either [1, 2] or [2, 3] which contains only two numbers and the length is 2

3. Input: [1, 4, 4, 1, 4]
Output: 5 
Max slice is whole array which contains only two numbers 1 and 4 and the length is 5

4. Input: [2]
Output: 1 
Max slice is whole array which contains only one number 2 and the length is 1

Algorithm

As we are looking for bi-value slice, we will keep two pointer lastSeen and secondLastSeen which keep track of the numbers we last read.

So if the current number we are reading is one of the number we read before that is it is same as either lastSeen or secondLastSeen, then we can increase our longest bi-value slice counter(say tempCounter) by 1

So we have three variables till now, lastSeen, secondLastSeen and tempCounter to store the current longest bi-value slice.


Consider the array [1, 2, 1, 2, 2, 3, 3, 2, 3]

say we read 1, 2, 1, 2, 2 and we were good at that point, now we read element 3, so in that case new series has started but including the current number 3 we can include the previous two 2's in this series that is starting from index 3.

So instead of going back and see the last repeated number, we will keep track of this in the separate variable lastSeenNumberRepeatedCount which holds the number of times last seen value repeated in this case lastSeenNumberRepeatedCount would be 2, because when we encountered 3 at index 5, the number before 3 is 2 which first occur at index 3 and then the same number repeated that is lastSeen number repeated at index 4 so making lastSeenNumberRepeatedCount to 2.

So when we encounter 3 at index 5, we directly add the lastSeenNumberRepeatedCount to our tempCounter so it would be lastSeenNumberRepeatedCount + 1 (added 1 because starting from 3 new series has started, so including the current number 3)

So we have four variables till now, lastSeen, secondLastSeen, tempCounter and lastSeenNumberRepeatedCount.

We also need one more variable for storing our longest bi-valued slice as tempCounter will change when new series starts so what about the previous value of tempCounter which was our last longest bi-value slice till that point.

So we have five variables till now, lastSeen, secondLastSeen, tempCounter, lastSeenNumberRepeatedCount and lbs for storing result.

Java Program to find largest bi-valued slice in an array

package javabypatel;

public class LongestBiValueSlice {
    public static void main(String[] args) {
        System.out.println(new LongestBiValueSlice().getLongestSlice(new int[]{2}));
    }

    public int getLongestSlice(int[] arr) {
        int lastSeen = -1;
        int secondLastSeen = -1;
        int lbs = 0;
        int tempCount = 0;
        int lastSeenNumberRepeatedCount = 0;

        for (int current : arr) {
            if (current == lastSeen || current == secondLastSeen) {
                tempCount ++;
            } else {
                // if the current number is not in our read list it means new series has started, tempCounter value in this case will be
                // how many times lastSeen number repeated before this new number encountered + 1 for current number.
                tempCount = lastSeenNumberRepeatedCount + 1;
            }

            if (current == lastSeen) {
                lastSeenNumberRepeatedCount++;
            } else {
                lastSeenNumberRepeatedCount = 1;

                secondLastSeen = lastSeen;
                lastSeen = current;
            }

            lbs = Math.max(tempCount, lbs);
        }
        return lbs;
    }
}
Read more
Categories: , ,

When to use volatile vs synchronized in Java

in , - on 16:54:00 - No comments

When to use volatile vs synchronized in Java

When to use volatile and synchronized keyword in Java is very important to understand as without the understanding you may go wrong in communicating between threads.


synchronized keyword:

 synchronized keyword is used at method level and block level, but the whole purpose of synchronized keyword is to apply access restrictions as only one thread holding the monitor would be able to execute the code inside synchronized method/block.

volatile keyword:

Volatile keyword is used when you don't want local CPU core to cache the variable from main memory, instead all read/write to volatile variable should happen directly from main memory.

The Java volatile keyword guarantees visibility of changes to variables across threads.

So lets understand with practical scenario when to use which,

Scenario 1:
If multiple threads are trying to read the value of a variable and based on the current value it takes the decision of incrementing or decrementing a variable value, is marking a variable volatile in this situation enough?

No, Volatile only guarantees visibility, check and act is like we want two operations to be atomic in that case we either need to use synchronized method/block or Atomic variables (AtomicInteger for example).

Scenario 2:
There are multiple threads reading the value of shared variable but only one thread is writing to a shared variable, is marking a variable volatile in this situation enough?

Yes. as is there no situation where we need more than one operation to be atomic here and also only one thread is writing to a variable others are simply reading the shared variable, so volatile variable should work.

So to summarize, there are 3 problems associated with Multithreading,
  1. Race Conditions. (check and act, like i++, i--)
  2. Local CPU Caching OR Stale memory. (Threads running in CPU, caches the value from main memory to local CPU cache and now main memory and local CPU cache is out of sync)
  3. Complier and CPU optimization (VM/CPU are free from reordering the instructions in the program for optimization and performance as long as the meaning of the instructions remain same.)

Volatile helps in resolving the problem happens due to point 2 and 3 but not 1.

Synchronization helps in resolving all of the above points.

 Example demonstrating need of volatile keyword in Java
package javabypatel;

public class VolatileExample extends Thread {

    //Remove the volatile keyword and see
    volatile boolean keepRunningFlag = true;

    public void run() {
        System.out.println("Volatile thread running");
        long counter = 0;
        while (keepRunningFlag) {
            counter++;
        }
        System.out.println("Volatile thread terminated." + counter);
    }

    public static void main(String[] args) throws InterruptedException {
        //Code below is executing under Main Thread
        VolatileExample volatileThread = new VolatileExample();
        volatileThread.start();

        Thread.sleep(1000);

        //Main Thread is changing the value of keepRunningFlag to false. Ideally after this changes,
        //volatileThread created above executing the run method should come out of the while loop,
        //but if you don't declare the variable keepRunningFlag as volatile then there is no guarantee when while loop will break.
        //How this works internally without volatile keyword,
        //Main thread say running in CPU core 1 updates the keepRunningFlag to false which is updated in Main thread CPU cache
        //volatileThread say running in CPU core 2 also has local CPU cache which before starting the thread had cached the variable
        //keepRunningFlag to its local cache as false.
        //So any updates on the local variable not marked as volatile will first get updated to its local CPU cache.
        //No when the local cache value will sync with Main memory is internal to CPU and that is where problem happens.
        //When we mark the variable as volatile, we are instructing CPU as not to read/write the value of this variable to
        //your local cache, instead directly read/write from main memory.
        volatileThread.keepRunningFlag = false;

        System.out.println("Main thread ended, keepRunningFlag = " + volatileThread.keepRunningFlag);
    }
}


Check the program below, what do you think we should use volatile or synchronization in below situation 
package javabypatel;

public class DBConnection {
    private boolean connected;

    public synchronized void setConnectionFlag(boolean connected) {
        this.connected = connected;
    }
    public synchronized boolean isConnected() {
        return connected;
    }
}
Think of synchronized keyword when you want to make more than one instruction to be marked as single unit that is Atomic operation.

Example: i++ where the operation is break down as,
1. Reading the value of i first
2. Incrementing the value of i.

So that is two step operation and you want to make this two step as a single Atomic operation.

Think of volatile when you want to resolve the issues of visibility, like updates from one thread should be immediately available to other thread for taking some action but there is no operation that you want to execute as atomic, like the example above. In the above example we are simply setting the value of connected in setConnectionFlag method and we are simply returning the value of connected variable in isConnected method, so better to mark the connected variable as volatile in this situation instead of marking the method as synchronized.

Remember whatever you could do with volatile keyword can also be done using synchronized but with synchronized keyword you also get the feature of making the multi step instructions as Atomic operation.

Using synchronized and volatile keyword together.
There may be a situation where you may need to use volatile and synchronized keyword together. In the example below we are using for the reason of performance.
 
package javabypatel;

public class SingletonTest {
    volatile static SingletonTest instance = null;

    public static SingletonTest getInstance() {
        if (instance == null) {
            synchronized (SingletonTest.class) {
                if (instance == null) {
                    instance = new SingletonTest();
                    System.out.println("instance created");
                }
            }
        }
        return instance;
    }
}
In the example above since the outer line "if (instance == null)" is not inside synchronized block, what will happen is, say if Thread A gets a chance and is executing the line "instance = new SingletonTest();" and after that it gets preempted. Now, what will Thread 2 see which reached the line "if (instance == null) {" outside the synchronized block, whether the instance would be null or non-null. possibly it may see null if the local cache of the thread 1 is not flushed. so to make sure Thread 2 see the update value of the instance variable instance is marked as volatile here.

You may also like to see

How ConcurrentHashMap works and ConcurrentHashMap interview questions.

How Thread.join() in Java works internally

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

Type Casting Interview Questions In Java

How is ambiguous overloaded method call resolved in java

Method Overriding rules in Java

Interface interview questions and answers in Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.
Read more
Categories: ,

Generate all the binary strings of N bits.

in , - on 14:05:00 - No comments

Generate all the binary strings of N bits. 

Given a positive integer number N. Generate all the binary strings(0 and 1) of N bits. 

 Case 1
 Input: length=2
 Output:
 0 0
 0 1
 1 0
 1 1
Case 2
 Input: length=3
 Output:
 0 0 0
 0 0 1 
 0 1 0
 0 1 1
 1 0 0
 1 0 1
 1 1 0
 1 1 1

Case 3
 Input: length=1
 Output:
 0
 1

Algorithm:

We will see two approach of generating the binary string combination. 

First approach, where we will form the binary string one by one and once it matches the required length, we will backtrack and switch the binary digit. In this approach, as String is immutable each character we append to a String will create new String object.

Recursive stack trace of Generating all the binary strings of N bits.
generate all binary strings of length n with k bits set
Generate all the binary strings of N bits.

Second approach, In the first approach, each time we append the new character to String, a new String literal is created, so why to waste the space. In this approach we will use the fixed size array so that anytime we iterate and use the array we will always be working on fixed size array.

for more details on String and Memory management in Java, visit Java Memory Management Interview Questions

Java Program to Generate all the binary strings of N bits.

package javabypatel;
 
public class GenerateBinaryString {
 
    public void printBinaryCombination(int length, String str) {
        if (str.length() == length) {
            System.out.println(str);
            return;
        }
        printBinaryCombination(length, str + "0");
        printBinaryCombination(length, str + "1");
    }
 
    public static void main(String[] args) {
        GenerateBinaryString obj = new GenerateBinaryString();
        int length = 3;

        System.out.println("Approach 1");
        obj.printBinaryCombination(length, "");
    }
}

Optimized Approach: Using Array so no new String is created when a character is appended each time

package javabypatel;
 
import java.util.Arrays;
 
public class GenerateBinaryString {
 
    public void printBinaryCombination(int index, int[] arr) {
        if (index == arr.length) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        arr[index] = 0;
        printBinaryCombination(index + 1, arr);
        arr[index] = 1;
        printBinaryCombination(index + 1, arr);
    }
 
    public static void main(String[] args) {
        GenerateBinaryString obj = new GenerateBinaryString();
        int length = 3;
 
        System.out.println("Approach 2");
        obj.printBinaryCombination(0, new int[length]);
    }
}

You may also like to see

Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).

Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).

Print all subsets of a given set.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.
Read more
Categories: ,