Sunday, 22 May 2016

Stariway to Kth floor problem

Question

There are N stairs that you need to take to the kth floor. You can either climb 1 stair at a time or 2 stair at a time. In how many ways you can cover N stairs.


Solution

Solution is simple recursive one. At a particular step 

  • If remaining step >=2 then you can either climb 1 step or 2 steps
  • Else If remaining step == 1 you dont have a choice, have to climb 1 step
  • Else you have reached your destination and have crossed n stairs - increment way

Java solution is as follows - 

    public static int findWays(int stairsClimbed, int totalStairs) {
        
        if(stairsClimbed == totalStairs) {
            return 1;
        }
        
        if((totalStairs - stairsClimbed) >= 2) {
            return findWays(stairsClimbed + 2, totalStairs) + findWays(stairsClimbed + 1, totalStairs);
        }
        else if ((totalStairs - stairsClimbed) == 1) {
            return findWays(stairsClimbed + 1, totalStairs);
        }
        return 0;
    }


You can find detailed Java solution with test cases on git repository - StairwayClimbWaysFinder .

PS : Git link has a bonus solution as well :)


Related Links

Saturday, 14 May 2016

Redis Tutorial (Basics & Configuration)

Background

I am just going to quote Redis from their website -

"Redis is an open source (BSD licensed), in-memory data structure store, used as database, cache and message broker. It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs and geospatial indexes with radius queries. Redis has built-in replication, Lua scripting, LRU eviction, transactions and different levels of on-disk persistence, and provides high availability via Redis Sentinel and automatic partitioning with Redis Cluster."

It is written in C language.




Peculiar features /  Advantages

  • Very Fast : Since Redis stores it's data entirely in memory (used disk for persistence) it is very fast in terms of I/O.
  • Various Data Structure Support : As saw before it supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs and geospatial indexes with radius queries.
  • Atomic operations : All Redis operation are atomic which means there is no race condition. Each client/thread will get updates data.
  • Multi Usability - Redis can be used as a database, as a cache or a message broker (like activeMQ)

Installation

To install redis simply install following command -
  • sudo apt-get install redis-server

To start redis server run following command
  • redis-server


That's it your redis server is up and running.

You can test your server with redis-cli
  • redis-cli
and then type ping you should get reply as pong


NOTE : You can also install redis desktop manager for Ubuntu

You can set the redis configuration using following command -
  • CONFIG GET CONFIG_SETTING_NAME
You can get all configuration by using *
  •  CONFIG GET *
To edit a configuration use following command -
  • CONFIG SET CONFIG_SETTING_NAME VALUE


 Data Types in Redis

There are 5 data types that redis supports -
  1. Strings
  2. Hashes
  3. Lists
  4. Sets
  5. Sorted Sets

 Strings

You can do string data storage with GET and SET commands. You can store upto 512 MB of data in a String.
  • SET name aniket
  • get name

 Hashes

Sets the specified fields to their respective values in the hash stored at key. This command overwrites any existing fields in the hash. If key does not exist, a new key holding a hash is created.

You can do hash operations with HMSET, HGET or HGETALL
  •  HMSET employee1 name aniket code 007
  •  HGET employee1 name
  •  HGETALL employee1


Lists

 Insertion order is retained. You can use lpush and lrange to add and view the list
  • lpush countrylist India
  • lpush countrylist China
  • lrange countries 0 -1



Sets and Sorted Sets

Sets are unorderd collection of strings where as in sorted setseach string is associated with a score that is used to sort the strings.

You can use SADD and SMEMBERS to add and view members of a set where as you can use ZADD and ZRANGEBYSCORE to add and view strings in sorted sets.

In sets each string is unique unlike list. So adding same key twice will result in just one entry in the set.





Related Links




Friday, 13 May 2016

Hibernate tutorial with xml configurations

Background

Hibernate is Java ORM (Object relation mapping) tool. It like other ORMs help map Java domain objects with tables in relational databases. It removes the overhead of using the underlying JDBC calls. It supports CRUD operations across all major relational databases. It supports transaction management and many other features. In this post we will see a demo example of hibernate application.


Architecture


Setup

I am simply going to create a simple standalone Java application using hibernate that used oracle database to connect to.  Also I am using Eclipse IDE with Apache Ivy dependency management tool. So create a project called HibernateDemo. It's structure will be as follows - 



Next lets create required files one by one. Lets start with the table creation. Following SQL should create the desired table for us in oracle - 

 CREATE TABLE Employee (

  id number(10) NOT NULL PRIMARY KEY,

  name varchar2(20) DEFAULT NULL,

  gender varchar2(20) DEFAULT NULL,

  accesstime_time DATE DEFAULT (sysdate)

);

 Next you will need some dependency jars like hibernate, slf4j etc. Add following dependency in ivy file - 

<?xml version="1.0" encoding="ISO-8859-1"?>
<!--
   Licensed to the Apache Software Foundation (ASF) under one
   or more contributor license agreements.  See the NOTICE file
   distributed with this work for additional information
   regarding copyright ownership.  The ASF licenses this file
   to you under the Apache License, Version 2.0 (the
   "License"); you may not use this file except in compliance
   with the License.  You may obtain a copy of the License at

     http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing,
   software distributed under the License is distributed on an
   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   KIND, either express or implied.  See the License for the
   specific language governing permissions and limitations
   under the License.    
-->
<ivy-module version="2.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:noNamespaceSchemaLocation="http://ant.apache.org/ivy/schemas/ivy.xsd">
    <info
        organisation="ofsg.com"
        module=""
        status="integration">
    </info>
    
    <dependencies>
        <dependency org="org.hibernate" name="hibernate-core" rev="5.1.0.Final"/>
        <dependency org="org.slf4j" name="slf4j-simple" rev="1.7.21"/>
    </dependencies>
    
    
</ivy-module>

You will also need to manually add oracle OJDBC jar in the classpath.

Java Code and configurations


Next lets create our persistent Java class - Employee.java


package com.osfg.models;


import java.util.Date;

/**
 * 
 * @author athakur
 * 
 */
public class Employee {

    private int id;
    private String name;
    private String gender;
    private Date accessTime;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getGender() {
        return gender;
    }

    public void setGender(String gender) {
        this.gender = gender;
    }

    public Date getAccessTime() {
        return accessTime;
    }

    public void setAccessTime(Date accessTime) {
        this.accessTime = accessTime;
    }

}



Next lets create configuration files that map this class to the database table - employee.hbm.xml

<?xml version="1.0"?>
<!DOCTYPE hibernate-mapping PUBLIC "-//Hibernate/Hibernate Mapping DTD 3.0//EN"
"http://hibernate.org/dtd/hibernate-mapping-3.0.dtd">

<hibernate-mapping>
    <class name="com.osfg.models.Employee" table="EMPLOYEE">
        <id name="id" type="int">
            <column name="ID" />
            <generator class="assigned" />
        </id>
        <property name="name" type="java.lang.String">
            <column name="NAME" />
        </property>
        <property name="gender" type="java.lang.String">
            <column name="GENDER" />
        </property>
        <property name="accessTime" type="timestamp">
            <column name="ACCESS_TIME" />
        </property>
    </class>
</hibernate-mapping>



NOTE : Notice the generator class. It is set to assigned so that you manually assign the primary key. There are many generator classes such as assigned (It is used if id is specified by the user), increment, hilo, sequence, native etc.

Now lets see the hibernate configuration file that has database connection details - hibernate.cfg.xml

<?xml version='1.0' encoding='UTF-8'?>  
<!DOCTYPE hibernate-configuration PUBLIC  
  "-//Hibernate/Hibernate Configuration DTD 3.0//EN"  
  "http://hibernate.sourceforge.net/hibernate-configuration-3.0.dtd">  
  
<hibernate-configuration>  
  
<session-factory>  
<property name="hbm2ddl.auto">update</property>  
<property name="dialect">org.hibernate.dialect.Oracle10gDialect</property>  
<property name="connection.url">jdbc:oracle:thin:@localhost:1699/test</property>  
<property name="connection.username">system</property>  
<property name="connection.password">test</property>  
<property name="connection.driver_class">oracle.jdbc.driver.OracleDriver</property>  
<mapping resource="/com/osfg/resources/employee.hbm.xml"/>  
</session-factory>  
  
</hibernate-configuration>  


And now finally write the demo code to demonstrate the functionality - HibernateDemo.java

package com.osfg.main;

import java.util.Date;

import org.hibernate.Session;
import org.hibernate.SessionFactory;
import org.hibernate.Transaction;
import org.hibernate.cfg.Configuration;

import com.osfg.models.Employee;

/**
 * 
 * @author athakur
 * 
 */
public class HibernateDemo {

    public static void main(String args[]) {

        Configuration cfg = new Configuration();
        cfg.configure("/com/osfg/resources/hibernate.cfg.xml");
        SessionFactory sFactory = cfg.buildSessionFactory();
        Session session = sFactory.openSession();
        Transaction transaction = session.beginTransaction();

        Employee newEmployee = new Employee();
        newEmployee.setId(1);
        newEmployee.setName("Aniket");
        newEmployee.setGender("male");
        newEmployee.setAccessTime(new Date());

        session.persist(newEmployee);

        transaction.commit();
        session.close();

        System.out.println("Employee record successfully saved");

    }

}

And you should be all set. Just run as any other Java application.






Related Links


Tuesday, 10 May 2016

Hide variable from console access - Javascript Closures and self executing functions

Background

I came across javascript closure when I was searching solution for an interesting question - can variable be private in javascript. Let me give an example to demonstrate this further. Consider following Javascript - 


<script>
var counter = 0;

function increment() {
    counter++;
    console.log('After increment counter : ' + counter);
}

function decrement() {
    counter--;
    console.log(' After decrement counter : ' + counter);
}
</script> 

Now from console in your browser try to access counter variable. You should be able to access it. You can also try to print counter value after executing increment and decrement methods from console.

Couple of notes before we proceed to see the output on console.
  1. In above code counter is a global variable.
  2. In a web page global variables belong to window object. So you can also access it using window.counter.
  3. Global variables can be accessed/changed by all scripts in a page.
  4.  A local variable can only be used inside the function where it is defined. It is hidden from other functions and other scripting code.
  5. Global and local variables with the same name are different variables. Modifying one, does not modify the other.  
  6. Variables created without the keyword var, are always global, even if they are created inside a function.

Now the question is we don't want to expose counter variable. What can we do? Closures to the rescue.

Javascript closure

Now see the javascript code below - 

<script>

var increment, decrement, printCounter;

(function () {
    var counter = 0;
    increment = function() {
        counter++;
        console.log('After increment counter : ' + counter);
    };
    decrement = function() {
        counter--;
        console.log(' After decrement counter : ' + counter);
    };
    printCounter = function() {
        console.log('counter : ' + counter);
    };
})();

</script>

Now repeat above operation. You cannot access counter variable now. Since it is define inside the closure it's scope is limited to that. functions on the other hand are global, so those you can use.


Noticed the following syntax?

(function(){
    //Bunch of code...
})();


It's called self executing function. It is executed only once when page loads.



So A closure is a function having access to the parent scope, even after the parent function has closed. 
If you just have one method you can also do something like -

 var increment = (function () {
    var counter = 0;
    return function () {return counter += 1;}
})();

increment();
increment();
increment();
// the counter is now 3 



Related Links

Sunday, 8 May 2016

Understanding Tries data structure

Standard Tries

The standard Trie for a set of strings S is an ordered tree such that
  • Each node but the node is labelled with a character
  • The children of a node are alphabetically ordered
  • The path from external nodes to the root yield the String of S.

For example see following picture -



How would you represent this in code? Each node will have an array of size 26 (assuming all english characters) where each index of array will store pointer to next node which is essentially next character of the string.

Running time for operations

  • A standard trie uses O(W) space.
  • Operations find, insert, delete take time O(dm) each where
    • w = total size of strings in S,
    • m = size of string involved in operation
    • d = alphabet size

Compressed Tries

  •  Trie with nodes of degree at least 2
  • Obtained from standart trie by compressing chains of redundant nodes.


 Applications

Trie has many useful applications like
  • Find first prefix in a text (pattern matching)
  • or auto complete a text (which is why it can be used in a search engine). The index of a search engine is stored into a compressed trie. Each leaf of trie is associated with a word and has a list of pages (URLs) containing that word called occurrence list. Trie is kept in memory while the occurrence lists are kept in external memory and are ranked by relevance.
  • Suffix tree (rooted directed tree whose edges are labelled with non empty substrings of S)


  • The suffix tree for a text X of size N from an alphabet of size d stores all the N suffixes of X is O(N) space. NOTE : There might be a case where a suffix is a prefix of another suffix in which case the suffix will end on an internal mode. To counter this case you can end the alphabet with a special character eg. $. Time complexity to build suffix tree - O(N^2)



Related Links



t> UA-39527780-1 back to top