Skip to content

Commit f5c255e

Browse files
sushant-sinhasushant-sinha
authored
Merge branch 'fishercoder1534:master' into patch-1
2 parents 9017164 + 54a07e0 commit f5c255e

File tree

322 files changed

+9578
-1545
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

322 files changed

+9578
-1545
lines changed

‎README.md

Lines changed: 152 additions & 16 deletions
Large diffs are not rendered by default.

‎build.gradle

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -24,9 +24,9 @@ repositories {
2424

2525
dependencies {
2626
compile 'com.google.code.gson:gson:2.8.0'
27-
compile 'junit:junit:4.12'
27+
compile 'junit:junit:4.13'
2828
compile group: 'org.apache.commons', name: 'commons-collections4', version: '4.0'
29-
testCompile group: 'junit', name: 'junit', version:'4.12'
29+
testCompile group: 'junit', name: 'junit', version:'4.13'
3030

3131
compileOnly 'org.projectlombok:lombok:1.18.12'
3232
annotationProcessor 'org.projectlombok:lombok:1.18.12'

‎database/_1113.sql

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
select extra as report_reason, count(distinct(post_id)) as report_count from Actions where action_date = '2019-07-04' and action = 'report' group by extra;

‎database/_1142.sql

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
--# Write your MySQL query statement below
2+
select ifnull(round(count(distinct session_id)/count(distinct user_id), 2), 0.00)
3+
as average_sessions_per_user
4+
from Activity
5+
where activity_date between '2019-06-28' and '2019-07-27';

‎database/_1371.sql

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
--# Write your MySQL query statement below
2+
select b.employee_id, b.name, count(*) as reports_count, round(avg(a.age)) as average_age
3+
from Employees a join Employees b on a.reports_to = b.employee_id
4+
group by b.employee_id
5+
order by b.employee_id

‎database/_1393.sql

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
select stock_name, sum(
2+
case
3+
when operation = 'Buy' then -price
4+
else price
5+
end
6+
) as capital_gain_loss from Stocks group by stock_name;

‎database/_1596.sql

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
--credit: https://leetcode.com/problems/the-most-frequently-ordered-products-for-each-customer/discuss/861257/simple-and-easy-solution-using-window-function
2+
3+
select customer_id, product_id, product_name from
4+
(
5+
select o.customer_id, o.product_id, p.product_name,
6+
rank() over (partition by customer_id order by count(o.product_id) desc) as ranking
7+
from Orders o
8+
join Products p
9+
on o.product_id = p.product_id
10+
group by customer_id, product_id
11+
) tmp
12+
where ranking = 1
13+
order by customer_id, product_id

‎database/_1729.sql

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
--# Write your MySQL query statement below
2+
select user_id, count(follower_id) as followers_count from followers group by user_id order by user_id;

‎database/_1757.sql

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
--# Write your MySQL query statement below
2+
select product_id from Products where low_fats = 'Y' and recyclable = 'Y';

‎fishercoder_checkstyle.xml

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,8 +55,6 @@
5555
<property name="ignorePattern" value="^package.*|^import.*|a href|href|http://|https://|ftp://"/>
5656
</module>
5757

58-
<module name="AvoidStarImport"/>
59-
6058
<module name="OneTopLevelClass"/>
6159

6260
<module name="NoLineWrap"/>

‎src/main/java/com/fishercoder/common/utils/CommonUtils.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,13 @@ public static void printArray(boolean[] booleans) {
3636
System.out.println();
3737
}
3838

39+
public static void printArray(double[] booleans) {
40+
for (double i : booleans) {
41+
System.out.print(i + ", ");
42+
}
43+
System.out.println();
44+
}
45+
3946
public static void printArray(int[] nums) {
4047
for (int i : nums) {
4148
System.out.print(i + ", ");

‎src/main/java/com/fishercoder/solutions/_1024.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Arrays;
4+
5+
public class _1024 {
6+
public static class Solution1 {
7+
/**
8+
* Greedy
9+
* Time: O(nlogn) where n is the number of clips
10+
* Space: O(1)
11+
*/
12+
public int videoStitching(int[][] clips, int time) {
13+
Arrays.sort(clips, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
14+
int count = 0;
15+
int covered = 0;
16+
for (int i = 0, start = 0; start < time; count++, start = covered) {
17+
for (; i < clips.length && clips[i][0] <= start; i++) {
18+
covered = Math.max(covered, clips[i][1]);
19+
}
20+
if (start == covered) {
21+
return -1;
22+
}
23+
}
24+
return count;
25+
}
26+
}
27+
28+
public static class Solution2 {
29+
/**
30+
* DP
31+
* Time: ?
32+
* Space: ?
33+
*/
34+
public int videoStitching(int[][] clips, int time) {
35+
//TODO: implement it.
36+
return -1;
37+
}
38+
}
39+
}

‎src/main/java/com/fishercoder/solutions/_1025.java

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,14 @@
22

33
public class _1025 {
44
public static class Solution1 {
5+
/**
6+
* After writing out a few examples, beginning from n = 1, up to n = 5, the logic flows out naturally:
7+
* 1. when N deduced to 1, whoever plays now loses because no integers exist between 0 and 1;
8+
* 2. when N deduced to 2, whoever plays now wins because he/she will pick one and the next player is left with nothing to play;
9+
* 3. all numbers N will eventually be deduced to either 1 or 2 depending on whether its odd or even.
10+
*/
511
public boolean divisorGame(int N) {
6-
//TODO: implement it
7-
return false;
12+
return N % 2 == 0;
813
}
914
}
1015
}

‎src/main/java/com/fishercoder/solutions/_1091.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
public class _1091 {
7+
public static class Solution1 {
8+
int[] directions = new int[]{0, 1, 1, 0, -1, 1, -1, -1, 0};
9+
10+
public int shortestPathBinaryMatrix(int[][] grid) {
11+
int m = grid.length;
12+
int n = grid[0].length;
13+
if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
14+
return -1;
15+
}
16+
int minPath = 0;
17+
Queue<int[]> queue = new LinkedList<>();
18+
queue.offer(new int[]{0, 0});
19+
boolean[][] visited = new boolean[m][n];
20+
visited[0][0] = true;
21+
while (!queue.isEmpty()) {
22+
int size = queue.size();
23+
for (int i = 0; i < size; i++) {
24+
int[] curr = queue.poll();
25+
if (curr[0] == m - 1 && curr[1] == n - 1) {
26+
return minPath + 1;
27+
}
28+
for (int j = 0; j < directions.length - 1; j++) {
29+
int newx = directions[j] + curr[0];
30+
int newy = directions[j + 1] + curr[1];
31+
if (newx >= 0 && newx < n && newy >= 0 && newy < n && !visited[newx][newy] && grid[newx][newy] == 0) {
32+
queue.offer(new int[]{newx, newy});
33+
visited[newx][newy] = true;
34+
}
35+
}
36+
}
37+
minPath++;
38+
}
39+
return -1;
40+
}
41+
}
42+
}

‎src/main/java/com/fishercoder/solutions/_1136.java

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.HashSet;
6+
import java.util.LinkedList;
7+
import java.util.List;
8+
import java.util.Map;
9+
import java.util.Queue;
10+
import java.util.Set;
11+
12+
public class _1136 {
13+
public static class Solution1 {
14+
public int minimumSemesters(int n, int[][] relations) {
15+
Map<Integer, Set<Integer>> indegree = new HashMap<>();
16+
for (int[] rel : relations) {
17+
if (!indegree.containsKey(rel[1])) {
18+
indegree.put(rel[1], new HashSet<>());
19+
}
20+
Set<Integer> prereqs = indegree.get(rel[1]);
21+
prereqs.add(rel[0]);
22+
}
23+
Queue<Integer> queue = new LinkedList<>();
24+
Set<Integer> taken = new HashSet<>();
25+
for (int i = 1; i <= n; i++) {
26+
if (!indegree.containsKey(i)) {
27+
queue.offer(i);
28+
taken.add(i);
29+
}
30+
}
31+
int minSemesters = 0;
32+
while (!queue.isEmpty()) {
33+
int size = queue.size();
34+
minSemesters++;
35+
for (int i = 0; i < size; i++) {
36+
Integer curr = queue.poll();
37+
for (int key : indegree.keySet()) {
38+
Set<Integer> prereqs = indegree.get(key);
39+
if (prereqs.contains(curr)) {
40+
prereqs.remove(curr);
41+
if (prereqs.size() == 0) {
42+
queue.offer(key);
43+
taken.add(key);
44+
}
45+
}
46+
}
47+
}
48+
}
49+
return taken.size() != n ? -1 : minSemesters;
50+
}
51+
}
52+
}

‎src/main/java/com/fishercoder/solutions/_1143.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.fishercoder.solutions;
2+
3+
public class _1143 {
4+
public static class Solution1 {
5+
/**
6+
* credit: https://leetcode.com/problems/longest-common-subsequence/solution/
7+
* <p>
8+
* Recall that there are two different techniques we can use to implement a dynamic programming solution; memoization and tabulation.
9+
* <p>
10+
* Memoization is where we add caching to a function (that has no side effects). In dynamic programming, it is typically used on recursive functions for a top-down solution that starts with the initial problem and then recursively calls itself to solve smaller problems.
11+
* Tabulation uses a table to keep track of subproblem results and works in a bottom-up manner: solving the smallest subproblems before the large ones, in an iterative manner. Often, people use the words "tabulation" and "dynamic programming" interchangeably.
12+
* <p>
13+
* For most people, it's easiest to start by coming up with a recursive brute-force solution and then adding memoization to it. After that, they then figure out how to convert it into an (often more desired) bottom-up tabulated algorithm.
14+
*/
15+
public int longestCommonSubsequence(String text1, String text2) {
16+
if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
17+
return 0;
18+
}
19+
int m = text1.length();
20+
int n = text2.length();
21+
int[][] dp = new int[m + 1][n + 1];
22+
for (int i = 0; i < m; i++) {
23+
for (int j = 0; j < n; j++) {
24+
dp[i][j] = -1;
25+
}
26+
}
27+
return topDownRecursiveSolve(dp, 0, 0, text1, text2);
28+
}
29+
30+
private int topDownRecursiveSolve(int[][] dp, int i, int j, String text1, String text2) {
31+
if (dp[i][j] != -1) {
32+
return dp[i][j];
33+
}
34+
//option1: we don't include text1.charAt(i) in the optimal solution
35+
int option1 = topDownRecursiveSolve(dp, i + 1, j, text1, text2);
36+
//option2: we do include text1.charAt(i) in the optimal solution as long as a match in text2 at or after j does exist
37+
int firstOccurence = text2.indexOf(text1.charAt(i), j);
38+
int option2 = 0;
39+
if (firstOccurence != -1) {
40+
option2 = 1 + topDownRecursiveSolve(dp, i + 1, firstOccurence + 1, text1, text2);
41+
}
42+
dp[i][j] = Math.max(option1, option2);
43+
return dp[i][j];
44+
}
45+
}
46+
}

‎src/main/java/com/fishercoder/solutions/_1145.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
public class _1145 {
6+
public static class Solution1 {
7+
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
8+
if (root == null) {
9+
return false;
10+
}
11+
12+
if (root.val == x) {
13+
// 3 possible paths to block, left, right, parent
14+
int leftCount = countNodes(root.left);
15+
int rightCount = countNodes(root.right);
16+
int parent = n - (leftCount + rightCount + 1);
17+
18+
// possible to win if no. of nodes in 1 path is > than sum of nodes in the other 2 paths
19+
return parent > (leftCount + rightCount) || leftCount > (parent + rightCount) || rightCount > (parent + leftCount);
20+
}
21+
return btreeGameWinningMove(root.left, n, x) || btreeGameWinningMove(root.right, n, x);
22+
}
23+
24+
private int countNodes(TreeNode root) {
25+
if (root == null) {
26+
return 0;
27+
}
28+
return countNodes(root.left) + countNodes(root.right) + 1;
29+
}
30+
}
31+
}

0 commit comments

Comments
 (0)