Blog | Sandeep Blogging

Binary Search

July 8, 2019 · 2 min read

Sandeep Bhardwaj

Binary Search Iterative and Recursive

/**
 * 704. Binary Search
 * <p>
 * Given a sorted (in ascending order) integer array nums of n elements and a target value, write a
 * function to search target in nums. If target exists, then return its index, otherwise return -1.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * Input: nums = [-1,0,3,5,9,12], target = 9
 * Output: 4
 * Explanation: 9 exists in nums and its index is 4
 * <p>
 * Example 2:
 * <p>
 * Input: nums = [-1,0,3,5,9,12], target = 2
 * Output: -1
 * Explanation: 2 does not exist in nums so return -1
 */
public class BinarySearch {

	/**
	 * Iterative binary search
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public int search(int[] nums, int target) {
		int low = 0;
		int high = nums.length - 1;

		while (low <= high) {
			int mid = (low + high) / 2;

			if (nums[mid] == target)
				return mid;

			if (nums[mid] > target) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}

	/**
	 * Recursive binary search
	 *
	 * @param nums
	 * @param low
	 * @param high
	 * @param target
	 * @return index of search element if found else -1
	 */
	public int binarySearch(int[] nums, int low, int high, int target) {
		while (low <= high) {
			int mid = (low + high) / 2;

			if (nums[mid] == target)
				return mid;

			if (nums[mid] > target) {
				return binarySearch(nums, low, mid - 1, target);
			} else {
				return binarySearch(nums, mid + 1, high, target);
			}
		}
		return -1;
	}

}

Add two numbers represented as LinkedList

July 7, 2019 · 2 min read

Sandeep Bhardwaj

Add two numbers represented as LinkedList

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

/**
 * 2. Add Two Numbers
 *
 * You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse
 * order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
 * <p>
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 * <p>
 * Example:
 * <p>
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 */
public class AddTwoNumbers {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode output = null;
		int carry = 0;

		ListNode current = null;
		while (l1 != null && l2 != null) {

			int val = (l1.val + l2.val + carry) % 10;
			carry = (l1.val + l2.val + carry) / 10;

			l1 = l1.next;
			l2 = l2.next;

			if (output == null) {
				output = new ListNode(val);
				current = output;
			} else {
				current.next = new ListNode(val);
				current = current.next;
			}
		}


		while (l1 != null) {
			int val = (l1.val + carry) % 10;
			carry = (l1.val + carry) / 10;

			l1 = l1.next;
			current.next = new ListNode(val);
			current = current.next;
		}

		while (l2 != null) {
			int val = (l2.val + carry) % 10;
			carry = (l2.val + carry) / 10;

			l2 = l2.next;
			current.next = new ListNode(val);
			current = current.next;
		}

		if (carry != 0) {
			current.next = new ListNode(carry);
		}
		return output;
	}
}

Detect a loop in LinkedList

May 21, 2018 · 2 min read

Sandeep Bhardwaj

Detect loop in a linked list.

Floyd’s Cycle-Finding Algorithm:

Traverse linked list using two pointers. Move one pointer(slowPtr) by one and other pointer(fastPtr) by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.

LinkedList.java

public class LinkedList<E> {
	static class Node<E> {
		E data;
		Node<E> next;

		Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}// end of node class

	private Node<E> head = null;

	Node<E> getHead() {
		return head;
	}

	public void add(E e) {
		Node<E> node = new Node<>(e, null);
		if (head == null) {
			head = node;
		} else {
			Node<E> current = head;
			while (current.next != null) {
				current = current.next;
			}
			current.next = node;
		}
	}

	public void display(Node<E> head) {
		Node<E> current = head;
		while (current != null) {
			System.out.print(current.data + "-> ");
			current = current.next;
		}
		System.out.print("NULL\n");
	}

	public boolean detectLoop(Node<E> head) {
		Node<E> slowPtr = head;
		Node<E> fastPtr = head;
		while (fastPtr != null && fastPtr.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
			if (slowPtr == fastPtr) {
				return true;
			}
		}
		return false;
	}

	/**
	 * <pre>
	 * 1 > 2 > 3 > 4
	 *     ^       ^
	 *     |_______|
	 *
	 * </pre>
	 *
	 * @author Sandeep Bhardwaj
	 *
	 */
	public static void main(String[] arg) {
		LinkedList<Integer> list = new LinkedList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		Node<Integer> head = list.getHead();
		//create loop
		head.next.next.next = head.next;
		list.display(head);
	}
}

Output

Loop found ...

Complexity

Time Complexity: O(n)
Auxiliary Space: O(1)

Reverse LinkedList Recursively

May 20, 2018 · 2 min read

Sandeep Bhardwaj

Reverse a linked list recursively.

LinkedList.java

public class LinkedList<E> {
	static class Node<E> {
		E data;
		Node<E> next;

		Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}// end of node class

	private Node<E> head = null;

	Node<E> getHead() {
		return head;
	}

	public void add(E e) {
		Node<E> node = new Node<>(e, null);
		if (head == null) {
			head = node;
		} else {
			Node<E> current = head;
			while (current.next != null) {
				current = current.next;
			}
			current.next = node;
		}
	}

	public void display(Node<E> head) {
		Node<E> current = head;
		while (current != null) {
			System.out.print(current.data + "-> ");
			current = current.next;
		}
		System.out.print("NULL\n");
	}

	/**
	 * Reverse a list recursively
	 *
	 * @param head
	 * @return head of reversed list
	 */
	public Node<E> reverseRecursively(Node<E> head) {
		// base condition
		if (head == null || head.next == null) {
			return head;
		}

		Node<E> current = head;
		head = reverseRecursively(current.next);
		current.next.next = current; // reverse list
		current.next = null; // remove link
		return head;
	}

	public static void main(String[] arg) {
		LinkedList<Integer> list = new LinkedList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		Node<Integer> head = list.getHead();
		System.out.println("List before reverse");
		list.display(head);
		System.out.println("\nList after reverse");
		head = list.reverseRecursively(head);
		list.display(head);
	}
}

Output

List before reverse
1-> 2-> 3-> 4-> NULL

List after reverse
4-> 3-> 2-> 1-> NULL

Reverse LinkedList Iteratively

May 19, 2018 · 2 min read

Sandeep Bhardwaj

LinkedList.java

public class LinkedList<E> {
	static class Node<E> {
		E data;
		Node<E> next;

		Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}// end of node class

	private Node<E> head = null;

	Node<E> getHead() {
		return head;
	}

	public void add(E e) {
		Node<E> node = new Node<>(e, null);
		if (head == null) {
			head = node;
		} else {
			Node<E> current = head;
			while (current.next != null) {
				current = current.next;
			}
			current.next = node;
		}
	}

	public void display(Node<E> head) {
		Node<E> current = head;
		while (current != null) {
			System.out.print(current.data + "-> ");
			current = current.next;
		}
		System.out.print("NULL\n");
	}

	public Node<E> reverseIteratively(Node<E> head) {
		Node<E> prev = null;
		Node<E> current = head;

		while (current != null) {
			Node<E> next = current.next; // getting the next Node
			current.next = prev; // reverse the list
			prev = current; // prev holds the reversed list
			current = next;
		}
		return prev;
	}

	public static void main(String[] arg) {
		LinkedList<Integer> list = new LinkedList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		Node<Integer> head = list.getHead();
		System.out.println("List before reverse");
		list.display(head);
		System.out.println("\nList after reverse");
		head = list.reverseIteratively(head);
		list.display(head);
	}
}

Output

List before reverse
1-> 2-> 3-> 4-> NULL

List after reverse
4-> 3-> 2-> 1-> NULL

Create Custom Lock In Java

May 15, 2018 · One min read

Sandeep Bhardwaj

Lock.java

public class Lock {

	private boolean isLocked = false;

	public synchronized void lock() throws InterruptedException {
		while (isLocked) {
			wait();
		}
		isLocked = true;
	}

	public synchronized void unlock() {
		isLocked = false;
		notify();
	}
}

Usage

lock.lock();
try {
  // ... method body
} finally {
  lock.unlock();
}

Double Checked Locking - Singleton Pattern

May 13, 2018 · One min read

Sandeep Bhardwaj

Singleton.java

public class Singleton {
	private static volatile Singleton _instance; // volatile variable
	private Singleton(){} //private constructor

	public static Singleton getInstance() {
		if (_instance == null) {
			synchronized (Singleton.class) {
				if (_instance == null)
					_instance = new Singleton();
			}
		}
		return _instance;
	}
}

CyclicBarrier In Java

May 6, 2018 · One min read

Sandeep Bhardwaj

CyclicBarrierExample.java

import java.util.concurrent.CyclicBarrier;

public class CyclicBarrierExample {

	public static void main(String[] args) {
		CyclicBarrier barrier = new CyclicBarrier(3, new BarrierAction());

		new Thread(new Party(barrier)).start();
		new Thread(new Party(barrier)).start();
		new Thread(new Party(barrier)).start();

		try {
			// sleep to avoid BrokenBarrierException
			Thread.sleep(1000);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}

		System.out.println("\nReset the barrier....\n");
		// reset the barrier
		barrier.reset();

		new Thread(new Party(barrier)).start();
		new Thread(new Party(barrier)).start();
		new Thread(new Party(barrier)).start();
	}

}

BarrierAction.java

public class BarrierAction implements Runnable {

	@Override
	public void run() {
		System.out.println("Barrier Action Executes !!!");
	}

}

Party.java

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;

public class Party implements Runnable {
	CyclicBarrier barrier;

	public Party(CyclicBarrier barrier) {
		this.barrier = barrier;
	}

	@Override
	public void run() {
		try {
			System.out.println(Thread.currentThread().getName() + " waiting at barrier.");
			this.barrier.await();
		} catch (InterruptedException | BrokenBarrierException e) {
			e.printStackTrace();
		}
	}

}

Output

Thread-2 waiting at barrier.
Thread-1 waiting at barrier.
Thread-0 waiting at barrier.
Barrier Action Executes !!!

Reset the barrier....

Thread-3 waiting at barrier.
Thread-4 waiting at barrier.
Thread-5 waiting at barrier.
Barrier Action Executes !!!

Semaphore In Java

April 3, 2017 · One min read

Sandeep Bhardwaj

SemaphoreExample.java

import java.util.concurrent.Semaphore;

public class SemaphoreExample {

	public static void main(String[] args) {
		Semaphore semaphore = new Semaphore(2);

		new Thread(new Task(semaphore)).start();
		new Thread(new Task(semaphore)).start();
		new Thread(new Task(semaphore)).start();
		new Thread(new Task(semaphore)).start();
	}

}

class Task implements Runnable {

	Semaphore semaphore;

	public Task(Semaphore semaphore) {
		this.semaphore = semaphore;
	}

	@Override
	public void run() {
		try {
			semaphore.acquire();
			System.out.println(Thread.currentThread().getName() + " acquired");

			Thread.sleep(2000);
		} catch (InterruptedException e) {
			e.printStackTrace();
		} finally {
			semaphore.release();
			System.out.println(Thread.currentThread().getName() + " released");
		}
	}
}

Output

Thread-0 acquired
Thread-1 acquired
Thread-1 released
Thread-0 released
Thread-2 acquired
Thread-3 acquired
Thread-2 released
Thread-3 released

Create Custom ThreadPool In Java

April 2, 2017 · 2 min read

Sandeep Bhardwaj

ThreadPool.java

Custom ThreadPool class with using the LinkedBlockingQueue for holding the incoming threads.

import java.util.concurrent.LinkedBlockingQueue;

public class ThreadPool
{
	volatile boolean isRunning;
	private LinkedBlockingQueue<Runnable> blockingQueue;
	private WorkerThread[] workerThreads;

	public ThreadPool(int poolSize)
	{
		blockingQueue = new LinkedBlockingQueue<>(4);
		workerThreads = new WorkerThread[poolSize];

		// create worker threads
		for (int i = 0; i < poolSize; i++)
		{
			workerThreads[i] = new WorkerThread(i + "", blockingQueue);
		}

		// start all threads
		for (WorkerThread workerThread : workerThreads)
		{
			workerThread.start();
		}
	}

	public void execute(Runnable task)
	{
		synchronized (blockingQueue)
		{

			while (blockingQueue.size() == 4)
			{
				try
				{
					blockingQueue.wait();
				} catch (InterruptedException e)
				{
					System.out.println("An error occurred while queue is waiting: " + e.getMessage());
				}
			}

			blockingQueue.add(task);

			// notify all worker threads waiting for new task
			blockingQueue.notifyAll();
		}
	}
}

WorkerThread.java

import java.util.concurrent.LinkedBlockingQueue;

public class WorkerThread extends Thread
{
	private LinkedBlockingQueue<Runnable> queue;

	public WorkerThread(String name, LinkedBlockingQueue<Runnable> queue)
	{
		super(name);
		this.queue = queue;
	}

	@Override
	public void run()
	{

		while (true)
		{
			synchronized (queue)
			{
				while (queue.isEmpty())
				{
					try
					{
						queue.wait();
					} catch (InterruptedException e)
					{
						System.out.println("An error occurred while queue is waiting: " + e.getMessage());
					}
				}

				try
				{
					Runnable runnable = this.queue.poll();
					System.out.println(
							"worker " + Thread.currentThread().getName() + " executing thread " + runnable.toString());
					runnable.run();
					Thread.sleep(1000);

					// notify threads waiting to put task in queue
					queue.notifyAll();
				} catch (InterruptedException e)
				{
					e.printStackTrace();
				}
			}
		}
	}

}

ThreadPoolTester.java

public class ThreadPoolTester
{

	public static void main(String[] args)
	{
		ThreadPool pool = new ThreadPool(2);

		for (int i = 0; i < 10; i++)
		{
			pool.execute(new Task(i + ""));
		}
	}

}

class Task implements Runnable
{
	String name;

	public Task(String name)
	{
		this.name = name;
	}

	@Override
	public void run()
	{
		System.out.println("Task " + this.name + " is running");
	}

	@Override
	public String toString()
	{
		return this.name;
	}
}

Output

worker 1 executing thread 0
Task 0 is running
worker 1 executing thread 1
Task 1 is running
worker 0 executing thread 2
Task 2 is running
worker 0 executing thread 3
Task 3 is running
worker 0 executing thread 4
Task 4 is running
worker 1 executing thread 5
Task 5 is running
worker 0 executing thread 6
Task 6 is running
worker 0 executing thread 7
Task 7 is running
worker 1 executing thread 8
Task 8 is running
worker 1 executing thread 9
Task 9 is running