frankierock
BAN USERIt's actually important to note that the input is a linked list, I think the question was asked. "Write a function to test if a singularly linked list is a palindrome using constant space."
The strategy for this is as follows:
1) Create a stack which to hold 1/2 of the first linked list.
2) Create two nodes, one is going 2x as the first and once the faster node reaches end. The slower node should be exactly at middle.
3) Collect the nodes in a stack until the faster node reaches the end.
4) Start popping the stack and match it against the values in the rest of the nodes.
public static boolean isPalindrome(CharNode root) {
// trivial case
if (root == null)
return false;
Stack<CharNode> stack = new Stack<>();
CharNode end = root.next;
CharNode mid = root;
while (true) {
stack.add(mid);
mid = mid.next;
if (end == null) {
// eject the middle element
stack.pop();
break;
}
else if (end.next == null)
break;
end = end.next.next;
}
while (!stack.isEmpty() && mid != null) {
CharNode node = stack.pop();
if (mid.value != node.value)
return false;
mid = mid.next;
}
return mid == null && stack.isEmpty();
}
For this question, you want to use DFS using post order traversal - that is visit left, right and self.
To calculate the height, the stack will always represent a *single* path of the tree. Therefore, during the self node valuation, just take the maximum of current stack size and the max thus far.
public int getHeight(Node node) {
if (node == null)
return -1;
int max = -1;
Stack<Node> stack = new Stack<Node>();
stack.add(node);
while (!stack.isEmpty()) {
Node current = stack.peek();
if (current.left != null) {
stack.add(current.left);
continue;
}
if (current.right != null) {
stack.add(current.right);
continue;
}
max = Math.max(max, stack.size() - 1);
stack.pop();
}
return max;
}
For the N-ary tree, it's bit tricky. You want to use the same strategy for the BST DFS, however since there is N number of children, you must keep track of the nodes that's visited or keep an index on each children node that you're processing.
public int height(GraphNode node) {
Set<GraphNode> visitedNodeSet = new HashSet<>();
Stack<GraphNode> stack = new Stack<GraphNode>();
int max = -1;
if (node == null)
return max;
while (!stack.isEmpty()) {
GraphNode currentNode = stack.peek();
for (GraphNode childNode : currentNode.children()) {
if (!visitedNodeSet.contains(childNode)) {
stack.add(childNode);
visitedNodeSet.add(childNode);
continue;
}
}
max = Math.max(max, stack.height() - 1);
stack.pop();
}
return max;
}
On a side note, it's pretty terrible they asked to use a stack. It's so much less code to do it recursively.
- frankierock September 26, 2014They're looking for O(log(value)) performance. Here's recursive and iterative versions.
public static int square1(int value) {
int multiplier = value;
int original = value;
boolean odd = value % 2 != 0;
while (multiplier > 1) {
value <<= 1;
multiplier /= 2;
}
return odd ? value + original : value;
}
public static int square(int value) {
return square(value, value);
}
public static int square(int value, int multiplier) {
if (multiplier == 1) {
return value;
}
if (multiplier % 2 == 0)
return square (value << 1, multiplier / 2);
return square(value << 1, multiplier / 2) + value;
}
Straight forward version
public static int square(int value) {
return square(value, value);
}
public static int square(int value, int multiplier) {
if (multiplier == 1) {
return value;
}
if (multiplier % 2 == 0)
return square (value << 1, multiplier / 2);
return square(value << 1, multiplier / 2) + value;
}
Here's both recursion and DP
public class MaxPath {
public int maxPathRecurse(int[][] path, int x, int y) {
if (x < 0 || y < 0 || y >= path.length || path[y].length >= x)
return 0;
return Math.max(path[y][x + 1], path[y + 1][x]) + path[y][x];
}
public int maxPathDP(int[][] maxPath) {
int max = Integer.MIN_VALUE;
for (int y = 0 ; y < maxPath.length ; y++) {
for (int x = 0 ; x < maxPath[y].length ; x++) {
int top = y - 1 > 0 ? maxPath[y - 1][x] : 0;
int left = x - 1 > 0 ? maxPath[y][x - 1] : 0;
maxPath[y][x] = Math.max(top, left);
max = Math.max(maxPath[y][x], max);
}
}
return max;
}
}
public class FindPath {
public class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public boolean findPath(Point start, Point end, Point current, char[][] map) {
// No path here
if (current.y < 0 || current.y >= map.length || current.x < 0 || map[current.y].length <= current.x || map[current.y][current.x] == 'x') {
return false;
}
if (current.x == end.x && current.y == end.y) {
return true;
}
return findPath(start, end, new Point(current.x - 1, current.y), map) ||
findPath(start, end, new Point(current.x + 1, current.y), map) ||
findPath(start, end, new Point(current.x, current.y + 1), map) ||
findPath(start, end, new Point(current.x, current.y - 1), map);
}
}
Here's an algorithm that combine LCD with distance between two nodes.
public static Integer nodeDistance(Node root, int targetA, int targetB, int distance) {
if (root == null)
return null;
if (root.data == targetA || root.data == targetB)
return distance;
Integer leftCount = nodeDistance(root.left, targetA, targetB, distance + 1);
Integer rightCount = nodeDistance(root.right, targetA, targetB, distance + 1);
if (leftCount != null && rightCount != null)
return leftCount + rightCount - (2 * distance);
return leftCount == null ? rightCount : leftCount;
}
For each task, check if it can fit into any server.
DFS as long as tasks fit
- frankierock October 12, 2014