Interview Preparation Kit
some company specified questions in various concepts are discussed below
AMAZON
Amazon(Q)-Largest subarray with equal number of 0s and 1s
Given an array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Expected time complexity is O(n).
Examples:
Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)
Input: arr[] = {1, 1, 1, 1}
Output: No such subarray
Input: arr[] = {0, 0, 1, 1, 0}
Output: 0 to 3 Or 1 to 4
import java.util.*;
import java.lang.*;
public class Main
{
static void findIndex(int[] arr,int n)
{
int max=-1,startIndex=0,endIndex=0,sum=0;
for(int index1=0;index1<n-1;index1++)
{
if(arr[index1]==0)
{
sum=-1;
}
else
{
sum=1;
}
for(int index2=index1+1;index2<n;index2++)
{
if(arr[index2]==0)
{
sum+=-1;
}
else
{
sum+=1;
}
if(sum==0&&max<index2-index1+1)
{
max=index2-index1+1;
startIndex=index1;
}
}
}
endIndex=startIndex+max-1;
if(max==-1)
{
System.out.print("No such subarray");
}
else
{
System.out.print(startIndex+" to "+endIndex);
}
}
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for(int index=0;index<n;index++)
{
arr[index]=sc.nextInt();
}
findIndex(arr,n);
}
}
Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert 'str1' into 'str2'. 1.Insert 2.Remove 3.Replace All of the above operations are of equal cost.
Examples:
Input: str1 = "geek", str2 = "gesek"
Output: 1
Explanation: We can convert str1 into str2 by inserting a 's'.
Input: str1 = "cat", str2 = "cut"
Output: 1
Explanation: We can convert str1 into str2 by replacing 'a' with 'u'.
Input: str1 = "sunday", str2 = "saturday"
Output: 3
Explanation: Last three and first characters are same. We basically need to convert "un" to "atur". This can be done using below three operations. Replace 'n' with 'r', insert t, insert a Sample Input: Scan the length of string 1 Scan the length of string 2 Scan the string 1 Scan the string 2
import java.util.*;
public class Main {
public static int edit(String s1,String s2,int m, int n)
{
int[][] edit=new int[m+1][n+1];
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0)
edit[i][j]=j;
else if(j==0)
edit[i][j]=i;
else if(s1.charAt(i-1)==s2.charAt(j-1))
edit[i][j]=edit[i-1][j-1];
else
{
edit[i][j]=1+Math.min(Math.min(edit[i-1][j],edit[i][j-1]),edit[i-1][j-1]);
}
}
}
return edit[m][n];
}
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
String s1=sc.next();
String s2=sc.next();
System.out.print(edit(s1,s2,m,n));
}
}
Amazon(Q)-Sort an array in wave form
Given an unsorted array of integers, sort the array into a wave like array. An array "arr[0..n-1]" is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ....
Input: arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
Output: arr[] = {10, 5, 6, 2, 20, 3, 100,80} OR {20, 5, 10, 2, 80, 6, 100,3}
First input represents the size of an array second input is array elements(get it one by one) Third line is print the output array.
For example:
8 //array size
10 //array elements commences from here
5
6
3
2
20
100
80
10 5 6 2 20 3 100 80 //array output
import java.util.*;
public class Main
{
public static void swap(int[] arr,int a, int b)
{
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void sortWave(int[] arr,int n)
{
for(int index=0;index<n;index+=2)
{
if(index>0&&arr[index-1]>arr[index])
{
swap(arr,index,index-1);
}
if(index<=n-2&&arr[index+1]>arr[index])
{
swap(arr,index+1,index);
}
}
}
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
sortWave(arr,n);
for(int index=0;index<n;index++)
{
if(index==n-1)
System.out.print(arr[index]);
else
System.out.print(arr[index]+" ");
}
}
}
Given two sorted arrays such the arrays may have some common elements. Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can switch from one array to another array only at common elements.
Expected time complexity is O(m+n) where m is the number of elements in ar1[] and n is the number of elements in ar2[].
Examples:
Input: ar1[] = {2, 3, 7, 10, 12}, ar2[] = {1, 5, 7, 8}
Output: 35 35 is sum of 1 + 5 + 7 + 10 + 12.
We start from first element of arr2 which is 1, then we move to 5, then 7. From 7, we switch to ar1 (7 is common) and traverse 10 and 12.
import java.util.*;
public class Main
{
static int MaxSumPath(int[] arr1,int[] arr2,int m,int n)
{
int index1=0,index2=0,res=0,sum1=0,sum2=0;
while(index1<m&&index2<n)
{
if(arr1[index1]<arr2[index2])
{
sum1+=arr1[index1++];
}
else if(arr1[index1]>arr2[index2])
{
sum2+=arr2[index2++];
}
else
{
res+=Math.max(sum1,sum2);
sum1=0;
sum2=0;
while(index1<m&&index2<n&&arr1[index1]==arr2[index2])
{
res+=arr1[index1++];
index2++;
}
}
}
while(index1<m)
{
sum1+=arr1[index1++];
}
while(index2<n)
{
sum2+=arr2[index2++];
}
res+=Math.max(sum1,sum2);
return res;
}
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
String s1[]=sc.nextLine().split(" ");
String s2[]=sc.nextLine().split(" ");
int n1=s1.length;
int n2=s2.length;
int[] arr1=new int[n1];
int[] arr2=new int[n2];
for(int index=0;index<n1;index++)
{
arr1[index]=Integer.parseInt(s1[index]);
}
for(int index=0;index<n2;index++)
{
arr2[index]=Integer.parseInt(s2[index]);
}
System.out.print(MaxSumPath(arr1,arr2,arr1.length,arr2.length));
}
}
Run Length Decoding:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
int l=str.length();
StringBuilder output=new StringBuilder();
String temp="";
int index2=0,count=0,val=0;
for(int index=0;index<l;index++)
{
if(Character.isDigit(str.charAt(index)))
{
count++;
if(count==1)
index2=index-1;
temp+=str.charAt(index);
val=Integer.valueOf(temp);
continue;
}
else
{
if(val==0)
{
output.append(str.charAt(index));
}
if(val!=0)
{
for(int ctr=1;ctr<val;ctr++)
{
output.append(str.charAt(index2));
}
index--;
}
temp="";
val=0;
count=0;
}
}
if(val!=0)
{
for(int index=1;index<val;index++)
{
output.append(str.charAt(index2));
}
}
System.out.print(output);
}
}
input 1:
a2c5z4
output 1:
aaccccczzzz
input 2:
a8b12dv3n2
output 2:
aaaaaaaabbbbbbbbbbbbdvvvnn
Undo keystroke using stack:
import java.util.*;
public class Main
{
static int top=-1;
static List<Character> al=new ArrayList<>();
static class Stack
{
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(char ch)
{
al.add(ch);
top++;
}
char pop()
{
char c=al.get(top);
al.remove(top);
top--;
return c;
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Stack st=new Stack();
String str=sc.nextLine();
int l=str.length();
for(int i=0;i<l;i++)
{
char ch=str.charAt(i);
if(ch=='*')
{
if(!st.isEmpty())
st.pop();
}
else
{
st.push(ch);
}
}
StringBuilder sb=new StringBuilder();
while(!st.isEmpty())
{
sb.append(st.pop());
}
System.out.print(sb.reverse().toString());
}
}
input 1:
tt***u
output 1:
u
input 2:
lucky * draty**w
output :
lucky draw
Story book stack:
import java.util.*;
public class Main
{
static class stack
{
int top=-1;
List<String> al=new ArrayList<>();
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(String str)
{
top++;
al.add(str);
}
String pop()
{
String s=al.get(top);
al.remove(top);
top--;
return s;
}
String peek()
{
String s=al.get(top);
return s;
}
}
public static void main(String args[])
{
Stack st=new Stack();
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
int n=sc.nextInt();
if(n==1)
{
String str=sc.nextLine();
st.push(str);
}
else if(n==2)
{
if(!st.isEmpty())
System.out.println(st.peek());
}
else if(n==-1)
{
if(!st.isEmpty())
st.pop();
}
else if(n==0)
{
System.exit(0);
}
}
}
}
input 1:
1 hello
1 hi
1 book
2
-1
2
-1
2
1 feels for the words
2
-1
-1
1 welcome to code jamm
1 learn your lessons
2
-1
2
0
output 1:
book
hi
hello
feels for the words
learn your lessons
welcome to code jamm
Find Next greater element using stack:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Stack<Integer> st=new Stack<Integer>();
int n=sc.nextInt();
int[] arr=new int[n];
for(int index=0;index<n;index++)
{
arr[index]=sc.nextInt();
}
int[] ans=new int[n];
for(int index=n-1;index>=0;index--)
{
while(!st.isEmpty()&&st.peek()<=arr[index])
{
st.pop();
}
if(st.isEmpty())
{
ans[index]=arr[index];
}
else
{
ans[index]=st.peek();
}
st.push(arr[index]);
}
for(int index=0;index<n;index++)
{
System.out.print(ans[index]+" ");
}
}
}
input 1:
5
10 20 30 40 40
output 1:
20 30 40 40 40
input 2:
8
12 46 18 36 19 36 68
output 2:
46 68 36 68 36 68 76 76
Remove adjacent equal elements using stack:
import java.util.*;
public class Main
{
static List<Integer> al=new ArrayList<>();
static int top=-1;
static class Stack
{
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(int x)
{
++top;
al.add(x);
}
int pop()
{
int num=0;
if(!isEmpty())
{
num=al.get(top);
al.remove(top);
top--;
}
return num;
}
int peek()
{
int num=0;
if(!isEmpty())
{
num=al.get(top);
}
return num;
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Stack st=new Stack();
int n=sc.nextInt();
for(int index=1;index<=n;index++)
{
int num=sc.nextInt();
if(st.isEmpty())
{
st.push(num);
}
else if(st.peek()==num)
{
st.pop();
}
else
{
st.push(num);
}
}
if(al.size()==0)
System.out.print("-1");
else
{
for(Integer num:al)
System.out.print(num+" ");
}
}
}
input 1:
9
10 50 30 40 40 30 50 20 90
output 1:
10 20 90
input 1:
6
30 45 80 80 45 30
output 2:
-1
VIRTUSA
Longest Common Substring Length (with o(m*n) time complexity and o(n) auxiliary space complexity):
import java.util.*;
public class Main
{
public static int LCS(String X,String Y)
{
int m=X.length(),n=Y.length();
int[][] L=new int[2][n+1];
int bi=0;
for(int i=0;i<=m;i++)
{
bi=i&1;
for(int j=0;j<=n;j++)
{
if(i==0||j==0)
L[bi][j]=0;
else if(X.charAt(i-1)==Y.charAt(j-1))
L[bi][j]=L[1-bi][j-1]+1;
else
L[bi][j]=Math.max(L[1-bi][j],L[bi][j-1]);
}
}
return L[bi][n];
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String X=sc.nextLine();
String Y=sc.nextLine();
System.out.println(LCS(X,Y));
}
}
input 1:
smartphone
marketplace
output 1:
6
input 2:
aggtab
gxtxayb
output 2:
4
Robot movement - Maximum possible steps:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int ways=sc.nextInt();
long[] totalWays=new long[N+1];
int[] Ways=new int[N+1];
for(int index=0;index<ways;index++)
{
Ways[index]=sc.nextInt();
}
totalWays[0]=1;
for(int step=1;step<=N;step++)
{
for(int way=0;way<ways;way++)
{
if(step>=Ways[way])
{
totalWays[step]+=totalWays[step-Ways[way]];
}
}
}
System.out.print(totalWays[N]);
}
}
input 1:
5 2
2 3
output 1:
2
input 2:
24 4
2 3 6 5
output 2:
3953
Robot movement - skip Damaged steps:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int ways=sc.nextInt();
int damage=sc.nextInt();
long[] totalWays=new long[N+1];
int[] Ways=new int[N+1];
List<Integer> Damage=new ArrayList<>();
for(int index=0;index<ways;index++)
{
Ways[index]=sc.nextInt();
}
for(int index=1;index<=damage;index++)
{
Damage.add(sc.nextInt());
}
totalWays[0]=1;
for(int step=1;step<=N;step++)
{
if(Damage.contains(step))
{
totalWays[step]=0;
continue;
}
for(int way=0;way<ways;way++)
{
if(step>=Ways[way])
{
totalWays[step]+=totalWays[step-Ways[way]];
}
}
}
System.out.print(totalWays[N]);
}
}
input 1:
5 2 1
2 3
2
output 1:
1
input 2:
18 3 2
2 3 5
4 13
output 2:
81
Check if a queue can be sorted into another queue using another stack
import java.util.*;
public class Main
{
static boolean checkSortedQueue(Queue<Integer> queue,int n)
{
Stack<Integer> stack=new Stack<Integer>();
int count=1,temp=0;
while(!queue.isEmpty())
{
temp=queue.poll();
if(temp==count)
count++;
else
{
if(stack.isEmpty())
stack.push(temp);
else if(!stack.isEmpty()&&stack.peek()<temp)
return false;
else
stack.push(temp);
}
while(!stack.isEmpty()&&stack.peek()==count)
{
stack.pop();
count++;
}
}
if(count-1==n&&stack.isEmpty())
return true;
return false;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
Queue<Integer> queue=new LinkedList<>();
int n=sc.nextInt();
for(int index=0;index<n;index++)
{
queue.add(sc.nextInt());
}
if(checkSortedQueue(queue,n))
System.out.print("yes");
else
System.out.print("no");
}
}
input 1:
6
5 1 2 6 3 4
output 1:
no
input 2:
5
5 1 2 3 4
output 2:
yes
String Comparator:
import java.util.*;
class Player
{
String name;
int score;
Player(String name, int score) {
this.name = name;
this.score = score;
}
}
class Checker implements Comparator<Player>
{
public int compare(Player a, Player b)
{
if(a.score>b.score)
return -1;
else if(a.score<b.score)
return 1;
else
return a.name.compareTo(b.name);
}
}
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Player[] player = new Player[n];
Checker checker = new Checker();
for(int i = 0; i < n; i++){
player[i] = new Player(scan.next(), scan.nextInt());
}
scan.close();
Arrays.sort(player, checker);
for(int i = 0; i < player.length; i++){
System.out.printf("%s %s\n", player[i].name, player[i].score);
}
}
}
input 1:
5
amy 100
david 100
heraldo 50
aakansha 75
aleksa 150
output 1:
aleksa 150
amy 100
david 100
aakansha 75
heraldo 50
Minimum Swaps to form an array in ascending order:
import java.util.*;
public class Main
{
static int findMinSwaps(List<Integer> al,int n)
{
int swaps=0,l=al.size();
int[] temp=new int[n];
for(int index=0;index<l;index++)
{
temp[index]=al.get(index);
}
for(int index=0;index<l;index++)
{
if(temp[index]==l-index)
continue;
swaps++;
int val=temp[index];
temp[index]=temp[l-val];
temp[l-val]=val;
index--;
}
return swaps;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
List<Integer> al=new ArrayList<>();
for(int index=0;index<n;index++)
{
al.add(sc.nextInt());
}
System.out.print(findMinSwaps(al,n));
}
}
input 1:
3
1 3 2
output 1:
2
input 2:
3
3 2 1
output 2:
0
Array Consecutive sum formed by any of the divided groups:
import java.util.*;
public class Main
{
static boolean divideArraySum(int[] arr,int mid,int ctr,int size)
{
int currSum=0;
for(int index=0;index<size;index++)
{
currSum+=arr[index];
if(currSum>mid)
{
currSum=arr[index];
ctr--;
}
if(ctr<0)
return false;
}
return true;
}
static int findLargeSum(int[] arr,int ctr, int M,int size)
{
int minVal=0,maxVal=0;
for(int index=0;index<size;index++)
{
maxVal+=arr[index];
minVal=Math.max(minVal,arr[index]);
}
int LargestSum=maxVal;
while(minVal<=maxVal)
{
int mid=(minVal+maxVal)/2;
if(divideArraySum(arr,mid,ctr-1,size))
{
maxVal=mid-1;
LargestSum=mid;
}
else
minVal=mid+1;
}
return LargestSum;
}
public static void main(String args[] ) throws Exception
{
Scanner sc=new Scanner(System.in);
int K=sc.nextInt();
int M=sc.nextInt();
int size=sc.nextInt();
int[] arr=new int[size];
for(int index=0;index<size;index++)
{
arr[index]=sc.nextInt();
}
System.out.print(findLargeSum(arr,K,M,size));
}
}
input 1:
3 5 5
2 4 5 7 3
output 1:
10
ZOHO
Find the Array Leaders
import java.util.*;
public class MyClass
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
List<Integer> al=new ArrayList<>();
while(sc.hasNext())
{
al.add(sc.nextInt());
}
int l=al.size();
for(int i=0;i<l;i++)
{
int j=0;
for(j=i+1;j<l;j++)
{
if(al.get(i)<=al.get(j))
{
break;
}
}
if(j==l)
System.out.print(al.get(i)+" ");
}
}
}
input:
10 17 5 3 4 2
output:
17 5 2
Check Parenthesis Matching using Stack:
import java.util.*;
public class Main
{
static class Stack
{
int top=-1;
char[] check=new char[100];
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(char element)
{
if(top!=check.length-1)
{
check[++top]=element;
}
}
char pop()
{
char element='\0';
if(top!=-1)
{
element=check[top--];
}
return element;
}
}
static boolean isMatchingPair(char c1,char c2)
{
if(c1=='{'&&c2=='}')
return true;
else if(c1=='('&&c2==')')
return true;
else if(c1=='['&&c2==']')
return true;
else
return false;
}
static boolean ParanthesisMatch(char[] arr)
{
Stack st=new Stack();
for(int index=0;index<arr.length;index++)
{
if(arr[index]=='{'||arr[index]=='('||arr[index]=='[')
{
st.push(arr[index]);
}
if(arr[index]=='}'||arr[index]==')'||arr[index]==']')
{
if(st.isEmpty())
return false;
else if(!isMatchingPair(st.pop(),arr[index]))
{
return false;
}
}
}
if(st.isEmpty())
return true;
else
return false;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
char[] arr=str.toCharArray();
if(ParanthesisMatch(arr))
{
System.out.print("yes");
}
else
{
System.out.print("no");
}
}
}
input 1:
[][]()[{}]()[]
output 1:
yes
input 2:
[][]([)[{}}()[]
output 2:
no
Insert zero after K times 1:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int count=0;
int n=sc.nextInt();
int k=sc.nextInt();
for(int index=1;index<=n;index++)
{
int num=sc.nextInt();
System.out.print(num+" ");
if(num==1)
{
count++;
if(count==k)
{
count=0;
System.out.print("0 ");
}
}
else
{
count=0;
}
}
}
}
input 1:
14 2
1 0 1 1 0 1 1 0 1 0 0 1 1 0
output 1:
1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0
Merge Sort - no dupliactes:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Set<Integer> hs=new HashSet<>();
int m=sc.nextInt();
int n=sc.nextInt();
for(int index=0;index<m;index++)
{
hs.add(sc.nextInt());
}
for(int index=0;index<n;index++)
{
hs.add(sc.nextInt());
}
List<Integer> al=new ArrayList<>(hs);
Collections.sort(al);
for(int index=0;index<al.size();index++)
{
System.out.print(al.get(index)+" ");
}
}
}
input 1:
7 6
1 3 4 5 6 2 7
4 1 5 8 10 9
output 1:
1 2 3 4 5 6 7 8 9 10
Number series arithmetic progression - value at kth position:
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
int d=sc.nextInt();
int k=sc.nextInt();
int diff1=c-a;
int diff2=d-b;
int num1=a,num2=b;
for(int index=1;index<=k-2;index++)
{
if(index%2==1)
{
num1=num1+diff1;
}
else
{
num2=num2+diff2;
}
}
if(k%2==0)
System.out.print(num2);
else
System.out.print(num1);
}
}
input 1:
1 1 5 4
10
output 1:
13
input 2:
2 1 4 7
7
output 2:
5
sort every k integers in descending order:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
List<Integer> al=new ArrayList<>();
int n=sc.nextInt();
int k=sc.nextInt();
for(int index=0;index<n;index++)
{
al.add(sc.nextInt());
}
int size=0;
if(n%k==0)
size=n;
else
size=n-(n%k);
for(int index=0;index<size;index+=k)
{
List<Integer> al1=new ArrayList<>();
for(int i=index;i<index+k;i++)
{
al1.add(al.get(i));
}
Collections.sort(al1,Collections.reverseOrder());
for(int j=0;j<al1.size();j++)
{
System.out.print(al1.get(j)+" ");
}
}
if(n%k!=0)
{
List<Integer> al1=new ArrayList<>();
for(int index=n-(n%k);index<n;index++)
{
al1.add(al.get(index));
}
Collections.sort(al1,Collections.reverseOrder());
for(int j=0;j<al1.size();j++)
{
System.out.print(al1.get(j)+" ");
}
}
}
}
input 1:
7 3
65 548 34 81 267 4 6
output 1:
548 65 34 267 81 4 6
S2 contained in S1 exactly at the same order or not:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
List<Integer> al=new ArrayList<>();
String str1=sc.next();
String str2=sc.next();
int l1=str1.length();
int l2=str2.length();
int ctr=0;
for(int index1=0;index1<l2;index1++)
{
for(int index2=ctr;index2<l1;index2++)
{
if(str2.charAt(index1)==str1.charAt(index2))
{
al.add(index2+1);
ctr=index2+1;
break;
}
}
}
int count=0;
for(int i=0;i<al.size()-1;i++)
{
if(al.get(i+1)>al.get(i))
{
count++;
}
}
if(count==l2-1)
System.out.print("YES");
else
System.out.print("NO");
}
}
input 1:
serksillnrvauegcsyek
skillrack
output 1:
YES
input 2:
geramtnts
men
output 2:
NO
Morse code conversion:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
String str[]=sc.nextLine().split(" ");
int l=str.length;
StringBuilder sb=new StringBuilder();
for(int index=0;index<l;index++)
{
int len=str[index].length();
sb.append((char)(96+len));
}
System.out.print(sb.toString()+" ");
}
}
}
input 1:
111 1 11111111111111
1111111111111111111111111 111111111111111 111111111111111111111
11111111 11111 1 111111111111111111
1111111111111 11111
output 1:
can you hear me
Maximum sum of subarray :
import java.util.*;
public class Main
{
static int maxSubArray(int[] arr)
{
int maxSum=arr[0],sum=arr[0];
for(int index=1;index<arr.length;index++)
{
sum=Math.max(arr[index],sum+arr[index]);
maxSum=Math.max(maxSum,sum);
}
return maxSum;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for(int index=0;index<n;index++)
{
arr[index]=sc.nextInt();
}
System.out.print(maxSubArray(arr));
}
}
input 1:
3
-5 -4 -6
Output 1:
-4
input 2:
5
5 4 -3 -5 6
output 2:
9
INFOMATICA
Path with maximum sum in a matrix
import java.util.*;
public class Main
{
static int findMaxPath(int mat[][],int R, int C)
{
int max=-1;
for(int col=0;col<C;col++)
{
max=Math.max(max,mat[0][col]);
}
for(int row=1;row<R;row++)
{
max=-1;
for(int col=0;col<C;col++)
{
if(col>0&&col<C-1)
{
mat[row][col]+=Math.max(mat[row-1][col],Math.max(mat[row-1][col-1],mat[row-1][col+1]));
}
else if(col>0)
{
mat[row][col]+=Math.max(mat[row-1][col],mat[row-1][col-1]);
}
else if(col<C-1)
{
mat[row][col]+=Math.max(mat[row-1][col],mat[row-1][col+1]);
}
max=Math.max(max,mat[row][col]);
}
}
return max;
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter row:");
int R=sc.nextInt();
System.out.println("Enter column:");
int C=sc.nextInt();
int[][] mat=new int[R][C];
for(int row=0;row<R;row++)
{
for(int col=0;col<C;col++)
{
mat[row][col]=sc.nextInt();
}
}
System.out.println(findMaxPath(mat,R,C));
}
}
input:
Enter row:
4
Enter column:
6
10 10 2 0 20 4
1 0 0 30 2 5
0 10 4 0 2 0
1 0 2 20 0 4
output:
74
explanation:
the path with maximum sum is 20->30->4->2
Quadrant with Maximum odd integers:
import java.util.*;
public class Main
{
static void print(int[][] mat,int startR,int startC,int endR,int endC)
{
for(int row=startR;row<endR;row++)
{
for(int col=startC;col<endC;col++)
{
System.out.print(mat[row][col]+" ");
}
System.out.println();
}
}
static int check(int[][] mat,int startR,int startC,int endR,int endC)
{
int count=0;
for(int row=startR;row<endR;row++)
{
for(int col=startC;col<endC;col++)
{
if(mat[row][col]%2==1)
{
count++;
}
}
}
return count;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
List<Integer> al=new ArrayList<>();
int R=sc.nextInt();
int C=sc.nextInt();
int[][] mat=new int[R][C];
for(int row=0;row<R;row++)
{
for(int col=0;col<C;col++)
{
mat[row][col]=sc.nextInt();
}
}
int startR=0,startC=0,endR=R-1,endC=C-1,count=0;
for(int index=1;index<=4;index++)
{
count=0;
if(index==1)
{
count=check(mat,0,0,R/2,C/2);
}
else if(index==2)
{
count=check(mat,0,C/2,R/2,C);
}
else if(index==3)
{
count=check(mat,R/2,0,R,C/2);
}
else if(index==4)
{
count=check(mat,R/2,C/2,R,C);
}
al.add(count);
}
int max=0,j=0;
for(int i=0;i<al.size();i++)
{
if(al.get(i)>max)
{
max=al.get(i);
j=i;
}
}
int ctr=0;
for(int i=0;i<al.size();i++)
{
if(al.get(i)==max)
ctr++;
}
if(ctr>1)
{
System.out.print("-1");
System.exit(0);
}
else
{
int q=j+1;
if(q==1)
{
print(mat,0,0,R/2,C/2);
}
else if(q==2)
{
print(mat,0,C/2,R/2,C);
}
else if(q==3)
{
print(mat,R/2,0,R,C/2);
}
else if(q==4)
{
print(mat,R/2,C/2,R,C);
}
}
}
}
input 1:
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
output 1:
-1
explanation:
the quadrant with maximum odd integers should be printed. if there is more than one quadrant with max odd integers, the program must print "-1".
input 2:
6 6
1 3 5 1 3 0
1 19 3 1 47 1
7 35 5 29 9 2
18 57 39 29 9 4
27 58 2 5 2 6
84 6 2 7 48 91
output 2:
1 3 5
1 19 3
7 35 5
GOOGLE
Given an array of distinct elements. The task is to find triplets in array whose sum is zero.
Note: The resulting array must be in ascending order.
Sample Input:
Enter n:4
Enter array:1 2 -3 4
Sample Output: -3 1 2
sample Input:
Enter n:5
Enter array:0 1 -3 -1 2
Sample Output: -3 1 2,-1 0 1
import java.util.*;
public class Main
{
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter n:");
int n=sc.nextInt();
System.out.println("Enter array:");
int[] arr=new int[n];
boolean found=false;
for(int index=0;index<n;index++)
{
arr[index]=sc.nextInt();
}
Arrays.sort(arr);
for(int index1=0;index1<n-2;index1++)
{
for(int index2=index1+1;index2<n-1;index2++)
{
for(int index3=index2+1;index3<n;index3++)
{
if(arr[index1]+arr[index2]+arr[index3]==0)
{
List<Integer> al=new ArrayList<Integer>();
al.add(arr[index1]);
al.add(arr[index2]);
al.add(arr[index3]);
Collections.sort(al);
System.out.print(al.get(0)+" ");
System.out.print(al.get(1)+" ");
System.out.print(al.get(2));
System.out.println();
found=true;
}
}
}
}
if(found==false)
{
System.out.print("No pair exists");
}
}
}
// Java code to count BST nodes that
// lie in a given range
Given a Binary Search Tree (BST) and a range, count number of nodes that lie in the given range.
Input:
10
/ \
5 50
/ / \
1 40 100
Range: 5, 45
Output: 3
import java.util.*;
public class Main {
static class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
Node root;
BinarySearchTree() {
root = null;
}
int getCount(Node node, int low, int high)
{
if(node == null)
return 0;
if(node.data >= low && node.data <= high)
return 1+getCount(node.left,low,high)+getCount(node.right,low,high);
else if(node.data < low)
return getCount(node.right, low, high);
else
return getCount(node.left, low, high);
}
// Driver function
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.root = new Node(10);
tree.root.left = new Node(5);
tree.root.right = new Node(50);
tree.root.left.left = new Node(1);
tree.root.right.left = new Node(40);
tree.root.right.right = new Node(100);
int l=5;
int h=45;
System.out.println("Count of nodes between [" + l + ", "
+ h+ "] is " + tree.getCount(tree.root,
l, h));
}
}
INFYTQ
Alternate sort of Upper and Lower case:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
int l=str.length();
List<Character>al1=new ArrayList<>();
List<Character> al2=new ArrayList<>();
for(int index=0;index<l;index++)
{
if(Character.isUpperCase(str.charAt(index)))
al1.add(str.charAt(index));
else
al2.add(str.charAt(index));
}
Collections.sort(al1);
Collections.sort(al2);
int index1=0,index2=0;
int l1=al1.size(),l2=al2.size();
while(index1<l1&&index2<l2)
{
System.out.print(al1.get(index1++)+""+al2.get(index2++));
}
while(index1<l1)
{
System.out.print(al1.get(index1++));
}
while(index2<l2)
{
System.out.print(al2.get(index2++));
}
}
}
input 1:
DeFgHIJabCe
output 1:
CaDbFeHeIgJ
Rotate string odd/even based on the sum of digit square:
import java.util.*;
public class Hello
{
static void rotateLeft(String word)
{
System.out.println(word.substring(2,word.length())+word.substring(0,2));
}
static void rotateRight(String word)
{
System.out.println(word.substring(word.length()-1,word.length())+word.substring(0,word.length()-1));
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String[] str=sc.next().split(",");
for(int index=0;index<str.length;index++)
{
String[] str1=str[index].split(":");
String word=str1[0];
String number=str1[1];
int value=0;
for(int i=0;i<number.length();i++)
{
int n=Integer.valueOf(number.charAt(i));
value+=n*n;
}
if(value%2==1)
rotateLeft(word);
else
rotateRight(word);
}
}
}
input 1:
abcde:234,pqrs:456
output 1:
cdeab
spqr
explanation:
The given string is separated by ',' with n number of words. each word has a string and number separated by ':'.
if the sum of digits squares of the umber is odd, then rotate the string left by two position.
if it is even, the rotate right by one position.
4 digit OTP:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
StringBuilder sb=new StringBuilder();
int l=str.length();
for(int index=1;index<l;index+=2)
{
int n=Character.getNumericValue(str.charAt(index));
int num=n*n;
sb.append(Integer.toString(num));
}
String ans=sb.toString();
if(ans.length()<4)
{
System.out.print("-1");
}
else if(ans.length()==4)
{
System.out.print(ans);
}
else
{
System.out.print(ans.substring(0,4));
}
}
}
input 1:
345271
output 1:
1641
explanation:
the digits at even positions are squared and append together. the 4 digit otp can be formed, print first 4 digits of the Number
else print -1.
Integer sum with Constraints :(INFYTQ)
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String[] str=sc.next().split(",");
StringBuilder sb=new StringBuilder();
long num=0;
int l=str.length;
for(int index=0;index<l;index++)
{
long n=Integer.parseInt(str[index]);
if(n==5)
{
break;
}
else
num+=n;
}
for(int index=0;index<l;index++)
{
long n=Integer.parseInt(str[index]);
if(n==8)
{
for(int i=index+1;i<str.length;i++)
{
num+=Integer.parseInt(str[i]);
}
break;
}
}
int flag=0;
for(int index=0;index<l;index++)
{
long n=Integer.parseInt(str[index]);
if(n==5)
{
for(int i=index;i<l;i++)
{
long m=Integer.parseInt(str[i]);
if(m==8)
{
sb.append(str[i]);
flag=1;
break;
}
else
sb.append(str[i]);
}
}
if(flag==1)
break;
}
long num1=Long.parseLong(sb.toString());
System.out.print(num1+num);
}
}
input 1:
3,2,5,6,7,8,9,3
output 1:
5695
explanation:
the integers before 5 adn after 8 are added as num --> 3 + 2 + 9 + 3 = 17
the integers within 5 and 8 are added includng it are appended and converted ad integer --> 5 + 6 + 7 + 8 = 5678
adding both gives 5678 + 17 = 5695 as output.
AJEERA
Coded message:
import java.util.*;
public class Main
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
int len=str.length();
int n=1;
for(int i=1;i<len/2;i++)
{
if((i*i)<=len)
{
n=i;
}
}
//System.out.println("N VALUE:"+n);
int k=0;
char mat[][]=new char[n+1][n+1];
for(int row=0;row<=n;row++)
{
for(int col=0;col<=n;col++)
{
if(k<(str.length()))
mat[row][col]=str.charAt(k++);
else
mat[row][col]=' ';
}
}
int count=0;
for(int col=0;col<=n;col++)
{
for(int row=0;row<=n;row++)
{
if(mat[row][col]==' ')
System.out.print("_");
else
System.out.print(mat[row][col]);
count++;
if(count>len)
System.exit(0);
}
}
}
}
input 1:
MEET ME IN THE PARK TONIGHT AT SEVEN
output 1:
M__OAN_EIPNT__ENAI___T_RGS___TKHE__MH
input 2:
THIS IS A CODED MESSAGE
output 2:
TIC_AHSOMGI_DEESAES___DS