public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] magcount = new int[26];
Arrays.fill(magcount, 0);
for (char c : magazine.toCharArray()) {
magcount[c  'a'] += 1;
}
for (char c : ransomNote.toCharArray()) {
int index = c  'a';
if (magcount[index] == 0) return false;
magcount[index] = 1;
}
return true;
}
}
diptesh
@diptesh
Posts made by diptesh

Java 13ms O(m + n) time O(1) space solution

RE: The failure rate of a cluster
@StefanPochmann My bad, ,the final loop should just use dp[n 1][i]. It was a typo.

RE: The failure rate of a cluster
Possible dp:
p > probability array of size N
dp[i][j] > Probability that exactly j nodes failed out of the first i nodes.
Hence,dp[i][j] = p[i  1] * dp[i  1][j  1] + (1  p[i]) * dp[i  1][j]; Base cases: dp[1][0] = 1p[0] dp[1][1] = p[0] dp[i][0] = dp[i  1][0]*(1p[0]) double ans = 0; for (int i = n / 2 + 1; i < n; i++) { ans += dp[n][i]; }

RE: Minimal run time scheduler
Can we not look at it as something like an interleaving iterator? Let's say the task counts are as follows:
A3
B5
C2We can simply do an interleaving as follows:
BACBACBABBReturning an interleaved version with round robin interleaving would minimize the cases with a task following itself.

RE: Design Hit Counter
@elmirap why not use ArrayDeque, instead of LinkedList. We get significant performance gain in ArrayDeque as compared to LinkedList.

RE: Count all numbers with unique digits
Please correct me if I am wrong, but this looks like a simple combinatorics problem.
First of all, we only need to consider n <= 9. Because for n >= 10, there has to be a number with repeated digit (Pigeon Hole Principle).
Let f(k) = number of numbers with unique digits if the length of the number is k
f(1) = 10
f(k) = 9 * 9 * 8 * ... (9  k + 2) [The first factor is 9 because a number cannot start with 0].So the code might look like this:
long countUnique(int n) { if (n == 0) return 2; long count = 10; for (int i = 2; i <= Math.min(n, 10); i++) { long num = 9 * 9; for (int j = 1; j <= i  2; j++) { num *= (9  j); } count += num; } return count; }
The time and space complexity is actually O(1).

RE: Longest substring of distinct characters in a stream
I have a question here. The problem description has longest "SUBSEQUENCE" and not "SUBSTRING". The solution given by @elmirap gives us the longest substring. Is it necessary that all characters in a subsequence should be contiguous in the original string? For example, assume the LCS problem from CLRS. We do consider subsequences where characters are noncontiguous in the original String.
In this case wouldn't the best solution be to just get all distinct characters in the stream and be done with it? Have something like a HashSet. If a new guy comes, insert, else do nothing.

RE: Uber find the largest kth element in a data stream
I think the min heap + hash table approach should be fine. One catch: We should remove the hashtable key as soon as the element is removed from heap, because that element can never come back into the heap.
space complexity: O(K)

RE: Follow up about LC problems minimum path sum
This is an easy one. For every cell in the grid, just keep a pointer to its predecessor. After the entire grid has been traversed, traverse the predecessors backwards and you should have the path.
List<String> getShortestPath(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; int[][] dir = new int[m][n]; for (int i = 0; i < m; i++) { Arrays.fill(dir[i], 1); } int[][] dp = new int[m][n]; // Each element in this array would be in {L, N, U} indicating left, no movement, up respectively. char[][] dir = new char[m][n]; dp[0][0] = grid[0][0]; int i,j; for (i = 1; i < m; i++) { dp[i][0] = dp[i  1][0] + grid[i][0]; Arrays.fill(dir[i], 'N'); } for (j = 1; j < n; j++) { dp[0][j] = dp[0][j  1] + grid[0][j]; } for (i = 1; i < m; i++) { for (j = 1; j < n; j++) { if (dp[i  1][j] < dp[i][j  1]) { dp[i][j] = dp[i  1][j] + grid[i][j]; dir[i][j] = 'L'; } else { dp[i][j] = dp[i][j  1] + grid[i][j]; dir[i][j] = 'R'; } } } List<String> path = new ArrayList<String>(); int x = m  1; int y = n  1; while (dir[x][y] != 'N') { path.add(0, x + "," + y); if (dir[x][y] == 'U') { x; } else { y; } } path.add(x + "," + y); return path }