Saturday, November 26, 2011 

Sorting algorithms.

Sorting Algorithms:
Lets say we have pack of cards that are to be sorted.

Bubble sort:
Compare first with the second, choose the smaller and swap them. Then compare the second one with the third and so on. Once a iteration is done, repeat the steps again. Repeat the iterations till you have not done even a single swap in the last iteration.

Time complexity:
Worst case: O(n2)
Base case: O(n)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: Yes
Java implementation:

Selection sort: 
Find out the smallest number in the given set of cards, you do this by taking the first card, compare it with the next set of the cards one by one, if you find a smaller card than the current card, you swap the smaller one on to your hand and continue with the comparison, once the list is exhausted. The card in your hand is the smallest,  place it at the start of the list. Then continue to find the smallest in the next set. Once you do this for the entire list, the list would be in sorted order.

Worst case: O(n2)
Base case: O(n2)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: No (however with a with increased space complexity can be done)
Java implementation:

Insertion sort:

Insertion sort is like adding new card to an already ordered set of cards at hand.
You pick a key element which is the new number that you have picked up, then you go through the already arranged elements and compare them with key, if any number is greater than key, you move it to one place up, and once you dont find any number greater than key with in the current list, you insert the key at that place.

Worst case: O(n2)
Best case: O(n)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: yes
Javascript implementation:
function insertionsort() {
    var a = [];
    var l = a.length;
    for (i = 1; i < l; i++) {
        k = i - 1;
        key = a[i];  // hold the current value of key in key.
        // check if the numbers which are sorted till now are greater than key, if you find any, move them one level up and insert the key there.
        while ((k > = 0) &&(a[k] > key)) {
            a[k + 1] = a[k];
        a[k + 1] = key;

Shell sort:
Its hard to explain shell sort. Basically you choose some gaps and then pick numbers with in that gap and sort/swap them. And repeat this process till the start end. You can find the video explaining this

Another better one.

The time complexity of the shell sort depends on the gap you have choosen. For

sequence (2 pow k − 1) complexity is (N pow 3/2)
successive numbers of the form (2 pow p) or (3 pow q)) complexity is (N((logN)pow 2)) - ex: 1, 2, 3, 4, 6, 8, 9, 12
Best case: O(n)
Space complexity: Inplace O(1)
IsStable: no
Java implementation:

Quick sort:
Pick a pivot card, and partition the numbers into to numbers less than pivot card, numbers greater than pivot card. This can be done by comparing the

You then repeat this process on the left and right hand side partitions by choosing another pivot with in them. The process continues till you cant select a pivot.

Time complexity:
Worst case: O(n2) (happens when the elements are already sorted in the opposite order, to avoid this we generally choose a randomized pivot)
Best case: nlogn
Average: nlogn
Space complexity: log n
IsStable: depends ??
Java implementation:
public static class QuickSort{
  public void sort(int[] a, int left, int right){
   int p;
   if(left < right){
   p = partition(a, left,right);
  public int partition(int[] a, int left, int right){
   int pivot = a[right];
   int i=left;
   int j= right;
   int temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
     return j;
Merge sort:
Divide cards into two sublists of about half the size. Sort each sublist recursively. Till the list is of length 0 or 1, then it is already sorted. Merge the sublists back into one sorted list.
Time complexity:
 Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: n
IsStable: yes
Java implementation:
Heap sort: Create a heap structure and then keep reading the min of the heap. Once the min is picked, keep deleting the min element. That would return the sorted list. This cannot be demonstrated using the cards.
 Time complexity:
 Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: 1
IsStable: No
Java implementation:
Binary sort: Construct a binary tree and do a inorder traversal to print the sorted sequence.

Non Comparison sorts:

These sorts are done where in we are dealing only with number esp of some range. Hence better performance then nlogn is possible.
Radix sort:
Lsd radix sort, sort the numbers based on their least significat bits and repeat this process with each more significant bit.
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1st place) gives:
 170, 90, 802, 2, 24, 45, 75, 66
Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.
Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
Note the sorting the last digits etc takes O(n) time only as we can use bucket sort.
 Time complexity:
 Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: 1
IsStable: No
Java implementation:
Bucket sort: Place each card in a buckets which are alread in sorted order, and then retrieve them as per the sort order of the buckets.
 Time complexity:
 Worst case: O(n+r) (r is the range of numbers to be sorted - basically number of buckets)
Best case: O(n+r)
Space complexity: O(n+r)
IsStable: Yes
Java implementation:
Count sort:
Asymptotic analysis: logn < n < n2 (n - square) <n3... < 2 to the power of n. big O notation. n2+2n+3n+logn = O(n2) ADT - Stack (with arrays) Stack implementation in Javascript. - Queue (with arrays / linked lists ) - Dqueue (with linked lists) - Dqueue can be used to implement stacks and queues - Circular lists with a sentinel is a efficient way to implement stacks / queues.?(this is interesting to implement) - Vector (ranks) - Position - List (based on positions) - Sequence (rank + positions) - Dictionary - Hash tables - Binary trees - Redblack trees - Avl trees - B-trees Binary Search: First sort and then divide and conquer the same to search O(log n base 2) Hash function: Hash codemap - key -> integer Hash compression map - integer -> [0, N-1] stack - creation tight strategy - (add constant) - f(N) = N+c  - O(n2) growth strategy - (double up) - f(N) = 2N  - O(n)

Thursday, November 24, 2011 

Multi tenant challenges.

The main reason for using multitenancy is to do remove maintenance night mare.

- Customizable with css and html (to an extent) - choosing a different css file for each tenant.
- In MVC drive the views based on tenant with each view for tenant in a different folder.
- All static files are stored under tenant specific folders - which is driven via a config file.

Business logic:
- Modularize the code and enable only few modules for each tenant.
- Inversion of control - using hooks.
- Dependency injection - driving the class names from config files based on the tenant.
- Generative programming. (while deploying the tenant, use admin tool to drive some of the code).


A database for each tenant
security- database conn is different so no problem
extending - create separate columns for the tenant if required. or have prefixed extendable columns.
scaling - scale the tenant database as required.

Single database with different table prefix for each tenant

security- database table prefix is different so not much problem if there is a single db class where we append prefix.
extending - create seperate columns for the tenant if required. or have prefixed extendable columns.
scaling - move the tables as required to a different database and scale it.

Single database with same tables with tenant id key.

security- Care should be taken to ensure the security of the queries.
extending - Have extrafields up front / have a separate table where you store extended columns. as explained here.
scaling - Use horizontal partitioning for tables using partition ids.


Web application security.

SQL injection:

The preferred option is to use a safe API which avoids the use of the interpreter entirely or provides a parameterized interface. Beware of APIs, such as stored procedures, that appear parameterized, but may still allow injection under the hood.
If a parameterized API is not available, you should carefully escape special characters using the specific escape syntax for that interpreter.
Positive or "whitelist" input validation with appropriate canonicalization also helps protect against injection, but is not a complete defense as many applications require special characters in their input.

Cross site scripting xss:

The preferred option is to properly escape all untrusted data based on the HTML context (body, attribute, JavaScript, CSS, or URL) that the data will be placed into. Developers need to include this escaping in their applications unless their UI framework does this for them. See the OWASP XSS Prevention Cheat Sheet for more information about data escaping techniques.
Positive or “whitelist” input validation is also recommended as it helps protect against XSS, but is not a complete defense as many applications must accept special characters. Such validation should decode any encoded input, and then validate the length, characters, and format on that data before accepting the input.

Using xss people can redirect users from your site to another, or get the session ids of your users and do session fixation etc.

Cross site forgery:

The easiest way to check whether an application is vulnerable is to see if each link and form contains an unpredictable token for each user. Without such an unpredictable token, attackers can forge malicious requests. Focus on the links and forms that invoke state-changing functions, since those are the most important CSRF targets.
- using posts and referrer header checks helps to an extent.

Failure to restrict private url access Insecure direct object references:
Just by chaning the parameters passed in the forms / urls users should not get access to what they are not supposed to access.
or just by pasting the internal urls users should not be able to view the internal pages with out login.
Broken session management: 
- You dont logout the user after some time of inactivity: If user forgets to logout, some one else can auto login.
- If you use session ids in the url, if another user gets access to that url in the meantime, he can use the session.
- Regenerate the session id on every request to avoid session fixation.

instead of

if (!isset($_SESSION['count']))
   $_SESSION['count'] = 0;
echo $_SESSION['count'];


if (!isset($_SESSION['initiated']))
   $_SESSION['initiated'] = true;

Password should be encrypted and stored:

Security misconfiguration:
directory listing.
older version of frameworks
exposing server version numbers.

Wednesday, November 16, 2011 

Another short but beautiful game I won.

Monday, November 14, 2011 

Javascript dom

Browser object model.
Window object: Its the global object that javascript core needs to function. 
It is preferred to wrap your code inside a self-executing anonymous function, which you stop your code from clobbering its variables with the global namespace. - for opening windows (popups) -'somepage.html','ppk',[arguments]);  - ppk is the window name.
Window.location - to change the current window location and access, the host, protocol properties.

Returns the code name of the browser
Returns the name of the browser
Returns the version information of the browser
Determines whether cookies are enabled in the browser
Returns for which platform the browser is compiled
Returns the user-agent header sent by the browser to the server

Window.opener - gives a reference to the parent window that has created this document.
window.history object.
setInterval - call a function every x  milli seconds (setInterval(func, 100))
setTimeout - call a function after x milli seconds

History Object Properties
Returns the number of URLs in the history list

History Object Methods

Loads the previous URL in the history list
Loads the next URL in the history list
Loads a specific URL from the history list

history.back(); // equivalent to clicking back button
history.go(-1); // equivalent to history.back();


Node interface:
To the W3C DOM, everything in an HTML document is a node. The entire document is a document node; every HTML tag element node and the texts contained in these elements are text nodes. Furthermore, HTML attributes like ID are attribute nodes, and even comments are comment nodes.

Every node in the document has five properties and two nodeLists that allow you easy short-distance travel. The five properties are parentNode, firstChild, lastChild, previousSibling, and nextSibling. chileNodes[] array

nodeName: The name of an element node is always the tag name, the name of an attribute node is always the attribute name, the name of a text node is always #text, and the name of the document node is always #document.

nodeType contains a number that gives the type of the node:
Element type

Node Methods:
There are four methods offered by node interface for changing the node tree. AppendChild(), insertBefore(), removeChild(), replaceChild(), cloneNode(). We would understand them along with the document object methods in the sections to follow.
Document object:

Other Document Object properties

Returns all name/value pairs of cookies in the document
Returns the mode used by the browser to render the document
Returns the domain name of the server that loaded the document
Returns the date and time the document was last modified
Returns the (loading) status of the document
Returns the URL of the document that loaded the current document
Sets or returns the title of the document
Returns the full URL of the document

Other Document Object Methods

Closes the output stream previously opened with
Accesses the first element with the specified id
Accesses all elements with a specified name
Accesses all elements with a specified tagname
Opens an output stream to collect the output from document.write() or document.writeln()
Writes HTML expressions or JavaScript code to a document
Same as write(), but adds a newline character after each statement

Document objects collection from the old dom0


Handling forms:
var sel = [the select box];
var value = sel.options[sel.selectedIndex].value;

var text = [text box]
text.value (will provide the value inside the text box)

var checkbox = [check box]
checkbox.checked - would return if the checkbox is checked or not. (and they too have value property).

<input type="radio" name="income" value="10" />&euro; 10 or lower<br />
<input type="radio" name="income" value="100" />&euro; 11-100<br />
<input type="radio" name="income" value="1000" />&euro; 101-1000<br />
<input type="radio" name="income" value="10000" />&euro; 1001-10000<br />

The above radio buttons are accessible through this DOM call:
var radios = document.forms[0].elements['income'];

var radios = document.forms[0].elements['income'];
for (var i=0;i<radios.length;i++) {
if (radios[i].checked)
// do something

var x = document.createElement('p');
var y = document.createTextNode('This is a created element');
x refers to the newly created <p> element, while y refers to the newly created text node. These nodes aren't inserted in the document yet. You would now use appendChild() or insertBefore() to add them to the document tree.


Element interface:

element interface properties: InnerHTML (set / get html content on an element), scroll, offset,client (width, height,top)
element methods: getAttribute, setAttribute, hasAttribute, removeAttribute

Event handling:

Dom Events:

Event bubbling:
Css modifications using javascript:

Saturday, November 12, 2011 


ECMA 262 standard.
Action script for flash is also based on ECMA standard.
Objects, Classes, Encapsulation, Inheritance, Polymorphism.
Objects - nouns, methods - verbs, properties - adjectives.
Encapsulation - Public, private, protected (information hiding) - In javascript everything is public - but use closures to hide.
Agregation - combining several objects into one.
Inheritance - classes inherit from classes (javascript objects inherits from objects - so objects based on objects)

Polymorphism - ability to calling the same method on two different objects.

Primitive types:
number, string,boolean, undefined, null

Numbers - 0x - hex, 2e+2 - means 200, 23, Infinity - is a special value /number :), NaN (is also a number - if you multiply 10*f  - as f is not a number result is a NaN) max 308 zeros 309 is too much.
Automatic string conversions to number take place if you use *number like string*  in arithematic operators otherwise NaN is r
Note - NaN == NaN - is false

typeof operator in javascript.

You can use array operators to access individual character in a javascript string - var s = 'one';
>>> s[0]

A better way to check if a variable is defined is to use typeof.
>>> if (typeof somevar !== "undefined"){result = 'yes';}
>>> result;
For-in Loops - for arrays
var a = [ 'a', 'b', 'c', 'x', 'y', 'z'];
var result = '\n';
for (var i in a) {
result += 'index: ' + i + ', value: ' + a[i] + '\n';

arguments is an array which receives the arguments, number of arguments passed / declared does not matter. extra arguments would remain undefined.

callbacks - functions passed as arguments to other functions - typical usage is to delegate the responsibility of calling a function to another function dynamically (say you can write a sort function which takes the comparison function as a call back). They can help with performance esp to avoid multiple for loops etc in few cases.
selfinvoking anonymous functions - usage is esp to avoid name space collisions
private functions - usage is to have functions secured with in a function not available in the global name space.
functions returning functions - this is to access scope see closures later.
functions updating themselves - generally to do some initial setup in the scope and once done, use a normal function.
var a = function() {
function someSetup(){
var setup = 'done';
function actualWork() {
return actualWork;

Function scope:
- this (the current object on which it is using  - if no object is used and the function is just called like that it uses window object as this)
- Lexical scope (all the variables with in the scope of this function and its parents - where it is defined (not executed) are accessible via this scope).
- Functions have lexical scope, ie scope is defined when the function is defined. However as soon as the function is called, the scope is used to assign the latest values to the variables used in the function. This is how closures work.

check below two examples to understand how this works.

Example1: Understanding what lexical scope means

>>> function f1(){var a = 1; f2();}
>>> function f2(){return a;}
>>> f1();
a is not defined
Inside the function f1() we call the function f2(). Because the local variable a is also inside f1(), one might expect that f2() will have access to a, but that's not the case. At the time when f2() was defined (as opposed to executed), there was no a in sight. f2(), just like f1(), only has access to its own scope.

Example2: Understanding how variable access from the scope happens when the actual function call is made.

function f() {
var a = [];
var i;
for(i = 0; i < 3; i++) {
a[i] = function(){
return i;
return a;

var a = f();
a[0]();  (output - 3)
a[1]();  (output - 3)
a[2]();  (output - 3)

Lexical scope + variable access during run time in action:

function f() {
var a = [];
var i;
for(i = 0; i < 3; i++) {
a[i] = (function(x){
return function(){
return x;
return a;

var a = f();
 a[0]();  (output - 0)
 a[1]();  (output - 1)
 a[2]();  (output - 2)

var o = {prop: 1};
var o = {"prop": 1};
var o = {'prop': 1};

property names of objects generally leave with out any quotes, however quotes are necessary if your property name starts with number/ has special chars / is a javascript identifier.

JavaScript uses arrays to represent indexed arrays and objects to represent associative arrays. If you want a hash in JavaScript, you use an object.

Object property values can be accessed using square bracket notation or . (dot) notation.
o.constructor property returns the constructor function
o.toString() is a method that returns a string representation of the object
o.valueOf() returns a single-value representation of the object, often this is the object itself

Constructor functions:
function Hero(name) { = name;
this.occupation = 'Ninja';
this.whoAreYou = function() {
return "I'm " + + " and I'm a " + this.occupation;

var h1 = new Hero('Michelangelo');
var h2 = new Hero('Donatello');

(output - "I'm Michelangelo and I'm a Ninja")

By convention, you should capitalize the first letter of your constructor functions so that you have a visual clue that this is not a normal function.

function Hero(){}
var h = new Hero();
var o = {};
>>> h instanceof Hero;
output - true
>>> h instanceof Object;
>>> o instanceof Object;

Functions that return objects 

function factory(name) {
return {
name: name

var o = factory('one');
however o.constructor() would return Object.

Objects are always assigned / passed by reference. See the below examples.

var original = {howmany: 1};
var copy = original;
>>> copy.howmany   (output: 1)
copy.howmany = 100;
>>> original.howmany (output: 100)

Built in objects:
Data wrapper objects—Object, Array, Function, Boolean, Number, and String.
Utility objects—These are Math, Date, RegExp
Error Object - Error

Array object:
var a = new Array(1,2,3)
>> a
var b = new Array(2);
[undefined, undefined]

Array has length property which on modifying dynamically changes the length of the array.
slice(), splice() functions give us a chunk of the array between offsets, however splice along with giving the slice modifies the original array by removing the slice it has returned.

Function objects:
 var sum = new Function('a', 'b', 'return a + b;');
creates a function sum similar to  function sum(a,b){return a+b;} however using the function constructor is not good just as eval.
Function objects have the following properties
- length - return the number of arguments it accepts.
- caller - returns the function that has actually called this function. If you call a function from global space caller would be null.
- prototype - property of a function contains an object. This is the object that is used to create new objects when this function is used as constructor. All objects created with this function keep a reference to the prototype property and can use its properties as their own.

Methods on function objects:
- toString - To string would return the function code in string format.
- call - used to call a method on a particular object on another object.
- apply - same as call but arguments are passed as array.

some_obj.someMethod.apply(my_obj, ['a', 'b', 'c']);, 'a', 'b', 'c');

The arguments variable with in a function looks like an array however it only has the length property of array. If you want to use some other methods of array on this use the apply method on those array methods.

The arguments object has a callee property which would have a reference to the function itself so you can do something like anonymous functions recursively calling themselves.

if (count < 5) {

Number object.
Number.MAX_VALUE will return the max value of that you can store in the number.
toFixed - method returns the number to the significant decimal digits.

var n = new Number(123.456)
>>> n.toFixed(1)

Simillar to Boolean(), the Number() function can be used as normal functions in order to try to convert any value to a number. This is similar to the use of parseInt() or parseFloat(). OR As a constructor function (with new) to create objects

var n = Number('12.12');
>>> n
>>> typeof n
var n = new Number('12.12');
>>> typeof n

- Note that this is not the case with Function object, it with either new / with out it would create a function.
var c = Function('a','return a;');
var f = new Function('a','return a;');

>>>typeof c
>>>typeof f

Delete variables in javascript:

Here is an excellent article from perfection kills on delete. The final gyst below
  • Variables and function declarations are properties of either Activation or Global objects.
  • Properties have attributes, one of which — DontDelete — is responsible for whether a property can be deleted.
  • Variable and function declarations in Global and Function code always create properties with DontDelete.
  • Function arguments are also properties of Activation object and are created with DontDelete.
  • Variable and function declarations in Eval code always create properties without DontDelete.
  • New properties are always created with empty attributes (and so without DontDelete).
  • Host objects are allowed to react to deletion however they want.

Javascript How functions / objects / Prototype / Constructor work.

  • When you define a function in javascript, it by default would have a prototype property set.
  • This prototype is an reference object which has - constructor property which is a reference to the function itself and any other methods added to it explicitly and few other internal methods.
  • When you create a object from a function (lets call it constructor function), using the new keyword, the following things happen.
    • An empty object is created, its internal __proto__ property is set to refer to same object that prototype of the constructor function (which is used to create it) is referring to.
    • Then the Constructor function is called with the "this" of that it pointing to the newly created object.
    • The Constructor then returns what ever value it has in return statement / the this object if nothing is returned.
  • The above process helps in getting the inheritance going.
  • Good thing is that you can extend the prototype object of the constructor function and it would add that extension to all the objects that are so far created with this constructor.
Javascript OOP:
  • Prototypal Inheritance: object.create()
Object.create() is automatically present in new browsers. For old browsers, use the following.
// helper function
if (typeof Object.create !== 'function') {
  Object.create = function (o) {
    function F() {}
    F.prototype = o;
    return new F();

var person = {
  sayHello : function () {
     alert('Person object');
  walk : function () {
var student1 = Object.create(person);
student1.sayHello = function () {
  alert('hello I am a student');
Adv: We dont call the super class constructor function, just copy the prototype of it onto a empty function and then copy it onto our object.
Objects inherit from objects.
Dis: This itself becomes a dis when you specifically want to call the super class constructor which might set some instance properties. 
You can manually call the constructors, chaining them.
  • Psuedo classical Inheritance: achieved like this. Difference between protoypal and classical as I observe is in prototypal, you just create an new object from old object. But in psuedo classical style, you create a inherits method on top of the constructor function of new object and point the prototype property of the constructor function of new object to the inherted object.
or instead of inherits you can also simply have.
// define the Person constructor function
function Person() {}
Person.prototype.sayHello = function(){
  alert ('hello');
// define the Student constructor function
function Student() {}
// inherit from Person
Student.prototype = new Person();
// correct the constructor pointer because it points to Person
Student.prototype.constructor = Student;
// replace the sayHello method (a polymorphism example)
Student.prototype.sayHello = function () {
  alert('hi, I am a student');
var student1 = new Student();
Adv: Super class constructor is called everytime so instance properties if any could be set.
Dis: If all you need is prototype properties than calling the constructor is a overhead.
  • Parasitic inheritance: In the "derived" constructor you create a "base" object instance, that object is augmented and that new instance is returned:
// Person constructor function
function Person(name) { = name;
function Student(value) {
  var that = new Person(value);
  that.sayHello = function () {
    alert('hello I am a student');
  return that;

How to do
  • Public, Private, Privileged methods / variables.

  • private variables are declared with the 'var' keyword inside the object, and can only be accessed by private functions and privileged methods.
  • private functions are declared inline inside the object's constructor (or alternatively may be defined via var functionName=function(){...}) and may only be called by privileged methods (including the object's constructor).
  • privileged methods are declared with this.methodName=function(){...} and may invoked by code external to the object.
  • public properties are declared with this.variableName and may be read/written from outside the object.
  • public methods are defined by Classname.prototype.methodName = function(){...} and may be called from outside the object.
  • prototype properties are defined by Classname.prototype.propertyName = someValue
  • static properties are defined by Classname.propertyName = someValue

If the arguments passed to a function are less than it expects, it can return a partial curry function, to which we can pass the missing arguments and get the actual result later as if we were called the original function with all the arguments.

function curry(func) {
var args= arguments.slice(1);
return function () {
return func.apply(null,
var inc = curry(function add(a, b) {
return a + b;
}, 1);
alert(inc(6)); // 7

when you find yourself calling the same function and mostly passing the same parameters, create a curry with redundant parameters

jslitmus - for performance testing.
closurecompiler - for optimizing js code.