Sunday, 25 April 2021

A Good Free Alternative To Collabedit

Many of us use Collabedit frequently to conduct technical interviews. It is a easy to use online code editor where code can be shared between interviewer & interviewee. It supports most of the common programming languages available like Java, C++, Python, PHP or JavaScript. But recently I have seen Collabedit having server problems frequently. Sometimes the website keeps loading & gets timed out.

So as an alternative I have been using codeshare.io for collaborating & sharing code. It has a free version & works well. And their server didn't give me any problem till now. So if you are looking for a free Collabedit alternative, you can give codeshare.io a try.



Saturday, 24 April 2021

Java Program to Solve Sliding Window Maximum Problem

Sliding Window Maximum problem is a question that is asked in different companies like Google, Amazon & Walmart. You will find the question in websites like LeetCode and InterviewBit.  

An array of integers A is given to us. We have a sliding window of size B which is moving from the left of the array to the right. Each time the window moves by one element to the right. We need to find the maximum element in each of these windows.

Suppose we have an array [1, 3 , 2, -4, 5] as input. Window size B is 3.
Current Window      Maximum Element
1,  3,  2                              3
3,  2 , -4                            3 
2, -4, 5                              5

To do this in O(n) time complexity, we will take the help of a deque. Within the deque we will store the index of the current window elements & they will be sorted by descending order of their values. So when we run a for loop, the first element of the deque would be the largest element of the previous window. We are then cleaning up any indexes from the deque which belong to previous window. If you see from the code below, any element in the deque can be added & removed only once. So time complexity for Sliding Window Maximum Problem would be O(n).


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public ArrayList<Integer> slidingMaximum(final List<Integer> A, int B) {
        ArrayList<Integer> results = new ArrayList<Integer>();
        if(B > A.size()){
            int slidingMaximum = 0;
            for(int a : A){
                if(slidingMaximum < a){
                    slidingMaximum = a;
                }
            }
            results.add(slidingMaximum);
            return results;
        }
        
        LinkedList<Integer> deque = new LinkedList<Integer>();
        
        for(int i=0; i<B; i++){
            while(!deque.isEmpty() && A.get(deque.getLast()) <= A.get(i)){
                deque.removeLast();
            }
            deque.addLast(i);
        }
        
        for(int i=B; i<A.size(); i++){
            results.add(A.get(deque.getFirst()));
            while(!deque.isEmpty() && deque.getFirst() <= (i-B)){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && A.get(deque.getLast()) <= A.get(i)){
                deque.removeLast();
            }
            deque.addLast(i);
        }
        results.add(A.get(deque.getFirst()));
        return results;
    }
}

Working Java Program For Largest Rectangle in Histogram

Problem:
An array of integers A is given of size N. A represents a histogram i.e A[i] denotes height of the ith histogram’s bar. Width of each bar is 1.

This is a question you will find in LeetCode or InterviewBit and asked in interviews of Google, Amazon or Facebook.


Above you can see  a histogram with different heights. Below the largest area has been highlighted.

For implementing we have used a stack. Stack will contain index of the array in ascending order of values.

Idea is we are going to calculate largest area for each bar & then take the maximum out of them. For a bar, the max area would start after the left bar where the value is less than the current bar. Area will end when a right bar has less value than the current bar.

If we are storing the index in ascending order of values in stack, we know the left border for a stack element would be the adjacent left element. And while adding, when we encounter a new index where value is smaller than stack top element, we would have found the right border of the stack top.

The time complexity would be O(n) as bars can be added & removed only once from the stack. Below you can find the Java program that solves the problem.




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public int largestRectangleArea(ArrayList<Integer> A) {
        int maxArea = 0;
        //stack keeping index of elements in ascending order
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0;
        for(; i < A.size();){
            if(stack.isEmpty() || A.get(stack.peek()) <= A.get(i)){
                stack.push(i);
                i++;
            } else {
                int currentIndex = stack.pop();
                //left border of a element is the previous index with lower value
                int leftBorder = stack.isEmpty() ? -1 : stack.peek();
                int area = A.get(currentIndex) * (i - leftBorder - 1);
                if(maxArea < area){
                    maxArea = area;
                }
            }
        }
        while(!stack.isEmpty()){
            int currentIndex = stack.pop();
            int leftBorder = stack.isEmpty() ? -1 : stack.peek();
            int area = A.get(currentIndex) * (i - leftBorder - 1);
            if(maxArea < area){
                maxArea = area;
            }
        }
        return maxArea;
    }
}

Friday, 23 April 2021

How To Embed Code Snippet In Blogger Blog Post Without Editing Template

There are several ways to add code box in Blogger blog posts. Many of them would suggest to edit blogspot template and add third-party CSS links. But I prefer a way that doesn't require any tampering or modification of blogspot template.

First of all, it is risky & you may corrupt template HTML. Secondly, if later you want to move out of Blogger & host it in some other blogging platform like Wordpress, that will break the formatting of the code block. You would have to add these CSS links in new template manually.

If you use proper HTML code without any third-party links for code display, that would be consistent & won't break even if you move out of Blogger platform.

I am using hilite.me website for highlighting my Java code blocks that I share here. It takes the Java code & pretty-prints it in HTML format. Then we can just copy & paste it in our Blogger blog post. It supports all the popular languages whether it is Java, Python, JavaScript, XML, Scala, Kotlin or MySQL. It can also colour highlight the code block & add line numbers to it. It will take care of adding scrolling too. Overall this website is pretty good & easy to use.



Thursday, 22 April 2021

Java Code Implementation For All Unique Permutations

This is a common question asked in interviews of Microsoft, Google & Facebook. You might have stumbled upon this question in LeetCode or InterviewBit.

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Here is the working solution for this problem in Java. It uses backtracking to solve the problem.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> currentResult = new ArrayList<Integer>();
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        int startPosition = 0;
        calculate(nums, startPosition, results);
        return results;
    }
    
    private void calculate(int[] nums, int startPosition, 
                           List<List<Integer>> results) {
        if(startPosition == nums.length - 1){
            List<Integer> currentResult = new ArrayList<Integer>();
            for(int num : nums){
                currentResult.add(num);
            }
            results.add(currentResult);
        }
        else {
            Set<Integer> usedNumbers = new HashSet<Integer>();
            for(int i = startPosition; i < nums.length; i++){
                if(usedNumbers.contains(nums[i])){
                    continue;
                } else {
                    usedNumbers.add(nums[i]);
                    swap(nums, startPosition, i);
                    calculate(nums, startPosition + 1, results);
                    //backtracking
                    swap(nums, startPosition, i);
                }
            }
        }
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Time complexity in O(n!).
T(n) = n * T(n-1)
T(n-1) = (n-1) * T(n-2)
T(n-2) = (n-2) * T(n-3)
As you can see time complexity becomes n * (n-2) * (n - 3) ... * 1 which is O(n!).

Wednesday, 21 April 2021

Log When JDBC Connection Is Acquired And Released

We are fond of one db session per request pattern. For web applications with JPA & Hibernate, it is good strategy in common cases. But for some long-running requests (definition of long-running depends on your use case, maybe 500 ms or 2 s), we need to tweak when we are actually acquiring a db connection from JDBC database connection pool & releasing it back. Otherwise if we are holding the connection for entire duration of the long running request, that might choke our Java application. The number of connections in JDBC pool is limited after all.

Just wanted to add another point. Until you make a database query from your application, request thread won't actually acquire a connection from the database pool.

So ultimately you might need to track when the database connection is actually getting acquired & when it is released. Based on the findings you can manually acquire & release db connection inside you code block & optimize the connection holding time in specific cases. For an example, you made a JDBC query & then you are making a network call which might take tens or hundreds of milliseconds. It would be better to release the connection before you make the API call over the network. You can acquire it again later in the same request if needed.

To log actually when Hibernate is acquiring a database connection from JDBC connection pool & releasing it back, you would have to enable DEBUG level logging on org.hibernate.engine.jdbc.internal.LogicalConnectionImpl class. You can enable logging at a higher package level. But here I am trying to keep log uncluttered. Just by enabling DEBUG log level on the above class, you will be able to see log getting printed as below:



2021-04-21_14:40:42.512 DEBUG o.h.e.j.i.LogicalConnectionImpl - Obtaining JDBC connection
2021-04-21_14:40:42.512 DEBUG o.h.e.j.i.LogicalConnectionImpl - Obtained JDBC connection
2021-04-21_14:40:47.500 DEBUG o.h.e.j.i.LogicalConnectionImpl - Releasing JDBC connection
2021-04-21_14:40:47.500 DEBUG o.h.e.j.i.LogicalConnectionImpl - Released JDBC connection

If we are using log4j framework, enabling log level would be somewhat similar to below:

<?xml version="1.0" encoding="UTF-8"?>
<Configuration status="WARN">
  <Appenders>
    <Console name="Console" target="SYSTEM_OUT">
      <PatternLayout pattern="%d{HH:mm:ss.SSS} [%t] %-5level %logger{36} - %msg%n"/>
    </Console>
  </Appenders>
  <Loggers>
    <Logger name="org.hibernate.engine.jdbc.internal.LogicalConnectionImpl" level="DEBUG">
      <AppenderRef ref="Console"/>
    </Logger>
    <Root level="error">
      <AppenderRef ref="Console"/>
    </Root>
  </Loggers>
</Configuration>

Tuesday, 6 April 2021

Evaluate Reverse Polish Notation In Java

Here is a fully working Java solution for evaluation of Reverse Polish Notation (Postfix Expression). This is a common interview question that is asked in Google, Yahoo and Facebook. Solution Java class doesn't have a main() method. You can write a main() method and call evalRPN() method from there. Input argument to evalRPN() method should be a String ArrayList with valid Postfix expression.

Sample input: ["6", "1", "-", "3", "*"]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public int evalRPN(ArrayList<String> A) {
        Stack<Integer> stack = new Stack<Integer>();
        for(String a : A){
            Integer current = null;
            //check if current value is operand
            try{
                current = Integer.parseInt(a);
            } catch(NumberFormatException e){
            }
            if(current != null){
                stack.push(current);
            } else{
                // find last two operands
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                //apply current operator on these operands
                int value = calculate(operand1, operand2, a);
                stack.push(value);
            }
        }
        return stack.pop();
    }
    
    private int calculate(int operand1, int operand2, String a){
        int result = 0;
        if(a.equals("+")){
            result = operand1 + operand2;
        } else if(a.equals("-")){
            result = operand1 - operand2;
        } else if(a.equals("*")){
            result = operand1 * operand2;
        } else if(a.equals("/")){
            result = operand1 / operand2;
        }
        return result;
    }
}

Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1's. A : [ 1 1 1 0 0 1 1 0 1 1 1 0 ] Output : 6 Dynamic programmi...