Coding Stories

Just simple stories about coding …

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!

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 :)

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.

Development Workflow: usual steps


……

Do you have established dev’s process ? How do you use it ? Do you like it ? What is the benefit from it ? And others

These questions are usual in programmers’ area (at least for me), so I decided to write short note about process and how it established in company where I am working.

Short and simple Rules:

Firstly – all have to use it, if some one decided to stop it will work rule of broken window.
Secondly – each team’s player has to understand all aspects of process, if something not clear will work first rule.
Thirdly – all points and rules have to be short, simple and understandable, because there is high probability that will work first two points described above.

Before start development you should set up some Source Control System, for me is better to use DVCS but you can choose what is the better for you.

So, My usual workflow of new feature:

  • Start new branch with name that clear describing new feature
  • Create some high level interfaces (API)
  • Create tests
  • Implement logic, if I need I can change API and test on this stage
  • Submit code to review tool.
  • Create event for review and assign as minimum to 2 diff developers (if developers from diff teams will be great)
  • Wait review, and fix review issues.
  • After receiving acceptance from reviewers, Run all tests, unit integration, high load and so on, wait for result.
  • If tests passed I can submit code to repository and merge to master branch, if no, process will start from writing code and will go through most steps.

Yes, has to be some “Code Conventions” for project and this convention should be described in project documents, even if you are using general CC.

Yes, has to be installed all infrastructure, with servers for code repository, review tool, testing, checking, issue tracking and desirable all these tools can be integrated to each other and as result to your IDE.

And Yes, you will spend more time than “just for development”, but as result, code will be as production of a few developers not just your thinking and bugs :) and more readable and clear for the next developers and changes.

Linux Bash get IP address


Today I’ve tried to prepare auto configuration of my application and one of the main point was create correct cluster with real IP addresses . For example you have some config files where you want to put real IP of installed machine. In real Linux world it should be configured manually after installation but I want to emulate auto configuration, so, I’ve prepared bash script for auto config all parameters for my app, but one point was interesting and I’ve decided to describe it in a few words.

So, How to get real IP address ? Each of us know that there are ifconfig util and we can get all information about interfaces and addresses, I’ve used this for prepared short script to get real IP v4 address

ifconfig eth0  $1 | grep “inet addr” | awk -F: ‘{print $2}’ | awk ‘{print $1}’

Use it in your scripts if you want to do tasks as I had.

Thanks.

How to install Yakuake on Cenros 6.3


I’ve started to use Centos server and tried to find good terminal emulator. Previously I’ve used guake for Ubuntu and some port of this emulator for Mac OS X. I’ve started to find repository of yakuake and found that there are no :(, So, I’ve prepared short instruction how to compile Yakuake for Centos 6.3.

Firstly you have to install kde dependencies, run your gnome terminal and execute next commands:

  1. su - go to root rights
  2. yum install gcc gcc-c++ make cmake kdebase kdelibs-devel

After this download Yakuake sources from this link, I use Yakuake 2.9.8 (KDE 4; Stable). Go to terminal and execute next commands

  1. cd  to download folder
  2. tar xaf yakuake-2.9.8.tar.bz2
  3. cd yakuake-2.9.8
  4. mkdir build
  5. cd build
  6. cmake -DCMAKE_INSTALL_PREFIX=$HOME/bin/yakuake/ ../
  7. make
  8. make install

And not mandatory step, but I did it, set yakuake to start automatically: System -> Preferences -> Startup Applications

And That’s all.

Cheers! :)

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.

Follow

Get every new post delivered to your Inbox.