Facebook Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
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))
#read the number
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
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);
}
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.add(8);
list.add(3);
list.add(2);
List<Object> inner1 = new ArrayList<>();
inner1.add(5);
inner1.add(6);
List<Object> inner2 = new ArrayList<>();
inner2.add(9);
inner1.add(inner2);
list.add(inner1);
list.add(6);
System.out.println(calculate(list, 1));
}
}
{{
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)
sum += addSumHelper((List)list, 0, level+1);
else
sum += (Integer)list;
}
return sum*level;
}
}}
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);
}}
type NType = (number | NType)[];
function add(what : 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;
last = last * add(e);
}
}
if (Number.isNaN(last)) {
assert(value == 0);
return 0;
}
return value + last;
}
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));
}
}
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;
}
'''
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))
#read the number
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
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
}
}
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));
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.
- MA November 17, 2018