Skip to content

Commit d0868cf

Browse files
amangit1314amangit1314
committed
#Modification 136
1 parent 3d9016a commit d0868cf

19 files changed

Lines changed: 896 additions & 4 deletions

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[324/450]
1+
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[330/450]
22

33
☄ This is a full fled-ged repository for learning Java Language & DSA for Placement Preparation.
44

‎Relevel_Test.java‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
2+
/*
3+
Problem -> Solve History Ranking
4+
5+
DUMB JERRY
6+
DUMB JERRY
7+
8+
Problem Statement
9+
10+
As usual, Jerry and Tom are fighting. Tom wants to prove that Jerry is Dumb, So he made a problem and asked jerry.
11+
12+
Given a sequence A of size N, and an operation.
13+
14+
In one operation you can pick an element either from the front or back of the Sequence and write it down and delete it from the array.
15+
Jerry has to perform the given operation until sequence A becomes empty.
16+
17+
Tom wants the written sequence to be lexicographically maximum possible by performing the given operation on sequence A.
18+
19+
Jerry can’t solve the problem on his own. So you have to help him.
20+
21+
Note:-
22+
23+
Sequence X of length N is lexicographically greater than Sequence Y of length N, if there exist such i (1<=i<=N), that Xi >Yi and for any j (1<=j<i) Xi=Yi.
24+
25+
Constraint
26+
27+
• 1 <= N <= 105
28+
• 0 <= Ai <= 109
29+
30+
• All input values are integer.
31+
32+
Input Format
33+
34+
• First-line contains N, length of the sequence A
35+
36+
• Second line contains N space-separated integers denoting the sequence A.
37+
38+
Output Format
39+
40+
• In first print the lexicographically maximum sequence made by performing operations on sequence A
41+
42+
Sample Input 1
43+
44+
3
45+
46+
3 1 2
47+
48+
Sample Output 1
49+
50+
3 2 1
51+
52+
Explanation of Sample 1
53+
54+
For test case1
55+
56+
We get sequence {3,1,2} if we
57+
Pick the element from the front of the sequence (3) and delete it from the original sequence {1,2}
58+
Pick the element from the front of the sequence (3,1) and delete it from the original sequence {2}
59+
Pick the element from the front of the sequence (3,1,2) and delete it from the original sequence {}
60+
We get sequence {3,2,1} if we
61+
Pick the element from the front of the sequence (3) and delete it from the original sequence {1,2}
62+
Pick the element from the back of the sequence (3,2) and delete it from the original sequence {1}
63+
Pick the element from the front of the sequence (3,2,1) and delete it from the original sequence {}
64+
We get sequence {2,3,1} if we
65+
Pick the element from the back of the sequence (2) and delete it from the original sequence {3,1}
66+
Pick the element from the front of the sequence (2,3) and delete it from the original sequence {1}
67+
Pick the element from the front of the sequence (2,3,1) and delete it from the original sequence {}
68+
We get sequence {2,1,3} if we
69+
Pick the element from the back of the sequence (2) and delete it from the original sequence {3,1}
70+
Pick the element from the back of the sequence (2,1) and delete it from the original sequence {3}
71+
Pick the element from the front of the sequence (2,1,3) and delete it from the original sequence {}
72+
Compare to other {3,2,1} is lexicographically largest.
73+
74+
Things to Note for the Candidate
75+
76+
You can use your own IDE like Visual Studio Code, Eclipse, or any other IDE that you are comfortable with to build your solution code.
77+
The IDE provided on the platform is purely for submission. Avoid using the IDE for coding out the solution.
78+
Test against any custom input in your own IDE. In the IDE provided on the platform, you cannot pass custom test cases and see the output.
79+
Use standard input and standard output in your program for the IDE to run the test cases smoothly against your code. We are giving a sample problem statement along with a solution that will pass the test cases in the IDE. - Sample Problem Statement (Right Click and Open in New Tab to view.)
80+
81+
82+
83+
*/
84+
85+
86+
/* package whatever; // don't place package name! */
87+
88+
import java.util.*;
89+
import java.lang.*;
90+
import java.io.*;
91+
92+
/* Name of the class has to be "Main" only if the class is public. */
93+
class Relevel_Test
94+
{
95+
96+
public static void main (String[] args) throws java.lang.Exception
97+
{
98+
// your code goes here
99+
Scanner sc = new Scanner(System.in);
100+
int m = sc.nextInt();
101+
int n = sc.nextInt();
102+
103+
int[] x = new int[m];
104+
int[] y = new int[n];
105+
106+
for (int a : x) {
107+
x[a] = sc.nextInt();
108+
}
109+
110+
for (int b : y) {
111+
y[b] = sc.nextInt();
112+
}
113+
}
114+
115+
public static int solve() {
116+
117+
}
118+
}

‎backtracking/Longest_Possible_Route_with_Hurdles_in_Matrix.java‎

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
package backtracking;
2+
3+
/**
4+
* Given - An m * n matrix with a few hurdles arbitrarily placed.
5+
* Task - Calculate the length of the longest possible route possible from the source to destination within the matrix.
6+
* Note - We are allowed to move to only adjacent cells which are not hurdles.
7+
* The route can not contain any diagonal moves and a location once visited in a particular path cannot be visited again.
8+
* Example -
9+
* i/p -> the longest path ->
10+
* 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1
11+
* 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1
12+
* 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
13+
*
14+
* o/p -> length of the path is 24
15+
*/
16+
17+
public class Longest_Possible_Route_with_Hurdles_in_Matrix {
18+
19+
static int R = 3; static int C = 10;
20+
21+
static class Pair {
22+
boolean found;
23+
int val;
24+
Pair(boolean x, int y) {
25+
found = x;
26+
val = y;
27+
}
28+
}
29+
30+
static Pair findLongestPathUtil(int[][] mat, int i, int j, int x, int y, boolean[][] visited) {
31+
if(i == x && j == y)
32+
return new Pair(true, 0);
33+
34+
if(i < 0 || i >= R || j < 0 || j >= C || mat[i][j] == 0 || visited[i][j])
35+
return new Pair(false, Integer.MAX_VALUE);
36+
37+
visited[i][j] = true;
38+
int res = Integer.MIN_VALUE;
39+
Pair sol = findLongestPathUtil(mat, i, j - 1, x, y, visited);
40+
41+
if(sol.found)
42+
res = sol.val;
43+
44+
sol = findLongestPathUtil(mat, i, j + 1, x , y, visited);
45+
46+
if(sol.found)
47+
res = Math.max(sol.val, res);
48+
49+
sol = findLongestPathUtil(mat, i - 1, j, x, y, visited);
50+
51+
if(sol.found)
52+
res = Math.max(sol.val, res);
53+
54+
sol = findLongestPathUtil(mat, i + 1, j, x, y, visited);
55+
56+
if(sol.found)
57+
res = Math.max(sol.val, res);
58+
59+
visited[i][j] = false;
60+
61+
if(res != Integer.MIN_VALUE)
62+
return new Pair(true, res + 1);
63+
64+
else
65+
return new Pair(false, Integer.MAX_VALUE);
66+
}
67+
68+
static void findLongestPath(int[][] mat, int i, int j, int x, int y) {
69+
boolean[][] visited = new boolean[i][j];
70+
71+
Pair p = findLongestPathUtil(mat, i, j, x, y, visited);
72+
73+
if(p.found)
74+
System.out.println("Length of longest possible route is " + p.val);
75+
76+
else
77+
System.out.println("Destination not reachable from given source");
78+
}
79+
80+
public static void main(String[] args) {
81+
int[][] mat = new int[R][C];
82+
int i = 0, j = 0, x = 0, y = 0;
83+
84+
findLongestPath(mat, i, j, x, y);
85+
}
86+
}

‎backtracking/Max_possible_no_by_doing_atmost_k_swaps.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package backtracking;
2+
import java.util.*;
3+
public class Max_possible_no_by_doing_atmost_k_swaps {
4+
static String strMax = "";
5+
6+
public static String findMaximumNum(String str, int k) {
7+
strMax = "";
8+
char[] arr = str.toCharArray();
9+
findNum(arr, k);
10+
if (strMax.isEmpty())
11+
return str;
12+
return strMax;
13+
}
14+
15+
public static void findNum(char[] arr, int k) {
16+
if (k == 0) return;
17+
int size = arr.length;
18+
19+
for (int i = 0; i < size - 1; i++) {
20+
for (int j = i + 1; j < size; j++) {
21+
char a = arr[i];
22+
char b = arr[j];
23+
24+
if(a < b) {
25+
char temp = arr[i];
26+
arr[i] = arr[j];
27+
arr[j] = temp;
28+
29+
String toStr = String.valueOf(arr);
30+
31+
if(toStr.compareTo(strMax) > 0)
32+
strMax = toStr;
33+
34+
findNum(arr, k - 1);
35+
}
36+
37+
if(a < b) {
38+
char temp = arr[i];
39+
arr[i] = arr[j];
40+
arr[j] = temp;
41+
}
42+
}
43+
}
44+
}
45+
public static void main (String[]args){
46+
47+
}
48+
}

‎backtracking/Nth_Root_of_M.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package backtracking;
2+
import java.util.*;
3+
4+
/**
5+
* Given - Two positive integers N and M
6+
* Task - You have to find the Nth root of m such that M^(1/N)
7+
* Note - Nth root of an integer M is a real number which when raised to the power N gives M as result
8+
* Nth root of M should be correct up tp 6 decimal place.
9+
* Example -
10+
* i/p - 1
11+
* 3 27
12+
* explanation - 3rd Root of 27 is 3.000000, as (3.000000)^3 is equal to 27
13+
* */
14+
15+
16+
public class Nth_Root_of_M {
17+
18+
public static double multiply(double number, int m) {
19+
double ans = 1.0;
20+
for(int i = 1; i <= m; i++)
21+
ans = ans * number;
22+
return ans;
23+
}
24+
25+
public static double getNthRoot(int n, int m) {
26+
double low = 1;
27+
double hi = m;
28+
double ops = 1e-9;
29+
30+
while((hi - low) > ops) {
31+
double mid = (low + hi) / 2 ;
32+
if(multiply(mid, n) < m)
33+
low = mid;
34+
else
35+
hi = mid;
36+
}
37+
return hi; // doubt hai is line m
38+
}
39+
40+
public static void main(String[] args) {
41+
Scanner sc = new Scanner(System.in);
42+
int n = sc.nextInt(), m = sc.nextInt();
43+
System.out.print(getNthRoot(n, m));
44+
}
45+
}

‎backtracking/Path_more_than_k.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package backtracking;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
6+
public class Path_more_than_k {
7+
8+
static class AdjListNode {
9+
int v;
10+
int weight;
11+
12+
AdjListNode(int _v, int _w) {
13+
v = _v;
14+
weight = _w;
15+
}
16+
17+
int getV() {return v;}
18+
}
19+
20+
static class Graph {
21+
int v;
22+
ArrayList<ArrayList<AdjListNode>> adj = new ArrayList<>();
23+
Graph(int v) {
24+
this.v = v;
25+
adj = new ArrayList<>();
26+
for(int i = 0; i < v; i++)
27+
adj.add(new ArrayList<>());
28+
}
29+
30+
void addEdge(int u, int v, int w) {
31+
AdjListNode n1 = new AdjListNode(v, w);
32+
adj.get(u).add(n1);
33+
AdjListNode n2 = new AdjListNode(u, w);
34+
adj.get(v).add(n2);
35+
}
36+
37+
boolean pathMoreThanK(int sre, int k) {
38+
boolean[] path = new boolean[v];
39+
Arrays.fill(path, false);
40+
path[sre] = true;
41+
return pathMoreThanKUtil(sre,k, path);
42+
}
43+
44+
boolean pathMoreThanKUtil(int src, int k, boolean[] path) {
45+
if(k <= 0)
46+
return true;
47+
48+
ArrayList<AdjListNode> it = adj.get(src);
49+
int index = 0;
50+
51+
for(int i = 0; i < adj.get(src).size(); i++) {
52+
AdjListNode vertex = adj.get(src).get(i);
53+
int v = vertex.v;
54+
int w = vertex.weight;
55+
index++;
56+
57+
if(path[v])
58+
continue;
59+
60+
if (w >= k)
61+
return true;
62+
63+
path[v] = true;
64+
65+
if(pathMoreThanKUtil(v, k-w, path))
66+
return true;
67+
68+
path[v] = false;
69+
}
70+
return false;
71+
}
72+
}
73+
74+
public static void main(String[] args) {
75+
int v = 1;
76+
Graph g = new Graph(v);
77+
}
78+
}

0 commit comments

Comments
 (0)