Day 4 - Bubble Sort

Bubble Sort - This is a simple sorting algorithm where elements of an array are swapped until sorting is achieved. It is a very inefficient algorithm. The basic theory behind bubble sorting is take an array of size n; iterate over the list; for each element at index i, if it greater than the element at next index (i+1), swap them. This causes the greater elements to go to the back of the array.

Implementation:
public class BubbleSort {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        int swap = 0;
        for(int i=0;i
        for(int j=i+1;j
        if(a[i]>a[j]){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        swap ++;
        }
        }
        }
        
        System.out.println("Array is sorted in "+swap+" swaps.");
        System.out.println("First element: "+a[0]);
        System.out.println("Last element: "+a[n-1]);

}

}

 Input: 

3

3 2 1

Output:

Array is sorted in 0 swaps.

First element: 1

Last element: 3

Day 2 - Queues & Stacks

Queues
Queues are data structures that follow the pattern of FIFO(first-in, first-out). It is similar to people standing in a queue. The first person gets serviced first.
The third person gets serviced after the first and second persons.
Similarly, in a queue, to get to the third element, first and second element need to be retrieved.

A simple implementation of a queue.
import java.util.LinkedList;

// Queue operate in FIFO. So, the first element added, gets out first.So, if we have to get the third element,
//we need to remove the first two elements to get to the third element
//Operations of a queue
// Check if queue is empty
// Get size of queue
// Enqueue - Add element to a queue
// Dequeue - Remove element from a queue. Usually the first element gets removed.
// Peek - Get the first element from a queue
public class Queue {
private LinkedList queue;
public Queue(){
queue = new LinkedList();
}

public boolean isEmpty(){
return queue.isEmpty();
}

public int size(){
return queue.size();
}

public void enqueue(int data){
queue.add(data);
}

public int dequeue(){
return (int)queue.remove(0);// When you remove the first element from a linked list, the second element becomes the head.
}

public int peek(){
return (int)queue.get(0);

}
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue(5);
queue.enqueue(6);
queue.enqueue(7);
System.out.println("Size of queue:"+queue.size());
System.out.println("First element:"+queue.dequeue());
System.out.println("First element:"+queue.peek());
System.out.println("Second element:"+queue.dequeue());
System.out.println("Third element:"+queue.dequeue());
System.out.println("Is the queue emepty:"+queue.isEmpty());
               System.out.println("Size of queue after dequeuing:"+queue.size());
}

}

Output:

Size of queue:3

First element:5

First element:6

Second element:6

Third element:7

Is the queue emepty:true

Size of queue after dequeuing:0

Java does have a Queue Interface where the above operations as well as some other useful methods are available, which can be implemented using LinkedList. 

The only way to traverse a stack or a queue is to pop/dequeue - which means we remove all the elements in the queue to get to the desired element/index. So, unless we store the dequeued /popped elements in another variable, they will be lost.

Stacks

Stack is a data structure which behaves in the LIFO (last-in, first-out) fashion. 

Taking the example of people standing a queue, the last person who came in, gets serviced first. And the first person gets serviced last. (Sounds weird, isn't it?)

Java already has a built in feature class called stack.

Stack has the following features: 

Push: Push/Inset an element.

Pop: Pop/Remove element

Peek: Returns the first element.

Taking an example:

import java.util.Stack;

public class StackEx {

public static void main(String[] args) {

Stack strStack = new Stack();

strStack.push("Hi ");

strStack.push("There ");

               

 System.out.println("First element/Peek:"+strStack.peek());

System.out.print(strStack.pop());

System.out.println(strStack.pop()+"!");

}

}

Output: 

First element/Peek:There 

There Hi !

The first element pushed into the stack was 'Hi'. But the first element popped out was 'There'. 

Another point is if we do a peek() operation after all the pop operations, it will give an IndexOutOfBoundsException. . Because, just like queues, when all elements are popped, the stack becomes empty. 

Comparing it with Queue. 

public static void main(String[] args) {

Queue queue = new Queue();

queue.enqueue("Hi ");

queue.enqueue("There ");

System.out.print(queue.dequeue());

System.out.println(queue.dequeue()+"!");

}

Output:

Hi There !

The queue pops out in whatever way the elements are inserted into the queue. 

Day 1 - Linked lists

Linked lists: Linked list is a list data structure where each element basically holds data as well as the reference to the next element.

Each element in a Linked List has two parts - Data (can be an Intger, String, Object) and a reference to the next element. Element of a linked list is also known as a node, perhaps for these reasons.

To define an element in a linked list. 

//Linked list have two things: data and reference to the next node.
// Here 'next' is a reference to the next node and 'data' is the value the node holds.
// 'data' is not limited to being an int. It could be a String, Object, float or any other datatype

public class Node {
Node next;
int data;

public Node(int newData){
data = newData;
}

public Node(Node newNode, int newData){
next = newNode;
data = newData;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}
}

To create a linked list data structure - 
import java.util.Scanner;

// Add nodes
// Remove nodes
// IsNodesavailable
// Get data related to a node
public class LinkedList {
static Node head; //First node
static int count; // count - tracks the number of nodes in the linked list

public LinkedList(){
head = null;
count = 0;
}

public LinkedList(Node newNode){
head = newNode ;
count ++;
}

// Add method - Create a new node with the data value as data 
public static Node add(int data){
Node temp = new Node(data);
if(count==0){
head = temp;
}
Node current = head;
while(current.getNext()!=null){
current = current.getNext();
}
if(count>0){
current.setNext(temp);
}
count++;
return head;

}
// Get the data at node 
public int get(int index){
if(index<=0){
return -1;
}
Node current = head;
for(int i=1;i
current = current.getNext();
}
return current.getData();
}

public int size(){
return count;
}

public boolean isEmpty(){
return head==null;
}
// Remove the last node from the list
public void remove(){
Node current = head;
while(current.getNext().getNext()!=null){
current = current.getNext();
}
current.setNext(null);
count--;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Node head = null;
int N = sc.nextInt();

while (N-- > 0) {
int ele = sc.nextInt();
head = add(ele);
}
display(head);
sc.close();
}

public static void display(Node head) {
Node start = head;
while (start != null) {
System.out.print(start.getData() + " ");
start = start.getNext();
}
}
}

Input 

4 (number of elements in list)

2

3

4

1

Output:

2 3 4 1 

Linked lists over Arrays - In arrays, the elements are indexed. For example, in an array of [2,4,1,5], the element at arr[3] can be easily retrieved. However, in linked list, we need to traverse from the beginning of the linked list. 

So, retrieval of an element in a linked list takes linear time - O(n) 

whereas in an array takes constant time - O(1)

The advantage lies in the fact that insertions  and deletions in a linked list are much quicker. 

Insertion/Deletion at beginning of the linked list or prepend to the linked list - O(1) -- constant time 

Insertion/Deletion at end of the linked list or append to the linked list - O(n) -- linear (as we need to traverse from the beginning till end of the linked list)

Doubly linked list have references to both the nodes/ 

i.e. 

class Node {

   Node prev;

   Node next;

   int data;

}

So, in a doubly linked list, the last node's 'next' reference will null and the first node's 'prev' reference will be null. All other elements in between have 'prev' and 'next' reference. 

In a singly linked list, the last node's 'next' reference will be null.

A brief tutorial is presented in: 

https://www.youtube.com/watch?v=njTh_OwMljA

Courtesy: Hackerrank site

Blogathon - GAJ (Get A Job)

From today, I am going to do a blog-a-thon to track my preparation in getting a job. The topics covered, coding problems attempted, interviews taken up, interview questions attempted, books read, technology covered, etc/ I feel this is the only way to track if my day was really productive or utilized productively. For the almost two months, I have been doing some form of studies. Hope this blog-a-thon brings a structured form.

HIbernate Problems & Solutions.

Hibernate: “Field 'id' doesn't have a default value”  - This error came up when a simple insert was tried using HIbernate.

                session.getTransaction().begin();

User user = new User();

user.setBirthDate(new Date());

user.setCreatedBy("ABC");

user.setCreatedDate(new Timestamp(new Date().getTime()));

user.setEmailAdress("abc@gmail.com");

user.setFirstName("ABC");

user.setLastName("DEF");

user.setLastUpdatedBy("SBC");

user.setLastUpdatedDate(new Timestamp(new Date().getTime()));

session.save(user);

session.getTransaction().commit();

Dropped the table 'User' which was created explicitly user DDL scripts and tried to generate it through HIbernate.

Ran the program after dropping the 'User' table in database.

But,the table did not get created in database. 

 

An error came up. Caused by: com.mysql.jdbc.exceptions.jdbc4.MySQLSyntaxErrorException: Table 'User' doesn't exist.

Resolution: Added a line in hibernate.cfg.xml file 

create

This will create table in database using HIbernate as well insert the above row into the table.

The Generation strategy used in User entity class was 

@Id

@GeneratedValue(strategy=GenerationType.IDENTITY)

@Column(name="USER_ID") 

 private Long userId;