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.

- MA November 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nikhil19kekan November 30, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- karansoft8 December 08, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check my solution below

- nitinguptaiit March 31, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yuhechen2018 March 12, 2020 | Flag
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;
    }

- Popeye November 12, 2018 | Flag Reply
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);
}

- Guy November 12, 2018 | Flag Reply
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.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));
	}
}

- Levi November 16, 2018 | Flag Reply
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)
sum += addSumHelper((List)list, 0, level+1);
else
sum += (Integer)list;
}
return sum*level;
}
}}

- Anonymous November 17, 2018 | Flag Reply
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)

- nikhil19kekan November 30, 2018 | Flag Reply
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);
}}

- Anonymous December 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- xiongmao December 08, 2018 | Flag Reply
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)

- SP December 21, 2018 | Flag Reply
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
```

- Anonymous December 30, 2018 | Flag Reply
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));

    }
}

- nitinguptaiit March 31, 2019 | Flag Reply
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;
}

- Anonymous August 18, 2019 | Flag Reply
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

- Kirk August 30, 2019 | Flag Reply
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

- Kirk August 30, 2019 | Flag Reply
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))

    #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

- yuhechen2018 March 12, 2020 | Flag Reply
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)

- arturocu81 October 12, 2020 | Flag Reply
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


    }
}

- Iterative December 22, 2020 | Flag Reply
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));

- Yuri Barssi January 15, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice

- Lekan June 27, 2021 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More