## Facebook Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

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

This can be solved using a stack, by pushing all elements until a closing bracket is encountered, then you start to pop the elements until you hit a starting bracket then multiply the result by the order of the nested brackets (3,2,1), then push that result into the stack until the whole array of characters is processed.

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

I think the input is not given as a string its rather list of lists

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

@MA you should write steps here. Its confusing what you mentioned.

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

Check my solution below

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

here is the code:

``````'''
I/P [8, 3, 2, [5, 6, [9]], 6]
O/P 8+3+2+2*(5+6+3*(9))+6 => 95
'''

def get_next_token(tokens, cursor):

#skip whitespaces and comma
while cursor < len(tokens) and tokens[cursor] in [' ', ',']:
cursor += 1

if cursor >= len(tokens): #at the end but no token is found
return None, cursor

c = tokens[cursor]
if  c in ['[', ']']:
return c, cursor+1

#invalid input
if c > '9' or c < '0':
raise Exception('unexpected charactor {} at position {}'.format(c, cursor))

number = 0
while cursor < len(tokens):
c = tokens[cursor]
if c in ['[', ']', ',', ' ']:
break

if c > '9' or c < '0':
raise Exception('unexpected charactor {} at position {}'.format(c, cursor))

number = number*10 + int(c)
cursor += 1

return number, cursor

def calculate(equation):
stack = []
brack_depth = 0
tokens = equation
cursor = 0
while True:
token, cursor = get_next_token(tokens, cursor)
if token == None: #done. pop and return the result
return stack.pop(-1)

if token == ']': #calculate result between [ and ]
r = 0
while True:
n = stack.pop(-1)
if n == '[':
r = r*brack_depth
stack.append(r) #push it back
brack_depth = brack_depth-1
break
else:
r = r + n
else:
stack.append(token)
if token == '[':
brack_depth += 1

if __name__ == "__main__":

equation = '[8, 3, 2, [5, 6, [9]], 6]'
result = calculate(equation)
print(result)

# tokens = '[8, 3, 2, [5, 6, [9]], 6]'
# tokens = '[8, 3, 12, [5, 6, [9]], 116 ]'
# cursor = 0
# while True:
#     token, cursor = get_next_token(tokens, cursor)
#     print(token)
#     if token == None:
#         break``````

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

``````class Element {
int val;
List<Element> list;
boolean isList;
}

private long getValue(Element e, int factor) {
long sum = 0;
if(e == null)
return sum;
if(!e.isList)
return factor * e.val;

for(Element item : e.list) {
sum += getValue(item, factor + 1);
}
return sum;
}``````

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

``````struct NestedList{
bool isList;
int val;
vector<NestedList> internal;

NestedList(int v):isList(false),val(v){
}

NestedList(const vector<NestedList> &v):isList(true),internal(v){}
};

int nestedListSum(const vector<NestedList> &v,int multFactor){
if(v.empty()){
return 0;
}

int sum = 0;
for(auto &l : v){
if(l.isList){
int res = nestedListSum(l.internal,multFactor + 1);
sum += res*multFactor;
}else{
sum += multFactor*l.val;
}
}

return sum;
}

int nestedListSum(const vector<NestedList> &v){
return nestedListSum(v,1);
}``````

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

``````public class Sum {
public static int calculate(List<Object> a, int multiplier) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
if (a.get(i) instanceof ArrayList) {
List l = (ArrayList) a.get(i);
if (l.size() >= 1) {
multiplier++;
sum += multiplier * ((int) calculate(l, multiplier));
}
} else {
sum += ((int) a.get(i));
}
}
return sum;
}

public static void main(String[] args) {
List<Object> list  = new ArrayList<>();

List<Object> inner1 = new ArrayList<>();

List<Object> inner2 = new ArrayList<>();

System.out.println(calculate(list, 1));
}
}``````

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

{{
private static void addSum(List in) {
int res = addSumHelper(in, 0 , 1);
System.out.println(res);
}

private static int addSumHelper(List in, int sum, int level) {
for (Object list : in) {
if(list instanceof List)
else
sum += (Integer)list;
}
return sum*level;
}
}}

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

``````l=[8,3,2,[5,6,[9]],6]
count=1
ans=0
def fun(l,count,ans):
for e in l:
if(type(e) is list):
ans=fun(e,count*(count+1),ans)
else:
ans+=count*e
return ans
ans=fun(l,count,ans)
print(ans)``````

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

Javascript Solution
{{
var input = [8,3,2,[5,6,[9]],6];

var mySum = function(inputX, level){
var result = 0;
var temp;
level = level + 1;
for(var i = 0; i < inputX.length; i++){
if(Array.isArray(inputX[i])){
temp = mySum(inputX[i], level);
result = result + (level * (temp));
}else{
result = result + inputX[i];
}
}
return result;
}

var result = mySum(input, 1);
console.log(result);
}}

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

``````type NType = (number | NType)[];
let value = 0;
let last = Number.NaN;
for (let e of what) {
if (typeof e == "number") {
value += last;
last = e;
} else {
if (Number.isNaN(last))
last = 1;
}
}
if (Number.isNaN(last)) {
assert(value == 0);
return 0;
}
return value + last;
}``````

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

``````arr = [8,3,2,[5,6,[9]],6]

def arr_calc(arr):

def helper(arr, i):
s = 0
for el in arr:
if type(el) == list:
s += i*helper(el,i+1)
else:
print el
s += el

print s
return s

return helper(arr, 2)

arr_calc(arr)``````

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

```
def sum_depth_based2(l):
return helper2(l, 1)

def helper2(l, depth):
ret = 0
for i in range(len(l)):
if type(l[i]) is list:
ret += depth * (helper2(l[i], depth+1))
else:
ret += depth * l[i]
return ret
```

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

BTW these are the famous problem,
there are two variation;
1. Forward depth sum [ the current question ]
2. Reverse depth sum

Here is the simple way ;

``````public interface NestedInteger
{
/** @return true if this LinkedInt.NestedInteger holds a single integer, rather than a nested list */
boolean isInteger();

/** @return the single integer that this LinkedInt.NestedInteger holds, if it holds a single integer
* Return null if this LinkedInt.NestedInteger holds a nested list */
Integer getInteger();

/** @return the nested list that this LinkedInt.NestedInteger holds, if it holds a nested list
* Return null if this LinkedInt.NestedInteger holds a single integer */
List<NestedInteger> getList();
}

public int getDepth(List<NestedInteger> input, int depth) {
int myDepth = depth;
if (input.size() == 1 && input.get(0).isInteger())
return myDepth;

for (NestedInteger nst : input) {
if (!nst.isInteger()) {
int d = getDepth(nst.getList(), depth + 1);
myDepth = Math.max(d, myDepth);
}
}
return myDepth;
}

@Override
public int reversDepthSum(List<NestedInteger> input) {

int myDeptht = getDepth(input, 1);

return reverseDepthSum(input, 1, myDeptht);

}

private int reverseDepthSum(List<NestedInteger> input, int depth, int myDepth) {
int sum = 0;
for (NestedInteger nst : input) {
// System.out.println(nst);
if (!nst.isInteger()) {
sum += reverseDepthSum(nst.getList(), depth + 1, myDepth);

} else {
sum += (myDepth - depth + 1) * nst.getInteger();
}
}

return sum;
}

@Override
public int forwardDepthSum(List<NestedInteger> input) {
return forwardDepthSum(input, 1);

}

private int forwardDepthSum(List<NestedInteger> input, int depth) {

int sum = 0;

for (NestedInteger nst : input) {
if (nst.isInteger()) {
sum += depth * nst.getInteger();
} else
sum += forwardDepthSum(nst.getList(), depth + 1);
}

return sum;

}

public class Main {

public static void main(String[] ar) {
IDepthSum depthSum = new DepthSum();

List<NestedInteger> sample1 = Arrays.asList(
new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)),
new NestedIntegerValue(2),
new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)));

List<NestedInteger> sample2 = Arrays.asList(
new NestedIntegerValue(1),
new NestedIntegerValues(new NestedIntegerValue(4), new NestedIntegerValues(new NestedIntegerValue(6))));

System.out.println(sample1);
System.out.println("depth: " + depthSum.getDepth(sample1, 1));

System.out.println(sample2);
System.out.println("depth: " + depthSum.getDepth(sample2, 1));

System.out.println("Reverse depth sum");
System.out.println(depthSum.reversDepthSum(sample1));
System.out.println(depthSum.reversDepthSum(sample2));

System.out.println("Forward depth sum");
System.out.println(depthSum.forwardDepthSum(sample1));
System.out.println(depthSum.forwardDepthSum(sample2));

}
}``````

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

C++ with boost:

``````typedef boost::make_recursive_variant<int, std::vector<boost::recursive_variant_>>::type ListItem;
typedef std::vector<ListItem> List;

int eval(const List& expr, int n = 1) {
int r = 0;
for (auto x: expr) {
if (int *i = boost::get<int>(&x)) {
r += *i;
} else {
r += (n + 1) * eval(boost::get<List>(x), n + 1);
}
}
return r;
}

// usage
{
List expr{8,3,2,List{5,6,List{9}},6};
std::cout << eval(expr) << std::endl;
}``````

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

In Ruby

``````def level_solve(arr, level = 1)
arr.to_a! if !arr.is_a?(Array)
sum = 0

sum = arr.reduce(0) do |sum, num|

if num.is_a?(Array)
level += 1
sum + (level * level_solve(num,level))
else
sum + num
end
end
sum
end``````

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

``````def level_solve(arr, level = 1)
arr.to_a! if !arr.is_a?(Array)
sum = 0

sum = arr.reduce(0) do |sum, num|

if num.is_a?(Array)
level += 1
sum + (level * level_solve(num,level))
else
sum + num
end
end
sum
end``````

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

``````'''
I/P [8, 3, 2, [5, 6, [9]], 6]
O/P 8+3+2+2*(5+6+3*(9))+6 => 95
'''

def get_next_token(tokens, cursor):

#skip whitespaces and comma
while cursor < len(tokens) and tokens[cursor] in [' ', ',']:
cursor += 1

if cursor >= len(tokens): #at the end but no token is found
return None, cursor

c = tokens[cursor]
if  c in ['[', ']']:
return c, cursor+1

#invalid input
if c > '9' or c < '0':
raise Exception('unexpected charactor {} at position {}'.format(c, cursor))

number = 0
while cursor < len(tokens):
c = tokens[cursor]
if c in ['[', ']', ',', ' ']:
break

if c > '9' or c < '0':
raise Exception('unexpected charactor {} at position {}'.format(c, cursor))

number = number*10 + int(c)
cursor += 1

return number, cursor

def calculate(equation):
stack = []
brack_depth = 0
tokens = equation
cursor = 0
while True:
token, cursor = get_next_token(tokens, cursor)
if token == None: #done. pop and return the result
return stack.pop(-1)

if token == ']': #calculate result between [ and ]
r = 0
while True:
n = stack.pop(-1)
if n == '[':
r = r*brack_depth
stack.append(r) #push it back
brack_depth = brack_depth-1
break
else:
r = r + n
else:
stack.append(token)
if token == '[':
brack_depth += 1

if __name__ == "__main__":

equation = '[8, 3, 2, [5, 6, [9]], 6]'
result = calculate(equation)
print(result)

# tokens = '[8, 3, 2, [5, 6, [9]], 6]'
# tokens = '[8, 3, 12, [5, 6, [9]], 116 ]'
# cursor = 0
# while True:
#     token, cursor = get_next_token(tokens, cursor)
#     print(token)
#     if token == None:
#         break``````

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

``````a = [8, 3, 2, [5, 6, [9]], 6]

def sum_dig(pos, elems):
sum = 0
for elem in elems:
if type(elem) is not list:
sum += elem
else:
pos = pos + 1
sum += pos * sum_dig(pos, elem)
return sum

val = sum_dig(1, a)
print(val)``````

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

``````package com.company;

import java.util.List;
import java.util.Stack;

public class SumOfNestedLists {

static class StackItem {
List l;
int level;
}

private static long sum(List<Object> l) {
if (l.isEmpty()) {
return 0;
}
Stack<StackItem> objectStack = new Stack<>();
StackItem si = new StackItem();
si.level = 1;
si.l = l;

int result = 0;
objectStack.push(si);
while (!objectStack.isEmpty()) {
var stackTop = objectStack.pop();
for (var item : stackTop.l) {
if (item instanceof List) {
var sii = new StackItem();
sii.level = stackTop.level + 1;
sii.l = (List<?>) item;
objectStack.push(sii);
} else {
var temp = (Integer) item * stackTop.level;
System.out.println("Adding " + item + " * " + stackTop.level);
if (stackTop.level > 1) {
System.out.println("Multiplier " + temp + " * " + (stackTop.level - 1));
temp *= stackTop.level - 1;
}
result += temp;
}
}
}

return result;
}

public static void main(String[] args) {
var l = List.of(8, 3, 2, List.of(5,6, List.of(9)), 6);
System.out.println(sum(l));
// [8, 3, 2, [5, 6, [9]], 6]

// O/P 8+3+2+2*(5+6+3*(9))+6 => 95

}
}``````

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

``````const list = [8,3,2,[5,6,[9]], 6];
const multiply = (list, times) => {
let result = 0;
for (let item of list) {
if (Array.isArray(item)) {
result+= multiply(item, times +1);
} else result+=item;
}
return result * times;

}
console.log(multiply(list, 1));``````

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

Nice

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.