Skip to content

Commit 9088b34

Browse files
EdwardTangEdwardTang
authored
smartnews-onsite retrospective (#4)
* smartnews-onsite retrospective * yoyo-phone-onsite
1 parent aebacda commit 9088b34

12 files changed

+1168
-0
lines changed

‎src/main/java/com/company/google/topmedium/leet84/_84LargestRectangleHistogram.java

+72
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.company.google.topmedium.leet84;
2+
3+
import static org.junit.Assert.assertEquals;
4+
5+
import java.util.Deque;
6+
import java.util.LinkedList;
7+
8+
public class _84LargestRectangleHistogram {
9+
10+
/**
11+
* Leetcode 84: Largest Rectangle in histograms
12+
*
13+
* <p>Given n non-negative integers representing the histogram's bar height where the width of
14+
* each bar is 1, find the area of largest rectangle in the histogram.
15+
*
16+
* <p>Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest
17+
* rectangle is shown in the shaded area, which has area = 10 unit.
18+
*
19+
* <p>For example, Given heights = [2,1,5,6,2,3], return 10.
20+
*
21+
* <p>C:
22+
*
23+
* <p>What is maximum area supported in this quesiont? Within Integer' data range
24+
*
25+
* <p>Is there any negative height? A:
26+
*
27+
* <p>assume the maximum area is less than Integer.MAX_VALUE
28+
*
29+
* <p>R:
30+
*
31+
* <p>Use a stack to maintain a series of monolithtic increasing histrograms's index. Only
32+
* monolithtic increasing histogram can produce more rectangle area.
33+
*
34+
* <p>When we meet decrease histogram: heights[i - 1] > heights[i], pop the stack top, and
35+
* calculate the area with the following formula: area = (i - stock[top - 1] - 1) *
36+
* heights[stack[top]] T:
37+
*
38+
* <p>null, empty -> 0
39+
*
40+
* <p>[1,2,3,4] -> 6
41+
*
42+
* <p>[1,2,3,4,3] -> 9
43+
*
44+
* <p>[3,2,1] -> 4
45+
*/
46+
public static int largestRectangleArea(int[] heights) {
47+
if (heights == null || heights.length == 0) {
48+
return 0;
49+
}
50+
Deque<Integer> stack = new LinkedList<>();
51+
int maxArea = 0;
52+
for (int i = 0; i <= heights.length; i++) {
53+
int cur = (i == heights.length) ? 0 : heights[i];
54+
while (!stack.isEmpty() && heights[stack.peekLast()] >= cur) {
55+
int height = heights[stack.pollLast()];
56+
int left = stack.isEmpty() ? 0 : stack.peekLast() + 1;
57+
maxArea = Math.max(maxArea, height * (i - left));
58+
}
59+
stack.addLast(i);
60+
}
61+
return maxArea;
62+
}
63+
64+
public static void main(String[] args) {
65+
assertEquals(0, largestRectangleArea(null));
66+
assertEquals(0, largestRectangleArea(new int[] {}));
67+
assertEquals(1, largestRectangleArea(new int[] {1}));
68+
assertEquals(6, largestRectangleArea(new int[] {1, 2, 3, 4}));
69+
assertEquals(9, largestRectangleArea(new int[] {1, 2, 3, 4, 3}));
70+
assertEquals(4, largestRectangleArea(new int[] {3, 2, 1}));
71+
}
72+
}

‎src/main/java/com/company/google/topmedium/leet84/uptake/_85MaxRectangleMatrix.java

+78
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package com.company.google.topmedium.leet84.uptake;
2+
3+
4+
import static com.company.google.topmedium.leet84._84LargestRectangleHistogram.largestRectangleArea;
5+
import static org.junit.Assert.assertEquals;
6+
7+
public class _85MaxRectangleMatrix {
8+
9+
/**
10+
* 85. Maximal Rectangle
11+
*
12+
* <p>Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only
13+
* 1's and return its area.
14+
*
15+
* <p>For example, given the following matrix:
16+
*
17+
* <p>1 0 1 0 0
18+
* 1 0 1 1 1
19+
* 1 1 1 1 1
20+
* 1 0 0 1 0
21+
*
22+
* Return 6.
23+
* <p>C:
24+
*
25+
* <p>What is the data type of the elements? char or int? -> char
26+
*
27+
* <p>How big can the matrix be? The area of the matrix can be fit into memory A:
28+
*
29+
* <p>The matrix cannot be null/ empty., and at least has one element. R:
30+
*
31+
* <p>1. rows as X axis， and columns as Y axis. The 1 rectangle can be considered as the a series
32+
* of histograms based on current row
33+
*
34+
* <p>Thus the matrix can be converted to 4 histograms:
35+
*
36+
* <p>1st row: [1, 0 , 1, 0, 0]
37+
*
38+
* <p>2nd row: [2, 0 , 2, 1, 1]
39+
*
40+
* <p>3rd row: [3, 1 , 3, 2, 2]
41+
*
42+
* <p>4th row: [4, 0 , 0, 3, 0]
43+
*
44+
* <p>2. Apply the monolithic increasing stack to get the max area among the histogram
45+
* T: <p>[[1]], problem example
46+
*/
47+
48+
public static int maxRetangleArea(char[][] A) {
49+
int[][] H = new int[A.length][A[0].length];
50+
for (int row = 0; row < A.length; row++) {
51+
for (int col = 0; col < A[0].length; col++) {
52+
if (row == 0) {
53+
H[row][col] = (A[row][col] - '0');
54+
} else {
55+
H[row][col] = (A[row][col] - '0') == 0 ? 0 : (H[row - 1][col]) + 1;
56+
}
57+
}
58+
}
59+
int maxArea = 0;
60+
for (int[] heights : H) {
61+
maxArea = Math.max(maxArea, largestRectangleArea(heights));
62+
}
63+
return maxArea;
64+
}
65+
66+
public static void main(String[] args) {
67+
char[][] test1 = new char[][] {{'1'}};
68+
char[][] test2 =
69+
new char[][] {
70+
{'1', '0', '1', '0', '0'},
71+
{'1', '0', '1', '1', '1'},
72+
{'1', '1', '1', '1', '1'},
73+
{'1', '0', '0', '1', '0'}
74+
};
75+
assertEquals(1, maxRetangleArea(test1));
76+
assertEquals(6, maxRetangleArea(test2));
77+
}
78+
}

‎src/main/java/com/company/google/topmedium/maxsquare/similar/_764LargestPlusSign.java

+73
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.company.google.topmedium.maxsquare.similar;
2+
3+
4+
import static org.junit.Assert.assertEquals;
5+
6+
import java.util.Arrays;
7+
8+
class _764LargestPlusSign {
9+
10+
/**
11+
* In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the
12+
* given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the
13+
* grid? Return the order of the plus sign. If there is none, return 0.
14+
*
15+
* <p>An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4
16+
* arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the
17+
* diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the
18+
* relevant area of the plus sign is checked for 1s.
19+
*
20+
* <p>Input: N = 5, mines = [[4, 2]] Output: 2 Explanation: 11111 11111 11111 11111 11011 In the
21+
* above grid, the largest plus sign can only be order 2.
22+
*/
23+
public static int orderOfLargestPlusSign(int N, int[][] mines) {
24+
int[][] dp = new int[N][N];
25+
26+
for (int[] row : dp) {
27+
Arrays.fill(row, N);
28+
}
29+
30+
for (int[] m : mines) {
31+
dp[m[0]][m[1]] = 0;
32+
}
33+
34+
for (int i = 0; i < N; i++) {
35+
36+
int left = 0;
37+
for (int j = 0; j < N; j++) {
38+
left = dp[i][j] == 0 ? 0 : left + 1;
39+
dp[i][j] = Math.min(dp[i][j], left);
40+
}
41+
42+
int right = 0;
43+
for (int j = N - 1; j >= 0; j--) {
44+
right = dp[i][j] == 0 ? 0 : right + 1;
45+
dp[i][j] = Math.min(dp[i][j], right);
46+
}
47+
48+
int top = 0;
49+
for (int j = 0; j < N; j++) {
50+
top = dp[j][i] == 0 ? 0 : top + 1;
51+
dp[j][i] = Math.min(dp[j][i], top);
52+
}
53+
54+
int bottom = 0;
55+
for (int j = N - 1; j >= 0; j--) {
56+
bottom = dp[j][i] == 0 ? 0 : bottom + 1;
57+
dp[j][i] = Math.min(dp[j][i], bottom);
58+
}
59+
}
60+
61+
int res = 0;
62+
for (int i = 0; i < N; i++) {
63+
for (int j = 0; j < N; j++) {
64+
res = Math.max(res, dp[i][j]);
65+
}
66+
}
67+
return res;
68+
}
69+
70+
public static void main(String[] args) {
71+
assertEquals(2, orderOfLargestPlusSign(5, new int[][] {{4, 2}}));
72+
}
73+
}

‎src/main/java/com/company/smartnews/onsite/DifferentWaysToAddParenthesis.java

+59
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.company.smartnews.onsite;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class DifferentWaysToAddParenthesis {
7+
8+
public static void main(String[] args) {
9+
String test1 = "2-1-1";
10+
System.out.println(findWays(test1).toString());
11+
String test2 = "2*3-4*5";
12+
System.out.println(findWays(test2).toString());
13+
}
14+
15+
public static List<Integer> findWays(String input) {
16+
String[] nums = input.split("[*,+,-]");
17+
char[] operators = input.replaceAll("[0-9]", "").toCharArray();
18+
List[][] mem = new List[nums.length][nums.length];
19+
return dfs(nums, operators, 0, nums.length - 1, mem);
20+
}
21+
22+
private static List<Integer> dfs(
23+
String[] nums, char[] operators, int start, int end, List[][] mem) {
24+
if (mem[start][end] != null) {
25+
return mem[start][end];
26+
}
27+
28+
if (start == end) {
29+
List<Integer> baseCase = new ArrayList<>();
30+
baseCase.add(Integer.parseInt(nums[start]));
31+
mem[start][end] = baseCase;
32+
return baseCase;
33+
}
34+
35+
List<Integer> result = new ArrayList<>();
36+
for (int k = start; k < end; k++) {
37+
List<Integer> group1 = dfs(nums, operators, start, k, mem);
38+
List<Integer> group2 = dfs(nums, operators, k + 1, end, mem);
39+
for (Integer num1 : group1) {
40+
for (Integer num2 : group2) {
41+
result.add(calcuate(operators[k], num1, num2));
42+
}
43+
}
44+
}
45+
mem[start][end] = result;
46+
return result;
47+
}
48+
49+
private static Integer calcuate(char operator, Integer nums1, Integer nums2) {
50+
switch (operator) {
51+
case '*':
52+
return nums1 * nums2;
53+
case '+':
54+
return nums1 + nums2;
55+
default:
56+
return nums1 - nums2;
57+
}
58+
}
59+
}

0 commit comments

Comments
 (0)