Skip to main content

Binary Search

· 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

· 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

· 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

· 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

· 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

· 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

· 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

· 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

· 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

· 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