Find the middle element of the linked list in single pass – O(n) complexity

A linked list contains Nodes that are linked to each other.

Create a Node – A node consists of data of that node and some information about the next linked node

function Node(data, nextNode){
this.data = data;
this.nextNode = nextNode;
}

Create all nodes

Note: First Node from right. This would be our last node in sequence. The reference to next node would be null since this is our last node.

var n5 = new Node("5", null); 
var n4 = new Node("4", n5);
var n3 = new Node("3", n4);
var n2 = new Node("2", n3);
var n1 = new Node("1", n2);

// So here is the representation of the linked list nodes, that we just created.
// n1 (1, n2) –> n2 (2, n3) –> n3 (3, n4) –> n4 (4, n5) –> n5 (5, null)

Here is how the linked list looks

linkedlist

The Naive Solution to this problem would be in 2 passes (2 for loops), which takes O(n^2) worst case complexity

1st pass is to loop thru to get the count of nodes in linked list and
2nd pass is to loop thru find the middle element by dividing the Count of Nodes by 2

So, for example if there are 5 Nodes.

1st pass is to count the number of nodes = 5
2nd pass is to loop thru to get the middle element by dividing 5/2 = 2.5 (so in the middle element to be 3)

There is a better and a faster way to get this in 1 Pass (1 for/while loop), with O(n) complexity

Assign 2 pointers while looping.
1st pointer moves 1 element at a time.
2nd pointer moves 2 elements at a time (twice as faster as the 1st pointer)

Some theory/story:

Assume that Person A and Person B would like to reach a destination X from same starting point.

Assume that it would actually take 10 mins to reach destination X.

Assume that Person B walks 2 times faster than Person A, then by the time Person B reaches destination X, Person A is exactly half way thru.

So, lets give a starting point to our node n1.

var slowNode = n1;
var fastNode = n1;

// Check if nextNode is not null and nextNode of the nextNode 
// (2 Nodes from the current Node) is also not null
while(fastNode.nextNode != null && fastNode.nextNode.nextNode != null) {
// slowNode should be moving to the next element of the linked list sequentially
slowNode = slowNode.nextNode;
// Now the fastNode should be twice as faster as the slowNode
fastNode = fastNode.nextNode.nextNode;
}

console.log(slowNode.data);

Relevant Code using Java

public class MiddleElementLinkedList {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		// Create Linked List Nodes
		
		LinkedListNode n5 = new LinkedListNode("5", null);
		LinkedListNode n4 = new LinkedListNode("4", n5);
		LinkedListNode n3 = new LinkedListNode("3", n4);
		LinkedListNode n2 = new LinkedListNode("2", n3);
		LinkedListNode n1 = new LinkedListNode("1", n2);
		
		// Set the starting point
		
		LinkedListNode slowNode = n1;
		LinkedListNode fastNode = n1;
		
		while(fastNode.getNextNode() != null && fastNode.getNextNode().getNextNode() != null){
			slowNode = slowNode.getNextNode();
			fastNode = fastNode.getNextNode().getNextNode();
		}
		
		System.out.println("Middle Element: " + slowNode.getData());

	}
	
	public static class LinkedListNode {
		private String data;
		/**
		 * @return the data
		 */
		public String getData() {
			return data;
		}

		/**
		 * @param data the data to set
		 */
		public void setData(String data) {
			this.data = data;
		}

		/**
		 * @return the nextNode
		 */
		public LinkedListNode getNextNode() {
			return nextNode;
		}

		/**
		 * @param nextNode the nextNode to set
		 */
		public void setNextNode(LinkedListNode nextNode) {
			if(nextNode == null)
				this.nextNode = null;
			this.nextNode = nextNode;
		}

		private LinkedListNode nextNode;
		
		LinkedListNode (String data, LinkedListNode nextNode) {
			this.data = data;
			this.nextNode = nextNode;
		}
	}

}

Here is how the linked list looks in Java

linkedlistjava

 

Happy Coding !!!

A few Javascript Gotchas

Regular Equality vs Strict Equality.

{} === {}

false // Even though they are empty objects, strict equality not only checks for type & value, but also checks the created instance. The created instance is different for each new Object

{} == {}
false

{x:5} == {x:5}
false

{x:5} === {x:5}
false

0 === false
false

0 == false
true

0 == 0
true

0 === 0
true

1 == 1
true

1 === 1
true

new Object() == new Object()
false

new Object() === new Object()
false

Object.create([]) === Object.create([])
false

Object.create([]) == Object.create([])
false

var x =””;
if(x){console.log(“123”)} else{console.log(“456”)}
456

var x = [];
if(x){console.log(“123”)} else{console.log(“456”)}
123

“” == 0
true

[] == “”
true

“” === 0
false

[] === “”
false

“” == ”
true

“” === ”
true

typeof(”)
“string”

typeof(“”)
“string”

” instanceof String
false

“” instanceof String
false

new String(“”) instanceof String
true

typeof(new String())
“object”

“”.toString == new String(“”)
false

“”.toString() == new String(“”)
true

“”.toString() == new String(“”).toString()
true

“”.toString === new String(“”)
false

“”.toString() === new String(“”)
false

“”.toString() === new String(“”).toString()
true

[] == new Array[];
VM362:1 Uncaught SyntaxError: Unexpected token ]

[] === new Array[];
VM363:1 Uncaught SyntaxError: Unexpected token ]

typeof(“”)
“string”

typeof(”)
“string”

typeof([])
“object”

typeof(Object)
“function”

typeof(new Array())
“object”

typeOf(new Array()) // typeOf is not defined, O in red is capital
VM418:1 Uncaught ReferenceError: typeOf is not defined(…)(anonymous function)

[].constructor.toString().indexOf(“Array”) > -1
true

[] instanceof Array
true

typeof null
“object”

typeof {}
“object”

{} instanceof Object
VM1270:1 Uncaught SyntaxError: Unexpected token instanceof

var t = {}
t instanceof Object
true

Object instanceof t
VM1385:1 Uncaught TypeError: Right-hand side of ‘instanceof’ is not callable(…)

typeof undefined
“undefined”
Note that typeof undefined is undefined which is wrapped in string quotes, but not a string.

typeof (typeof undefined)
“string”
Since the (inner) typeof undefined is undefined wrapped in string quotes, and the (outer) typeof (“undefined”) is being assumed as a string.

typeof when variable is defined.

var d = {};

typeof d === undefined
false

typeof d === “undefined”
false

d === “undefined”
false

d === undefined
false

typeof when variable is not defined

typeof u === undefined
false

typeof u === “undefined”
true

u === “undefined”
VM455:1 Uncaught ReferenceError: u is not defined
at <anonymous>:1:1
(anonymous) @ VM455:1

u === undefined
VM458:1 Uncaught ReferenceError: u is not defined
at <anonymous>:1:1

Numbers

1/-0 > 0
false

1/-0
-Infinity

-Infinity == 0
false

-Infinity > 0
false

-Infinity === 0
false

-Infinity > 1
false

-Infinity == 1
false

-Infinity === 1
false

Infinity == NaN
false

Infinity === NaN
false

1 instanceof Number
false

1/0 instanceof Number
false

1/0
Infinity

Infinity instanceof Number
false

typeof(“”)
“string”

typeof(Infinity)
“number”

new Number(1) instanceof Number
true

99.99 instanceof Number
false

typeof(99.99)
“number”

new Number(99.99) instanceof Number
true

typeof(NaN)
“number”

NaN instanceof Number
false

new Number(NaN)
Number {[[PrimitiveValue]]: NaN}

new Number(NaN) instanceof Number
true

NaN == Number
false

NaN === Number
false

new Number(NaN) === Number
false

new Number(NaN) == Number
false

NaN == undefined
false

NaN === undefined
false

NaN === ”
false

NaN == ”
false

NaN == null
false

NaN === null
false

isNaN(NaN)
true

Objects/Functions

var e = function(){};
var r = function(){};
var e1 = new e();
var r1 = new r();

e == r
false

e === r
false

typeof e
“function”

e instanceof function
VM352:1 Uncaught SyntaxError: Unexpected end of input

function instanceof e
VM387:1 Uncaught SyntaxError: Unexpected token instanceof

e1 == r1
false

e1 === r1
false

e1 instanceof r1
VM750:1 Uncaught TypeError: Right-hand side of ‘instanceof’ is not callable(…)(anonymous function) @ VM750:1

e1 instanceof Function
false

e1 instanceof Object
true

typeof(e1)
“object”

Assignments

var a = [1,2,3];
var b = [4,5,6];

a = b
[4, 5, 6] // This the value of a

a
[4, 5, 6] // a assignment to b copied over all values of b

b
[4, 5, 6] // No changes to b, so b still had reference to its original values

Pass by reference/value

var func = function(a) { var tempArray = [4,5,6];   a = tempArray;   console.log(a);}

func([1,2,3]);

[4,5,6] // Even though we pass by reference with a different value, the assigned variable value would be overridden with internal assignment (if any).

Which is best to use: typeof or instanceof?

http://stackoverflow.com/questions/899574/which-is-best-to-use-typeof-or-instanceof

Area, Perimeter and Type of a Triangle.

Problem Statement: Given 3 sides of a triangle, find the area, perimeter and determine the type of the triangle, if isosceles, equilateral, or scalene. Also, check for Right Angled Triangle. /*Skipping Acute and Obtuse triangle types.*/

Prompt 3 user inputs for sides of the triangle and a dialog to output.

Solution:

import javax.swing.JOptionPane;

public class Triangle {

	/**
	 * This is a class to determine if the given side lengths form a triangle.
	 * It lets the user know the type of the triangle based on the given side lengths.
	 * Also, it gives the Perimeter and Area of the triangle.
	 * @param args
	 */
	public static void main(String[] args) {

//		String sideA, sideB, sideC;
		double a,b,c;
		a = Double.parseDouble(JOptionPane.showInputDialog(null,"Please input side 1 length of the triangle: ", "Triangle Side 1", JOptionPane.QUESTION_MESSAGE));
		b = Double.parseDouble(JOptionPane.showInputDialog(null,"Please input side 2 length of the triangle: ", "Triangle Side 2", JOptionPane.QUESTION_MESSAGE));
		c = Double.parseDouble(JOptionPane.showInputDialog(null,"Please input side 3 length of the triangle: ", "Triangle Side 3", JOptionPane.QUESTION_MESSAGE));
		
		// For right angled triangle, as per mathematics, square of the hypotenuse is equal to the sum of the squares of the other 2 sides. h^2 = a^2 + b^2 where h is hypotenuse (can be any side a,b,c)
		// So we first need to determine the hypotenuse
		
		double h = a > b ? (a > c ? a : c) : (b > c ? b : c);
		
		// Permiter of the triangle
		double p = a + b + c, s = p/2;
		
		//Area of triangle
		double areaOfTriangle = Math.sqrt(s * (s-a) * (s-b) * (s-c));
		
		// Check to see if the triangle is equilateral -- All sides should be equal
		if(a == b && b == c){ // no need to check a == c the value always holds true.
			JOptionPane.showMessageDialog(null, "Based on the given sides, the triangle is a equilateral." +
					"\nPerimeter of the triangle is " + p + 
					"\nArea of Triangle is " + areaOfTriangle);
		} 
		// Check to see if the triangle is isosceles -- At least 2 sides should be equal
		else if(a == b || b == c || c == a) {
			JOptionPane.showMessageDialog(null, "Based on the given sides, the triangle is a isosceles." +
					"\nPerimeter of the triangle is " + p + 
					"\nArea of Triangle is " + areaOfTriangle);
		}
		// Check to see if the triangle is right angle -- Can be verified if sum of squares of each of the sides is equal to twice the square of the hypotenuse. 
		//Ex : 3^2 + 4^2 + 5^2 = 2 * h^2 where h is the hypotenuse
		else if(Math.pow(h,2) * 2 == Math.pow(a,2) + Math.pow(b,2) + Math.pow(c,2)) {
			JOptionPane.showMessageDialog(null, "Based on the given sides, the triangle is a right angled triangle." +
					"\nPerimeter of the triangle is " + p + 
					"\nArea of Triangle is " + areaOfTriangle);
		}// Check to see if the triangle is scalene -- no sides should be equal
		else if(a != b && b != c && a != c) {
			JOptionPane.showMessageDialog(null, "Based on the given sides, the triangle is scalene." +
					"\nPerimeter of the triangle is " + p + 
					"\nArea of Triangle is " + areaOfTriangle);
		}
		// Check if the triangle is not a triangle
		else if(a > b + c || b > a + c || c > a + b ) {
			JOptionPane.showMessageDialog(null, "Based on the given sides, the triangle is not a triangle");
		}
		else {
			JOptionPane.showMessageDialog(null, "Based on the given sides, the triangle is a normal triangle." +
					"\nPerimeter of the triangle is " + p + 
					"\nArea of Triangle is " + areaOfTriangle);
		}
	}

triangle

 

mailto: protocol with attachment in javascript?

Hello Folks,

It’s been quite a while I haven’t word pressing. I wanted to take some time out to blog a few helpful coding tips & tricks that I am coming across these days.

A few days back, my colleague had a requirement on opening a Outlook email using simple javascript which also includes a attachment to the outlook email. Well google’ing a bit found the answer to do so, but including a attachment to that is being hosted on a different server (OnBase Document Server) was a challenge.

Clicking this button below opens the Mail Draft Dialog Window (Mail is a default application for eMails in Mac OSX) / Outlook Draft Dialog Window (if Windows OS), with user set TO (sent by) email address, Subject Line (Outlook takes in maximum of 255 characters on Subject Line), Message Body. Note that the FROM (received from) email address will be decided by the default account set in Mail App/Outlook App.

mailTo

<a href="mailto:rc@rakeshchouhan.com?subject=Test%20Mail-To-Talk"></a>
According to RFC 2368 you can’t add an attachment to a message with the mailto: URL scheme due security reasons:

The user agent interpreting a mailto URL SHOULD choose not to create a message if any of the headers are considered dangerous; it may also choose to create a message with only a subset of the headers given in the URL. Only the Subject, Keywords, and Body headers are believed to be both safe and useful.

Conclusion:

mailto: only supports header values or text/plain content.

 

Happy learning 🙂

Convert a Maven project to eclipse project..

Given that a project is built in Maven, and you would like to import the same project in eclipse IDE. Or sometimes developers intentionally do not check in .project, .settings files to the repository. These files are generated by the eclipse IDE.

cd to the project directory

mvn eclipse:eclipse

Note: ensure that the project directory has pom.xml

Pascal’s Triangle with O(n^2) worst case.

public class PascalTriangle {
    
    public static void main(String[] args) {
        showPascal(9);
    }
    
    // This takes O(n^2) constraint.
    public static void showPascal(int rows){
    	// rows = Number of Pascal triangle rows to show up
    	// i = loop thru each row.
    	for(int i = 0; i<rows; i++)
    	{
    		// Start from 1. So, initialize the first number to 1
    		int number = 1;
    		// Give the spacing - Ex: If rows is 9, then the spacing  would 18 (because I specified the args as "", else if I specify args as "_", you would notice that the spacing is 17 and on 18th bit there would be a '_' ) for the first iteration of i = 0.
    		System.out.format("%"+(rows-i)*2+"s", "");
    		// j = loop thru  each column of a row by CALCULATing and display
    		for(int j=0; j<=i; j++)
    		{
    			// Give 3 more spacing and print the number on the 4th bit.
    			System.out.format("%4d", number);
    			
    			// Formula to calculate each column.
    			number = number * (i - j)/(j + 1);
    		}
    		// Print a empty line after each row.
    		System.out.println();
    	}
    }

Here is how the output look like:

pascaltriangleoutput

Happy Coding !!!

DB2 – Drop Table “IF EXISTS”

Hello Folks,

As most of you may probably be aware that DB2 does NOT have a “If Exists” check safe keyword to safely execute the DML statements.

Here is one another way apart from the many ways one would find over the net.

BEGIN
DECLARE CONTINUE HANDLER FOR SQLSTATE ‘{SQL_STATE}’
BEGIN END;
EXECUTE IMMEDIATE ‘DROP TABLE {SCHEMA_NAME.TABLE_NAME}’
END
GO

This query is fail safe, meaning that it captures the SQL State error if the statement failed to execute and continuous with other below statements, if any.

Here the SQL_STATE can be found at http://www.ibm.com/support/knowledgecenter/SSEPEK_10.0.0/codes/src/tpc/db2z_sqlstatevalues.html

and SCHEMA_NAME.TABLE_NAME is self explanatory.

Happy Learning !!

WebPage Loading & Rendering – How fast it that?

Hello There…

For the past few days, I was speed testing how fast my website loads and researching on how can I improve it. During this research, I came across many different ways and different techniques to improve a web page to load faster and render with a  very minimal memory footprint, from coding standpoint to server configuration.

Here are the metrics of my website’s performance, studied and tested with…

  1. Google Developers Page Speed Performance toolgoogledevelopersperformanceinsights
  2. Pingdom Website Speed Testpingdomspeedtest
  3. GTmetrix Performance Toolgtmetrixperformance

 

Notice that each test tool provides different performance test results. All the results are approximated based on their test strategy. However, there may be many other test tools to test out the website’s speed, but the important point to note is, these tools lets us know what went wrong and what can be done to improve it.

Here are some of things I had to do for improving..

Within HTML, JS & CSS files

  1. Minifying HTML, Javascript’s and CSS.
  2. Using ‘async’ and ‘defer’ (sometimes together where ever required) while loading javascript files.
  3. Inlining small CSS and scripting small JS within main document to minimize requests.
  4. Placing CSS in the document head.
  5. Sizing Content to Viewport.
  6. Serving Scaled images (If images are small sized, use data-uri’s instead)

      Within .htaccess file. (This file exists on the domain root folder)

  1. Leverage Browser Caching by specifying a “Cache-Control” to all Files Matching html, js, css, etc…
  2. Specifying a “Vary: Accept-Encoding header” to advise public proxies to store both compressed and uncompressed version of the resource.
  3. Specifying a ETag Header to validate Cache for all resources ending with file names.
  4. Ensuring landing page redirects are avoided (enabled by default)
  5. Ensuring gzip compression (enabled by default)
  6. Ensuring Keep-Alive is enabled (enabled by default in http.conf. If shared host, then we would have to set it manually in .htaccess)

Having done that, I do had some unanswered questions during this research.

  1. How to leverage browser caching andE-Tag (Cache Validator) to certain resources that do not end with file name in .htaccess file?Example for Resource URL’s:
    http://fonts.googleapis.com/css?family=Lato:400,700
    https://maps.googleapis.com/maps/vt?pb=!&#8230;

    The above resource URL’s DO NOT END with any file names.

  2. Since these resources are not cached by some proxy caching servers. How to remove query string and encode the parameters into the URL for resources having “?” (see resource URLs example from Q.1 above).
  3. How to prioritize visible content for rendering “above-fold-content” (as suggested in the Google developers page test tool), when your page is just one single page template?

Here are the resources that I was going through this research process..

 

Happy Learning 🙂

Well Known TCP/IP (Reserved) Ports

In TCP/IP and UDP networks, a port is an endpoint to a logical connection and the way a client program specifies a specific server program on a computer in a network. Some ports have numbers that are pre-assigned to them by the IANA, and these are called the “wellknown ports” which are specified in RFC 1700.

Port numbers range from 0 to 65536, but only ports numbers 0 to 1024 are reserved for privileged services and designated as wellknown ports. This list of wellknown port numbers specifies the port used by the server process as its contact port.

Note: Important ones are highlighted in bold.

Port Number Description
1 TCP Port Service Multiplexer (TCPMUX)
5 Remote Job Entry (RJE)
7 ECHO
18 Message Send Protocol (MSP)
20 FTP Data
21 FTP Control
22 SSH Remote Login Protocol
23 Telnet
25 Simple Mail Transfer Protocol
29 MSG ICP
37 Time
42 Host Name Server (Nameserv)
43 WhoIs
49 Login Host Protocol (Login)
53 Domain Name System (DNS)
69 Trivial File Transfer Protocol (TFTP)
70 Gopher Services
79 Finger
80 HTTP
103 Standard
108 SNA Gateway Access Server
109 POP2
110 POP3
115 Simple File Transfer Protocol (SFTP)
118 SQL Services
119 Newsgroup (NNTP)
137 NetBIOS Name Service
139 NetBIOS Datagram Service
143 Interim Mail Access Protocol (IMAP)
150 NetBIOS Session Service
156 SQL Server
161 SNMP
179 Border Gateway Protocol (BGP)
190 Gateway Access Control Protocol (GACP)
194 Internet Relay Chat (IRC)
197 Directory Location Service (DLS)
389 Lightweight Directory Access Protocol (LDAP)
396 Novell Netware over IP
443 HTTPS
444 Simple Network Paging Protocol (SNPP)
445 Microsoft-DS
458 Apple QuickTime
546 DHCP Client
547 DHCP Server
563 SNEWS
569 MSN
1080 Socks

@Courtesy: http://www.webopedia.com/quick_ref/portnumbers.asp

Happy Learning !!!