Coding Stories

Just simple stories about coding …

Category: Java

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 util.

/**
 * @author szagriichuk
 */
public class StringUtils {
   // due to comments I've decided to hide code here, will publish it later, now if you want try to implement it by yourself.
}

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.

Reverse LinkedList {Recursion implementation}


Recently I’ve read IT topic about interview questions and was surprised, Programmers discussed about “hard” interview question “Reversing of Linked List”. Judging to that topic the task was hard for most candidates and I decided to write short note about Reversing Linked List.

  • Firstly this task was for Singly Linked List;
  • Secondly time for creating algorithm was about 5 mins;

So, I’ve used Java for realization but you can write the same code using C,C++ and other languages.

Ok, Lets go…

I’ve created new structure for Singly linked list :

package com.codingstories.list;

/**
 * @author szagriichuk
 */
public class Node {
    private int value;
    private Node next;

    public Node(int value) {
        this.value = value;
    }

    public static Node createLinkedListFromArray(int... data) {
        Node root = null;
        if (data != null && data.length > 0) {
            Node node = new Node(data[0]);
            root = node;
            for (int i = 1; i < data.length; i++) {
                node.setNext(new Node(data[i]));
                node = node.getNext();
            }
        }
        return root;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        Node root = this;
        while (root != null) {
            stringBuilder.append(root.getValue()).append(",");
            root = root.getNext();
        }
        return stringBuilder.toString();
    }
}

Also, I’ve decided to create a few implementations and this structure will be used for all of them.

I’ve extracted common interface called Reverser with simple API for algorithm implementations:

package com.codingstories.list.reverse;

import com.codingstories.list.Node;

/**
 * @author szagriichuk
 */
public interface Reverser {
    Node reverse (Node node);
}

After it, I’ve started to create first implementation.

So, First implementation is Recursion.

Steps of algorithm:

Go through all nodes and reverse them :)
Ok, seriously

  • Check if input Node is not null, if null return it {first rule to stop recursion}
  • Check if next Node is not null, if null return input node {second rule to stop recursion}
  • Get and save next Node
  • Set null as next value for input node
  • Call recursion method with next node and save result to reversed Node root
  • Set input Node as next to next Node :)
  • Return reversed Node root

Code:

package com.codingstories.list.reverse;

import com.codingstories.list.Node;

/**
 * @author szagriichuk
 */
public class RecursionReverser implements Reverser {
    @Override
    public Node reverse(Node node) {
        if( node == null)
            return node;
        Node next = node.getNext();
        if(next == null)
            return node;
        node.setNext(null);
        Node reverseList = reverse(next);
        next.setNext(node);
        return reverseList;
    }
}

Pros:

  • Simple to implement
  • You can see all process of reversing
  • You can understand recursion :)

Cons:

  • Usage of Stack Memory
  • As result can be thrown StackOverflowError

It’s first implementation of reverse functionality for LinkedList, I am going to add a few other ways of implementation in next posts.

Thanks.

Amazing story about crashing JVM


Hi All,

A few days ago I’ve investigated API of one over price external library. One note this library is native, written using C++ and provides ports to other language in particular for Java using JNI.

So, I’ve started to run provided example all is OK, and I’ve decided to use this application to write my API using OSGI and Spring. Native example implements 5 interfaces and provides a lot of methods that I do not need to implement and I’ve used just a 3. Implemented methods of these interfaces and try to run tests, so, I was very surprised JVM was crashed!

I’ve started to investigate this problem, check all implementation of methods, all input parameters to the external library, tests but did not find any problems that can crache JVM. After it I’ve downloaded decompiler for java and C++ codes and start to investigate external library. And what was my astonishment when I found that JVM will be crashed if class (MY CLASS)/MY API does not implement one of the interface from external library(I did’t do it).

It is a hard story about API architecture and in what places JVM can be crashed …

Thanks.

Maven: Set up java.library.path


I’ve tried to set up java.library.path as next example

     <plugin>
       <groupId>org.apache.maven.plugins</groupId>
       <artifactId>maven-surefire-plugin</artifactId>
       <configuration>
          <systemProperties>
            <property>
              <name>java.library.path</name>
              <value>target/lib/</value>
           </property>
       </systemProperties>
    </configuration>
</plugin>

but there were problems in testing, one test with JNI was passed but others were failed. I’ve spent about 4 hours for investigation and found that in last part of documentation there are special properties, so I’ve tried it and it is working!!!

Simple example of working plugin configuration

<plugin>
      <groupId>org.apache.maven.plugins</groupId>
      <artifactId>maven-surefire-plugin</artifactId>
      <configuration>
         <forkMode>once</forkMode>
         <workingDirectory>target</workingDirectory>
        <argLine>-Djava.library.path=${basedir}/lib</argLine>
    </configuration>
</plugin>

Cheers!

Algorithms: Customization binary search


I had some interviews into big companies like Google, Amazon and so on, and there were tasks related to the algorithms. So, Here I’ll describe one of the tasks and publish code for this algorithm. Note, during interview you can chose algorithm by your self and time for implementation (runtime implementation) about 30 mins. So,

Predefined: There is dictionary of words with unspecified size, we just know that all words in dictionary are sorted (for example by alphabet). Also we have just a one method

String getWord(int index) throws IndexOutOfBoundsException

Needs: Need to develop algorithm to find some input word in dictionary using java. For this we should implement method

public boolean isWordInTheDictionary(String word)

Limitations: We cannot change the internal structure of dictionary, we have no access to internal structure, we do not know counts of elements in dictionary.

Issues: I have developed modified-binary search, But you can try to implement interpolation search or modification interpolation + binary :) .

So, my code :

/** * @author Sergii Zagriichuk */

public class Dictionary {
    private static final int BIGGEST_TOP_MASK = 0xF00000;
    private static final int LESS_TOP_MASK = 0x0F0000;
    private static final int FULL_MASK = 0xFFFFFF;
    private String[] data;
    private static final int STEP = 100; // for real test step should be Integer.MAX_VALUE
    private int shiftIndex = -1;
    private static final int LESS_MASK = 0x0000FF;
    private static final int BIG_MASK = 0x00FF00;

    public Dictionary() {
        data = getData();
    }

    String getWord(int index) throws IndexOutOfBoundsException {
        return data[index];
    }

    public String[] getData() {
        return new String[]{"a", "aaaa", "asss", "az", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "test", "u", "v", "w", "x", "y", "z"};
    }

    public boolean isWordInTheDictionary(String word) {
        boolean isFound = false;
        int constantIndex = STEP; // predefined step
        int flag = 0;
        int i = 0;
        while (true) {
            i++;
            if (flag == FULL_MASK) {
                System.out.println("Word is not found ... Steps " + i);
                break;
            }
            try {
                String data = getWord(constantIndex);
                if (null != data) {
                    int compareResult = word.compareTo(data);
                    if (compareResult > 0) {
                        if ((flag & LESS_MASK) == LESS_MASK) {
                            constantIndex = prepareIndex(false, constantIndex);
                            if (shiftIndex == 1)
                                flag |= BIGGEST_TOP_MASK;
                        } else {
                            constantIndex = constantIndex * 2;
                        }
                        flag |= BIG_MASK;

                    } else if (compareResult < 0) {
                        if ((flag & BIG_MASK) == BIG_MASK) {
                            constantIndex = prepareIndex(true, constantIndex);
                            if (shiftIndex == 1)
                                flag |= LESS_TOP_MASK;
                        } else {
                            constantIndex = constantIndex / 2;
                        }
                        flag |= LESS_MASK;
                    } else {
                       // YES!!! We found word.
                        isFound = true;
                        System.out.println("Steps " + i);
                        break;
                    }
                }
            } catch (IndexOutOfBoundsException e) {
                if (flag > 0) {
                    constantIndex = prepareIndex(true, constantIndex);
                    flag |= LESS_MASK;
                } else constantIndex = constantIndex / 2;
            }
        }
        return isFound;
    }

    private int prepareIndex(boolean isBiggest, int constantIndex) {
        shiftIndex = (int) Math.ceil(getIndex(shiftIndex == -1 ? constantIndex : shiftIndex));
        if (isBiggest)
            constantIndex = constantIndex - shiftIndex;
        else
            constantIndex = constantIndex + shiftIndex;
        return constantIndex;
    }

    private double getIndex(double constantIndex) {
        if (constantIndex <= 1)
            return 1;
        return constantIndex / 2;
    }
}

I hope this post will help some one to pass interview into bigest companies :)

Cheers!

PlayFramework: Run and Debug Using IDE


Introduction

I think each of us looking for the best IDE and best way of development. I think the best code editor is IntellJ IDEA and I am using it for 6 years. A few month ago I’ve started to use PlayFramework and were surprized that there is no way to debug application using IDE just browser and console logs and messages. After short investigation I’ve found solution …

Solution

This step-by-step solution for IntellJ IDEA but I think you can use it for other IDEs.

Step1
Go to  Run/Debug Configurations and add Application configuration

Step 2
Put  main class

play.server.Server

Step 3
Add VM Options

-Dapplication.path=<Path to your application>

-Djavaagent=<Path to play framework>/play-1.2.3.jar

And that is all…

Cheers!!!

Android: Formatting Strings


Introduction
If you are java developer you can use String.format for adding some parameters into your string. Core Java provides us mechanism to manage it using symbols like %s or {1}, but how to use this mechanism in Android resource strings?

Resource Strings
Android provides us good mechanism to format strings in application too. Just try to add %1$s  or %1$d into your resource strings. The last symbols mean

  • s –  for string formatting
  • d – for decimal formatting

So, simple example:

<string name=“my_name”>My name is %1$s.</string>
<string name=“my_age”>I am %1$d years old.</string>

Here is we can see two types of using, the first is string formatting the second is number. In java code you have to add just simple String.format like in Core Java.

Resources res = getResources();
String myNameString = String.format(res.getString(R.string.my_name)“Tom”);
String myAgeString = String.format(res.getString(R.string.my_age)25);

And that is all …

P.S. If you want to use more parameters in string just increase a number  %1$d ,%2$d ,%3$d

Cheers!

Follow

Get every new post delivered to your Inbox.