Buttercola: LinkedIn: Nested Integer
Given a nested list of integers, returns the sum of all integers in the list weighted by their depth. For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1)
Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3)
Followup:
What if the list is in reverse order?
e.g. {{1, 1}, 2, {1, 1}}, then 4 1s at depth 1, and one 2 at depth 2, so the sum is 8
Solution:
We can first get the depth of the list, then everything would be the same.
Read full article from Buttercola: LinkedIn: Nested Integer
Given a nested list of integers, returns the sum of all integers in the list weighted by their depth. For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1)
Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3)
public int depthSum (List<NestedInteger> input) { //Implement this function return depthSumHelper(input, 1); } private int depthSumHelper(List<NestedInteger> input, int level) { if (input == null || input.size() == 0) { return 0; } int sum = 0; for (int i = 0; i < input.size(); i++) { if (input.get(i).inInteger()) { sum += input.get(i).getInteger() * level; } else { sum += depthSumHelper(input.get(i).getList(), level + 1); } } return sum; } /** * This is the interface that allows for creating nested lists. * You should not implement it, or speculate about its implementation */ public interface NestedInteger { // Returns true if this NestedInteger holds // a single integer, rather than a nested list public boolean isInteger(); // Returns the single integer that this NestedInteger holds, // if it holds a single integer // Returns null if this NestedInteger holds a nested list public Integer getInteger(); // Returns the nested list that this NestedInteger // holds, if it holds a nested list // Returns null if this NestedInteger holds a single integer public List<NestedInteger> getList(); } |
What if the list is in reverse order?
e.g. {{1, 1}, 2, {1, 1}}, then 4 1s at depth 1, and one 2 at depth 2, so the sum is 8
Solution:
We can first get the depth of the list, then everything would be the same.
public int depthSum (List<NestedInteger> input) { //Implement this function int depth = getDepth(input); return depthSumHelper(input, depth); } private int getDepth(List<NestedInteger> input) { if (input == null || input.size() == 0) { return 0; } int depth = 0; for (int i = 0; i < input.size(); i++) { if (!input.get(i).isInteger()) { depth = Math.max(depth, getDepth(input.get(i).getList())); } } return depth + 1; } private int depthSumHelper(List<NestedInteger> input, int level) { if (input == null || input.size() == 0) { return 0; } int sum = 0; for (int i = 0; i < input.size(); i++) { if (input.get(i).inInteger()) { sum += input.get(i).getInteger() * level; } else { sum += depthSumHelper(input.get(i).getList(), level - 1); } } return sum; }