Acarus
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
O(N) dynamic programming solution:
Let dp[i][0]  answer for first i elements with no ith element included,
dp[i][1]  answer for first i elements with ith element included.
Then dp[i][0] = max(dp[i  1][0], dp[i  1][1])  if last element is not included lets select max from 2 possible answers for i  1.
dp[i][1] = d[i  1][0] + a[i]  select answer when prev is not included + current value.
Finally, answer is max(dp[n][1], dp[n][0]).
Here is implementation in Java:
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
int[][] dp = new int[n + 1][2];
for (int i = 1; i <= n; i++) {
dp[i][1] = dp[i  1][0] + arr[i  1];
dp[i][0] = Math.max(dp[i  1][0], dp[i  1][1]);
}
out.println(Math.max(dp[n][1], dp[n][0]));

Acarus
November 20, 2016 Comment hidden because of low score. Click to expand.
0
of 0 vote
Solution with O(N) time and O(1) memory (modifying tree):
Let's convert binary tree into a linked list where a right link points to the next element. And print all elements in a linked list.
import java.io.*;
import java.util.*;
public class Main {
static class TreeNode {
int x;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
this.x = x;
}
}
static class Result {
TreeNode start;
TreeNode end;
public Result(TreeNode start, TreeNode end) {
this.start = start;
this.end = end;
}
}
private void solve(TreeNode root) {
Result res = flatten(root);
TreeNode curr = res.start;
while (curr != null) {
System.out.print(curr.x + " ");
curr = curr.right;
}
System.out.println();
}
private Result flatten(TreeNode root) {
if (root == null  (root.left == null && root.right == null)) {
return new Result(root, root);
}
if (root.left == null) {
Result right = flatten(root.right);
right.end.right = root;
root.right = null;
return new Result(right.start, root);
} else if (root.right == null) {
Result left = flatten(root.left);
left.end.right = root;
root.right = null;
return new Result(left.start, root);
} else {
Result left = flatten(root.left);
Result right = flatten(root.right);
left.end.right = right.start;
right.end.right = root;
root.right = null;
return new Result(left.start, root);
}
}
}

Acarus
November 17, 2016 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Could be solved with self join:
 Acarus November 22, 2016select distinct(a.email) from emails a join emails b on a.email=b.email and a.id!=b.id;