Last active
November 17, 2020 12:08
-
-
Save raviranjan3570/8846614513ff40b6e9bbe74b06cfc5c9 to your computer and use it in GitHub Desktop.
Algorithms for coding interview
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public int search(int[] nums, int target) { | |
int left = 0; | |
int right = nums.length - 1; | |
while(left <= right){ | |
int mid = left + (right - left) / 2; | |
// if target is found | |
if(nums[mid] == target){ | |
return mid; | |
} | |
// if target is greater than the middle element. | |
else if(nums[mid] < target){ | |
left = mid + 1; | |
} | |
// if target is less than the middle | |
else{ | |
right = mid - 1; | |
} | |
} | |
return -1; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public int[] sortArray(int[] nums) { | |
bubbleSort(nums, nums.length); | |
return nums; | |
} | |
// TC is O(n^2) and space complexity is O(1) | |
public void bubbleSort(int[] array, int size){ | |
for(int i = 0; i < size; i++){ | |
// flag | |
int swapped = 0; | |
for(int j = 0; j < size - i - 1; j++){ | |
if(array[j] > array[j + 1]){ | |
// swap | |
int swap = array[j]; | |
array[j] = array[j + 1]; | |
array[j + 1] = swap; | |
swapped = 1; | |
} | |
} | |
// if list is already in ascending order | |
if(swapped == 0) break; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Building max heap | |
public class Main { | |
static int array[] = { 1, 3, 5, 4, 6, 13, 10, | |
9, 8, 15, 17 }; | |
static int size = array.length; | |
public static void main(String[] args) { | |
buildMaxHeap(array, size); | |
extractMax(array); | |
increaseKey(array, 1, 90); | |
printHeap(array, size); | |
} | |
static void maxHeapify(int[] array, int root, int size){ | |
// initialize largest as root | |
int largest = root; | |
// left and right child position in the array | |
int left = 2 * root + 1; | |
int right = 2 * root + 2; | |
// we will check which element is largest (parent or left child or right child) | |
if(left < size && array[left] > array[largest]){ | |
largest = left; | |
} | |
if(right < size && array[right] > array[largest]){ | |
largest = right; | |
} | |
// if parent is not the largest then swap parent with largest | |
if(largest != root){ | |
int swap = array[root]; | |
array[root] = array[largest]; | |
array[largest] = swap; | |
// recursively heapify affected subtree | |
maxHeapify(array, largest, size); | |
} | |
} | |
static void buildMaxHeap(int[] array, int size){ | |
// last non-leaf | |
int startIndex = (size / 2) - 1; | |
for(int root = startIndex; root >= 0; root--){ | |
maxHeapify(array, root, size); | |
} | |
} | |
static void printHeap(int[] array, int size){ | |
System.out.println("The heap is : "); | |
// printing heap level wise | |
for (int root = 0; root < size; root++){ | |
System.out.println(array[root]); | |
} | |
} | |
// extracting max element and removing it from the tree (TC : O(logn)) | |
static void extractMax(int[] array){ | |
// if heap is empty | |
if(size < 0){ | |
System.out.println("heap is empty"); | |
} | |
int max = array[0]; | |
array[0] = array[size - 1]; | |
// decrease the size to delete the element | |
size -= 1; | |
maxHeapify(array, 0, size); | |
System.out.println(max + " is the maximum element."); | |
} | |
// for increasing the value of a particular node (TC : O(logn)) | |
static void increaseKey(int[] array, int index, int quantity){ | |
if(quantity < array[index]){ | |
System.out.println("you cannot decrease the value"); | |
} | |
array[index] = quantity; | |
// making it max heap again | |
while(index > 0 && array[index/2] < array[index]){ | |
int swap = array[index]; | |
array[index] = array[index/2]; | |
array[index/2] = swap; | |
index /= 2; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
static final int V = 9; | |
public static void main(String[] args) { | |
int graph[][] = {{ 0, 4, 0, 0, 0, 0, 0, 8, 0 }, | |
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 }, | |
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 }, | |
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 }, | |
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 }, | |
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 }, | |
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 }, | |
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 }, | |
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }}; | |
dijsktra(graph, 0); | |
} | |
static int selectMinDistance(int[] distance, boolean[] isIncluded){ | |
int vertex = -1; | |
int minimum = Integer.MAX_VALUE; | |
for(int i = 0; i < V; i++){ | |
if(isIncluded[i] == false && distance[i] < minimum){ | |
vertex = i; | |
minimum = distance[i]; | |
} | |
} | |
return vertex; | |
} | |
static void printSolution(int[] distance){ | |
System.out.println("Vertex \t Distance from Source"); | |
for (int i = 0; i < V; i++) | |
System.out.println(i + "\t" + distance[i]); | |
} | |
static void dijsktra(int[][] graph, int source){ | |
int[] distance = new int[V]; | |
Arrays.fill(distance, Integer.MAX_VALUE); | |
boolean[] isIncluded = new boolean[V]; | |
Arrays.fill(isIncluded, Boolean.FALSE); | |
distance[source] = 0; | |
for(int i = 0; i < V; i++){ | |
int u = selectMinDistance(distance, isIncluded); | |
isIncluded[u] = true; | |
for(int j = 0; j < V; j++){ | |
if(graph[u][j] != 0 && isIncluded[j] == false && | |
distance[u] != Integer.MAX_VALUE && | |
distance[u] + graph[u][j] < distance[j]){ | |
distance[j] = distance[u] + graph[u][j]; | |
} | |
} | |
} | |
printSolution(distance); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
// weight, profit of items and capacity of bag | |
int[] weight = {2,3,5,7,1,4,1}; | |
int[] profit = {10,5,15,7,6,18,3}; | |
int capacity = 15; | |
double maxProfit = greedyKnapsack(weight, profit, capacity); | |
System.out.println(maxProfit); | |
} | |
static class Item{ | |
double weight, profit, profitPerUnitOfWeight; | |
public Item(int weight, int profit){ | |
this.weight = weight; | |
this.profit = profit; | |
profitPerUnitOfWeight = profit / weight; | |
} | |
} | |
static double greedyKnapsack(int[] weight, int[] profit, int capacity){ | |
// here we are creating a list of Item object so that we can sort them. | |
List<Item> items = new ArrayList<>(); | |
for(int i = 0; i < weight.length; i++){ | |
items.add(new Item(weight[i], profit[i])); | |
} | |
items.sort((Item first, Item second) -> Double.compare(second.profitPerUnitOfWeight, first.profitPerUnitOfWeight)); | |
// we'll try to fill the bag with the object that has maximum profit per unit of weight | |
double totalProfit = 0; | |
for(Item item : items){ | |
double currentWeight = item.weight; | |
double currentProfit = item.profit; | |
// if we can take the whole object | |
if(capacity - currentWeight >= 0){ | |
capacity -= currentWeight; | |
totalProfit += currentProfit; | |
} | |
// if we can take only a portion of it | |
else{ | |
double fraction = capacity / currentWeight; | |
totalProfit += currentProfit * fraction; | |
break; | |
} | |
} | |
return totalProfit; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Building max heap | |
public class Main { | |
static int array[] = { 1, 3, 5, 4, 6, 13, 10, | |
9, 8, 15, 17 }; | |
static int size = array.length; | |
public static void main(String[] args) { | |
buildMaxHeap(array, size); | |
heapSort(array); | |
printHeap(array, size); | |
} | |
static void maxHeapify(int[] array, int root, int size){ | |
// initialize largest as root | |
int largest = root; | |
// left and right child position in the array | |
int left = 2 * root + 1; | |
int right = 2 * root + 2; | |
// we will check which element is largest (parent or left child or right child) | |
if(left < size && array[left] > array[largest]){ | |
largest = left; | |
} | |
if(right < size && array[right] > array[largest]){ | |
largest = right; | |
} | |
// if parent is not the largest then swap parent with largest | |
if(largest != root){ | |
int swap = array[root]; | |
array[root] = array[largest]; | |
array[largest] = swap; | |
// recursively heapify affected subtree | |
maxHeapify(array, largest, size); | |
} | |
} | |
static void buildMaxHeap(int[] array, int size){ | |
// last non-leaf | |
int startIndex = (size / 2) - 1; | |
for(int root = startIndex; root >= 0; root--){ | |
maxHeapify(array, root, size); | |
} | |
} | |
static void printHeap(int[] array, int size){ | |
System.out.println("The heap is : "); | |
// printing heap level wise | |
for (int root = 0; root < size; root++){ | |
System.out.println(array[root]); | |
} | |
} | |
static void heapSort(int[] array){ | |
int heapSize = size; | |
for(int i = array.length - 1; i > 0; i--){ | |
int swap = array[0]; | |
array[0] = array[i]; | |
array[i] = swap; | |
heapSize -= 1; | |
maxHeapify(array, 0, heapSize); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
int numberOfCharacters = 4; | |
char[] characterArray = {'a', 'b', 'c', 'd'}; | |
int[] frequencyArray = {50, 35, 5, 5}; | |
buildHuffmanTree(characterArray, frequencyArray, numberOfCharacters); | |
} | |
static void buildHuffmanTree(char[] characterArray, int[] frequencyArray , int numberOfCharacters){ | |
// for taking characters with less frequency first | |
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>( | |
(HuffmanNode first, HuffmanNode second) -> | |
first.frequency - second.frequency); | |
for(int i = 0; i < numberOfCharacters; i++){ | |
HuffmanNode newNode = new HuffmanNode(frequencyArray [i], characterArray[i], null, null); | |
pq.add(newNode); | |
} | |
// optimal merge pattern | |
HuffmanNode root = null; | |
while(pq.size() > 1){ | |
HuffmanNode first = pq.poll(); | |
HuffmanNode second = pq.poll(); | |
int frequency = first.frequency + second.frequency; | |
HuffmanNode newNode = new HuffmanNode(frequency, '+', first, second); | |
root = newNode; | |
pq.add(newNode); | |
} | |
printCode(root, ""); | |
} | |
static void printCode(HuffmanNode root, String s) | |
{ | |
if(root == null) return; | |
if (root.left == null && root.right == null) { | |
System.out.println(root.character + ":" + s); | |
} | |
printCode(root.left, s + "0"); | |
printCode(root.right, s + "1"); | |
} | |
} | |
class HuffmanNode{ | |
int frequency; | |
char character; | |
HuffmanNode left; | |
HuffmanNode right; | |
public HuffmanNode(int frequency, char character, | |
HuffmanNode left, HuffmanNode right){ | |
this.frequency = frequency; | |
this.character = character; | |
this.left = left; | |
this.right = right; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public int[] sortArray(int[] nums) { | |
// j = 1, because single element is always sorted | |
for(int j = 1; j < nums.length; j++){ | |
// picking it up so that we don't loose this value | |
int key = nums[j]; | |
// we start from the previous element | |
int i = j - 1; | |
// we continue finding the correct place for key | |
while(i >= 0 && nums[i] > key){ | |
nums[i + 1] = nums[i]; | |
i -= 1; | |
} | |
//after finding correct place of the key, we insert it. | |
nums[i + 1] = key; | |
} | |
return nums; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
int[] deadline = {2, 1, 2, 1, 3}; | |
int[] profit = {100, 19, 27, 25, 15}; | |
char[] ids = {'a', 'b', 'c', 'd', 'e'}; | |
int timeAvailable = 3; | |
jobScheduling(ids, deadline, profit, timeAvailable); | |
} | |
static void jobScheduling(char[] ids, int[] deadline, int[] profit, int timeAvailable){ | |
int numberOfJobs = ids.length; | |
List<Job> jobs = new ArrayList<>(); | |
for(int i = 0; i < numberOfJobs; i++){ | |
Job newJob = new Job(ids[i], deadline[i], profit[i]); | |
jobs.add(newJob); | |
} | |
jobs.sort((Job first, Job second) -> second.profit - first.profit); | |
boolean[] isAvailable = new boolean[timeAvailable]; | |
char[] assignedJob = new char[timeAvailable]; | |
for(int i = 0; i < numberOfJobs; i++){ | |
for(int j = Math.min(timeAvailable - 1, jobs.get(i).deadline - 1); j >= 0; j--){ | |
// slot is available | |
if(isAvailable[j] == false){ | |
isAvailable[j] = true; | |
assignedJob[j] = jobs.get(i).id; | |
break; | |
} | |
} | |
} | |
for(char job : assignedJob){ | |
System.out.print(job + " "); | |
} | |
} | |
} | |
class Job{ | |
char id; | |
int deadline; | |
int profit; | |
public Job(char id, int deadline, int profit){ | |
this.id = id; | |
this.deadline = deadline; | |
this.profit = profit; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
int[] weight = {10, 20, 30}; | |
int[] profit = {60, 100, 120}; | |
int capacity = 50; | |
int quantity = weight.length; | |
System.out.println(knapsack(weight, profit, capacity, quantity)); | |
} | |
static int knapsack(int[] weight, int[] profit, int capacity, int quantity){ | |
int[][] dp = new int[quantity + 1][capacity + 1]; | |
for(int i = 0; i <= quantity; i++){ | |
for(int j = 0; j <= capacity; j++){ | |
if(i == 0 || j == 0) dp[i][j] = 0; | |
else if(weight[i - 1] <= j){ | |
dp[i][j] = Math.max( | |
profit[i - 1] + dp[i - 1][j - weight[i - 1]], | |
dp[i - 1][j]); | |
} | |
else dp[i][j] = dp[i - 1][j]; | |
} | |
} | |
return dp[quantity][capacity]; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
int[] array = {10, 20, 30, 40, 50}; | |
int target = 30; | |
System.out.print(linearSearch(array, target)); | |
} | |
// search the array linearly | |
public static int linearSearch(int[] array, int target){ | |
for(int i = 0; i < array.length; i++){ | |
if(array[i] == target){ | |
return i; | |
} | |
} | |
return -1; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
String s1 = "pqprqrp"; | |
String s2 = "qpqrr"; | |
char[] first = s1.toCharArray(); | |
char[] second = s2.toCharArray(); | |
System.out.println("Length of LCS is "+ longestCommonSubsequence(first, second)); | |
} | |
static int longestCommonSubsequence(char[] first, char[] second){ | |
int m = first.length; | |
int n = second.length; | |
int[][] dp = new int[m + 1][n + 1]; | |
for(int i = 0; i <= m; i++){ | |
for(int j = 0; j <= n; j++){ | |
// three conditions for solving longest common subsequence problem | |
if(i == 0 || j == 0) dp[i][j] = 0; | |
else if(first[i - 1] == second[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1]; | |
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); | |
} | |
} | |
return dp[m][n]; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
int[] array = {1, 2, 1, 4, 1}; | |
System.out.println( | |
"Minimum number of multiplications required is " | |
+ matrixChainMultiplication(array)); | |
} | |
static int matrixChainMultiplication(int[] array){ | |
int size = array.length; | |
int dp[][] = new int[size][size]; | |
int cost; | |
int j; | |
// cost is zero when we multiply one matrix. | |
for(int i = 1; i < size; i++){ | |
dp[i][i] = 0; | |
} | |
// l is chain of length 2 | |
for(int l = 2; l < size; l++){ | |
for(int i = 1; i < size - l + 1; i++){ | |
j = i + l - 1; | |
if(j == size) continue; | |
dp[i][j] = Integer.MAX_VALUE; | |
// finding the split | |
for(int k = i; k <= j - 1; k++){ | |
cost = dp[i][k] + dp[k + 1][j] + array[i - 1] * array[k] * array[j]; | |
if(cost < dp[i][j]){ | |
dp[i][j] = cost; | |
} | |
} | |
} | |
} | |
return dp[1][size - 1]; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
int[] array = {1, 2, 1, 4, 1}; | |
System.out.println( | |
"Minimum number of multiplications required is " | |
+ memoizedMatrixChain(array)); | |
} | |
static int memoizedMatrixChain(int[] array){ | |
int size = array.length; | |
int dp[][] = new int[size][size]; | |
for(int i = 1; i < size; i++){ | |
for(int j = 1; j < size; j++){ | |
dp[i][j] = Integer.MAX_VALUE; | |
} | |
} | |
return lookUpChain(dp, array, 1, size - 1); | |
} | |
static int lookUpChain(int[][] dp, int[] array, int i, int j){ | |
if(dp[i][j] < Integer.MAX_VALUE){ | |
return dp[i][j]; | |
} | |
else if(i == j){ | |
return 0; | |
} | |
else{ | |
for(int k = i; k < j; k++){ | |
int cost = lookUpChain(dp, array, i, k) + | |
lookUpChain(dp, array, k + 1, j) + | |
array[i - 1] * array[k] * array[j]; | |
if(cost < dp[i][j]){ | |
dp[i][j] = cost; | |
} | |
} | |
} | |
return dp[i][j]; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public int[] sortArray(int[] nums) { | |
mergeSort(nums, 0, nums.length - 1); | |
return nums; | |
} | |
/** | |
* [10, 20, 30, 40, 1, 5, 6, 9] | |
* p = 0(index of first element of first sorted list) | |
* q = 3(index of last element of first sorted list) | |
* r = 7(index of last element of second sorted list) | |
*/ | |
// TC = O(n), SC = O(n) for merge process | |
public void merge(int[] array, int p, int q, int r){ | |
// n1 and n2 are number of elements in first and second list | |
int n1 = q - p + 1; | |
int n2 = r - q; | |
// for copying each sorted list into seperate list | |
// later we'll use this for comparision | |
int[] a1 = new int[n1 + 1]; | |
int[] a2 = new int[n2 + 1]; | |
for(int i = 0; i < n1; i++){ | |
a1[i] = array[p + i]; | |
} | |
for(int j = 0; j < n2; j++){ | |
a2[j] = array[q + j + 1]; | |
} | |
// last element of each lists | |
a1[n1] = Integer.MAX_VALUE; | |
a2[n2] = Integer.MAX_VALUE; | |
// two pointers for two lists | |
int i = 0; | |
int j = 0; | |
// comparing and merging two lists | |
for(int k = p; k <= r; k++){ | |
if(a1[i] < a2[j]){ | |
array[k] = a1[i]; | |
i += 1; | |
} | |
else{ | |
array[k] = a2[j]; | |
j += 1; | |
} | |
} | |
} | |
// SC = (logn) for stack where n is number of funtion calls | |
public void mergeSort(int[] array, int p, int r){ | |
if(p < r){ | |
// for dividing array into two sub-arrays | |
int q = (p + r) / 2; | |
//divide | |
mergeSort(array, p, q); | |
mergeSort(array, q + 1, r); | |
// conquer | |
merge(array, p, q, r); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
static final int INF = Integer.MAX_VALUE; | |
static final int N = 8; | |
public static void main(String[] args) { | |
int[][] graph = {{INF, 1, 2, 5, INF, INF, INF, INF}, | |
{INF, INF, INF, INF, 4, 11, INF, INF}, | |
{INF, INF, INF, INF, 9, 5, 16, INF}, | |
{INF, INF, INF, INF, INF, INF, 2, INF}, | |
{INF, INF, INF, INF, INF, INF, INF, 18}, | |
{INF, INF, INF, INF, INF, INF, INF, 13}, | |
{INF, INF, INF, INF, INF, INF, INF, 2}}; | |
System.out.println(shortestDistance(graph)); | |
} | |
static int shortestDistance(int[][] graph){ | |
int[] distance = new int[N]; | |
distance[N - 1] = 0; | |
for(int i = N - 2; i >= 0; i--){ | |
distance[i] = INF; | |
for(int j = i + 1; j < N; j++){ | |
// no edge condition | |
if(graph[i][j] == INF){ | |
continue; | |
} | |
// recursive equation | |
distance[i] = Math.min(distance[i], graph[i][j] + distance[j]); | |
} | |
} | |
return distance[0]; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
static final int V = 5; | |
public static void main(String[] args) { | |
int graph[][] = {{ 0, 2, 0, 6, 0 }, | |
{ 2, 0, 3, 8, 5 }, | |
{ 0, 3, 0, 0, 7 }, | |
{ 6, 8, 0, 0, 9 }, | |
{ 0, 5, 7, 9, 0 }}; | |
primsMst(graph); | |
} | |
static int selectMinVertex(int[] value, boolean[] isIncluded){ | |
int vertex = -1; | |
int minimum = Integer.MAX_VALUE; | |
for(int i = 0; i < V; i++){ | |
if(isIncluded[i] == false && value[i] < minimum){ | |
vertex = i; | |
minimum = value[i]; | |
} | |
} | |
return vertex; | |
} | |
static void printMST(int parent[], int graph[][]) | |
{ | |
System.out.println("Edge \tWeight"); | |
for (int i = 1; i < V; i++) | |
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]); | |
} | |
static void primsMst(int[][] graph){ | |
// stores MST, (1->2) parent of 2 is 1 so we'll store 1 at index 2 in parent | |
int[] parent = new int[V]; | |
// used for edge relaxation | |
int[] value = new int[V]; | |
// fill the array with infinity | |
Arrays.fill(value,Integer.MAX_VALUE); | |
// true -> vertex is included in MST | |
boolean[] isIncluded = new boolean[V]; | |
// initialise the array with false. | |
Arrays.fill(isIncluded, Boolean.FALSE); | |
// start node has no parent | |
parent[0] = -1; | |
// so that start node gets picked first | |
value[0] = 0; | |
for(int i = 0; i < V - 1; i++){ | |
// it selects best vertex by applying greedy method | |
int u = selectMinVertex(value, isIncluded); | |
isIncluded[u] = true; | |
// relaxing adjacent vertices | |
for(int j = 0; j < V; j++){ | |
/** | |
* edge is present from u to j. | |
* vertex j is not included in MST. | |
* edge weight is smaller than current edge weight | |
*/ | |
if(graph[u][j] != 0 && isIncluded[j] == false && graph[u][j] < value[j]){ | |
value[j] = graph[u][j]; | |
parent[j] = u; | |
} | |
} | |
} | |
// print the constructed MST | |
printMST(parent, graph); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public int[] sortArray(int[] nums) { | |
quickSort(nums, 0, nums.length - 1); | |
return nums; | |
} | |
/** | |
* [5, 7, 6, 1, 3, 2, 4] | |
* p = 0(index of first element of first sorted list) | |
* r = 7(index of last element of second sorted list) and it will be the initial pivot | |
* after first pass the array will look something like this [1, 3, 2, 4, 7, 6, 5] | |
*/ | |
public int partition(int[] nums, int p, int r){ | |
// last element of the array | |
int x = nums[r]; | |
// i will start at index -1 | |
int i = p - 1; | |
/** | |
* loop through the array and move all the smaller elements | |
* to the left of the last element and larger elements to the | |
* right of the last element. | |
*/ | |
for(int j = p; j < r; j++){ | |
if(nums[j] <= x){ | |
i++; | |
// swap nums[i] with nums[j] | |
int temp = nums[i]; | |
nums[i] = nums[j]; | |
nums[j] = temp; | |
} | |
} | |
// swap the last element with its correct position | |
int temp = nums[i + 1]; | |
nums[i + 1] = nums[r]; | |
nums[r] = temp; | |
// return the pivot index | |
return i + 1; | |
} | |
public void quickSort(int[] nums, int p, int r){ | |
if(p < r){ | |
int q = partition(nums, p, r); | |
quickSort(nums, p, q - 1); | |
quickSort(nums, q + 1, r); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main { | |
public static void main(String[] args) { | |
int[] set = {6, 3, 2, 1}; | |
int sum = 5; | |
int length = set.length; | |
if(isSubsetSum(set, sum, length)) System.out.println("Found a subset with given sum"); | |
else System.out.println("No subset with given sum"); | |
} | |
static boolean isSubsetSum(int[] set, int sum, int length){ | |
boolean[][] dp = new boolean[length + 1][sum + 1]; | |
// if sum == 0 then it is always true | |
for(int i = 0; i <= length; i++) dp[i][0] = true; | |
// if set is empty | |
for(int j = 1; j <= sum; j++) dp[0][j] = false; | |
for(int i = 1; i <= length; i++){ | |
for(int j = 1; j <= sum; j++){ | |
// if sum required is less than element | |
if(j < set[i - 1]) dp[i][j] = dp[i - 1][j]; | |
else dp[i][j] = dp[i - 1][j - set[i - 1]] || dp[i - 1][j]; | |
} | |
} | |
return dp[length][sum]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment