One Plus Three

Categories: Blogroll

Implementation of Singly Linked List in Java

October 9, 2015 Leave a comment
/**
 * Implementation of Node Class
 */
package com.sachin.datastructure;

/**
 * @author skakkar
 *
 */
public class Node {
	
	protected int data;
	protected Node link;
	
	public Node(){
		link = null;
		data = 0;
	}
	
	public Node(int d, Node n){
		this.data = d;
		this.link = n;
	}

	/**
	 * @return the data
	 */
	public int getData() {
		return data;
	}

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

	/**
	 * @return the link
	 */
	public Node getLink() {
		return link;
	}

	/**
	 * @param link the link to set
	 */
	public void setLink(Node link) {
		this.link = link;
	}
}

/**
 * Implementation of Singly Linked List in Java
 */
package com.sachin.datastructure;

/**
 * @author skakkar
 *
 */
public class LinkedList {

	protected Node start;
	protected Node end;
	public int size;

	public LinkedList() {
		start = null;
		end = null;
		size = 0;
	}

	/*
	 * Method to check if list is empty
	 */
	public boolean isEmpty() {
		return start == null;
	}

	/*
	 * Function to get size of the list
	 */
	public int size() {
		System.out.println("Singly Linked List Size "+size);
		return size;
	}

	/*
	 * Method to insert an element at begining
	 */
	public void insertAtStart(int val) {
		Node nptr = new Node(val, null);
		size++;
		if (start == null) {
			start = nptr;
			end = start;
		} else {
			nptr.setLink(start);
			start = nptr;
		}
	}

	/*
	 * Method to insert an element at end
	 */
	public void insertAtEnd(int val) {
		Node nptr = new Node(val, null);
		size++;
		if (start == null) {
			start = nptr;
			end = start;
		} else {
			end.setLink(nptr);
			end = nptr;
		}
	}

	/*
	 * Method to insert an element at given position
	 */
	public void insertAtPos(int val, int pos) {
		// Node that needs to be added at given position
		Node nptr = new Node(val, null);
		// Start node, after this new node has to be insert
		Node ptr = start;
		pos = pos - 1;
		for (int i = 1; i < pos; i++) {
			if (i == pos) {
				// Before this node new node has to be insert
				Node tmp = ptr.getLink();
				// setting up new linking between nodes for new node
				ptr.setLink(nptr);
				nptr.setLink(tmp);
				break;
			}
			// Move to next node if condition not matched
			ptr = ptr.getLink();
		}
		size++;
	}

	/*
	 * Method to delete an node from given position
	 */
	public void deleteAtPos(int pos) {
		// Delete First Node if position is first
		if (pos == 1) {
			start = start.getLink();
			size--;
			return;
		}
		// Delete Node from end if position is equal to size of list
		if (pos == size) {
			Node s = start; // end node
			Node t = start; // previous to end node
			while (s != end) {
				t = s;
				s = s.getLink();
			}
			end = t; // setting previous node as end node
			end.setLink(null);
			size--;
			return;
		}

		// Delete Node from between two nodes
		Node ptr = start;
		pos = pos - 1;
		for (int i = 1; i < size-1; i++) {
			if (i == pos) {
				Node tmp = ptr.getLink();
				tmp = tmp.getLink();
				ptr.setLink(tmp);
				break;
			}
			ptr = ptr.getLink();
		}
		size--;
	}

	/*
	 * Method to display elements
	 */
	public void display() {
		System.out.print("\nSingly Linked List = ");
		if (size == 0) {
			System.out.print("empty\n");
			return;
		}
		if (start.getLink() == null) {
			System.out.println(start.getData());
			return;
		}
		Node ptr = start;
		System.out.print(start.getData() + "->");
		ptr = start.getLink();
		while (ptr.getLink() != null) {
			System.out.print(ptr.getData() + "->");
			ptr = ptr.getLink();
		}
		System.out.print(ptr.getData() + "\n");
	}

	/*
	 * Method to insert in linked list in next position
	 */
	public void insertNext(int val) {
		Node nptr = new Node(val, null);
		size++;
		if (start == null) {
			start = nptr;
			end = start;
		} else {
			end.setLink(nptr);
			end = nptr;
		}
	}
	
	/*
	 * Method to reverse the linked list
	 */
	public void reverse(){
		if(start == null){
			return;
		}
		Node current = start;
		Node after = start.getLink();
		while(after != null){
			Node tmp = after.getLink();// save next node that will come
			after.setLink(current);// reverse the pointer
			current = after;// move the cursor
			after = tmp; //the node after is one saved earlier
		}
		start.setLink(null);
		start = current;
		
	}

	public static void main(String args[]) {
		LinkedList head = new LinkedList();
		head.insertNext(1);
//		head.insertNext(2);
//		head.insertNext(3);
//		head.insertNext(4);
//		head.display();
//		head.size();
//		head.reverse();
//		head.display();
//		head.size();
		 head.insertAtStart(1);
		 head.display();
		// head.insertAtEnd(2);
		// head.display();
		// // list.insertAtPos(3, 0);
		 head.size();
		 head.deleteAtPos(1);
		 head.display();
	}
}

Implementation of Doubly LinkedList in Java

October 9, 2015 Leave a comment
/**
* Implementation of Doubly LinkedList in Java
*/
package com.sachin.datastructure.DoublyLinkedList;</code>

/*
* Data Structure of Doubly LinkedList
*/
class Node {
protected int data;
protected Node next, prev;

public Node() {
next = null;
prev = null;
data = 0;
}

public Node(int d, Node n, Node p) {
data = d;
next = n;
prev = p;
}

public void setLinkNext(Node n) {
next = n;
}

public void setLinkPrev(Node p) {
prev = p;
}

public Node getLinkNext() {
return next;
}

public Node getLinkPrev() {
return prev;
}

public void setData(int d) {
data = d;
}

public int getData() {
return data;
}

}

/*
* @author skakkar
* 1) Create 2 reference variable and initialize them with
* reference of existing next and previous Node
* 2) Set prev and next of the new node
* 3) increase the size variable, as this is going to keep the size of the
* doubly link list
*/
public class DoublyLinkedList {

public int size;
protected Node start, end;

public DoublyLinkedList() {
start = null;
end = null;
size = 0;
}

public boolean isEmpty() {
return start == null;
}

public int getSize() {
System.out.println("Linked List Size "+size);
return size;
}

public void insertAtStart(int val) {
Node nptr = new Node(val, null, null);
if (start == null) {
start = nptr;
end = start;
} else {
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}

public void insertAtEnd(int val) {
Node nptr = new Node(val, null, null);
if (start == null) {
start = nptr;
end = start;
} else {
end.setLinkNext(nptr);
nptr.setLinkPrev(end);
end = nptr;
}
size++;
}

public void insertAtPos(int val, int pos) {
Node nptr = new Node(val, null, null);
if (pos == 1) {
insertAtStart(val);
return;
}

Node ptr = start;
for (int i = 2; i &lt; pos; i++) {
if (i == pos) {
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++;
}

public void deleteAtPos(int pos) {
if (pos == 1) {
if (size == 1) {
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return;
}
if (pos == size) {
end = end.getLinkPrev();
end.setLinkNext(null);
size--;
}
// Delete between two nodes
Node ptr = start.getLinkNext();
for (int i = 2; i &lt;= size; i++) {
if (i == pos) {
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();

p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}

/* Function to display status of list */

public void display(){

System.out.print("\nDoubly Linked List = ");
if (size == 0){
System.out.print("empty\n");
return;
}

if (start.getLinkNext() == null){
System.out.println(start.getData());
return;
}

Node ptr = start;
System.out.print(start.getData() + " ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != null){
System.out.print(ptr.getData() + " ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData() + "\n");
}

public void reverse(){
while (start != null) {
Node temp = start.getLinkNext();
start.setLinkNext(start.getLinkPrev());
start.setLinkPrev(temp);
if (temp == null)
break;
start = temp;
}
}

/**
* @param args
*/
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtStart(1);
list.insertAtStart(2);
list.insertAtStart(3);
list.insertAtStart(4);
list.getSize();
list.display();
// list.deleteAtPos(2);
list.reverse();
list.display();
list.getSize();

// list.insertAtPos(2, 2);
// list.display();
}

}

What is Blocking Queue ? Why to use blocking queue in producer consumer problem and implement custom blocking queue?

September 6, 2015 Leave a comment

Java.util.concurrent.BlockingQueue is a java.util.Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element.

A BlockingQueue does not accept null elements and throw NullPointerException on attempts to add, put or offer a null.

Java.util.concurrent.BlockingQueue interface is part of Collection interface and its primarily used for producer-consumer problem.

BlockingQueue implementations are thread-safe. All queuing methods achieve their effects atomically using internal locks or other forms of concurrency control.

For Implementing custom blocking queue, we will use linked list and following methods are important to know:

  • put(E e): This method inserts the specified element into this queue, waiting if necessary for space to become available.
  • E take(): This method retrieves and removes the head of this queue, waiting if necessary until an element becomes available.

BlockingQueue.java

package com.sachin.threads.blockingqueue;

import java.util.LinkedList;
import java.util.List;

/**
 * @author skakkar
 *
 */
public class BlockingQueue<E> {
	
	private List<E> queue = new LinkedList<E>();
	private int limit = 10;
	
	public BlockingQueue(int limit){
		this.limit = limit;
	}
	
	public synchronized void put(E item) throws InterruptedException{
		while(this.queue.size() == this.limit){
			System.out.println(" Waiting for Enqueue ");
			wait();
		}
		if(this.queue.size() == 0){
			notifyAll();
		}
		System.out.println(" Enqueue "+item.toString());
		this.queue.add(item);
	}
	
	public synchronized E take() throws InterruptedException{
		while(this.queue.size() == 0){
			System.out.println(" Waiting for Dequeue ");
			wait();
		}
		if(this.queue.size() == this.limit){
			notifyAll();
		}
		E val = this.queue.remove(0);
		System.out.println(" Dnqueue "+val.toString());
		return val;
	}

}

Interview questions asked in Impetus Technologies Noida

December 22, 2014 2 comments

Recently I collected interview questions asked for 4-8 years of experienced Java professionals for Senior Software Engineer and Team Lead Positions.

Impetus Technologies was hiring Java Professionals for some Big Data Projects. They have asked variety of questions on Core Java, Spring, Hibernate, Web Services and Database concepts.

Interview starts with basic OOPs Concepts following with some advanced java concepts I am providing some list of questions If you recently appeared for the interview please share your questions as well. So, It’ll be helpful for the other job seekers as well.

Some Of the Questions are:

    • What is Singleton Design Pattern – how to do early and lazy initialization of object ?
    • Define Producer Consumer Problem?
    • Why use Blocking-queue in Producer Consumer Problem ?

Answer :- Java.util.concurrent.BlockingQueue is a java.util.Queue that additionally supports operations that wait for the   queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element. Read More

    • How to create Immutable objects in java ?

Answer : – Immutable objects are those, whose state can not be changed once created e.g. java.lang.String, once created can not be modified. All fields of Immutable class should be final. Object must be properly constructed i.e. object reference must not leak during construction process and Object should be final in order to restrict sub-class for altering immutability of parent class. Read More

  • How to get frequency of each word in a paragraph of strings ?

Answer : – Use Collections.frequency() method to get the frequency of each word used in a paragraph. Read More

    • What is the connection between Object class’s clone method and Clonable Interface ?
    • How Hashmap works internally ?
    • What if we not implement Hash-code method during hash-map implementation ? As hashcode method is already written in Object class.

Answer : – Suppose I have this simple class

public class A{  
private String name;
private String data;
}

I want to put my class A objects into a HashMap. I will use the field name as the key, and the whole object as the value. We only need to implement hashCode and equals for the key type. as here we are using String Type as a key, String is immutable and always return same hashcode value. However you need to override them both if you are planning to use Class A as the key.

  • How can we pass shared resource in multi-threading environment. can we use any specific data structure to pass ?
  • generate random number without using Random class ?

Here I am providing important interview questions  to help you brush up your knowledge and prepare yourself to impress interviewer. Just like other interview questions posts, chances are that I will be adding more questions to this list in future, so you might want to bookmark it for future reference. I hope most of you are already aware with these basic concepts.

As of know I am not writing answers to these questions If you know answers of these questions please post them in comment section, I’ll include them also. If you guys needs any more clarification, I would be happy to post them here.

Keep Learning.

How to get frequency of each word in a paragraph of strings?

This question asked in Impetus technologies’s telephonic round. how to get frequency of each word in paragraph of strings?

package com.sachin.examples;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;

public class WordFrequency{

	public static void main(String args[]){
		String paragraph= "ab bc ab bc abbbb bc ab cd ef bc bc ";
		
		String eachWord[]=paragraph.split(" ");
		
		ArrayList listEachWord = new ArrayList(Arrays.asList(eachWord));
		LinkedHashMap numeach = new LinkedHashMap ();
		 
		for(int i=0;i&lt;eachWord.length;i++){
		 numeach.put(eachWord[i],Collections.frequency(listEachWord,eachWord[i]));  
		}
		 
		 
		System.out.println(numeach);
	}
}

output: {ab=3, bc=5, abbbb=1, cd=1, ef=1}

Threads In Java

July 30, 2013 1 comment

Introduction

The java.lang.Thread class is a thread of execution in a program. A Java program can have many threads, and these threads can run concurrently, either asynchronously or synchronously. A thread is an independent path of execution within a program. Many threads can run concurrently within a program.

Multithreading means two or more tasks executing concurrently within a single program.

Following methods are member of Object and Thread class:

Object – notify(), notifyAll(),  wait()

Thread – sleep(), yield()

In the Java language there are two ways of creating a thread:

1. Implementing Runnable interface – java.lang.Runnable

2. Extending Thread class – java.lang.Thread

Runnable Interface signature:

public interface Runnable {

void run();

}

The run() method contains the logic of the thread. One way to create a thread in java is to implement the Runnable Interface and then instantiate an object of the class. We need to override the run() method into our class which is the only method that needs to be implemented.

Example of Runnable Interface implementation:

/*******************************************************************************
* ------- Copyright 2011 @ SolutionString.com All Rights Reserved -------
******************************************************************************/
package com.example.thread;

/**
* @author skakkar
*
*/
public class RunnableExample implements Runnable
{
Thread runnableThread;

/**
* Default
*/
public RunnableExample()
{
}

/**
* @param args
*/
public static void main(String[] args)
{

Thread threadObj = new Thread(new RunnableExample());

//starts the thread
threadObj.start();

try {
//delay for one second
Thread.currentThread().sleep(1000);
} catch (InterruptedException e) {
}
//Display info about the main thread
System.out.println(Thread.currentThread());

}

@Override
public void run()
{
System.out.println("----&gt; "+Thread.currentThread());

}

}

 

public void run () method is defined in Runnable interface and since java.lang.Thread class implements Runnable interface it gets this method automatically.

Now the question is “Which way of implementing Thread is better? Extending Thread class or implementing Runnable interface?”

– And the answer is implementing Runnable interface is better because in Java we can only extend one class so if we extend Thread class we can not extend any other class while by implementing Runnable interface we still have that option open with us. as java is not supporting multiple inheritance and java recommends programming to interface concept.

We have created a thread , Thread will not start until we call the start() method of java.lang.Thread class. When we call start () method JVM execute run () method of that Thread class into separate Thread other than calling thread.

Extending Thread Class

public void run () method is defined in Runnable interface and since java.lang.Thread class implements Runnable interface it gets this method automatically.

Example of extending Thread class:

 /*******************************************************************************
 * ------- Copyright 2011 @ SolutionString.com All Rights Reserved -------
 ******************************************************************************/
package com.example.thread;

/**
 * @author skakkar
 *
 */
public class ThreadExample extends Thread
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		ThreadExample threadObj = new ThreadExample();
//		threadObj.setName("Thread1");
		threadObj.start();
//		threadObj.start();// It will throw IllegalThreadStateException

	}

	@Override
	public void run(){
		System.out.println(Thread.currentThread().getName());
	}
}