Monday, November 16, 2015

LinkedIn: Nested Integer

Problem: 
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)

Code (Java):
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();
    } 

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. 

Code (Java):
import java.io.*;
import java.util.*;

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;
    }

    /**
     * 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();
    } 







No comments:

Post a Comment