damien5314
BAN USER
Comments (5)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Java solution for minimum height tree question.
private static <T> Node<T> getBalancedRoot(Node<T> node) {
// Variables to cache the longest and second longest adjacent paths
Stack<Node<T>> longest = new Stack<>();
Stack<Node<T>> longest2 = new Stack<>();
// Loop through each adjacent node
for (Node<T> connection : node.adjacent) {
// Get the longest path for that child node
Stack<Node<T>> childPath = getLongestPath(connection, node);
// Adjust cached longest paths accordingly
if (childPath.size() > longest.size()) {
longest2 = longest;
longest = childPath;
} else if (childPath.size() > longest2.size()) {
longest2 = childPath;
}
}
// Set the returned root node to our originating node, for now
Node<T> root = node;
int diff = longest.size()  longest2.size();
// If the difference in size between the adjacent paths is more than 1 node, we need to rebalance
while (diff > 1) {
// This is equivalent to moving one node over, e.g.
// 5 3 9 1 (7) 4 2  Difference = 4  2 = 2
// becomes
// 5 3 9 (1) 7 4 2  Difference = 3  3 = 0
root = longest.pop();
diff = 2;
}
// The node at the start of the longest path is now the root, return it
return root;
}
private static <T> Stack<Node<T>> getLongestPath(Node<T> node, Node<T> previous) {
Stack<Node<T>> longestPath = new Stack<>();
if (!node.adjacent.isEmpty()) {
for (Node<T> adjacent : node.adjacent) {
if (adjacent == previous) continue; // Prevent circular loop
Stack<Node<T>> thisLongest = getLongestPath(adjacent, node);
if (thisLongest.size() > longestPath.size()) {
longestPath = thisLongest;
}
}
}
longestPath.add(node);
return longestPath;
}

damien5314
November 30, 2015 Comment hidden because of low score. Click to expand.
0
of 0 vote
@Scott: That is one way to put it, but assuming this is an undirected graph you don't really get specific pointers to the parent and children like you would in a real tree data structure. Just an adjacency list or matrix for each node and you have to find which node would best serve as the root to reduce the height of a depthfirst search to a minimum.
Approach 2 is pretty interesting, I will definitely try to implement this and post my solution as graphs are my weakness :(
Comment hidden because of low score. Click to expand.
0
of 0 vote
Pretty similar to what others have posted.
int concatenate(int[] nums) {
String[] nums2 = new String[nums.length];
int j = 0;
for (int a : nums) nums2[j++] = String.valueOf(a);
Comparator<String> c = (s1, s2) > {
for (int i = 0; i < Math.max(s1.length(), s2.length()); i++) {
int i1 = Math.min(s1.length()1, i);
int i2 = Math.min(s2.length()1, i);
char n1 = s1.charAt(i1);
char n2 = s2.charAt(i2);
if (n1 != n2) return n2  n1;
}
return 0;
};
Arrays.sort(nums2, c);
StringBuilder result = new StringBuilder();
for (String s : nums2) result.append(s);
return Integer.valueOf(result.toString());
}

damien5314
November 23, 2015 Comment hidden because of low score. Click to expand.
0
of 0 vote
public class TransformWithDictionary {
public static Integer getMinTransformations(String[] dictionary, String start, String end) {
// Construct Map of words to a Set of their adjacent words in the dictionary
Map<String, Set<String>> adjacent = new HashMap<>();
for (String s : dictionary) {
Set<String> adjacentWords = new HashSet<>();
for (String s2 : dictionary) {
if (s == s2) continue;
if (isOneEditAway(s, s2)) adjacentWords.add(s2);
}
adjacent.put(s, adjacentWords);
}
return getMinTransformations(adjacent, start, end, null, 0);
}
/**
* Checks if start can be transformed into end by changing no more than one letter
*/
public static boolean isOneEditAway(String start, String end) {
if (start == null  end == null) return false;
int edits = 0;
int index = 0;
while (edits < 2 && index < end.length()) {
if (start.charAt(index) != end.charAt(index)) edits++;
index++;
}
return edits == 1;
}
public static Integer getMinTransformations(Map<String, Set<String>> dictionary, String start, String end,
Integer min, int steps) {
if (min != null && steps == min) return null; // This path is already longer than the min, just return null
Set<String> adjacentWords = dictionary.get(start);
if (adjacentWords == null) return null; // No adjacent words remaining, return null
if (adjacentWords.contains(end)) return 1; // Base case
// Remove the current word from dictionary to prevent an endless loop
dictionary.remove(start);
// Loop through adjacent words looking for min transformation steps
for (String word : adjacentWords) {
Integer result = getMinTransformations(dictionary, word, end, min, steps + 1);
if (result != null) {
min = min == null ? result + 1 : Math.min(min, result + 1);
}
}
// Finally, return the minimum number of transformations we found
return min;
}
public static void main(String[] args) {
String[] dictionary = new String[] {
"cat", "dog", "pog", "bog", "cot", "all", "yew", "nit", "cog", "raw", "sew", "mow", "saw", "was", "pam",
"sam", "lit", "bit", "wit", "vim", "war", "rat", "mat", "log", "cow", "paw" };
System.out.println("pog > dog = " + getMinTransformations(dictionary, "pog", "dog")); // 1
System.out.println("pam > saw = " + getMinTransformations(dictionary, "pam", "saw")); // 2
System.out.println("cat > dog = " + getMinTransformations(dictionary, "cat", "dog")); // 3
System.out.println("sam > lit = " + getMinTransformations(dictionary, "sam", "lit")); // null
}
}

damien5314
November 17, 2015 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Java implementation of Tarjan's algorithm:
 damien5314 December 03, 2015