Linkedin Interview Question Software Engineer / Developers
Country: United States
//The above code has an issue with respect to using level++ in the recursion //because for the same level nested integer the level is incremented already
//Here is my attempt
public int depthSum (List<NestedInteger> input)
{ // ur implementation here}
int finalSum = 0;
for (NestedInteger nestedInteger : input) {
finalSum += depthSumInternal(nestedInteger,1);
}
return finalSum;
}
private int depthSumInternal(NestedInteger input, int level) {
int returnSum = 0;
if(input.isInteger()) return level*input.getInteger();
for(NestedInteger childInput:input.getList()) {
int childLevel = level+1;
returnSum+=depthSumInternal(childInput,childLevel);
}
return returnSum;
}
Here's a python solution
def calStrWeight( str ):
currentDepth = 0
weight = 0
if len(str)==0:
return 0
for i in range(len(str)):
if currentDepth<0:
break
if str[i]=='{':
currentDepth+=1
elif str[i]=='}':
currentDepth-=1
elif str[i].isdigit():
weight += int(str[i]) * currentDepth
return weight
print calStrWeight('{1,{4,{6
}')
Below is the code which uses the same approach as mentioned above, with added classes and method implementations.
/**
* This is the interface that represents nested lists. You should not implement
* it, or speculate about its implementation.
*/
interface NestedInteger {
/**
* @return true if this NestedInteger holds a single integer, rather than a
* nested list
*/
boolean isInteger();
/**
* @return the single integer that this NestedInteger holds, if it holds a
* single integer Return null if this NestedInteger holds a nested
* list
*/
Integer getInteger();
/**
* @return the nested list that this NestedInteger holds, if it holds a
* nested list Return null if this NestedInteger holds a single
* integer
*/
List<NestedInteger> getList();
}
class MyNestedIneteger implements NestedInteger {
private Integer theSingleInteger;
private List<NestedInteger> theList;
public MyNestedIneteger(Integer theSingleInteger, List<NestedInteger> theList) {
this.theSingleInteger = theSingleInteger;
this.theList = theList;
}
@Override
public boolean isInteger() {
return null == theList && null != theSingleInteger;
}
@Override
public Integer getInteger() {
return theSingleInteger;
}
@Override
public List<NestedInteger> getList() {
return theList;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("{");
if (null != theSingleInteger) {
string.append(theSingleInteger);
}
if (null != theList) {
for (NestedInteger current : theList) {
string.append(", " + current.toString());
}
}
string.append("}");
return string.toString();
}
}
public class NestedIntegerSum {
/**
* 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 static int depthSum(List<NestedInteger> input) {
if (null == input) {
return 0;
} else {
int sum = 0;
for (NestedInteger current : input) {
sum += depthSumNestedInteger(current, 1);
}
return sum;
}
}
private static int depthSumNestedInteger(NestedInteger current, int level) {
System.out.println("current: " + current + " level: " + level);
if (null == current) {
return 0;
} else {
if (current.isInteger()) {
return current.getInteger() * level;
} else {
int tempSum = 0;
if (current.getInteger() != null) {
tempSum = current.getInteger() * level;
}
for (NestedInteger nestedCurrent : current.getList()) {
tempSum += depthSumNestedInteger(nestedCurrent, level + 1);
}
return tempSum;
}
}
}
public static void main(String[] args) {
List<NestedInteger> list1 = new ArrayList<>();
List<NestedInteger> list2 = new ArrayList<>();
NestedInteger nestedInteger1 = new MyNestedIneteger(1, list1);
NestedInteger nestedInteger2 = new MyNestedIneteger(4, list2);
NestedInteger nestedInteger3 = new MyNestedIneteger(6, null);
list1.add(nestedInteger2);
list2.add(nestedInteger3);
List<NestedInteger> input = new ArrayList<>();
input.add(nestedInteger1);
System.out.println(input);
System.out.println(depthSum(input));
}
}
public class DepthSumDemoTest {
public static void main(String[] args) {
//for my test case
//{{1,1},2,{1,1}}
List<NestedIntegers> parent = new ArrayList<NestedIntegers>();
parent.add(new NestedIntegers(2));
List<NestedIntegers> myChild1 = new ArrayList<NestedIntegers>();
myChild1.add(new NestedIntegers(1));
myChild1.add(new NestedIntegers(1));
parent.add(new NestedIntegers(myChild1));
List<NestedIntegers> myChild2 = new ArrayList<NestedIntegers>();
myChild2.add(new NestedIntegers(1));
myChild2.add(new NestedIntegers(1));
parent.add(new NestedIntegers(myChild2));
System.out.println("sum of all depth is : "+myDepthSum(parent, 1));
// {1,{4,{6
= 27
List<NestedIntegers> myParent2 = new ArrayList<NestedIntegers>();
myParent2.add(new NestedIntegers(1));
List<NestedIntegers> myChild21 = new ArrayList<NestedIntegers>();
myChild21.add(new NestedIntegers(4));
myParent2.add(new NestedIntegers(myChild21));
List<NestedIntegers> myChild22 = new ArrayList<NestedIntegers>();
myChild22.add(new NestedIntegers(6));
myChild21.add(new NestedIntegers(myChild22));
System.out.println("sum of all depth is : "+myDepthSum(myParent2, 1));
}
public static int myDepthSum(List<NestedIntegers> list,int level){
int sum = 0;
for(NestedIntegers entry: list){
if(entry.isSingleInteger()){
sum+=entry.getInteger()*level;
}
else{
sum+=myDepthSum(entry.getList(), level+1);
}
}
return sum;
}
}
interface INestedIntegers{
boolean isSingleInteger();
List<NestedIntegers> getList();
Integer getInteger();
}
class NestedIntegers implements INestedIntegers{
List<NestedIntegers> list = new ArrayList<NestedIntegers>();
Integer singleValue = null;
public NestedIntegers(Integer SingleValue){
this.singleValue = SingleValue;
}
public NestedIntegers(List<NestedIntegers> listValues){
singleValue = null;
this.list = listValues;
}
@Override
public boolean isSingleInteger() {
return singleValue!=null;
}
@Override
public List<NestedIntegers> getList() {
return list;
}
@Override
public Integer getInteger() {
return singleValue;
}
}
Simple recursion. First call with weight=1
public int depthSum (List<NestedInteger> input, int weight)
{
if (input == null) {
return 0;
}
int sum = 0;
for (NestedInteger elem : input)
{
if (elem.isInteger()) {
sum += weight * elem.getInteger();
} else {
sum += depthSum(elem.getList(), weight+1);
}
}
return sum;
}
Here's a python solution
def calStrWeight( str ):
currentDepth = 0
weight = 0
if len(str)==0:
return 0
for i in range(len(str)):
if currentDepth<0:
break
if str[i]=='{':
currentDepth+=1
elif str[i]=='}':
currentDepth-=1
elif str[i].isdigit():
weight += int(str[i]) * currentDepth
return weight
print calStrWeight('{1,{4,{6
}')
- Paul Lee November 06, 2014public int depthSum (List<NestedInteger> input) { return depthSumHelper(input, 1); } private int depthSumHelper(List<NestedInteger> input, int level){ int sum = 0; // look at each nested integer for( NestedInteger nestedInt : input){ if(nestedInt.isInteger()){ sum += nestedInt.getInteger() * level; } else { sum += depthSumHelper(nestedInt.getList(), level++); } } return sum; }