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!

Reverse LinkedList {Loop implementation}


In the first part I’ve described how to reverse single LinkedList using recursion. Today we will to do the same using one loop.
The structure of linked list will be the same, look to the Node class.
OK, What we should understand? The first implementation used next steps:

  • Go throughout all nodes and set next to null { after these steps we have n-null pointed LinkedLists.}
  • Read from end and change direction of linking.

Current implementation will have different approach and will be implemented using next steps:

  • Create reversed root node.
  • Read next node.
  • Save as next reversed root.
  • Set node to reversed root.
  • Set next node to node; {For making loop}.

Steps are good but example better :), So, we have next list:

1->2->3->4->null

First algorithm {recursion implementation} works using two-time loop {recursion} from start to end and from end to start , it’s like recursion working.

So, After first time loop {recursion from start to end} we will have n-lists:

1->null; 2->null; 3->null; 4->null;

During second time loop {recursion from end to start } we add

n-1->n-2

elements and will have reversed list

4->3->2->1->null

and on the start of second loop {recursion from end to start } we have first element of reversed list and just add new elements to end .

So, what is different to current implementation ?

We have the same list:

1->2->3->4->null

and we have just a one loop. So, the main different is changing root element of reversed list. In other words new element will be added to head or better to new element will be added tail of reversed list.

Explanation of above steps:

We have root of reversed list

reversedList = null

read first element and add tail {reversedList} as next to first element after it assign first element as tail to {reversedList} for next loop iteration, so we will have

reversedList = 1->null

after second iteration will have

reversedList = 2->1->null

and so on.

Code:

package com.codingstories.list.reverse;

import com.codingstories.list.Node;

/**
 *@authorszagriichuk
 */
public class LoopReverser implements Reverser {
    @Override
    public Node reverse(Node node) {
        Node prev = null;
        while (node!=null){
            Node next = node.getNext();
            node.setNext(prev);
            prev = node;
            node = next;
        }
        return prev;
    }
}

Pros:

  • Faster than first implementation because use one loop from start to end
  • Do not use Stack Memory

Cons:

  • Hard to understand for some people {because use diff approach than recursion and stack}

How to clean your mac after deleting IntelliJ IDEA


If you tried to delete an IntelliJ IDEA from your mac station you know that problem is not simple, so, I’ve decided to write short note “how to clean your mac after deleting IntelliJ IDEA app from Application folder”.

Generally check all next folders and clean/change what you want:

~/Library/Preferences/com.jetbrains.intellij.plist
~/Library/Preferences/com.jetbrains.intellij.plist.lockfile
~/Library/Preferences/IntelliJIdeaX
~/Library/Caches/IntelliJIdeaX
~/Library/Application Support/IntelliJIdeaX
~/Library/Caches/com.jetbrains.intellij
~/Library/Logs/IntelliJIdeaX
~/Library/Saved Application State/com.jetbrains.intellij.savedState

Where it can be used ?
If you have some problems in update;
If you have problems with license;
If you have problems with old (incorrect) prefereces;
You just want clean installation of new version of IntelliJ IDEA.