Open Source For Geeks: May 2016

Sunday, 29 May 2016

Greasemonkey script to block Game of Thrones spoilers

Background

Greasemonkey is a Firefox plugin that runs user scripts just like tampermonkey in chrome. In this post we will see a simple script that will blacklist certain words appearing in Game of thrones which will potentially be spoilers.

Greasemonkey script to block Game of Thrones spoilers

Script is as follows -

// ==UserScript==
// @name           Spoiler Killer
// @include        http://*.facebook.com/*
// @include        https://*.facebook.com/*
// @require        http://code.jquery.com/jquery-1.7.1.min.js
// @require        https://gist.github.com/raw/2625891/waitForKeyElements.js
// @grant          none
// @version 1
// @namespace http://opensourceforgeeks.blogspot.in/
// @description Blacken facebook posts possibly containing Game of Thrones spoilers.
// copied from https://gist.github.com/vshivam/94d18c5d652217a449a5b785cbda1073
// ==/UserScript==

(function(){
    var terms = ['spoiler', 'game of thrones', 'hodor', 'jon snow', 'khaleesi', 'stark', 'dothraki'];
    function actionFunction(node){
        var content = node.html();
        content = content.toLowerCase();
        $.each(terms, function(index, term){
            if(content.indexOf(term) > -1){
                var overlay = $('<div />' ).css({
                     position: "absolute",
                     width: "100%",
                     height: "100%",
                     left: 0,
                     top: 0,
                     zIndex: 1000000,
                     background: "#000000",
                 });
                (function(overlay, node){
                    overlay.appendTo(node.css("position", "relative"));
                    $(node).on("mouseenter", function(){
                        overlay.hide();
                    });
                    $(node).on("mouseleave", function(){
                        overlay.show();
                    });
                })(overlay, node);
            }
        });
    }
    waitForKeyElements("div.userContentWrapper", actionFunction);
})();

NOTE : This script is copied over from https://gist.github.com/vshivam/94d18c5d652217a449a5b785cbda1073. It's original version can be found at https://gist.github.com/vshivam/9080a0b5ece35689163ed12955c131a9 (simply replaces text)

Script essentially blackens the posts that contain spoiler words. Feel free to add/remove words as you choose suitable. Make sure that the script is running on the site you intend it to be. You can test that from Greasemonkey icon near URL bar. See following screenshot for details -

Pushing existing local project to Github

Background

We have seen before how to clone a remote repository to local, work on it, modify files, commit and push to remote repository. But most of the time what happens we have a project on local (a new one) and want to save it on github. In this post we will see how to do that.

Pushing existing local project to Github

You will need to initialize a new repository on Github first. Simple create an empty repository.

Now to add your local repo you can execute following commands -

mkdir MyTestRepo
cd MyTestRepo/
touch test.txt
git init
git add .
git commit -m "First commit"
git remote add origin https://github.com/aniket91/MyTestRepo.git
git push -f origin master

Output is as follows -

You can then see this commit on remote.

After creating a new repo on github you will see following options -

Saturday, 28 May 2016

Installing Git in Ubuntu

Background

Sometime back I had written a post about git (it's installation and usage in windows). This post simple covers it's Linux counterpart. How to install git in Ubuntu.

Install and use Git on Windows

Installing git on Ubuntu

To install git execute following command -

git apt-get install git-core

Post installation you can run following command to verify installation -

git --version

And you are all good to go!

To set up git config you can use following command -

git config --global user.name "aniket91"
git config --global user.email "you@example.com"

To view the config you can do

git config --list

or view the config file

cat ~/.gitconfig

Try cloning a repository

git clone https://github.com/aniket91/DataStructures.git

My Git Repositories

Avoid Merge Commits

Whenever you have unpushed commits on your local and you try to do a git pull after those commits it will create a merge commit .
To avoid it follow one of the below mentioned methods,

run git pull --rebase
To avoid running it with the rebase flag and to make the above the default behavior when pulling changes, git config --global branch.autosetuprebase always
In SourceTree under tools->options/preferences under the Git tab select "Use rebase instead of merge by default for tracked branches"

Friday, 27 May 2016

Installing Oracle Java 8 In Ubuntu Or Linux Mint Via PPA Repository [JDK8]

Background

I have written a couple of posts on new features in Java 8 (See Related Links section at the bottom of this page).

In this post we will see how to install and configure Java 8 on Ubuntu. Current Java version that is set on my machine in Java7.

Installing Java 8

To install Java run the following commands -

sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer

Once you have run above commands you can verify the installation by running following command

java -version

Webupd8 ppa repository also provides package to set environment variables. Run following command for it

sudo apt-get install oracle-java8-set-default

NOTE : If you've already installed oracle-java6-set-default or oracle-java7-set-default, they will be automatically removed when installing oracle-java8-set-default (and the environment variables will be set for Oracle Java 8 instead).

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

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 -

Strings
Hashes
Lists
Sets
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.

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.

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.

In above code counter is a global variable.
In a web page global variables belong to window object. So you can also access it using window.counter.
Global variables can be accessed/changed by all scripts in a page.
A local variable can only be used inside the function where it is defined. It is hidden from other functions and other scripting code.
Global and local variables with the same name are different variables. Modifying one, does not modify the other.
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

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)

Sunday, 1 May 2016

Database Normalization

Background

Database Normalization is a technique to store data in a database in most efficient and organized manner possible. The main aim is to eliminate data redundancies and undesirable characteristics like

Insertion Anomaly
Update Anomaly
Deletion Anomaly

Database normalization is step by step process which we will look into shortly.

Problems faced without database normalization

Lets say you have following table -

Employee_ID	Name	Skill level	Team
1	John	A	Team C
2	Sam	A+	Team B
3	Margaret	B	Team A
4	John	A	Team A

Lets analyze above table data and see whats wrong with it .

Lets saw a new Employee is hired. When you make entry for him in this table his skill level will be null (as his skill sets are not yet tested ) and also his team (which may be determined by his skill set and level). This will result into Insertion Anomaly.
Now lets say John has become proficient in work and his skill level need to be updated. We will need to update all rows corresponding to John (He may be part of different teams) to keep the data consistent. This is called Update Anomaly.
Lets say Sam drops out of a team temporarily then we will have to delete the entire row (which inturn will delete employee details with it). This is called Deletion Anomaly.

Now lets see how we can resolve these anomalies.

Normalization Steps are as follows -

First Normal Form (1NF)
Second Normal Form (2NF)
Third Normal Form (3NF)
BCNF

Now lets see these in detail -

First Normal Form (1NF)

A relation is in first normal form if and only if the domain of each attribute contains only atomic (indivisible) values, and the value of each attribute contains only a single value from that domain. (Wiki)

So basically a column can have set of atomic (cannot be broken down) values and each row can only have a single value from this set. So something like below is not allowed in 1 NF -

Name	Skill level	Team
John	A	Team C, Team C
Sam	A+	Team B
Margaret	B	Team A

Instead following table is in 1 NF -

Name	Skill level	Team
John	A	Team C
Sam	A+	Team B
Margaret	B	Team A
John	A	Team A

Second Normal Form (1NF)

A table that is in first normal form (1NF) must meet additional criteria if it is to qualify for second normal form. Specifically: a table is in 2NF if it is in 1NF and no non-prime attribute is dependent on any proper subset of any candidate key of the table.

A non-prime attribute of a table is an attribute that is not a part of any candidate key of the table. (Wiki)

In above table which is in 1 NF you can see that the candidate key (primary key consisting of multiple columns) is {Name,Team} However Name -> Skill level. So it violated 2 NF which states a non prime key (Skill level) should not depend on any proper subset of candidate key (Name).

So we split the table with the subset and dependent column to new table. So that the tables now become -

Name	Skill level
John	A
Sam	A+
Margaret	B

and

Name	Team
John	Team C
Sam	Team B
Margaret	Team A
John	Team A

Third Normal Form (3NF)

3NF ensures the entity is in second normal form, and all the attributes in a table are determined only by the candidate keys of that table and not by any non-prime attributes. (Wiki)

Consider following table

Name	Skill level	Address	Zip Code
John	A	ADDR 1	123
Sam	A+	ADDR 2	345
Margaret	B	ADDR 3	156

This is in 2 NF but not in 3 NF as Zip Code (non prime key) -> Address (non prime key) (Candidate key - Name )So we need to move this dependency (also called transitive dependency) to new table with Zip code as primary key.

Resultant tables will be -

Name	Skill level	Zip Code
John	A	123
Sam	A+	345
Margaret	B	156

and

Zip Code	Asdress
123	ADDR 1
345	ADDR 2
156	ADDR 3

Boyce-Codd Normal Form (BCNF)

For table to be BCNF compliant it should satisfy -

For any non-trivial functional dependency, X → A, X must be a super-key. OR
If X → Y is a trivial functional dependency then (Y ⊆ X)

NOTE : A superkey is a combination of columns that uniquely identifies any row within a relational database management system (RDBMS) table. A candidate key is a closely related concept where the superkey is reduced to the minimum number of columns required to uniquely identify each row.

To Sum it up -