Skip to content

Commit 5425da9

Browse files
amangit1314amangit1314
committed
#Modification 86
1 parent 7c00e72 commit 5425da9

8 files changed

Lines changed: 344 additions & 70 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11

2-
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[175/450]
2+
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[177/450]
33
🐼 This is a full fled-ged repository for learning Java Language & DSA for Placement Preparation.
44

55
💪 Here you can find the solution's of **_450 Questions of (Data Structure & Algorithms Cracker Sheet)_** By **LOVE BABBAR** Bhaiya.

‎graphs/Graph_Problem_12.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package graphs;
2+
import java.util.*;
3+
4+
// Problem Title => Dijkstra's Algorithm (Find Shortest Path)
5+
public class Graph_Problem_12 {
6+
// finding vertex with min distance,
7+
// from set of non-included vertices in the shortest path tree
8+
int minDistance(int[] dist, boolean[] sptSet, int V){
9+
// Initializing the min value
10+
int min = Integer.MAX_VALUE, min_index = -1;
11+
for(int v = 0; v < V; v++){
12+
if(!sptSet[v] && dist[v] <= min){
13+
min = dist[v];
14+
min_index = v;
15+
}
16+
}
17+
return min_index;
18+
}
19+
20+
void printSolution(int[] dist, int V){
21+
System.out.println("Vertex \t\t Distance from Source");
22+
for (int i = 0; i < V; i++)
23+
System.out.println(i + " \t\t " + dist[i]);
24+
}
25+
26+
void dijskstra(int[][] graph, int V){
27+
int[] dist = new int[V];
28+
boolean[] sptSet = new boolean[V];
29+
30+
for(int i = 0; i < V; i++){
31+
dist[i] = Integer.MAX_VALUE;
32+
sptSet[i] = false;
33+
}
34+
35+
dist[0] = 0;
36+
37+
for(int count = 0; count < V -1; count++){
38+
int u = minDistance(dist, sptSet, V);
39+
40+
sptSet[u] = true;
41+
42+
for(int v = 0; v < V; v++){
43+
if(!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
44+
dist[v] = dist[u] + graph[u][v];
45+
}
46+
47+
printSolution(dist, V);
48+
}
49+
}
50+
51+
public static void main(String[] args) {
52+
Scanner sc = new Scanner(System.in);
53+
int V = sc.nextInt();
54+
55+
56+
int[][] graph = new int[][]{
57+
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
58+
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
59+
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
60+
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
61+
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
62+
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
63+
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
64+
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
65+
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
66+
};
67+
Graph_Problem_12 t = new Graph_Problem_12 ();
68+
t.dijskstra(graph, V);
69+
}
70+
}

‎heap/Problem_5.java‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package heap;
2+
// Problem Title => Find Kith the smallest element in an Unsorted Array
3+
4+
public class Problem_5 {
5+
// A class for Max Heap
6+
static class MinHeap {
7+
8+
int[] harr; // pointer to array of elements in heap
9+
int capacity; // maximum possible size of min heap
10+
int heap_size; // Current number of elements in min heap
11+
12+
int parent(int i) { return (i - 1) / 2; }
13+
int left(int i) { return ((2 * i )+ 1); }
14+
int right(int i) { return ((2 * i) + 2); }
15+
int getMin() { return harr[0]; } // Returns minimum
16+
17+
// to replace root with new node x and heapify() new root
18+
void replaceMax(int x) {
19+
this.harr[0] = x;
20+
minHeapify(0);
21+
}
22+
23+
// Constructor
24+
MinHeap(int[] a, int size) {
25+
heap_size = size;
26+
harr = a; // store address of array
27+
int i = (heap_size - 1) / 2;
28+
while (i >= 0) {
29+
minHeapify(i);
30+
i--;
31+
}
32+
}
33+
34+
// Method to remove maximum element (or root) from min heap
35+
int extractMin() {
36+
if (heap_size == 0)
37+
return Integer.MAX_VALUE;
38+
39+
// Store the maximum value.
40+
int root = harr[0];
41+
42+
// If there are more than 1 items, move the last item to root and call heapify.
43+
if (heap_size > 1) {
44+
harr[0] = harr[heap_size - 1];
45+
minHeapify(0);
46+
}
47+
heap_size--;
48+
return root;
49+
}
50+
51+
// A recursive method to heapify a subtree with root at given index.
52+
// This method assumes that the subtrees are already heaped
53+
void minHeapify(int i) {
54+
int l = left(i);
55+
int r = right(i);
56+
int smallest = i;
57+
if (l < heap_size && harr[l] < harr[i])
58+
smallest = l;
59+
if (r < heap_size && harr[r] < harr[smallest])
60+
smallest = r;
61+
if (smallest != i) {
62+
int t = harr[i];
63+
harr[i] = harr[smallest];
64+
harr[smallest] = t;
65+
minHeapify(smallest);
66+
}
67+
}
68+
}
69+
70+
// Function to return kith the largest element in a given array
71+
int kthSmallest(int[] arr, int n, int k) {
72+
73+
// Build a heap of first k elements: O(k) time
74+
MinHeap mh = new MinHeap(arr, n);
75+
76+
// Process remaining n-k elements.
77+
// If current element is smaller than root, replace root with current element
78+
for (int i = 0; i < k - 1; i++)
79+
mh.extractMin();
80+
81+
// Return root
82+
return mh.getMin();
83+
}
84+
85+
// Driver program to test above methods
86+
public static void main(String[] args) {
87+
int[] arr = { 12, 3, 5, 7, 19 };
88+
int n = arr.length, k = 2;
89+
Problem_5 heap = new Problem_5();
90+
System.out.print("Kith smallest element is " + heap.kthSmallest(arr, n, k));
91+
}
92+
}

‎miscellaneous/BinarySearch.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package miscellaneous;
2+
3+
import java.util.Scanner;
4+
import java.util.concurrent.ThreadLocalRandom;
5+
6+
public class BinarySearch {
7+
8+
int count = 0;
9+
10+
public static int getRandomValue(int Min, int Max) {
11+
// Get and return the random integer within Min and Max
12+
return ThreadLocalRandom.current().nextInt(Min, Max + 1);
13+
}
14+
15+
public static int search(int[] a, int n, int l, int r, int e){
16+
l = 0;
17+
r = n;
18+
19+
if(r >= l){
20+
int m = l + (r-l)/2;
21+
22+
if(a[m] == e)
23+
return m;
24+
25+
if(a[m] > e)
26+
search(a, n, l, m-1, e);
27+
28+
search(a, n, l, m+1, e);
29+
}
30+
return 0;
31+
}
32+
33+
public static void main(String[] args) {
34+
35+
Scanner sc = new Scanner(System.in);
36+
int n = sc.nextInt();
37+
38+
int l = 0, r = n, e;
39+
40+
System.out.println("Enter the value to be found");
41+
e = sc.nextInt();
42+
43+
System.out.println("Enter Min and Max range of random values");
44+
int Min = sc.nextInt(), Max = sc.nextInt();
45+
46+
System.out.println("Input elements of array");
47+
int[] a = new int[n];
48+
for(int i = 0; i < n; i++){
49+
a[i] = getRandomValue(Min, Max);
50+
System.out.println(a[i] + " ");
51+
}
52+
search(a, n, l, r, e);
53+
}
54+
}

‎sortingAlgorithms/MergeSort.java‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -25,13 +25,12 @@ void merge(int[] arr, int l, int m, int r) {
2525
// Copy data to temp arrays
2626
for (int i = 0; i < n1; ++i){
2727
L[i] = arr[l + i];
28-
count++;
2928
}
3029

3130

3231
for (int j = 0; j < n2; ++j){
3332
R[j] = arr[m + 1 + j];
34-
count++;
33+
3534
}
3635

3736
// Merge the temp arrays
@@ -51,21 +50,24 @@ void merge(int[] arr, int l, int m, int r) {
5150
j++;
5251
}
5352
k++;
54-
// count++;
53+
count++;
5554
}
5655

5756
// Copy remaining elements of L[] (Left array) if any
5857
while (i < n1) {
5958
arr[k] = L[i];
6059
i++;
6160
k++;
61+
count++;
62+
//251024
6263
}
6364

6465
// Copy remaining elements of R[] (Right array) if any
6566
while (j < n2) {
6667
arr[k] = R[j];
6768
j++;
6869
k++;
70+
count++;
6971
}
7072
}
7173

0 commit comments

Comments
 (0)