HackWithInfy Java Practice Set
(Top 5 Frequently Asked Coding Problems)
------------------------------------------
1) Largest Rectangle in Histogram
------------------------------------------
import [Link].*;
public class Main {
public static int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int n = [Link];
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (![Link]() && h < heights[[Link]()]) {
int height = heights[[Link]()];
int width = [Link]() ? i : i - [Link]() - 1;
maxArea = [Link](maxArea, height * width);
}
[Link](i);
}
return maxArea;
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] heights = new int[n];
for (int i = 0; i < n; i++) heights[i] = [Link]();
[Link](largestRectangleArea(heights));
}
}
------------------------------------------
2) 0-1 Knapsack
------------------------------------------
import [Link].*;
public class Main {
public static int knapSack(int W, int wt[], int val[], int n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i - 1] <= w)
dp[i][w] = [Link](val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i -
1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int W = [Link]();
int[] wt = new int[n];
int[] val = new int[n];
for (int i = 0; i < n; i++) wt[i] = [Link]();
for (int i = 0; i < n; i++) val[i] = [Link]();
[Link](knapSack(W, wt, val, n));
}
}
------------------------------------------
3) First Non-Repeating Character
------------------------------------------
import [Link].*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s = [Link]();
int[] freq = new int[256];
for (char c : [Link]()) freq[c]++;
for (char c : [Link]()) {
if (freq[c] == 1) {
[Link](c);
return;
}
}
[Link](-1);
}
}
------------------------------------------
4) Longest Word from Dictionary
------------------------------------------
import [Link].*;
public class Main {
public static boolean isSubsequence(String s, String word) {
int i = 0, j = 0;
while (i < [Link]() && j < [Link]()) {
if ([Link](i) == [Link](j)) j++;
i++;
}
return j == [Link]();
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s = [Link]();
int n = [Link]();
[Link]();
List<String> words = new ArrayList<>();
for (int i = 0; i < n; i++) [Link]([Link]());
String ans = "";
for (String word : words) {
if (isSubsequence(s, word)) {
if ([Link]() > [Link]() ||
([Link]() == [Link]() && [Link](ans) < 0))
ans = word;
}
}
[Link](ans);
}
}
------------------------------------------
5) Sliding Window Maximum
------------------------------------------
import [Link].*;
public class Main {
public static List<Integer> maxSlidingWindow(int[] nums, int k) {
Deque<Integer> dq = new ArrayDeque<>();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < [Link]; i++) {
if (![Link]() && [Link]() <= i - k)
[Link]();
while (![Link]() && nums[[Link]()] <= nums[i])
[Link]();
[Link](i);
if (i >= k - 1)
[Link](nums[[Link]()]);
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link](), k = [Link]();
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = [Link]();
List<Integer> ans = maxSlidingWindow(nums, k);
for (int x : ans) [Link](x + " ");
}
}