Archive
Implementation of Singly Linked List in Java
/**
* 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
/**
* 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 < 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 <= 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?
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
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<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}
Difference between web server and application server?
A Web server serves pages for viewing in a Web browser, while an application server provides methods that client applications can call.
The Web server
A Web server handles the HTTP protocol. When the Web server receives an HTTP request, it responds with an HTTP response, such as sending back an HTML page. To process a request, a Web server may respond with a static HTML page or image, send a redirect, or delegate the dynamic response generation to some other program such as CGI scripts, JSPs (JavaServer Pages), servlets, ASPs (Active Server Pages), server-side JavaScripts, or some other server-side technology. Whatever their purpose, such server-side programs generate a response, most often in HTML, for viewing in a Web browser.
The application server
As for the application server, according to our definition, an application server exposes business logic to client applications through various protocols, possibly including HTTP. While a Web server mainly deals with sending HTML for display in a Web browser, an application server provides access to business logic for use by client application programs. The application program can use this logic just as it would call a method on an object (or a function in the procedural world).
Webserver is used only for jsp and servlets and for static functionality it has limited functionality and it doesn’t provide any security persistence and it doesn’t support EJB and JMS and JAAS like other functionality
whereas Application server provide all functionalities
In simple words, Application Server = Web Server + EJB Container
How To Create Immutable class and objects in Java
Immutable objects are those, whose state can not be changed once created e.g. java.lang.String, once created can not be modified.
Creating immutable classes in Java is becoming popular, because of concurrency and multithreading advantage provided by immutable objects. Immutable objects offers several benefits over conventional mutable object:
Especially while creating concurrent Java application.
Immutable object not only guarantees safe publication of object’s state, but also can be shared among other threads without any external synchronization.
JDK itself contains several immutable classes like String, Integer and other wrapper classes.
here are few rules, which helps to make a class immutable in Java :
1. State of immutable object can not be modified after construction, any modification should result in new immutable object.
2. All fields of Immutable class should be final.
3. Object must be properly constructed i.e. object reference must not leak during construction process.
4. Object should be final in order to restrict sub-class for altering immutability of parent class.
/**
* Simplest way of creating Immutable class
*/
package com.practise.immutables;</code>
/**
* @author skakkar
*
*/
//Class should be final to avoid immutability on risk due to Inheritance and Polymorphism
public final class ImmutableClass {
//Create all fields Final
private final String name;
private final String mobile;
public ImmutableClass(String name, String mobile) {
this.name = name;
this.mobile = mobile;
}
public String getName() {
return name;
}
public String getMobile() {
return mobile;
}
}
Advantages of Immutable Classes in Java
1) Immutable objects are by default thread safe, can be shared without synchronization in concurrent environment.
2) Immutable object simplifies development, because its easier to share between multiple threads without external synchronization.
3) Immutable object boost performance of Java application by reducing synchronization in code.
4) Another important benefit of Immutable objects is reusability, you can cache Immutable object and reuse them, much like String literals and Integers.
Java Interview questions asked recently
- What is hash map and how hash map is working?
Problem –
HashMap <Integer, String> fooMap = new HashMap<Integer, String>(); fooMap.put(1, "John"); fooMap.put(2, "Jackson"); fooMap.put(1, "Michael"); fooMap.get (1) what will be the output and how you'll get the value= "Michael"
- Difference between Wait and Sleep?
Ans. – Main difference between wait and sleep is that wait() method release the acquired monitor when thread is waiting while Thread.sleep() method keeps the lock or monitor even if thread is waiting.
- How can a thread acquire lock on resource?
- difference between compareTo and Comaparator?
- How to do exception handling in JSP?
- How to do Servlet Filter?
- Difference between List and Set?
- Does Wait will release lock on object or sleep release?
- What is indexing and different types of indexing in SQL?
- SQL – Emp table that has two fields EmpId and EmpName. get the name of Emp that has 3rd highest EmpId?
Difference between web server and application server?
Why can’t we make jsp as a controller and action servlet in struts?
When JSP compiles, internally the jsp compiler converts it to  servlets and compiles servlets java file and generartes the class file. Every time it will do the same thing, so it may take several time. It may cause performance issue.
Most of the applications are created in MVC design pattern to seperate the functions of differnetcomponents and handle the complexity of applications. JSP and Servlets are the server sidecomponents which can respond to the client request.
Servlets are the basic components for request handling in Web Server. They contains pure Java code. Everything that needs to be done to generate the proper user response (which is genarally HTML code) needs to be done through coding. As a single servlet cannot respond each and every request by itself as client request varies in type (e.g. enquiry, update request, add etc) the request and response object is passed onto different servlets with little task completed by each servlet. This controlling part is easier to write in java. So Servlet is used as controller.
JSP is again a servlet which has syntax more like to HTML with java support. Whatever user is going to see as result of his request is HTML. Programmer can easily write html tags inside JSP to render html. This is very economical to change also. So all this code is written JSP which is (generally) the final link in Servlet chaining.
In simple words, Controller (servlet) has pure Java code while View (JSP) has HTML code.
JAVA FAQ - Java Interview Questions 