Algorithm {Binary Tree Maximum Path Sum}


Hey, I’ve just solved one more problem from leetcode and going to share that solution. So, solved problem calls Binary Tree Maximum Path Sum.

Problem description:

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

OK, stop and think …. What do we have ???  The main point is binary tree. We can use perfect traversing algorithms. In our case we need to use post order traversal, is not it ? OK, good, if we got left, right and current what we should check ???
We should understand how post order is working . Tree should be like that:
       1
      / \
     2   3
    / \  / \
  null null null

We will traverse to the left, check if node is null return 0 (the max path equals to 0 ) and go to the right node, again if node is null return 0 and go up to parent. Parent is 2. We should check what is the max path left +parent or right +parent. After that check if this max path biggest that current value (because left or right can be negative). Good, after that we will have max current path in other words max path for current value. So, after that we should check what is the bigger max current path or full path (full path is left + current + right, because the path can start and end at any node) and if that value biggest that stored set it like a max path. That is all, so, words are good but better code, let’s go …

public int maxPathSum(TreeNode root) {
        Integer max[] = new Integer[1];
        maxPathSum(root, max);
        return max[0];
    }
 
    public int maxPathSum(TreeNode root, Integer[] max) {
        if (root == null) {
            return 0;
        }
        int left = maxPathSum(root.left, max);
        int right = maxPathSum(root.right, max);
        int current = root.val;
 
        // choose biggest path for return
        int maxCurrentPath = max(current, max(left+current, right+current));
 
        if (max[0] == null)
            max[0] = current;
        else {
            // choose max path
            int fullPath = left + current + right;
            max[0] = max(max[0], max(maxCurrentPath, fullPath));
        }
        return maxCurrentPath;
    }

So, that is all, if you have some questions don’t hesitate to ask me :)
Cheers !!!

Algorithm {Max Points on a Line}


Hi, Today we will try to solve next problem from leetcode. The problem is Max Points on a Line.

Problem description:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

So, that is short desciption…. Try Stop and Think

What do we have, we have input array/list of points and should return max number of the points on one line. We can try to remember school math course and one part is Collinear.

Three or more points P1,P2 ,P3 , …, are said to be collinear if they lie on a single straight line .

Hm, this is our case :), we should find max points on the one line. Ok, Lets go to implement it.

    public int maxPoints(Point[] points) {
        if (points == null)
            return 0;
 
        if (points.length <= 1 || isOnePoint(points))
            return points.length;
        int max = 2; // 2 points are collinear
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (points[i].x == points[j].x && points[i].y == points[j].y)
                    continue;
                int pointsCount = 2;
                for (int k = 0; k < points.length; k++) {
                    if (k != i && k != j && areCollinear(points[i], points[j], points[k])) {
                        pointsCount++;
                    }
                }
                max = Math.max(max, pointsCount);
            }
        }
        return max;
    }
 
    boolean areCollinear(Point a, Point b, Point c){
        return (a.x - b.x) * (c.y-b.y) - (c.x-b.x) * (a.y-b.y) == 0; // collinearity formula (x1 - x2)/(x2 - x3) = (y1 -y2)/(y2 - y3
    }
 
    boolean isOnePoint(Point[] x) {
        int x0 = x[0].x;
        int y0 = x[0].y;
        for (int i = 1; i < x.length; i++) {
            if (x[i].x != x0 || x[i].y != y0)
                return false;
        }
        return true;
    }

So, that is easy, with one trick , is checking if all input array contains the same points.

        if (points.length <= 1 || isOnePoint(points))
            return points.length; 

Other cases are easy to understand, run 3 loops (to get 3 Points) check if the points different and if collinear (lay on the one line) increase count of the points, after that check with max value, if count > max assign max to current count and try other points.

The complexity of current implementation is O (N^3), memory O (1) :(,  but leetcode accepted that solution, so this is good, but…

Can we improve current solution? 

Generally yes, we can use some container like Map, for storing lines and count of the Points on that line and after that just choose what line contains max count of Points. My friend is solved the problem using that approach, Complexity will be O (N^2) and memory usage O (N). 

Thanks.

Algorithm {Reverse Words in a String}


Hey, today we will try to solve “Reverse Words in a String” task for leetcode.

Task description:

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Clarification:

  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.

Stop and think…

You can see that is easy task. I think there are a lot ways to solve this task I will provide just a one. So, what is the solution can be ?

For example:

-  we can create new one string and goes through input string from end to start  and copy all elements from input to created string, can work ? Why not …

- we can create four indexes like next

        int firstWordStart = 0;
        int firstWordEnd = 0;
        int lastWordStart = s.length()-1;
        int lastWordEnd = s.length()-1;

and work with these indexes, till

firstWordEnd < lastWordStart

but we should manage string with shifting all words because length of first and last words can be diff, So, That is hard but can be solution with swap in place.

- we can use recursion and if we found whitespace start next recursion cycle with string without first word and after recursion add first word to the end (it’s like Reverse LinkedList {Recursion implementation} ), that is good solution, but can be problem with stack memory.

- we can split words by whitespace char ” ” and reverse all words in splitted array after that create result string from array, that solution like first but more elegant for my point of view, so, I am going to implement the solution (leetcode accepted it, so, it’s right :) )

public String reverseWords(String s) {
       s = s.trim();
       String [] data = s.split(" ");
       int lastIndex = data.length-1;
       for(int i = 0; i < data.length/2; i++){
        swap(data, i, lastIndex);
        lastIndex--;
       }
       return returnString(data);
    }
 
    void swap(String[] data, int startIndex, int endIndex){
        String temp;
        temp = data[endIndex];
        data[endIndex] = data[startIndex];
        data[startIndex] = temp;
    }
 
    String returnString(String [] data){
        StringBuilder result = new StringBuilder();
        for(String datum:data){
            if(datum!=null && datum.trim().length()!=0)
                result.append(datum).append(" ");
        }
        return result.toString().trim();
    }

So, we have 3 methods, first is main and executing main logic.

Next one swap, swap is very easy, just swapping elements in array.

Last one is reversed string creator.

So, that is all…

Cheers !

 

Algorithm {Triangle}


Hey, next problem from leetcode will be Triangle. Task description:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

 Stop and think …  

Judging to example we should go level by level and choose smallest “connected” value . Why I’ve written “connected” because if we have something like  that

   [5,6,7],
  [4,4,1,8]

we should choose 6,1 but not 5,4 because sum 6+1 < 5+4. OK interesting observation… So, what will be if we start from bottom to top ? We can choose smallest number and all will be correct. That is good, but how to check “connection”. In this situation we can use rule from Dynamic Programming(DP) (Store sum under i position of i-element from next level and min from i and i+1 element from stored values.) OK, lets go …

    public int minimumTotal(@NotNull ListList<List<Integer>> triangle) {
        if (triangle.size() == 0) return 0;
        int[] cache = new int[triangle.size()];
        List<Integer> bottom = triangle.get(triangle.size() - 1);
        for (int i = 0; i < cache.length; i++) {
            cache[i] = bottom.get(i);
        }
        int layer = cache.length - 2;
        while (layer >= 0) {
            List<Integer> list = triangle.get(layer);
            for (int i = 0; i <= layer; i++) {
                cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);
            }
            layer--;
        }
        return cache[0];
    }

What I’ve written :

Create cache (remember about DP)

int[] cache = new int[triangle.size()];

Get last line(level) from triangle and put to cache

List<Integer> bottom = triangle.get(triangle.size() - 1);
for (int i = 0; i < cache.length; i++) {
  cache[i] = bottom.get(i);
}

after that start from next level and

Store sum under i position of i-element from next level and min from i and i+1 element from stored values.

while (layer >= 0) {
  List<Integer> list = triangle.get(layer);
  for (int i = 0; i <= layer; i++) {
   cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);
  }
  layer--;
}

How this technique is working ? That is very easy, try to test our example :

  • firstly we have put last level to cache , so, cache contains next values
[4,1,8,3]
  • start loop from next level
[6,5,7],

i == 0, so, we store under 0-position  smallest sum  (6+4 or 6+1)

cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);

next positions the same, OK after second line we will have our cache like next

[7,6,8,3]
  • go to next level
[3,4],

cache will be next

[9,9,8,3]
  • go to next level
[2]

cache will be next

[11,9,8,3] 

so, just return 0 position and that is all

  return cache[0];

So, we solved next task, that is good :) Thanks!

Algorithm {Single Number}


Hey, We are working on next task from leetcode. So, next task will be …. , {Single Number} :).

Task:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Stop and think …

What we have, input array of integers and we should find one NOT DUPLICATE number. So, it’s easy … Go to the math knowledge and try to remember XOR if you don’t remember you can try to refresh knowledge in XOR Truth Table. So, main idea that two equal numbers will return 0. What does it mean ??? If we have array like next

1,1,4,4,5

And try to XOR all values we will get 5, OK, that is very good and we can start use that functionality to develop our algorithm.

Lets go :

public int singleNumber(int[] A) {
        int result = 0;
        for(int i = 0; i < A.length; i ++){
            result^=A[i];
        }
        return result;
}

OK, what we can see, we have result value, and one loop all values are XORed to the result (read about XOR functionality) so after the loop we will have Single number …That is perfect :)

OK, What  is the complexity, as you can see, we have just a one loop , so, complexity will be O(N), as we are using just a one int variable it means we do not use extra memory … Perfect, we solved that task …

Cheers ! :)

Algorithm {The maximum-subarray problem}


Hey,
I’ve just opened Introduction to Algorithms on Divide-and-Conquer chapter, and found interesting item – The maximum-subarray problem. In book you can find implementation with complexity O(NlogN) with good explanation, but in Exercises part there is good task:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j] , extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of A[1..j+1] is either a maximum subarray of A[1..j] or a subarray A[i..j+1], for some 1<=i<=j+1. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j .

So, That is easy, because there are some ideas, you just need to stop and think a bit and all will be clear …

As described in the book you need to return 3 params
– max sum
– start index of sub array
– end index of sub array

OK, lets go …

Firstly create return structure.

public class SubArrayResult {
        final long sum;
        final int startIndex;
        final int endIndex;
 
        private SubArrayResult(long sum, int startIndex, int endIndex) {
            this.sum = sum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }
 
        public long getSum() {
            return sum;
        }
 
        public int getStartIndex() {
            return startIndex;
        }
 
        public int getEndIndex() {
            return endIndex;
        }
 
        @Override
        public String toString() {
            return "SubArrayResult{" +
                    "sum=" + sum +
                    ", startIndex=" + startIndex +
                    ", endIndex=" + endIndex +
                    '}';
        }
    }

After that try to create algorithm.

public SubArrayResult findMaximumSubArray(int[] A) {
        long sum = 0;
        long result = 0;
        int start = 0;
        int end = 0;
 
        for (int i = 0; i < A.length; i++) {
            if (sum == 0 && A[i] <= 0) {
                start = i + 1;
                continue;
            }
            sum += A[i];
            if (sum > result) {
                end = i;
                result = sum;
            }
            if (sum < 0) {
                start = i + 1;
                sum = 0;
            }
 
        }
        return new SubArrayResult(result, start, end);
    }

OK, what algorithm is doing:

- firstly run throughout all array

for (int i = 0; i < A.length; i++)

- skipping negative values and move start index

if (sum == 0 && A[i] <= 0) {
   start = i + 1;
   continue;
}

- just add next value to current sum 

sum += A[i];

- check if current sum > result value, if yes, assign sum to result and move end to current index

if (sum > result) {
 end = i;
 result = sum;
}

- and last one if sum < 0 assign 0 to sum and move start to next index

if (sum < 0) {
  start = i + 1;
  sum = 0;
}

So, that is all :)

Algorithm {Evaluate Reverse Polish Notation}


Hey,

I’ve solved a few tasks from http://leetcode.com/ and going to publish my solutions,

So, first task is “Evaluate Reverse Polish Notation

The task description is :

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +-*/. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Stop and think

What do we have ? I can see some  list of the numbers and operations, so, it looks like you or me added all items in LIFO style, like  {2->1->+-> and so on}. OK, good, we can try to find data structure implemented that style. Each of us knows about Stack … OK, good, try to use that data structure in our implementation …

Firstly I’ve added calculator:

enum Operation{
            PLUS("+"){
                int calculate(int left, int right){
                    return left+right;
                }
            },MINUS("-"){
                int calculate(int left, int right){
                    return left-right;
                }
            },MULTIPLY("*"){
                int calculate(int left, int right){
                    return left*right;
                }
            },DIVIDE("/"){
                int calculate(int left, int right){
                    return left/right;
                }
            };
            String operation;
            Operation(String op){
                operation = op;
            }
            String getName(){
                return operation;
            }
            abstract int calculate(int left, int right);
            static Operation get(String val){
                Operation[] operations = values();
                for(Operation operation: operations){
                    if(operation.getName().equals(val))
                        return operation;
                }
                return null;
            }
        }
OK, based on that calculator implementation of solution will be easy:
public class Solution {
     public int evalRPN(String[] tokens) {
            Stack<Integer> result = new Stack<Integer>();
            for (String token : tokens) {
                Operation operation;
                if(!isNum(token)){
                    operation  = Operation.get(token);
                    int secondValue = result.pop();
                    result.push(operation.calculate(result.pop(),secondValue));
                }else {
                    result.push( Integer.valueOf(token));
                }
            }
            return result.pop();
        }
 
        boolean isNum(String data){
            boolean isNum = true;
            try{
                Integer.parseInt(data);
            }catch(Exception e){
                isNum = false;
            }
            return isNum;
        }
}
So, you can see I am using Stack to store numbers and result of calculations,  after all calculations last value in Stack will be our result…
That is easy and perfect :)
Cheers !

Algorithm {Longest substring with 2 unique chars}


Hi,

A few days ago my friend asked me question,

How can we find longest substring which contains 2 unique characters in linear time without additional memory ?

Yeah, we spoke about algorithms :). I suggested to use 2 cursors like start and end and just get substring by these cursors. Generally idea is right, but how can we manage these cursors ? This is quite hard. Maybe not so hard but need some time to think about it.

OK, what do we have ?

1)  we have input string like next abcc;

2)  we should not use additional memory, it means we can store some indexes (like start and end cursors), maybe some additional points, but cannot clone input string or use some data – structure to manage string, I mean trie tree and/or so on.

3) complexity should be linear

OK,  we have all information about algorithm and can start development. Yes, firstly I’ve provided these implementation after that he told me about algorithm Kadane.

Yes, we should modify it, but idea is great, ok lets go to implementation:

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
 
/** * * @author szagriichuk */
public class LongestSubstring {
    public String subString(String data) {
 
        if (data == null || data.isEmpty()) {
            return "";
        }
        if (data.length() <= 2) {
            return data;
        }
 
        Set<Character> chars = new LinkedHashSet<Character>();
        String maxString = "";
 
        int start = 0;
        int end;
 
        for (end = 0; end < data.length(); end++) {
            chars.add(data.charAt(end));
            if (chars.size() > 2) // next letter in string
            {
                Character removed = removeFirst(chars);
                String tempString = data.substring(start, end);
                maxString = chooseMaxString(maxString, tempString);
                start = moveStart(start, removed, tempString);
            }
        }
        if (chars.size() <= 2) {
            maxString = chooseMaxString(maxString, data.substring(start, end));
        }
        return maxString;
    }
 
    private String chooseMaxString(String maxString, String tempString) {
        if (maxString.length() < tempString.length()) {
            return tempString;
        }
        return maxString;
    }
 
    private int moveStart(int start, Character removed, String data) {
        int result = data.length() - 2;
        Character lastChar = data.charAt(data.length() - 1);
        Character prevChar = data.charAt(result);
        while (prevChar.equals(lastChar)) {
            prevChar = data.charAt(--result);
        }
        return data.indexOf(removed) < 0 ? start + result : start + result + 1 ; // +1 because we took last char
    }
 
    private Character removeFirst(Set<Character> chars) {
        Character character = null;
        Iterator<Character> iterator = chars.iterator();
        if (iterator.hasNext()) {
            character = iterator.next();
            iterator.remove();
        }
        return character;
    }
}

I am using next variables:

        Set<Character> chars = new LinkedHashSet<Character>();
        String maxString = "";
 
        int start = 0;
        int end;
 

Instead of Set we can use two Characters, but it’s more readable use Set and store just 2 chars in it.

Start and End these are two cursors I’ve written above and maxString is result string of the our algorithm.

All steps in implementation are easy but I want to draw your attention to method moveStart. This implementation contains simple trick :). But I think all of you can understand it !!!

OK, testing code (maybe there are some problems in code I’ve tested on a few test data)

        LongestSubstring longestSubstring = new LongestSubstring();
        assertEquals("", longestSubstring.subString(null));
        assertEquals("", longestSubstring.subString(""));
        assertEquals("bcbbbbcccb", longestSubstring.subString("abcbbbbcccbdddadacb"));
        assertEquals("a", longestSubstring.subString("a"));
        assertEquals("ab", longestSubstring.subString("ab"));
        assertEquals("ab", longestSubstring.subString("abc"));
        assertEquals("bcc", longestSubstring.subString("abcc"));
        assertEquals("aaaaaaaaaaaaaaab", longestSubstring.subString("aaaaaaaaaaaaaaabcccccc"));
        assertEquals("aaaaaaaaaaaaaaa", longestSubstring.subString("aaaaaaaaaaaaaaa"));

Looks like working in linear time :)

Thanks.

Simple puzzle NPE (String)


Hi,

We had training related to java, and was short example of code, like that :

void todoSomethig(Agent agent){
  if(agent!=null && agent.getName().length() > 0){
    System.out.println(agent.getFullName())   
 }
}

and all developers tried to find places where NPE can be thrown. Yes, we found that name can be null

 agent.getName()

also that agent.getFullName() can throw NPE. But I asked, next question :

Can  method length()  throw NPE ???

So, here is short description how that can be implemented :)

OK, we should know where method length() is declared, short investigation can show us that method length() is from interface CharSequence.

OK, good, BUT how can we overwrite this method in final class String ???

The answer we cannot! (Reflection we cannot use for that task)

OK, So, we have full information and can start develop our puzzle with throwing NPE in length() method.

 

First step is develop String and StringUtils.

public class String implements CharSequence {
    final Integer length = null;
    @Override
    public CharSequence subSequence(int start, int end) {
        return null;
    }
 
    @Override
    public int length() {
        return length;
    }
 
    @Override
    public char charAt(int index) {
        return 0;
    }
}
public class StringUtils {
 
    @SuppressWarnings("unchecked")
    public static <C extends CharSequence> C getString(java.lang.String string) {
        if (!"".equals(string)) {
            return (C) "";
       }
        return (C) new String();
    }
}

and  Second is just a main method with calling util class.

/**
 * @author szagriichuk
 */
public class Main {

 public static void main(String[] args) {
   String test = StringUtils.getString("test");
   System.out.println(test.length()); <-- All is good
   System.out.println(StringUtils.getString(test).length()); <--NPE
 }
}

SO, this is simple trick :) to get NPE in length() method :)

What is the advice, try to think out of the scope :)

Thanks!

How to increase disk size for VirtualBox VMs.


I am using VirtualBox as VM platform for different OS’. Last time I’ve investigated kafka messaging system I’ve created simple VM based on the ubuntu OS. Disk was created by default with size amount 8 Gb. During investigation I’ve found that kafka stores a lot of files (related to configuration) and free space on my disk is very low, I’ve decided to extend it, but did not found standart ( on menu ) option to do it. After investigation VirtualBox documentation I’ve found option how can I to do it.

Steps:

  • Go to the VitualBox VM folders, usualy it’s

     ~/VirtualBox VMs/

  • Run next command

     [path to VBox]/VBoxManage modifyhd [name of VM].vdi --resize [size in MB]

  • Start your VM and resize your partition Disk Management for Windows or GPartition for Linux

That’s All :)