Facebook Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
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;
}
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