## Google Interview Question for Java Developers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

static class Node {
Integer id;
Integer parent;
int weight;
int subweight;
}

public void parseAndCalculate(String filename) throws FileNotFoundException {
List<Node> list = parseFile(filename);
calculate(list);
}

public void calculate(List<Node> list) {
Map<Integer, Node> map = new HashMap<>();
for (Node node : list) {
node.subweight = node.weight;
map.put(node.id, node);
}
for (Node node : list) {
calculate(node.id, null, map);
}
}

public void calculate(Integer currentId, Node prev, Map<Integer, Node> map) {
Node current = map.get(currentId);
if (current == null) {
return;
}
if (prev != null) {
current.subweight += prev.subweight;
}
calculate(current.parent, current, map);
}

public List<Node> parseFile(String filename) throws FileNotFoundException {
Scanner scanner = new Scanner(new File(filename));
scanner.useDelimiter(",|\n");
while (scanner.hasNext()) {
Node node = new Node();
node.id = scanner.nextInt();
String weight = scanner.next();
node.parent = weight.length() < 1 ? null : Integer.valueOf(weight);
node.weight = scanner.nextInt();
}
return list;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Works as long as there are no cycles

static class Node {
int id, weight;
Node parent;
List<Node> children = new ArrayList<>();

Node(int id) {
this.id = id;
}
}

private static final Map<Integer, Node> nodeGraph = new HashMap<>();

public static void parseCsvFile(String fileName) throws IOException {
try (Stream<String> stream = Files.lines(Paths.get(fileName))) {
stream.forEach(s -> parseCsvRow(s));
}
}

private static void parseCsvRow(String row) {
String[] cells = row.split(",");
int id = Integer.parseInt(cells[0]);
int parent = !cells[1].isEmpty()
? Integer.parseInt(cells[1])
: -1;
int weight = Integer.parseInt(cells[2]);

createNode(id, parent, weight);
}

private static void createNode(int id, int parent, int weight) {
Node node = nodeGraph.computeIfAbsent(id, Node::new);
node.weight = weight;

Node parentNode = parent != -1
? nodeGraph.computeIfAbsent(parent, Node::new)
: null;
if (parentNode != null) {
node.parent = parentNode;
}
}

public static int subWeight(Node node) {
if (node == null) return 0;

int weight = node.weight;
for (Node child : node.children) {
weight += subWeight(child);
}

return weight;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Works as long as there are no cycles

static class Node {
int id, weight;
Node parent;
List<Node> children = new ArrayList<>();

Node(int id) {
this.id = id;
}
}

private static final Map<Integer, Node> nodeGraph = new HashMap<>();

public static void parseCsvFile(String fileName) throws IOException {
try (Stream<String> stream = Files.lines(Paths.get(fileName))) {
stream.forEach(s -> parseCsvRow(s));
}
}

private static void parseCsvRow(String row) {
String[] cells = row.split(",");
int id = Integer.parseInt(cells[0]);
int parent = !cells[1].isEmpty()
? Integer.parseInt(cells[1])
: -1;
int weight = Integer.parseInt(cells[2]);

createNode(id, parent, weight);
}

private static void createNode(int id, int parent, int weight) {
Node node = nodeGraph.computeIfAbsent(id, Node::new);
node.weight = weight;

Node parentNode = parent != -1
? nodeGraph.computeIfAbsent(parent, Node::new)
: null;
if (parentNode != null) {
node.parent = parentNode;
}
}

public static int subWeight(Node node) {
if (node == null) return 0;

int weight = node.weight;
for (Node child : node.children) {
weight += subWeight(child);
}

return weight;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Sort all nodes based on the parent id.
2. Processes getChildren returns the first and last index of children of the parent by doing binary search on the list for the parent ID. It takes O(lg n) time.
3. Recursively print out the all the subweights by calling the subweight procedure on the root.

subweight(root)
if root = null
return 0
children <- getChildren(root.ID)
childrenWeights <- 0
for child in children
childrenWeights <- childrenWeights + subweight(child)

return root.weight + childrenWeights

in total it takes O(n lg n) time and O(n) memory.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.