Umut’s tech-blog – Programming, Artificial Intelligence and some other fun inside :)

Print all k-sum paths in a binary tree

March 22, 2017March 22, 2017
by hevi

Introduction

Binary Trees are the indispensable data structures of the interviews. Mostly because they are hard to understand and can change the complexity drastically; usually from O(n) to O(log(n)). Trees are the representatives of divide and conquer approach in the data structures, open to mind confusing recursive algorithms.

Problem

A binary tree with integer data and a number k are given. Print every path in the tree with sum of the nodes in the path as k.
A path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree.

here is where I first saw the problem : http://www.geeksforgeeks.org/amazon-interview-experience-set-323-software-development-engineer-off-campus/

but couldn’t understand it and found http://www.geeksforgeeks.org/print-k-sum-paths-binary-tree/ where I copied the problem definition from.

taken from http://www.geeksforgeeks.org/print-k-sum-paths-binary-tree/

Solution

My approach is basic, first think about a Tree with root only, if its value is equal to the given value then it is a solution. Now lets add a left and a right node. In this case as we go deeper on the tree we need to look for;

starting from root, is the sum equals to the given value
starting from the left is the sum equals to the given value and same for right

Hard part is collecting the correct path information.

The BST in solution hold lower values on the left and BST may contain negative values.

Here is the code;


void findSum(Integer originalSum, Integer sum,
             List<List<Integer>> result, List<Integer> currentList,
             Node node) {

    if (node == null) return;

    Integer nodeValue = node.value;
    currentList.add(nodeValue);

    if (Objects.equals(sum, nodeValue)) {
        List<Integer> resultL = new ArrayList(currentList);
        result.add(resultL);
    }

    // as the BST may contain negative values we have to iterate it all
    findSum(originalSum, originalSum, result, new ArrayList(), node.right);

    findSum(originalSum, originalSum, result, new ArrayList(), node.left);

    int remaining = sum - nodeValue;
    findSum(originalSum, remaining, result, new ArrayList(currentList), node.left);

    findSum(originalSum, remaining, result, new ArrayList(currentList), node.right);

}


public void findSum(Integer sum) {
    List<List<Integer>> result = new ArrayList<>();
    findSum(sum, sum, result, new ArrayList<>(), root);
    System.out.println(result);
}

Conclusion

The complexity of my solution is O(n^2) hope it is not a concern for you 🙂

I know my solution is terrible with brute-force but having negative values is the problem here, besides that the long signature is also terrifying but we have to carry the original value to start testing from any node.

By the way solution on http://www.geeksforgeeks.org/print-k-sum-paths-binary-tree/ is not working or I couldn’t make it work for some reason.

interviews

A social experiment – Interviews

March 22, 2017
by hevi

Hi folks, it has been a while since… Still checking some interesting interview questions just for fun and brain teasing.

To be honest asking these questions to candidates and expecting them to solve in a few minutes sounds just wrong 🙂 What’s even more interesting is that they expect candidates to write their answers (actual code) on the paper or -even worse- google docs etc. I feel like this is a test of obeisance. They set the rules, you have to obey even if they are nonsense. In my opinion it is a subconscious message; its interpretation is ‘I am the boss, do what I say’.

I am really curios about the statistics of employees chosen by these kind of interviews. It has to be correct and just right? Having interviews many times along my career (I’ve been on both sides) I can easily say that as the interview gets technical as the interviewers see theirselves more powerful and even superior.

Have you heard about Stanford prison experiment? I find these arrogant interviews rather similar to this experiment.

Apart from the psychological aspects of these interviews, lets talk about the reality. Say you want to get hired by one of these big bosses (google-amazon-facebook-yahoo etc) you have to memorize few hundred of questions and during the interview pretend (act and lie) that you never heard of the question, try to remember what was the brute-force solution 🙂 sounds funny and sad at the same time.

Does all these questions and struggle make you a great engineer or coder? Does it? What’s the reason – Where is the proof? I’ve been working over 10 years in the field and never ever had to open the cracking the coding interview book to find any help at all (I respect the book, it is great, but it’s the fact). When you face with real challenges you are not expected to write your code on the paper and hand it over to your team lead and s/he scratches on it 🙂 Thanks god it has been a while since the technology developed and we are not coding on Punched Cards any more.

I can hear what you are saying, how could they possibly pick the better candidates? My answer is; not like that. People giving up all the work they are doing -including their software projects- and memorizing 189 questions in weeks if not months??? Do we really want to work with them? Are they really more productive? Just an observation those getting high marks from interviews are tend to be less collaborative.

To conclude check this out and have fun 🙂 http://pythonforengineers.com/the-programming-interview-from-hell/

do it yourself

How to Serialize and Deserialize Generic Objects using GSON

September 28, 2015March 10, 2017
by hevi

Introduction

Java is great its Generic collections are awesome! Well not always. The real problem with generics and java before java 1.8 is that you cannot determine the type parameter in a generic class on runtime. That is the main reason why you often see passing XXX.class as a parameter to constructors and methods. I am not going to yell further so lets cut it short and see the problem and solution.

Problem

Lets say we are using command pattern and want the commands to be serialized and deserialized from java object to string and vice versa. GSon (wiki) is a great library for object-to-json transformation. However if the object is a generic object then you have some more coding to do. Here is my example;
Command class which is parent of all commands

public class Command<T> implements Serializable{

   public enum State{
      NONE,
      IDLE,
      PROCESSING,
      DONE
   }

   protected State state = State.NONE;

   protected Object undoData;

   public String getName(){
      return this.getClass().getSimpleName();
   }

   public State getState() {
      return state;
   }

   public void setState(State state) {
      this.state = state;
   }

   public Object getUndoData() {
      return undoData;
   }

   public void setUndoData(Object undoData) {
      this.undoData = undoData;
   }
}

Create command to be used for creation of some sort T

public class CreateCommand<T> extends Command<T> {

   T source;

   public CreateCommand() {
   }

   public CreateCommand(T source) {
      this.source = source;
   }

   public T getSource() {
      return source;
   }

   public void setSource(T source) {
      this.source = source;
   }
}

MigrateCommand is to be used for migrating some data from source to destination

public class MigrateCommand<T> extends Command<T> {
   T destination;
   T source;

   public MigrateCommand() {

   }

   public MigrateCommand(T destination, T source) {
      this.destination = destination;
      this.source = source;
   }

   public T getDestination() {
      return destination;
   }

   public void setDestination(T destination) {
      this.destination = destination;
   }

   public T getSource() {
      return source;
   }

   public void setSource(T source) {
      this.source = source;
   }
}

Lets make things even more complicated. We want to have a chain of commands which holds a list of commands of same type where T is the source type for Command and C is the type of command;

public class ChainCommand<T, C> extends Command<T> implements Iterable<C> {

   List<C> commands = new ArrayList<C>();

   Class<C> clazz;

   public ChainCommand(Class<C> clazz) {
      this.clazz = clazz;
   }

   public ChainCommand() {

   }

   public boolean addCommand(C command) {
      return commands.add(command);
   }

   public boolean removeCommand(C command) {
      return commands.remove(command);
   }

   public boolean containsCommand(C command) {
      return commands.contains(command);
   }

   @Override
   public Iterator<C> iterator() {
      return commands.iterator();
   }

   public List<C> getCommands() {
      return commands;
   }

   public Class<C> getClazz() {
      return clazz;
   }

   public void setCommands(List<C> commands) {
      this.commands = commands;
   }

   public void setClazz(Class<C> clazz) {
      this.clazz = clazz;
   }
}

That’s enough complicated for a generic type serialization but seriously this is just a case you may end up struggling in the field.
Now it is time for the meat of the code 🙂 ;

class CommandProcessor{

   // this method simply creates the test data and serialize
   void testSerializeCommands() {

      List<Command<String>> commands = new ArrayList<Command<String>>();

      commands.add(new CreateCommand<String>("CreateSource"));
      commands.add(new MigrateCommand<String>("MigrateDestination", "MigrateSource"));

      Command c1 = new CreateCommand<String>("ChainCreate1");
      Command c2 = new CreateCommand<String>("ChainCreate2");
      ChainCommand chainCommand = new ChainCommand(CreateCommand.class);
      chainCommand.addCommand(c1);
      chainCommand.addCommand(c2);

      commands.add(chainCommand);

// CommandSerializer is our class which does the actual serialisation
      Gson gson = new GsonBuilder().registerTypeAdapter(CommandPersistContainer.class,new CommandSerializer()).create();

      ObjectMapper objectMapper = new ObjectMapper();
      try {
         String jsonString = objectMapper.writeValueAsString(commands);
         System.out.println(jsonString);
      }
      catch (JsonProcessingException e) {
         e.printStackTrace();
      }
      catch (IOException e) {
         e.printStackTrace();
      }
   }
}

Here is the code doing the actual serialization

public class CommandSerializer implements JsonDeserializer<List<Command<String>>>{

   private Class getCommandClassForString(String classSimpleName) {
      if (StringUtils.equalsIgnoreCase(classSimpleName, CreateCommand.class.getSimpleName())) {
         return new CreateCommand<String>().getClass();
      }
      if (StringUtils.equalsIgnoreCase(classSimpleName, DeleteCommand.class.getSimpleName())) {
         return new DeleteCommand<String>().getClass();
      }
      if (StringUtils.equalsIgnoreCase(classSimpleName, MigrateCommand.class.getSimpleName())) {
         return new MigrateCommand<String>().getClass();
      }
      if (StringUtils.equalsIgnoreCase(classSimpleName, UpdateCommand.class.getSimpleName())) {
         return new UpdateCommand<String>().getClass();
      }

      return null;
   }

   private Command<String> deserializeFor(JsonElement je, JsonDeserializationContext context) {
      JsonObject asJsonObject = je.getAsJsonObject();
      String classSimpleName = asJsonObject.get("name").getAsString();

      if (StringUtils.equalsIgnoreCase(classSimpleName, CreateCommand.class.getSimpleName())) {
         return context.<Command<String>>deserialize(je, getCommandClassForString(classSimpleName));
      }
      if (StringUtils.equalsIgnoreCase(classSimpleName, DeleteCommand.class.getSimpleName())) {
         return context.<Command<String>>deserialize(je, getCommandClassForString(classSimpleName));
      }
      if (StringUtils.equalsIgnoreCase(classSimpleName, MigrateCommand.class.getSimpleName())) {
         return context.<Command<String>>deserialize(je, getCommandClassForString(classSimpleName));
      }
      if (StringUtils.equalsIgnoreCase(classSimpleName, UpdateCommand.class.getSimpleName())) {
         return context.<Command<String>>deserialize(je, getCommandClassForString(classSimpleName));
      }

      return null;
   }

   @Override
   public List<Command<String>> deserialize(JsonElement json, Type typeOfT, JsonDeserializationContext context)
         throws JsonParseException {
      List<Command<String>> commandList = new ArrayList<Command<String>>();

      JsonArray ja = json.getAsJsonArray();

      for (JsonElement je : ja) {

         JsonObject asJsonObject = je.getAsJsonObject();
         Command<String> command = deserializeFor(je, context);

         if (command != null) {
            commandList.add(command);
         }
         else {
            ChainCommand<String, Command<String>> chainCommand = new ChainCommand<String, Command<String>>();
            chainCommand.setState(Command.State.valueOf(asJsonObject.get("state").getAsString()));
            JsonElement rawUndoData = asJsonObject.get("undoData");
            String undoData = rawUndoData.isJsonNull() ? null : rawUndoData.getAsString();
            chainCommand.setUndoData(undoData == null ? null : OrganisationUnitBean.State.valueOf(undoData));

            JsonArray jsonArray = asJsonObject.get("commands").getAsJsonArray();

            for (JsonElement child : jsonArray) {
               chainCommand.getCommands().add(deserializeFor(child, context));
            }
            if(!chainCommand.getCommands().isEmpty()){
               chainCommand.setClazz((Class<Command<String>>) chainCommand.getCommands().get(0).getClass());
            }
            commandList.add(chainCommand);
         }
      }
      return commandList;
   }

}

do it yourself

How to Install and Configure Squid3 on Ubuntu 14.04…

September 23, 2015April 11, 2017
by hevi

What is Proxy Server

In brief a proxy server is a gateway which forwards your communication to the destination on behalf of you and sends back the messages to you. So the destination thinks that you are the proxy server and threats you accordingly. For instance if your proxy server is in Japan and you are in the US you may end up seeing advertisements or even sites in Japanese. In addition to that your ISP also thinks that you are trying to reach the address of your proxy server not the actual site you are requesting. For more info hit the wiki page.

To simplify it further, lets think that you want to send an mail to someone else but you don’t want neither your post office to know whom you are sending the mail nor the destination to know from where it received the mail while being able to send the response back to you. In this case you can simply hire someone in another country to just forward the mails to addresses hidden inside the envelope and re-envelope them before sending. As long as no one opens the envelope before your proxy, no one knows where the mail being sent. However if you are not using an encrypted form of communication with your proxy, someone can just open the mail get the address and still send it to its destination.

For securing the communication between you and the proxy server one method is using encrypted tunnels such as ssh tunneling which is completely possible with squid3 but hold on this post is just about setting squid3 up on Ubuntu 14.04 with basic authentication so you are not completely safe 😉

What is Squid

Squid is a popular easily configurable, robust, low resource consuming, fast and customisable proxy server – squid3 is currently the latest version of it.

Installation

squid3 comes within Ubuntu 14.04 default repo so nothing special;

sudo apt-get install squid3

Setup

First we need to edit the conf file, I prefer nano for editing, you can choose what u want

sudo nano /etc/squid3/squid.conf

Find INSERT YOUR OWN RULE(S) HERE TO ALLOW ACCESS FROM YOUR CLIENTS in the conf file and add the following lines just after it


acl allcomputers src 0.0.0.0/0.0.0.0
auth_param basic program /usr/lib/squid3/basic_ncsa_auth /etc/squid3/passwords
auth_param basic realm proxy
acl authenticated proxy_auth REQUIRED
http_access allow authenticated allcomputers

By doing that you tell squid to allow all computers (with 0.0.0.0 mask) with authentication and the username-password s are in etc/squid3/passwords file. You can change these two for your own setup, I will continue as if you did not change them.

Authentication – User creation

I prefer to use htpasswd for password creation which you can install by;

sudo apt-get install apache2-utils

after that, we need to create the password file;

sudo htpasswd -c -d /etc/squid3/passwords any_username_you_want

and enter your 8-digits long password twice. By using -d we tell htpasswd to use default crypt, I failed authenticating without it don’t really know why though.

Just to be sure the file is accessible;

sudo chmod o+r /etc/squid3/passwords

WARNING: At this point be careful your password should be 8 digits long otherwise it will use the first 8 digits off your password. You can use something shorter.

RUN / Start-Stop

You can use

sudo start squid3

sudo service squid3 start

for stopping or restarting simply type stop or restart instead of start

Final Words

Squid3 runs just perfect even with low resources. However there are some issues you just consider about security. From my own experiences I do not recommend you to use any proxy server without authentication. What happened to me was some robots found my 3128 port running (which is the default squid port) and started using my proxy server without my knowledge, when I realized that there already were hundred MBs of log. So do not use without authentication and keep an eye on the logs from time to time. You can simply do that by;

tail -100f /var/log/squid3/access.log

Here you will see which IPs are trying to use your proxy and the addresses trying to be accessed. I also recommend you to change the default squid port as the robots directly trying to reach some known default ports such as 3128. Changing the port is also simpe, open the squid.conf file and search for

http_port 3128

simply put something else instead of 3128.

For the client side I use FoxyProxy for FireFox, I think there is also a plugin for Chrome as well.

Enjoy!

Uncategorized

Road and Scene Recognition for the Analysis of Egocentric…

September 5, 2015March 11, 2017
by hevi

Abstract

Road recognition for safe driving purposes has been a widely investigated subject in computer vision for over forty years. In the literature road recognition refers to having camera(s) fixed inside of a vehicle, which is four-wheeled, looking along the movement direction. In some cases some other active or passive sensing devices have been used for better understanding of the three dimensional scene, hence, escalating the robustness. This thesis aims to introduce a real ego-centric analysis of the road and its surrounding scene from a single point camera attached to motorcyclist’s helmet or wore by the motorcyclist. One reason for choosing motorcyclists is the large number of publicly available videos. Different from the usual approaches, instead of having multiple sensors for leveraging the level of information, combining scene recognition road recognition on semantic basis would be considered as the second major aim of this thesis. Both of these aims are also the novelties of this thesis as they have not been investigated together in this field yet. Above these two aims, on humanitarian level this thesis expects to take a pace towards safe driving assistance for cyclists and motorcyclist which has not been considered in the literature or in the industry.

java

Java 1.8 + JavaScript Engine Nashorn + Debugging javascript…

July 25, 2014April 18, 2017
by hevi

Introduction

This is an extremely quick tutorial about using javascript engine (nashorn) usage in Java 1.8

These are the versions of apis and frameworks etc. used;

Java 1.8
JUnit 4.11
IntelliJ IDEA 13.1.4

WARNING: Using java versions below 8 will cause java.lang.NullPointerException as nashorn javascript engine comes with java 8.

Within this tutorial you will see

Testing (Kind of encouraging test driven development)
Creating and using nashorn javascirpt engine
Calling javascript functions from java
Calling java methods from javascript
Debugging javascript file using IntelliJ IDEA

Project Structure

INFO: Using maven is not really necessary for this project as all, infact JUnit is the only dependency, nashorn comes with jdk bundle. It is besically just an encouragement.

Dependencies

<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0
         http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>
	<groupId>info.hevi.learn</groupId>
	<artifactId>javascriptengine</artifactId>
	<version>1.0</version>

	<description>simple javascript engine tutorial with debugging</description>

	<properties>
		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <junit.version>4.11</junit.version>
    </properties>

	<dependencies>

        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>${junit.version}</version>
            <scope>test</scope>
        </dependency>

    </dependencies>

</project>

Code

Test File(MainTest.java)

public class MainTest {

    public String getName(){
        return "hevi.info";
    }

    @Test
    public void testScript() {
        ScriptEngineManager engineManager = new ScriptEngineManager();
        ScriptEngine scriptEngine = engineManager.getEngineByName("nashorn");

        String fileName = "src/main/resources/jsfile.js";
        String functionName = "doIt";
        try {

            scriptEngine.eval("load('" + fileName + "');");
            Invocable inv = (Invocable) scriptEngine;

            String retValue = (String) inv.invokeFunction(functionName, new MainTest());

            System.out.println(fileName + "@" + functionName + " returned " + retValue);

        } catch (ScriptException e) {
            e.printStackTrace();
        } catch (NoSuchMethodException e) {
            e.printStackTrace();
        }
    }
}

JavaScript File(jsfile.js)

function doIt(param) {
    var message = "hello world " + param.getName() + "!";
    return message;
}

So what happenes above is that doIt javascript function is called fully parametric, and pass MainTest instance as a parameter to the method;

inv.invokeFunction(functionName, new MainTest())

The doIt function calles getName() method which corresponds to a java method defined in MainTest class.

Debugging

Debugging is as just easy as debugging java files using IntelliJ IDEA 13.1. Here you can find here the IntelliJ blog for the debugging feature. The only point is that you suppose to use “nashorn” engine instead of raw “javascript” for creating scprint engine as below;

        ScriptEngine scriptEngine = engineManager.getEngineByName("nashorn");

Unfortunatelly java 8 is the requirement here.

Download Source Code

Download project – javajavascriptengine.zip

ehcache

Maven 3 + Hibernate 4 + Spring 3 +…

July 20, 2014April 6, 2017
by hevi

Introduction

This is a quick tutorial about integration of second level caching, more specifically ehcache to spring 3 along with hibernate 4.1.

These are the versions of apis and frameworks etc. used;

Java 1.6
Spring 3.2.8.RELEASE
Hibernate 4.2.11.FINAL
Mysql 5
JUnit 4.11

WARNING: Using java 8 will cause “org.springframework.core.NestedIOException: ASM ClassReader failed to parse class file – probably due to a new Java class file version that isn’t supported yet …” also here is the stackoverflow case.

WARNING: Using hibernate 4.3.x will cause “ERROR SessionFactoryImpl:1518 – HHH000302: Unable to construct current session context [org.springframework.orm.hibernate4.SpringSessionContext]
java.lang.reflect.InvocationTargetException”

Within this tutorial you will see

Testing with Spring and JUnit, application context loading. (Kind of encouraging test driven development)
Separated Dao and Service layers
Second level caching with ehcache
Spring caching
Spring 3 + Hibernate 4 + Ehcache integration
Hibernate statistics
Many-to-Many on Hibernate

DB Table

No worries, tables will be created automatically! 🙂

CREATE DATABASE `learn`
    CHARACTER SET 'utf8'
    COLLATE 'utf8_general_ci';

USE `learn`;

Project Structure

Dependencies (pom.xml)


<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0
         http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>
	<groupId>info.hevi.learn</groupId>
	<artifactId>spring-hibernate-ehcache</artifactId>
	<version>1.0</version>

	<description>Annotation Based Spring 3 + Hibernate 4 + EHCache + log4j Demo</description>

	<properties>
		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
		<project.build.mainClass>info.hevi.learn.spring3hibernate4ehcache.Main</project.build.mainClass>
		<java.version>1.6</java.version>
		<spring.version>3.2.8.RELEASE</spring.version>
		<hibernate.version>4.2.11.Final</hibernate.version>

	</properties>

	<dependencies>

		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-context</artifactId>
			<version>${spring.version}</version>
		</dependency>

		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-orm</artifactId>
			<version>${spring.version}</version>
		</dependency>

        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-aop</artifactId>
            <version>${spring.version}</version>
        </dependency>
		<!--@Transactional -->
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-tx</artifactId>
			<version>${spring.version}</version>
		</dependency>

		<dependency>
			<groupId>org.hibernate</groupId>
			<artifactId>hibernate-entitymanager</artifactId>
			<version>${hibernate.version}</version>
		</dependency>

		<dependency>
			<groupId>org.hibernate</groupId>
			<artifactId>hibernate-ehcache</artifactId>
			<version>${hibernate.version}</version>
		</dependency>

		<!-- connection pooling with c3p0 -->
        <dependency>
			<groupId>c3p0</groupId>
			<artifactId>c3p0</artifactId>
			<version>0.9.1.2</version>
		</dependency>

        <dependency>
            <groupId>log4j</groupId>
            <artifactId>log4j</artifactId>
            <version>1.2.17</version>
        </dependency>		

		<dependency>
			<groupId>mysql</groupId>
			<artifactId>mysql-connector-java</artifactId>
			<version>5.1.27</version>
		</dependency>

        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.11</version>
            <scope>test</scope>
        </dependency>

        <dependency>
            <groupId>cglib</groupId>
            <artifactId>cglib</artifactId>
            <version>3.1</version>
        </dependency>

        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-test</artifactId>
            <version>${spring.version}</version>
            <scope>test</scope>

        </dependency>

	</dependencies>

    <repositories>

        <repository>
            <id>JBoss repository</id>
            <url>http://repository.jboss.org/nexus/content/groups/public/</url>
        </repository>

        <repository>
            <id>java.net-Public</id>
            <url>https://maven.java.net/content/groups/public/</url>
        </repository>

    </repositories>

</project>

Bean & hibernate definitions (applicationContext.xml)

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:context="http://www.springframework.org/schema/context"
       xmlns:tx="http://www.springframework.org/schema/tx" xmlns:p="http://www.springframework.org/schema/p"
       xsi:schemaLocation="http://www.springframework.org/schema/beans  http://www.springframework.org/schema/beans/spring-beans-3.2.xsd  http://www.springframework.org/schema/context  http://www.springframework.org/schema/context/spring-context-3.2.xsd  http://www.springframework.org/schema/tx  http://www.springframework.org/schema/tx/spring-tx-3.2.xsd">

    <!-- Autowired -->
    <!--  used to activate annotations in beans already registered in the application context (no matter if they were defined with XML or by package scanning) -->
    <context:annotation-config/>
    <!-- scans packages to find and register beans within the application context. -->
    <context:component-scan base-package="info.hevi.learn.spring3hibernate4ehcache"/>

    <!-- enable @Transactional Annotation -->
    <tx:annotation-driven transaction-manager="transactionManager"/>

    <!--spring cache-->
    <bean id="cacheManager" class="org.springframework.cache.support.SimpleCacheManager">
        <property name="caches">
            <set>
                <bean class="org.springframework.cache.concurrent.ConcurrentMapCacheFactoryBean" p:name="task" />
            </set>
        </property>
    </bean>

    <!-- @PersistenceUnit annotation -->
    <bean class="org.springframework.orm.jpa.support.PersistenceAnnotationBeanPostProcessor"/>

    <!--  classpath*:*.properties-->
    <context:property-placeholder location="classpath:db.properties"/>

    <!-- data source with c3p0 -->
    <bean id="dataSource" class="com.mchange.v2.c3p0.ComboPooledDataSource" destroy-method="close"
          p:driverClass="${jdbc.driverClassName}"
          p:jdbcUrl="${jdbc.url}"
          p:user="${jdbc.username}"
          p:password="${jdbc.password}"
          p:acquireIncrement="${c3p0.acquire_increment}"
          p:minPoolSize="${c3p0.min_size}"
          p:maxPoolSize="${c3p0.max_size}"
          p:maxIdleTime="${c3p0.max_idle_time}"
          p:unreturnedConnectionTimeout="${c3p0.unreturned_connection_timeout}"/>

    <!-- Hibernate as JPA vendor-->
    <bean id="jpaAdapter"
          class="org.springframework.orm.jpa.vendor.HibernateJpaVendorAdapter"
          p:database="${jpa.database}" p:showSql="${jpa.showSql}"/>

    <bean id="sessionFactory" class="org.springframework.orm.hibernate4.LocalSessionFactoryBean">
        <property name="dataSource" ref="dataSource"/>

        <property name="hibernateProperties">
            <props>
                <prop key="hibernate.hbm2ddl.auto">${hibernate.hbm2ddl.auto}</prop>
                <prop key="hibernate.dialect">${hibernate.dialect}</prop>
                <!--<prop key="hibernate.connection.autocommit">${hibernate.connection.autocommit}</prop>-->

                <prop key="hibernate.cache.use_second_level_cache">true</prop>
                <prop key="hibernate.cache.use_query_cache">true</prop>
                <prop key="hibernate.cache.region.factory_class">org.hibernate.cache.ehcache.EhCacheRegionFactory</prop>
                <prop key="hibernate.show_sql">true</prop>

                <!--useful for debugging-->
                <prop key="hibernate.generate_statistics">true</prop>
            </props>
        </property>
        <property name="packagesToScan" value="info.hevi.learn.spring3hibernate4ehcache"/>
    </bean>

    <bean id="transactionManager"
          class="org.springframework.orm.hibernate4.HibernateTransactionManager">
        <property name="sessionFactory" ref="sessionFactory" />
    </bean>
</beans>

Ehcache cache definitions (ehcache.xml)

<?xml version="1.0" encoding="UTF-8"?>
<ehcache xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:noNamespaceSchemaLocation="http://ehcache.org/ehcache.xsd"
         updateCheck="false">
    <diskStore path="cacheIO" />

    <defaultCache maxElementsInMemory="10000" eternal="true"
                  overflowToDisk="false" diskPersistent="false"
                  diskExpiryThreadIntervalSeconds="1800" memoryStoreEvictionPolicy="FIFO">
    </defaultCache>

    <cache name="info.hevi.learn.spring3hibernate4ehcache.domain.Country"
           maxElementsInMemory="300"
           eternal="true"
           overflowToDisk="false"
           timeToIdleSeconds="12000"
           timeToLiveSeconds="12000"
           diskPersistent="false"
           diskExpiryThreadIntervalSeconds="120"
           memoryStoreEvictionPolicy="LRU"  />

    <cache name="countryCache"
           maxElementsInMemory="300"
           eternal="true"
           overflowToDisk="false"
           timeToIdleSeconds="12000"
           timeToLiveSeconds="12000"
           diskPersistent="false"
           diskExpiryThreadIntervalSeconds="120"
           memoryStoreEvictionPolicy="LRU"  />

    <cache name="countryByNameCache"
           maxElementsInMemory="300"
           eternal="true"
           overflowToDisk="false"
           timeToIdleSeconds="12000"
           timeToLiveSeconds="12000"
           diskPersistent="false"
           diskExpiryThreadIntervalSeconds="120"
           memoryStoreEvictionPolicy="LRU"  />

</ehcache>

Class Diagram of Services

Spring3Hibernate4EhcacheAnnotationServicesDiagram

Test file (MainTest.java)

@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(locations = {"/applicationContext.xml"})
public class MainTest {

    @Autowired
    ILanguageService languageService;

    @Autowired
    ICountryService countryService;

    @After
    public void cleanup() {
        Logger rootLogger = Logger.getRootLogger();
        rootLogger.setLevel(Level.ERROR);

        countryService.deleteAll();
        languageService.deleteAll();
    }

    @Before
    public void setup() {
        Logger rootLogger = Logger.getRootLogger();
        Level level = rootLogger.getLevel();
        rootLogger.setLevel(Level.ERROR);

        Language english = new Language("english");
        Language french = new Language("french");
        Language german = new Language("german");
        Language spanish = new Language("spanish");
        Language turkish = new Language("turkish");
        Language finnish = new Language("finnish");

        languageService.save(english);
        languageService.save(french);
        languageService.save(german);
        languageService.save(spanish);
        languageService.save(turkish);
        languageService.save(finnish);

        Country uk = new Country("uk");
        Country us = new Country("us");
        Country tr = new Country("tr");
        Country es = new Country("es");
        Country sw = new Country("sw");
        Country fn = new Country("fn");
        Country gr = new Country("gr");

        countryService.save(uk);
        countryService.save(us);
        countryService.save(tr);
        countryService.save(es);
        countryService.save(fn);
        countryService.save(sw);
        countryService.save(gr);

        Country country = countryService.getByName("gr");

        // adding some languages to Greece
        country.getLanguages().add(english);
        country.getLanguages().add(finnish);
        country.getLanguages().add(french);
        country.getLanguages().add(turkish);
        countryService.save(country);
        rootLogger.setLevel(level);
    }

    @Test
    public void testCache() {
        countryService.getAll();
        countryService.getByName("gr");
        countryService.getAll();
    }
}

Download Source Code

Download project – spring3hibernate4ehcache.zip

google

Google Interview Question: Chain of strings

October 9, 2013
by hevi

There is a list of strings and they ask if it is possible create a chain of string using all the strings in the given list.
A chain can be formed b/w strings if last char of the 1st string matches with 1st char of second string. (this question is taken from careercup)
To give an example;
let’s say the given list is {aaszx, prtws, stuia} in this case the only posible chain is prtws–stuia–aaszx

At first sight the problem looks to be pretty easy, just put the first and last characters on two seperate hasmaps ;

 
List<String> stringList = ...
stringList.add ...
Map<Character, Integer> firstCharacterCountMap = ...;
for each string : str in the list
    increment firstCharacterCountMap(first character of str)
    decrement lastCharacterCountMap(last character of str)

in the pseudo code above the idea is finding the number of characters at start position and number of end characters at the end. after check if there final sum of the results is 0. A reasonable solution yet doesn’t provide the chain to be constructed.
the difficulty is that there might be some dead-ends. let say the list is {ab, bd, cb, bc} if we start with ab; ab->bd->? there is no solution even though there is one. (Btw the solution is; ab->bc->cb->bd). At this point one solution may come to mind is starting from a string whose first character doesn’t correspond to and end. Unfortunately this idea is not as good as it seems since there might all the first characters have a correspondence.

My solution is in O(n^2) 🙁 yet it works. Anyway topological sorting also has n^2 complexity.

I first create two separate hashmaps for both start and end characters. then I put the strings to these maps with corresponding characters. next I check for all possible combinations recursively;

You also can run the code from ideone

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: uerturk
 * Date: 08/10/13
 * Time: 17:04
 * To change this template use File | Settings | File Templates.
 */
class HasChain {

    Map<Character, List<String>> startsWithStringMap = new HashMap<Character, List<String>>();
    Map<Character, List<String>> endsWithStringMap = new HashMap<Character, List<String>>();

    private Character getFirstChar(String str) {
        return str.charAt(0);
    }

    private Character getLastChar(String str) {
        return str.charAt(str.length() - 1);
    }

    boolean hasChain(List<String> stringList) {
        // create relations between strings and their first 
        // and last characters using two hasmaps.  
        for (String str : stringList) {
            Character start = getFirstChar(str);
            Character end = getLastChar(str);
            List<String> startsWithList;
            List<String> endsWithList;

            if (startsWithStringMap.containsKey(start)) {
                startsWithList = startsWithStringMap.get(start);
            } else {
                startsWithList = new ArrayList<String>();
                startsWithStringMap.put(start, startsWithList);
            }

            if (endsWithStringMap.containsKey(end)) {
                endsWithList = endsWithStringMap.get(end);
            } else {
                endsWithList = new ArrayList<String>();
                endsWithStringMap.put(end, endsWithList);
            }
            startsWithList.add(str);
            endsWithList.add(str);
        }

        // this stack is the solution stack
        Stack<String> stringStack = new Stack<String>();
        for (String str : stringList) {
            if (hasChain(stringList.size(), str, stringStack)) {
                System.out.println(stringStack);

                return true;
            }
        }

        return false;
    }

    // recursively iterates through all possibilities
    private boolean hasChain(int size, String startString, Stack<String> stringStack) {
        if (size == stringStack.size()) return true; // if the stack is full of strings, we found it!
        Character last = getLastChar(startString);
        if (startsWithStringMap.containsKey(last)) {
            List<String> stringList = startsWithStringMap.get(last);
            for (int i = 0; i < stringList.size(); i++) {
                String candidate = stringList.remove(i--); // remove the candidate as it shouldn't be used in the next iterations
                stringStack.push(candidate); // as if it is the solution
                if (hasChain(size, candidate, stringStack)) {
                    return true; // no need to continue
                }
                stringStack.pop(); // candidate is not the solution
                stringList.add(++i, candidate); // put it back to the list, where it belongs
            }
        }

        return false;
    }

    public static void main(String[] args) {
        List<String> stringList = new ArrayList<String>();
        stringList.add("bd");
        stringList.add("fk");
        stringList.add("ab");
        stringList.add("kl");
        stringList.add("cf");
        stringList.add("ff");
        stringList.add("fa");
        stringList.add("ak");
        stringList.add("ka");
        stringList.add("lf");
        stringList.add("bc");

        System.out.println(new HasChain().hasChain(stringList)); // should return true as there is a solution

        stringList.remove("ka"); // we break the chain here

        System.out.println(new HasChain().hasChain(stringList));  // should return false as there is no solution after removing 'ka'

    }
}

hope that helped to someone 🙂

google

Google Interview Question: Find a Pair Set Where Sum…

October 4, 2013
by hevi

Here is another google interview question (taken from here)

They give you a list of numbers such as {4, 1, 5, 2, 3, -1, 6,} and a threshold lets say 4
and ask for distinct pair sets from the list, where sum of the numbers in each pair less or equal to the threshold.
in this case answer should be;(4, -1), (1, -1), (1, 1), (1, 2), (1, 3), (5, -1), (2, -1), (2, 1), (2, 2), (3, -1), (3, 1), (-1, -1), (-1, 1), (-1, 2), (-1, 3), (-1, 4), (-1, 5)

well my solution is not O(n) as I use a sorted set. First put all the numbers and then get the range up to the difference between a number and the threshold.
In the worst case my solution is O(n^2) and on average O(n.logn)

You can run it from here
here is the code:

/**
 * User: uerturk
 */

import java.util.*;

/**
 * Input - array of integers size N, integer Threshold.
 * Output - the pairs (x, y) of distinct elements with condition x + y <= Threshold.
 * Is that possible to implement is with O(n) ?
 */
class FindPairsUnderThreshold {


    public List<Map.Entry<Integer, Set<Integer>>> solve(Integer[] integers, Integer threshold) {

        // the complexity > O(n), sorted list is the key in this solution
        SortedSet<Integer> sortedSet = new TreeSet<Integer>();

        // first put values into the sorted set
        for (Integer number : integers) {
            sortedSet.add(number);
        }

        // then get the range from the head (smallest value) to the maximum value that satisfies the condition
        List<Map.Entry<Integer, Set<Integer>>> result = new ArrayList<Map.Entry<Integer, Set<Integer>>>();
        for (Integer number : integers) {
            // headSet is not inclusive, +1 is to make it include the exact sum
            int diff = threshold - number + 1;
            Set<Integer> integerIntegerSortedMap = sortedSet.headSet(diff);

            Map.Entry<Integer, Set<Integer>> integerSetPair = new AbstractMap.SimpleEntry<Integer, Set<Integer>>(number, integerIntegerSortedMap);
            result.add(integerSetPair);
        }
        return result;
    }


    public static void main(String[] args) {
        Integer[] integers = {4, 1, 5, 2, 3, -1, 6,};
        Integer threshold = 4;
        List<Map.Entry<Integer, Set<Integer>>> solution = new FindPairsUnderThreshold().solve(integers, threshold);
        for (Map.Entry<Integer, Set<Integer>> entry : solution) {
            Integer first = entry.getKey();
            for (Integer second : entry.getValue()) {
                System.out.print("(" + first + ", " + second + "), ");
            }
        }
        System.out.println(solution);
    }

}

google

Google Interview Question: Find the Longest Sequence in an…

October 2, 2013
by hevi

Google interview questions are popular since a while and it’s become a fashion to ask difficult to answer questions during interviews.
Here is one question :
Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Eg. {1,6,10,4,7,9,5}
then answer is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time?

here is my solution. Buy I can’t understand the reason for asking such questions to be solved in a very short time. I wonder who could really solve this problem in 5 minutes time and if someone can does it really mean that s/he is a good programmer?

Run the code below from here


import java.util.HashMap;
import java.util.Map;

/**
 * User: uerturk
 */

/**
 * Given an int array which might contain duplicates, find the largest
 * subset of it which form a sequence.
 * Eg. {1,6,10,4,7,9,5}
 * then answer is 4,5,6,7
 * Sorting is an obvious solution. Can this be done in O(n) time
 */
class FindTheLongestSequence {
    private int follow(int startNumber, Map<Integer, Pair<Boolean, Integer>> pairMap) {
        Pair<Boolean, Integer> currentPair = pairMap.get(startNumber);
        if (currentPair == null) {
            return 0;
        } else {
            if (currentPair.getFirst()) {
                return currentPair.getSecond();
            } else {
                int result = follow(startNumber + 1, pairMap) + 1;
                currentPair.setFirst(true);
                currentPair.setSecond(result);
                return result;
            }
        }
    }

    public void longestSequence() {
        int[] ints = {1, 6, 10, 4, 7, 9, 5};
        // in the map first is the number, in the pair first isVisited flag, second is the score
        Map<Integer, Pair<Boolean, Integer>> pairMap = new HashMap<Integer, Pair<Boolean, Integer>>();
        for (Integer i : ints) {
            pairMap.put(i, new Pair<Boolean, Integer>(false, 1));
        }

        int[] results = new int[ints.length];
        for (int i = 0; i < ints.length; i++) {
            int result = follow(ints[i], pairMap);
            results[i] = result;
            System.out.println(ints[i] + ":" + result);
        }

    }

    class Pair<First, Second> {
        First first;
        Second second;

        public Pair(First first, Second second) {
            this.first = first;
            this.second = second;
        }

        public void setFirst(First first) {
            this.first = first;
        }

        public void setSecond(Second second) {
            this.second = second;
        }

        public First getFirst() {
            return first;
        }

        public Second getSecond() {
            return second;
        }

        public void set(First first, Second second) {
            setFirst(first);
            setSecond(second);
        }
    }

    public static void main(String[] args) {
        new FindTheLongestSequence().longestSequence();
    }
}