Coding Questions - Neethahiremath/Wiki GitHub Wiki
https://techinterviewhandbook.org/best-practice-questions/
linked list:
https://afteracademy.com/blog/types-of-linked-list-and-operation-on-linked-list
knights-tour-problem: https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/
find missing number:
https://www.geeksforgeeks.org/find-the-missing-number/
class GFG{
// getMissingNo function for
// finding missing number
static int getMissingNo(int a[], int n)
{
int n_elements_sum = n * (n + 1) / 2;
int sum = 0;
for(int i = 0; i < n - 1; i++)
sum += a[i];
return n_elements_sum - sum;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 2, 4, 5, 6 };
int n = a.length + 1;
int miss = getMissingNo(a, n);
System.out.print(miss);
}
}
find the leader in the array
class LeadersInArray
{
/* Java Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
int max_from_right = arr[size-1];
/* Rightmost element is always leader */
System.out.print(max_from_right + " ");
for (int i = size-2; i >= 0; i--)
{
if (max_from_right < arr[i])
{
max_from_right = arr[i];
System.out.print(max_from_right + " ");
}
}
}
/* Driver program to test above functions */
public static void main(String[] args)
{
LeadersInArray lead = new LeadersInArray();
int arr[] = new int[]{16, 17, 4, 3, 5, 2};
int n = arr.length;
lead.printLeaders(arr, n);
}
}
Next greater element:
class NextGreaterElement {
static int arr[] = { 11, 13, 21, 3 };
/* prints element and NGE pair for all
elements of arr[] of size n */
public static void printNGE()
{
Stack<Integer> s = new Stack<>();
int nge[] = new int[arr.length];
// iterate for rest of the elements
for (int i = arr.length - 1; i >= 0; i--)
{
/* if stack is not empty, then
pop an element from stack.
If the popped element is smaller
than next, then
a) print the pair
b) keep popping while elements are
smaller and stack is not empty */
if (!s.empty())
{
while (!s.empty()
&& s.peek() <= arr[i])
{
s.pop();
}
}
nge[i] = s.empty() ? -1 : s.peek();
s.push(arr[i]);
}
for (int i = 0; i < arr.length; i++)
System.out.println(arr[i] +
" --> " + nge[i]);
}
/* Driver Code */
public static void main(String[] args)
{
// NextGreaterElement nge = new
// NextGreaterElement();
printNGE();
}
stock span problem :
static void calculateSpan(int A[],
int n, int ans[])
{
// Span value of first element is always 1
ans[0] = 1;
// Calculate span values for rest of the elements
for (int i = 1; i < n; i++) {
int counter = 1;
while ((i - counter) >= 0 && A[i] >= A[i - counter]) {
counter += ans[i - counter];
}
ans[i] = counter;
}
}
https://www.geeksforgeeks.org/the-stock-span-problem/
Reverse a linked List:
Node reverse(Node node)
{
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
reverse linked list with K
Node reverse(Node head, int k)
{
if(head == null)
return null;
Node current = head;
Node next = null;
Node prev = null;
int count = 0;
/* Reverse first k nodes of linked list */
while (count < k && current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from
current. And make rest of the list as next of
first node */
if (next != null)
head.next = reverse(next, k);
// prev is now head of input list
return prev;
}
https://www.geeksforgeeks.org/iterative-tower-of-hanoi/
public static void main(String[] args) {
char t1='t';
char t2='u';
char t3='v';
System.out.println(count(5,t1, t2,t3));
}
public static int count(int n,char t1,char t2,char t3){
if(n==1){
return 1;
}
//move from t1 to t3 with t2 as auxillary
int step1=count(n-1,t1,t3,t2);
int step2=1;
//move from t3 to t2 with t1 as auxillary
int step3=count(n-1,t3,t2,t1);
return step1+step2+step3;
}
Left view of node:
private static void printLeftView(Node root)
{
if (root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
// number of nodes at current level
int n = queue.size();
// Traverse all nodes of current level
for (int i = 1; i <= n; i++) {
Node temp = queue.poll();
// Print the left most element at
// the level
if (i == 1)
System.out.print(temp.data + " ");
// Add left node to queue
if (temp.left != null)
queue.add(temp.left);
// Add right node to queue
if (temp.right != null)
queue.add(temp.right);
}
}
}
right view binary tree
void rightView(Node root)
{
if (root == null) {
return;
}
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
// get number of nodes for each level
int n = q.size();
// traverse all the nodes of the current level
for (int i = 0; i < n; i++) {
Node curr = q.poll();
// print the last node of each level
if (i == n - 1) {
System.out.print(curr.data);
System.out.print(" ");
}
// if left child is not null add it into
// the
// queue
if (curr.left != null) {
q.add(curr.left);
}
// if right child is not null add it into
// the
// queue
if (curr.right != null) {
q.add(curr.right);
}
}
}
}
top view of binary search https://www.techiedelight.com/print-top-view-binary-tree/
class BinaryTree {
Node root;
public BinaryTree() { root = null; }
// function should print the topView of
// the binary tree
private void TopView(Node root)
{
class QueueObj {
Node node;
int hd;
QueueObj(Node node, int hd)
{
this.node = node;
this.hd = hd;
}
}
Queue<QueueObj> q = new LinkedList<QueueObj>();
Map<Integer, Node> topViewMap
= new TreeMap<Integer, Node>();
if (root == null) {
return;
}
else {
q.add(new QueueObj(root, 0));
}
System.out.println(
"The top view of the tree is : ");
// count function returns 1 if the container
// contains an element whose key is equivalent
// to hd, or returns zero otherwise.
while (!q.isEmpty()) {
QueueObj tmpNode = q.poll();
if (!topViewMap.containsKey(tmpNode.hd)) {
topViewMap.put(tmpNode.hd, tmpNode.node);
}
if (tmpNode.node.left != null) {
q.add(new QueueObj(tmpNode.node.left,
tmpNode.hd - 1));
}
if (tmpNode.node.right != null) {
q.add(new QueueObj(tmpNode.node.right,
tmpNode.hd + 1));
}
}
for (Entry<Integer, Node> entry :
topViewMap.entrySet()) {
System.out.print(entry.getValue().data);
}
}
Bottom view of tree:
public void bottomView()
{
if (root == null)
return;
// Initialize a variable 'hd' with 0 for the root element.
int hd = 0;
// TreeMap which stores key value pair sorted on key value
Map<Integer, Integer> map = new TreeMap<>();
// Queue to store tree nodes in level order traversal
Queue<Node> queue = new LinkedList<Node>();
// Assign initialized horizontal distance value to root
// node and add it to the queue.
root.hd = hd;
queue.add(root);
// Loop until the queue is empty (standard level order loop)
while (!queue.isEmpty())
{
Node temp = queue.remove();
// Extract the horizontal distance value from the
// dequeued tree node.
hd = temp.hd;
// Put the dequeued tree node to TreeMap having key
// as horizontal distance. Every time we find a node
// having same horizontal distance we need to replace
// the data in the map.
map.put(hd, temp.data);
// If the dequeued node has a left child add it to the
// queue with a horizontal distance hd-1.
if (temp.left != null)
{
temp.left.hd = hd-1;
queue.add(temp.left);
}
// If the dequeued node has a right child add it to the
// queue with a horizontal distance hd+1.
if (temp.right != null)
{
temp.right.hd = hd+1;
queue.add(temp.right);
}
}
Anagram of each other
class GFG{
static int NO_OF_CHARS = 256;
// function to check if two strings
// are anagrams of each other
static boolean areAnagram(char[] str1,
char[] str2)
{
// Create a count array and initialize
// all values as 0
int[] count = new int[NO_OF_CHARS];
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for(i = 0; i < str1.length; i++)
{
count[str1[i] - 'a']++;
count[str2[i] - 'a']--;
}
// If both strings are of different
// length. Removing this condition
// will make the program fail for
// strings like "aaca" and "aca"
if (str1.length != str2.length)
return false;
// See if there is any non-zero
// value in count array
for(i = 0; i < NO_OF_CHARS; i++)
if (count[i] != 0)
{
return false;
}
return true;
}
implement stack using priority queue:
public class StackWithPriorityQueue {
class Node{
private Integer id;
private int value;
public Node(int id,int value){
this.id=id;
this.value=value;
}
}
PriorityQueue<Node> pq;
int count;
public StackWithPriorityQueue(int initialCapacity,int count){
pq=new PriorityQueue<Node>(initialCapacity,(c1,c2)->c1.id.compareTo(c2.id));;
this.count=count;
}
public void push(int ele){
count--;
pq.add(new Node(count,ele));
}
int pop(){
if(pq.isEmpty()){
System.out.println("Stack is empty");
return -1;
}
Node node=pq.poll();
return node.value;
}
int peek(){
Node node=pq.peek();
return node.value;
}
void printPQ(){
pq.stream().forEach(
p->
System.out.println(p.id+" "+p.value)
);
}
public static void main(String[] args) {
System.out.println("=====================");
StackWithPriorityQueue stack=new StackWithPriorityQueue(10,6);
stack.push(10);
stack.push(20);
stack.push(110);
stack.push(12);
stack.push(11);
stack.push(21);
stack.printPQ();
System.out.println("===============");
System.out.println(stack.peek());
stack.pop();
//stack.pop();
System.out.println(stack.peek());
System.out.println("================");
PriorityQueue<Integer> pqs=new PriorityQueue<>();
pqs.offer(10);
pqs.offer(20);
pqs.offer(5);
System.out.println(pqs);
System.out.println(pqs.peek());
System.out.println(pqs.poll());
System.out.println(pqs.peek());
PriorityQueue<Integer> pqs=new PriorityQueue<>(5,(c1,c2)-> -c1.compareTo(c2));
pqs.offer(10);
pqs.offer(5);
pqs.offer(7);
pqs.offer(3);
pqs.offer(2);
for(int i=0;i<5;i++){
System.out.println(pqs.poll());
}
}
}
Trains arrival = { 2.00, 2.10, 3.00, 3.20, 3.50, 5.00 } Trains departure = { 2.30, 3.40, 3.20, 4.30, 4.00, 5.20 } Find minimum platforms needed to avoid delay in the train arrival
public class test {
public static void main(String[] args) {
Double[] arrival = new Double[] {2.00, 2.10, 3.00, 3.20, 3.50, 5.00};
Double[] dep = new Double[] {2.30, 3.40, 3.20, 4.30, 4.00, 5.20};
int i = 0, j = 0;
int min = 0;
int minP = 0;
Arrays.sort(arrival);
Arrays.sort(dep);
while (i < arrival.length) {
if (arrival[i] < dep[j]) {
min++;
i++;
minP = Integer.max(min, minP);
} else {
min--;
j++;
}
}
System.out.print(minP);
}
}
https://www.techiedelight.com/find-index-0-replaced-get-maximum-length-sequence-of-continuous-ones/ code:
int[] arr = new int[]{0, 0, 1, 0, 1, 1, 1, 0, 1, 1 };
int counter=0,maxCount=0;
int c =-1,p=-1;
for(int i=0;i<arr.length;i++)
{
if(arr[i]==1)
{
counter++;
}
else{
counter = i-p;
p=i;
}
if(counter>maxCount)
{
maxCount = counter;
c = p;
}
}
System.out.print(c);
height of tree with queue :
https://makeinjava.com/find-height-binary-tree-bfs-level-order-traversal-example/
package org.learn.Question;
import java.util.LinkedList;
import java.util.Queue;
public class HeightOfTree {
public static int heightOfTree(Node root) {
if (root == null) {
System.out.println("Tree is empty");
return -1;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
// level delimiter
queue.offer(null);
int height = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
if (null == node) {
if (!queue.isEmpty()) {
// level delimiter
queue.offer(null);
}
height++;
} else {
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return height;
}
}
BFS graph:
https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
DFS graph:
https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
There are n villages, and k schools. village is said to be educated if it has a school or connected to school with less than or equal to distance of 2
print all uneducated villages that are not connected
package com.interview;
import java.util.*;
public class IlleterateVillage {
private static LinkedList<Integer> adj[];
private static int N;
public IlleterateVillage(int N) {
adj = new LinkedList[N];
for (int i = 0; i < N; i++) {
adj[i] = new LinkedList<>();
}
this.N = N;
}
private static void addAdjects(Integer src, Integer dest) {
adj[src].push(dest);
adj[dest].push(src);
}
public static void main(String[] args) {
IlleterateVillage illeterateVillage = new IlleterateVillage(7);
addAdjects(1, 3);
addAdjects(3, 4);
addAdjects(4, 5);
addAdjects(2, 4);
addAdjects(5, 6);
final int D = 2;
int[] literate = {1, 2};
for (Integer i : literate) {
bfs(i, D);
}
for (int i = 1; i <= N; i++) {
if (!visitedEle.contains(i)) {
System.out.print(i + " ");
}
}
}
private static Set<Integer> visitedEle = new HashSet<>();
private static void bfs(int src, int D) {
boolean[] visited = new boolean[N];
visited[src] = true;
visitedEle.add(src);
Queue<Integer> queue = new LinkedList<>();
queue.add(src);
int counter = 0;
while (!queue.isEmpty()) {
if (counter == D) {
break;
}
int ele = queue.poll();
Iterator<Integer> itr = adj[ele].listIterator();
while (itr.hasNext()) {
int value = itr.next();
if (!visited[value]) {
visited[value] = true;
visitedEle.add(value);
queue.add(value);
}
}
counter++;
}
}
}
given list of meeting rooms Find the minimum meeting rooms required for meeting timing given below
public class MeetingRoomOrTrainDepartureProblem {
public static void main(String[] args) {
// maximum meeting rooms required or maximum platform required for trains
Integer[][] arr = {{900, 930}, {700, 900}, {800, 1000}, {940, 1000}, {1010, 1030}};
int[] startArr = new int[arr.length];
int[] endArr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
startArr[i] = arr[i][0];
endArr[i] = arr[i][1];
}
Arrays.sort(startArr);
Arrays.sort(endArr);
System.out.print(Arrays.toString(startArr));
System.out.print(Arrays.toString(endArr));
int i = 0;
int j = 0;
int count = 0;
int max = 0;
while (i < startArr.length) {
if (startArr[i] < endArr[j]) {
count++;
max = Math.max(max, count);
i++;
} else {
count--;
j++;
}
}
System.out.print(max);
}
}
given list of meeting rooms find the max meetings that can be attended in a single meeting room
public class MaxMeetingInRoomProblem {
// maximum meeting that can be conduct in a single room or maximum meetings you can attend or max trains come to plateform without collision
public static void main(String[] args) {
Integer[][] arr = {{900, 930}, {700, 900}, {800, 1000}, {940, 1000}, {1010, 1030}};
Arrays.sort(arr, Comparator.comparingInt(a -> a[1]));
for (Integer[] val : arr) {
System.out.print(Arrays.toString(val));
}
int count = 1;
int lastTime = arr[0][1];
for (int i = 1; i < arr.length; i++) {
if (arr[i][0] >= lastTime) {
count++;
lastTime = arr[i][1];
}
}
System.out.print(count);
}
}
write a code for consumer and producer problem:
public class ProducerAndConsumerProblem {
LinkedList<Integer> store = new LinkedList<>();
Integer capacity = 2;
int val = 0;
void producer() throws InterruptedException {
while (true) {
synchronized (this) {
while (store.size() == capacity) wait();
store.add(val++);
System.out.print("producer running" + val);
notify();
sleep(500);
}
}
}
void consumer() throws InterruptedException {
while (true) {
synchronized (this) {
while (store.size() == 0) {
wait();
}
Integer val = store.removeFirst();
System.out.printf("consumer running" + val);
notify();
sleep(500);
}
}
}
public static void main(String[] args) throws InterruptedException {
ProducerAndConsumerProblem obj = new ProducerAndConsumerProblem();
Thread thread1 =
new Thread(
() -> {
try {
obj.producer();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
Thread thread2 =
new Thread(
() -> {
try {
obj.consumer();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
thread1.start();
thread2.start();
thread1.join();
thread2.join();
}
}
linked list operations for -> singly linked list adding a node deleting a node searching a node
public class LinkedListOperations {
Node head;
static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
void pushBeginning(int val) {
Node node = new Node(val);
node.next = head;
head = node;
}
void pushEnd(int val) {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
Node node = new Node(val);
temp.next = node;
}
void delete(int val) {
Node temp = head;
if (temp.data == val) {
head = temp.next;
} else {
while (temp.next != null) {
if (temp.next.data == val) {
break;
}
temp = temp.next;
}
temp.next = temp.next.next;
}
}
void search(int val)
{
boolean flag = false;
Node temp = head;
while (temp!=null)
{
if(temp.data==val)
{
flag = true;
break;
}
temp = temp.next;
}
if(flag)
System.out.println("Element is present in the list at the position : " + val);
else
System.out.println("Element is not present in the list");
}
void print() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
public static void main(String[] args) {
LinkedListOperations linkedList = new LinkedListOperations();
linkedList.pushBeginning(9);
linkedList.pushBeginning(8);
linkedList.pushBeginning(6);
linkedList.pushEnd(9);
linkedList.pushEnd(8);
linkedList.pushEnd(6);
linkedList.search(6);
System.out.printf("*********");
linkedList.print();
System.out.printf("*********");
linkedList.delete(8);
linkedList.print();
}
https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/
merge k sorted list
public class MergeKLinkedList {
public static void printList(Node node) {
while (node != null) {
System.out.print(" "+node.data);
node = node.next;
}
}
// The main function to merge given `k` sorted linked lists.
// It takes array `lists` of size `k` and generates the sorted output
public static Node mergeKLists(Node[] lists) {
PriorityQueue<Node> queues = new PriorityQueue<>(Comparator.comparingInt(a -> a.data));
queues.addAll(Arrays.asList(lists).subList(0, lists.length));
Node head = null, last = null;
while (!queues.isEmpty()) {
Node temp = queues.poll();
if (head == null) {
head = temp;
last = temp;
} else {
last.next = temp;
last = temp;
}
if (temp.next != null) {
queues.add(temp.next);
last.next = null;
}
}
return head;
}
public static void main(String[] args) {
int k = 3; // total number of linked lists
// an array to store the head nodes of the linked lists
Node[] lists = new Node[k];
lists[0] = new Node(1);
lists[0].next = new Node(5);
lists[0].next.next = new Node(7);
lists[1] = new Node(2);
lists[1].next = new Node(3);
lists[1].next.next = new Node(6);
lists[1].next.next.next = new Node(9);
lists[2] = new Node(4);
lists[2].next = new Node(8);
lists[2].next.next = new Node(10);
// Merge all lists into one
Node head = mergeKLists(lists);
printList(head);
}
buy and sell stock problem:
public class BestTimeToSellAndBuy {
public static void main(String[] args) {
Integer[] prices = new Integer[] {10, 15, 3, 12, 2, 9};
int min = Integer.MAX_VALUE;
int sell = 0;
int max = 0;
/*
for (int i = 0; i < prices.length - 1; i++) {
if (prices[i] < prices[i + 1]) min = Math.min(min, prices[i]);
if (prices[i + 1] > min) sell = Math.max(sell, prices[i + 1]);
}
System.out.print(Math.max(sell - min, 0));*/
/*for (Integer price : prices) {
if (price < min)
min = price;
else if (price - min > max) {
max = price - min;
}
}*/
for(int i =0;i<prices.length-1;i++)
{
min = Math.min(min,prices[i]);
max = Math.max(max, prices[i] - min);
}
System.out.print(max);
}
}
contain duplicates:
public class ContainDuplicate {
public static void main(String[] args) {
Integer[] array = new Integer[] {1, 3, 4, 2, 5};
boolean flag = false;
Set<Integer> store = new HashSet<>();
for (Integer integer : array) {
if (!store.contains(integer))
store.add(integer);
else {
flag = true;
break;
}
}
if (flag) System.out.print("Duplicates are present");
else {
System.out.print("Duplicates are not present");
}
}
fizz buzz problem
public class FizzBuzzProblem {
public static void main(String[] args) {
for (int i = 1; i <= 100; i++) {
if (i % 3 == 0 && i % 5 == 0) {
System.out.printf("FizzBuzz ");
} else if (i % 3 == 0) {
System.out.printf("Fizz ");
} else if (i % 5 == 0) {
System.out.printf("Buzz ");
} else {
System.out.print(i + " ");
}
}
}
}
anagram problem:
public class AnagramProblem {
public static void main(String[] args) {
String a = "anagram";
String b = "naram";
if (a.length() != b.length()) {
System.out.printf("not anagrams");
} else {
int[] array = new int[256];
boolean flag = true;
for (int i = 0; i < a.length(); i++) {
int ascii = a.charAt(i);
int as = b.charAt(i);
array[ascii] = array[ascii] + 1;
array[as] = array[as] - 1;
}
for (int i = 0; i < 256; i++) {
if (array[i] != 0) {
flag = false;
break;
}
}
if (flag) System.out.printf("anagrams");
}
}
}
find loop in linkedList
public class FindLinkedListLoop {
static Node head;
public static void push(int new_data) {
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
public static boolean findLoop() {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
if (slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}
public static void main(String[] args) {
// 1->2->3->4->5->6
push(3);
push(1);
push(3);
head.next.next.next = head.next;
Set<Node> store = new HashSet<>();
boolean flag = false;
Node temp = head;
while (temp != null) {
if (store.contains(temp)) {
flag = true;
break;
} else store.add(temp);
}
System.out.print(flag);
boolean loop = findLoop();
System.out.print(loop);
}
Given an m x n matrix, 0 for empty, 1 for healthy and 2 for unhealthy unhealthy makes healthy node unhealthy what is the minimum time required to make all people unhealthy. if cant be made return -1.
static class Pair{
int x,y;
public Pair(int x,int y){
this.x=x;
this.y=y;
}
}
private static int timeToConvertToUnhealthyMatrix(int[][] matrix) {
int time=0,next=0,count=0;
Queue<Pair> queue=new LinkedList<>();
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(matrix[i][j]==2){
queue.add(new Pair(i,j));
count++;
}
}
}
while(!queue.isEmpty()){
for(int i=0;i<count;i++){
Pair pair=queue.poll();
int x=pair.x;
int y=pair.y;
if(isValid(x+1,y,matrix) && matrix[x+1][y]==1){
matrix[x+1][y]=2;
queue.add(new Pair(x+1,y));
next++;
}
if(isValid(x-1,y,matrix) && matrix[x-1][y]==1){
matrix[x-1][y]=2;
queue.add(new Pair(x-1,y));
next++;
}
if(isValid(x,y-1,matrix) && matrix[x][y-1]==1){
matrix[x][y-1]=2;
queue.add(new Pair(x,y-1));
next++;
}
if(isValid(x,y+1,matrix) && matrix[x][y+1]==1){
matrix[x][y+1]=2;
queue.add(new Pair(x,y+1));
next++;
}
}
if(next==0 )
break;
count=next;
next=0;
time++;
}
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[i].length;j++){
if(matrix[i][j]==1)
return -1;
}
}
return time;
}
private static boolean isValid(int x, int y, int[][] matrix) {
if(x<0 || y<0 || x>=matrix.length|| y>=matrix[0].length|| matrix[x][y]==0)
return false;
return true;
}
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once.
Input: board = "A","B","C","E"], ["S","F","C","S"], ["A","D","E","E" word = "ABCCED" Output: true
public class FindIfWordExistInGivenMatrixOfCharacters {
public static void main(String[] args) {
String[][] board={{
"A","B","C","E"
},{"S","F","C","S"},{"A","D","E","E"}};
String word="ABCCED";
System.out.println(isWordPresent(board,word));
}
private static boolean isWordPresent(String[][] board, String word) {
boolean isPresent=false;
boolean[][] visited=new boolean[board.length][board[0].length];
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
if(board[i][j].equals(word.substring(0,1))){
isPresent=isGivenWord(board,word,visited,i,j,0);
if(!isPresent)
visited=new boolean[board.length][board[0].length];
else
return isPresent;
}
}
}
return isPresent;
}
private static boolean isGivenWord(String[][] board, String word,boolean[][] visited,int i,int j,int index) {
if(index==word.length())
return true;
if(i<0||i>board.length-1|| j<0||j>board[i].length-1|| visited[i][j])
return false;
if(board[i][j].equals(word.substring(index,index+1))) {
visited[i][j]=true;
boolean found = isGivenWord(board, word, visited, i + 1, j, index + 1)|
isGivenWord(board, word, visited, i - 1, j, index + 1) |
isGivenWord(board, word, visited, i, j - 1, index + 1)|
isGivenWord(board, word, visited, i, j + 1, index + 1);
visited[i][j] = false;
return found;
}else{
return false;
}
}
}
car pooling https://leetcode.com/problems/car-pooling/
public class Carpooling {
public static void main(String[] args) {
int[][] trips = {{2,1,5},{3,3,7}};
int capacity = 5;
int[] line=new int[1001];
for(int i=0;i<trips.length;i++){
line[trips[i][1]]+=trips[i][0];
line[trips[i][2]]-=trips[i][0];
}
boolean isPossible=true;
for(int i=0;i<1001;i++){
capacity-=line[i];
if(capacity<0){
isPossible=false;
break;
}
}
System.out.println(isPossible);
}
}
generate permutations for a given string
public static void main(String[] args) {
permute("ABC","");
}
static void permute(String input,String answer){
if(input.length()==0){
System.out.println(answer+" ");
return;
}
for(int i=0;i<input.length();i++){
char ch=input.charAt(i);
String leftSubStr=input.substring(0,i);
String rightSubStr=input.substring(i+1);
String rest=leftSubStr+rightSubStr;
permute(rest,answer+ch);
}
}
check if list is palindrome
static Node slow,fast,secondHalf;
static boolean isPalindromeCheckUsingReversingHalfList(){
slow=head;
fast=head;
Node prevSlow=head;
Node midNode=null;
boolean res=true;
if(head!=null && head.next!=null){
while(fast!=null && fast.next!=null){
prevSlow=slow;
slow=slow.next;
fast=fast.next.next;
}
if(fast!=null){
midNode=slow;
slow=slow.next;
}
secondHalf=slow;
prevSlow.next=null;
reverse();
res=compareLists(head,secondHalf);
reverse();
if(midNode!=null){
prevSlow.next=midNode;
midNode.next=secondHalf;
}else{
prevSlow.next=secondHalf;
}
}
return res;
}
static void reverse(){
Node prev=null;
Node current=secondHalf;
Node next;
while(current!=null){
next=current.next;
current.next=prev;
prev=current;
current=next;
}
secondHalf=prev;
}
static boolean compareLists(Node head1,Node head2){
Node temp1=head1;
Node temp2=head2;
while(temp1!=null && temp2!=null){
if(temp1.data==temp2.data){
temp1=temp1.next;
temp2=temp2.next;
}else return false;
}
if(temp1==null && temp2==null){
return true;
}
return false;
}
isMirror image tree
static boolean isMirror(Node root){
if(root==null)
return true;
return isMirror(root.left,root.right);
}
static boolean isMirror(Node left,Node right ){
if(left==null && right==null){
return true;
}
if(left==null || right==null)
return false;
return (left.data==right.data) &&
isMirror(left.left,right.right) &&
isMirror(left.right,right.left);
}
same tree
static boolean sameTree(Node root,Node root1){
if(root==null && root1==null){
return true;
}
if((root==null && root1!=null)
|| (root!=null && root1==null)
|| (root.data!=root1.data)){
return false;
}
return sameTree(root.left,root1.left) && sameTree(root.right,root1.right);
}
left view of tree recursion
static void leftView(Node root,int level){
if(root==null){
return;
}
if(maxLevel<level) {
maxLevel++;
System.out.print(root.data + " ");
}
leftView(root.left,level+1);
leftView(root.right,level+1);
}
common prefix:
public class CommonPrefix {
public static void main(String... args){
String[] strs = {"flower","flow"};//,"aflight"};
System.out.println(commonPrefix(strs));
}
public static String commonPrefix(String[] strs){
TreeMap<Integer,Character> lookup=new TreeMap<>();
// {"flower","flow","flight"}
int commonPrefixLen=Integer.MAX_VALUE;
for(int j=0;j< strs.length;j++){//String str:strs){
int samePrefix=-1;
char[] strchar=strs[j].toCharArray();
for(int i=0;i<strchar.length;i++){
if(lookup.containsKey(i)){
if(lookup.get(i)==strchar[i]){
samePrefix=i;
}else{
break;
}
}else{
lookup.put(i,strchar[i]);
}
}
if(j!=0)
commonPrefixLen=Integer.min(commonPrefixLen,samePrefix);
}
if(commonPrefixLen==-1){
return "";
}else{
return strs[0].substring(0,commonPrefixLen+1);
}
}
}
longest consecutive numbers
Set<Integer> S= IntStream.of(arr).boxed().collect(Collectors.toSet());
System.out.println(S);
int maxLen = 0;
for(int e:arr){
if(!S.contains(e-1)){
int len=1;
while(S.contains(e+len)){
len++;
}
maxLen=Integer.max(len,maxLen);
}
}
return maxLen;
}
longest sub array with equal no of 1s and 0s
class LargestSubArray1 {
// Returns largest subarray with
// equal number of 0s and 1s
int maxLen(int arr[], int n)
{
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM
= new HashMap<Integer, Integer>();
// Initialize sum of elements
int sum = 0;
// Initialize result
int max_len = 0;
int ending_index = -1;
int start_index = 0;
for (int i = 0; i < n; i++) {
arr[i] = (arr[i] == 0) ? -1 : 1;
}
// Traverse through the given array
for (int i = 0; i < n; i++) {
// Add current element to sum
sum += arr[i];
// To handle sum=0 at last index
if (sum == 0) {
max_len = i + 1;
ending_index = i;
}
// If this sum is seen before,
// then update max_len if required
if (hM.containsKey(sum)) {
if (max_len < i - hM.get(sum)) {
max_len = i - hM.get(sum);
ending_index = i;
}
}
else // Else put this sum in hash table
hM.put(sum, i);
}
for (int i = 0; i < n; i++) {
arr[i] = (arr[i] == -1) ? 0 : 1;
}
int end = ending_index - max_len + 1;
System.out.println(end + " to " + ending_index);
return max_len;
}
/* Driver program to test the above functions */
public static void main(String[] args)
{
LargestSubArray1 sub = new LargestSubArray1();
int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
int n = arr.length;
sub.maxLen(arr, n);
}
}
minimum no of jumps to reach end of the array
private static int minJumps(int[] arr, int n)
{
// jumps[n-1] will hold the
int jumps[] = new int[n];
// result
int i, j;
// if first element is 0,
if (n == 0 || arr[0] == 0)
return Integer.MAX_VALUE;
// end cannot be reached
jumps[0] = 0;
// Find the minimum number of jumps to reach arr[i]
// from arr[0], and assign this value to jumps[i]
for (i = 1; i < n; i++) {
jumps[i] = Integer.MAX_VALUE;
for (j = 0; j < i; j++) {
if (i <= j + arr[j]
&& jumps[j]
!= Integer.MAX_VALUE) {
jumps[i] = Math.min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n - 1];
}
longest sub array with given sum k
static int lenOfLongSubarr(int[] arr, int n, int k)
{
// HashMap to store (sum, index) tuples
HashMap<Integer, Integer> map = new HashMap<>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'map'
if (!map.containsKey(sum)) {
map.put(sum, i);
}
// check if 'sum-k' is present in 'map'
// or not
if (map.containsKey(sum - k)) {
// update maxLength
if (maxLen < (i - map.get(sum - k)))
maxLen = i - map.get(sum - k);
}
}
return maxLen;
}
Next greater number https://www.geeksforgeeks.org/find-next-greater-number-set-digits/
public static void main(String[] args) {
String word="";
System.out.println(findNextWord(word.toCharArray(),word.length()));
}
private static String findNextWord(char[] arr,int n){
int i;
for(i=n-1;i>0;i--){
if(arr[i]>arr[i-1]){
break;
}
}
if(i<=0){
return "No Answer";
}else{
char x=arr[i-1];
int min=i;
for(int j=i+1;j<n;j++){
if(arr[j]>x && arr[j]<arr[min]){
min=j;
}
}
char ch=arr[i-1];
arr[i-1]=arr[min];
arr[min]=ch;
Arrays.sort(arr,i,n);
String nextString=new String(arr);
return nextString;
}
}
Mountain Array
public class HillInArray {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 1};
int i=0;
while(i<arr.length-1 && arr[i]<arr[i+1]){
i++;
}
int j=arr.length-1;
while(j>0 && arr[j]<arr[j-1]){
j--;
}
if(i==j){
System.out.println(true);
} else {
System.out.println(false);
}
}
}