Juspay Coding Answers
1. Example
s=’|**|*|’
n = 2
startIndex=[0,0]
endIndex=[4,5]
For the first pair of indices (0,4) the substrings is “|**|*” . There are 2 stars
between a pair of bars
For the second pair of indices (0,5) the substring is “|**|*|” and there are 2+1=3
stars in between the bars.
Both of the answers are returned to the array [2,3].
Constraints
1 <= n <= 105
1 <= StartIndex[i] <= endIndex[i]
Each Character of s is either “*” or “|”
Input Format for Custom testing
First line contains a string S. The next line contains an integer n , the no.of
elements in startIndex and endIndex. Each line i of the n subsequent lines contains
an integer of startIndex. Each line i of the n subsequent lines contains an integer
of endindex.
Sample Input
*|*| → s=”*|*|”
1 → size of startindex[] and endIndex[] is 1.
0 → startindex = 0
2 → endindex = 2
Sample output:
0
Explanation :
The substring from index = 0 to index = 2 is “*|*” . there is no consecutive pair
of bars in this string.
Code : Java
import java.util.*;
class Main
{
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String str = scn.next();
int n = scn.nextInt();
int startIndex[] = new int[n];
int endIndex[] = new int[n];
for(int i = 0; i < n; i++)
{
startIndex[i] = scn.nextInt();
}
for(int i = 0; i < n; i++)
{
endIndex[i] = scn.nextInt();
}
int len = str.length();
int counter[] = new int[len];
int count = 0;
int lastIdx = -1;
Arrays.fill(counter, -1);
Stack<Integer> st = new Stack<>();
for(int i = 0; i < len; i++)
{
char ch = str.charAt(i);
if(ch == '|')
{
while(!st.empty())
{
int idx = st.pop();
counter[idx] = i;
}
}
st.push(i);
}
int ansArr[] = new int[n];
for(int i = 0; i < n; i++)
{
int sIndex = startIndex[i];
int eIndex = endIndex[i];
int sCount = 0;
if(str.charAt(sIndex) != '|')
sIndex = counter[sIndex];
if(sIndex == -1 || counter[sIndex] == -1)
{
ansArr[i] = 0;
continue;
}
while(sIndex < eIndex)
{
int nextIdx = counter[sIndex];
if((nextIdx != -1) && (nextIdx <= eIndex))
{
sCount += nextIdx - sIndex - 1;
}
sIndex = nextIdx;
}
ansArr[i] = sCount;
}
for(int ele : ansArr)
{
System.out.print(ele + " ");
}
}
}
2. Input Format:
First line with the number of people in the town, n.
Second line with a string with n characters, denoting the one digit power in every
blood.
Output Format:
Total minimum power Stephan will gather before the battle.
Constraints:
1 <= n <= 10^4
Sample input:
6
093212
Sample output
9
Explanation:
Stephan riches the town, drinks the blood with power 9. Now Damon cannot reach 9 by
drinking all the other bloods.
Code : Java
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String str=sc.next();
char arr[]=str.toCharArray();
int a[]=new int[arr.length];
for(int i=0;i<a.length;i++)
a[i]=Integer.parseInt(arr[i]+"");
Arrays.sort(a);
int sum=0;
for(int i=0;i<a.length;i++) sum=sum+a[i]; int sumA=0; int sumB=sum; ArrayList
subsetA=new ArrayList(); for(int i=a.length-1;i>=0;i--)
{
sumA=sumA+a[i];
sumB=sumB-a[i];
subsetA.add(a[i]);
if(sumA>sumB)
break;
}
Iterator itr=subsetA.iterator();
while(itr.hasNext())
{
System.out.print((Integer)itr.next());
}
}
}
3. Input Format:
First line takes n, which is the total no. of mails recieved.
Second line takes the n no. of email id as input./li>
Output Format:
Total no. of duplicate email id’s to be deleted.
Constraints:
1 <= n <= 10^4
Sample input:
6
1 3 3 4 3 3
Sample output
3
Code : Java
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
TreeSet list=new TreeSet<>();
for(int i=0;i<n;i++)
list.add(sc.nextInt());
System.out.println(Math.abs(n-list.size()));
}
}
4. Input Format:
Single line with the id generating string
Output format:
The last id as per lexicographical order.
Constraints:
Number of characters in the string<=10^9
Sample Input:
dc
Explanation:
The last student as per lexicographical order will be with the id dc. The
lexicographical order for adbc will be :
a
ab
abd
abdc
b
bd
bdc
c
d
dc
Code : Java
import java.util.*;
public class Main
{
public static String maxString(char set[])
{
int n=set.length;
String temp="";
TreeSet<String> list=new TreeSet<>();
for(int i=0;i<n;i++)
{
temp="";
for(int j=i;j<n;j++)
{
temp=temp+set[j];
list.add(temp);
}
}
return list.last();
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
char arr[]=str.toCharArray();
System.out.println(maxString(arr));
}
}
5. Input Format:
First line with n, number of steps in the game
Next n lines, n integers denoting outcomes of every game. Positive means winning
and negative means losing that money.
Output Format:
One single integer denoting the minimum amount to start with
Constraints:
Number of steps<=10^9
-1000<=Money needed in each step<=1000
Sample Input:
4
2
-9
15
2
Sample Output:
7
Explanation:
If he starts with 7 rupees, then after steps : 7 ->9 -> 0-> 15 -> 17.
Code : Java
import java.util.*;
public class Main
{
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();
int sum=0,ans=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
if(sum<1)
{
sum=-sum;
ans+=sum;
sum=0;
}
}
System.out.println(ans);
}
}
6. Reverse Linked List
public class Solution
{
public static LinkedListNode<Integer> reverseLinkedList(LinkedListNode<Integer>
head)
{
// Write your code here!
LinkedListNode temp=head;
LinkedListNode prev =null;
LinkedListNode next=null;
while(temp!=null){
LinkedListNode front =temp.next;
temp.next=prev;
prev=temp;
temp=front;
return prev;
}
}
7. Nearest meeting cell
INPUT FORMAT :-
The first line contains the number of cells N.
The second line has a list of N values of the edge[ ] array, where edge[i] conatins
the cell number that can be reached from cell 'i' in one step. edge[i] is -1 if the
ith doesn't have an exit.
Third line for each testcase contains two cell numbers whose nearest meeting cell
needs to be found. (return -1 if there is no meeting cell from tw.
OUTPUT FORMAT :
1.Output a single line that denotes the nearest meeting cell (NMC).
Sample Input :
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
9 2
Sample Output :
4
Code : C++
int minimumWeight(int n, vector<vector<int>>& edges, int C1, int C2) {
//Create directed graph from the array given in input
//Create two arrays A and B for storing min distance from C1 and C2
vector<long long> A(n,LLONG_MAX), B(n,LLONG_MAX);
//Part 1 and Part 2 of Algo -> Implement a dijktra fucntion and call it for
both arrays A and B [I have not implemented, I am giving gist of algo].
Dijkstra(C1,graph,A);
Dijkstra(C2,graph,B);
//Now comes Part 3 part of algo-> loop through and get node with min(A[i]
+B[i])
int node=0 , dist=LLONG_MAX;
for(int i=0;i<=n-1;i++){
//if node is not accessible from any of them ignore it
if(A[i]==LLONG_MAX || B[i]==LLONG_MAX) continue;
if(dist>A[i]+B[i]) dist= A[i]+B[i] , node=i;
}
return node;
}
8. Largest Sum Cycle
INPUT FORMAT :-
The first line contains the number of cells N.
The second line has a list of N values of the edge[ ] array, where edge[i] conatins
the cell number that can be reached from cell 'i' in one step. edge[i] is -1 if the
ith doesn't have ans exit.
OUTPUT FORMAT :
First line denotes length of the largest cycle..
Sample Input :
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
Sample Output :
6
CODE : C++
int dfs(int node, vector<int> &vis, vector<int> &path, vector<int> adj[], int sum)
{
vis[node] = 1;
path[node] = sum;
int tsum = INT_MIN;
for(auto it : adj[node]) {
if(!vis[it]) {
int x = dfs(it, vis, path, adj, sum + it);
tsum = max(tsum, x);
} else if(path[it] != -1) {
int x = path[node] - path[it] + it;
tsum = max(tsum, x);
}
}
path[node] = -1;
return tsum;
}
int main() {
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
vector<int> adj[n]; for(int i = 0; i < n; i++) if(v[i] != -1)
adj[i].push_back(v[i]);
vector<int> vis(n, 0);
vector<int> path(n, -1);
int ans = 0;
for(int i = 0; i < n; i++) {
if(!vis[i]) {
int x = dfs(i, vis, path, adj, i);
ans = max(ans, x);
}
}
cout << ans;
}
9. Maximum Weight Node
INPUT FORMAT :-
The first line contains the number of cells N.
The second line has a list of N values of the edge[ ] array, where edge[i] conatins
the cell number that can be reached from cell 'i' in one step. edge[i] is -1 if the
ith doesn't have ans exit.
OUTPUT FORMAT :
First line denotes the node number with maximum weight node.
Sample Input :
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
Sample Output :
22
class Solution
{
public:
int maxWeightCell(int N, vector Edge)
{
vector weight(N);
for(int i=0;i<N;i++){
if(Edge[i]!=-1){
weight[Edge[i]]+=i;
}
}
array<long long,2> ans={-1,-1};
for(int i=0;i<N;i++){
ans=max(ans,{weight[i],i});
}
return ans[1];
}
};
10. Tree Traversals
import java.util.*;
public class Main {
public static String solution(String str) {
Map<Character, Integer> Map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (!Map.containsKey(ch)) {
Map.put(ch, 1);
} else {
Map.put(ch, Map.get(ch) + 1);
}
}
List<Character> chars = new ArrayList<>(Map.keySet());
Collections.sort(chars, new Comparator<Character>() {
public int compare(Character ch1, Character ch2) {
return Map.get(ch2) - Map.get(ch1);
}
});
StringBuilder sb = new StringBuilder();
for (char ch : chars) {
int freq = Map.get(ch);
for (int i = 0; i < freq; i++) {
sb.append(ch);
}
}
return sb.toString();
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String str = scan.nextLine();
String sortStr = solution(str);
System.out.println(sortStr);
}
}
