ajit@ajitk.in
BAN USERThis is standard dynamic programing problem. You can reach any cell (x,y) from either (x-1, y) or (x, y-1).
f(x, y) = val[x,y] + Max(f(x-1, y), f(x, y-1))
If you code it recursively you can solve it in O(nm) time and O(nm) space as mentioned by divm01986. If you solve it iteratively you can do it in O(n) space. If you solve column by column, you can store last computed column. So for any (x,y) you just need to keep track of last val (x-1, y).
int max(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int[] lastCol = new int[grid.length];
for (int j=0; j < grid[0].length; j++) {
int lastVal = 0;
for (int i=0; i < grid.length; i++) {
lastVal = Math.max(lastCol[i], lastVal) + grid[i][j];
lastCol[i] = lastVal;
}
}
return lastCol[grid.length - 1];
}
This is a system design question. highscalability. com/blog/2013/7/8/the-architecture-twitter-uses-to-deal-with-150m-active-users.html is the best resource.
- ajit@ajitk.in April 24, 2016Given head, reverse rest of list and then add head at the end.
private static Node reverse(Node node) {
if (node == null || node.next == null) {
return node;
}
Node newHead = reverse(node.next);
node.next.next = node;
node.next = null;
return newHead;
}
Here is the code. Binary numbers are much faster to manipulate than number in base 10.
Each character is taking 2 bits here:
public Set<String> findRepeated(String s) {
if (s == null || s.length() < 10) {
return Collections.emptySet();
}
Map<Character, Integer> map = new HashMap<>();
map.put('A', 0);
map.put('C', 1);
map.put('G', 2);
map.put('T', 3);
Set<Integer> visited = new HashSet<>();
Set<String> result = new HashSet<>();
int mask = (1 << 20) -1; //111...11 (20 times)
int number = 0;
for (int i = 0; i < s.length(); i++) {
if (i < 9) {
number = (number << 2) + map.get(s.charAt(i));
} else {
number = (number << 2) + map.get(s.charAt(i));
//make sure number is only 20 bits
number = number & mask;
if (visited.contains(number)) {
result.add(s.substring(i - 9, i + 1));
}
visited.add(number);
}
}
return result;
}
If you tweak the problem and replace A, T, G and C by 0, 1, 2, 3 problem is comparatively easy.
Problem reduces to finding repeated 10 digit number. Adding one digit and removing first digit in a number is relatively much easier than adding new char to string and computing hash code each time.
How are you removing c from bacdbcb?
- ajit@ajitk.in September 29, 2015public Node successor(Node root, int value) {
Node curr = root;
Node result = null;
while (curr != null) {
if (curr.value <= value) {
curr = curr.right;
} else {
result = curr;
curr = curr.left;
}
}
return result;
}
yeah, simple recursive solution.
S(k) = max(S(k-2) + a[k], S(k-1).
public int sum(int[] input) {
return sum(0, input)
}
private int sum(int index, int[] input) {
if (index >= input.length) return 0;
return Math.max(
sum(index+1, input),
sum(index+2, input) +input[index]
);
}
If you bother about printing subsequeunce also, you can pass a list and add input[index] to list if sum(index+2, input) is greater.
Only problem with the recursive solution is you would be computing S(k) over and over again. You can get rid of this by memorization.
store S(k) in maxIndex when you compute S(k). So next time you can get S(k) from it. You have to initialize maxIndex with all -1.
public int sum(int index, int[] input, int[] maxIndex) {
if (index >= input.length) return 0;
if (maxIndex[index] != -1) {
return maxIndex[index];
}
int result = Math.max(
sum(index+1, input, maxIndex),
sum(index+2, input, maxIndex) +input[index]
);
maxIndex[index] = result;
return result;
}
You can solve this be creating a weight grid.
w[0][0] .. w[0][n] contains will be mass of n sections.
w[1][0] = w[0][0] + w[0][1]
w[1][1] = w[0][1] + w[0][2]
.....
w[i][j] = w[i-1][j] + w[0][j+i]
where w[i][j] represents wt of section j + j+1... + j+i.
i will vary from 0 to n/2.
Now start traversing weight grid row by row starting from i=n/2.
If you find two weights weights in row which are non overlapping, return it otherwise go to lower row.
Yes, you can do either DFS or BFS and you can find if there is a path between a and b.
- ajit@ajitk.in April 24, 2016Only caveat is, this is a directed graph. Suppose graph is B -> A and if you do a BFS/DFS starting with A you won't be able to reach B.
So you have to do DFS/BFS twice, once starting with A and other starting with B.