Linkedin Interview Question for Backend Developers


Country: United States
Interview Type: Phone Interview




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

/* It deals with single digit numbers only. 
           Easily extendible to numbers with Scanner or such Io classes. 
        */
	public int reverseDepthSum (String input)
	{
		// String input = "{{1,1},2,{1,1}}";
		char[] strArray = input.toCharArray();
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();

		int depth = 0, maxDepth = 0;

		for (int i = 0; i < strArray.length; i++) {
			if (strArray[i] == '{') {
				depth++;
				if (depth > maxDepth)
					maxDepth = depth;
			} else if (strArray[i] == '}')
				depth--;
			else {
				if (Character.isDigit(strArray[i])) {
					if (map.containsKey(depth))
						map.put(depth, map.get(depth) + Character.getNumericValue(strArray[i]));
					else
						map.put(depth, Character.getNumericValue(strArray[i]));
				} else {
					// "," => no op
				}
			}
		}

		int result = 0;
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			result += (maxDepth - entry.getKey() + 1) * entry.getValue();
		}

		return result;
	}

- X May 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ReversedDepthSum {

    interface NestedInteger {
        boolean isInteger();
    }

    static class NestedIntegerValue implements NestedInteger {
        Integer value;

        public NestedIntegerValue(Integer value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return value.toString();
        }

        @Override
        public boolean isInteger() {
            return true;
        }
    }

    static class NestedIntegerValues implements NestedInteger {
        List<NestedInteger> values;

        public NestedIntegerValues(NestedInteger... values) {
            this.values = Arrays.asList(values);
        }

        @Override
        public String toString() {
            StringBuffer buff = new StringBuffer();
            buff.append('{');
            values.forEach(v -> {
                buff.append(v.toString());
                buff.append(',');
            });
            buff.setCharAt(buff.length() - 1, '}');
            return buff.toString();
        }

        @Override
        public boolean isInteger() {
            return false;
        }
    }

    public static int getMaxDepth(List<NestedInteger> input, int depth) {
        int maxDepth = depth;
        for (NestedInteger value : input) {
            if (!value.isInteger()) {
                maxDepth = getMaxDepth(NestedIntegerValues.class.cast(value).values, ++depth);
                if (maxDepth < depth) {
                    return depth;
                }
                depth--;
            }
        }
        return maxDepth;
    }

    public static int reverseDepthSum(List<NestedInteger> input, int depth, int maxDepth) {
        int sum = 0;
        for (NestedInteger value : input) {
            if (value.isInteger()) {
                NestedIntegerValue nestedInteger = NestedIntegerValue.class.cast(value);
                sum += nestedInteger.value * (maxDepth - depth + 1);
            } else {
                sum += reverseDepthSum(NestedIntegerValues.class.cast(value).values, ++depth, maxDepth);
                --depth;
            }
        }
        return sum;
    }

    public static int reverseDepthSum(List<NestedInteger> input) {
        int maxDepth = getMaxDepth(input, 1);
        return reverseDepthSum(input, 1, maxDepth);
    }

    // {{1,1},2,{1,1}}
    private static List<NestedInteger> getSample1() {
        return Arrays.asList(
                new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)),
                new NestedIntegerValue(2),
                new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)));
    }

    // {1,{4,{6

private static List<NestedInteger> getSample2() {
return Arrays.asList(
new NestedIntegerValue(1),
new NestedIntegerValues(new NestedIntegerValue(4), new NestedIntegerValues(new NestedIntegerValue(6))));
}


public static void main(String[] args) {
System.out.println(getSample1() + " -> " + reverseDepthSum(getSample1()));
System.out.println(getSample2() + " -> " + reverseDepthSum(getSample2()));
}

}

- terminator June 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ReversedDepthSum {

    interface NestedInteger {
        boolean isInteger();
    }

    static class NestedIntegerValue implements NestedInteger {
        Integer value;

        public NestedIntegerValue(Integer value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return value.toString();
        }

        @Override
        public boolean isInteger() {
            return true;
        }
    }

    static class NestedIntegerValues implements NestedInteger {
        List<NestedInteger> values;

        public NestedIntegerValues(NestedInteger... values) {
            this.values = Arrays.asList(values);
        }

        @Override
        public String toString() {
            StringBuffer buff = new StringBuffer();
            buff.append('{');
            values.forEach(v -> {
                buff.append(v.toString());
                buff.append(',');
            });
            buff.setCharAt(buff.length() - 1, '}');
            return buff.toString();
        }

        @Override
        public boolean isInteger() {
            return false;
        }
    }

    public static int getMaxDepth(List<NestedInteger> input, int depth) {
        int maxDepth = depth;
        for (NestedInteger value : input) {
            if (!value.isInteger()) {
                maxDepth = getMaxDepth(NestedIntegerValues.class.cast(value).values, ++depth);
                if (maxDepth < depth) {
                    return depth;
                }
                depth--;
            }
        }
        return maxDepth;
    }

    public static int reverseDepthSum(List<NestedInteger> input, int depth, int maxDepth) {
        int sum = 0;
        for (NestedInteger value : input) {
            if (value.isInteger()) {
                NestedIntegerValue nestedInteger = NestedIntegerValue.class.cast(value);
                sum += nestedInteger.value * (maxDepth - depth + 1);
            } else {
                sum += reverseDepthSum(NestedIntegerValues.class.cast(value).values, ++depth, maxDepth);
                --depth;
            }
        }
        return sum;
    }

    public static int reverseDepthSum(List<NestedInteger> input) {
        int maxDepth = getMaxDepth(input, 1);
        return reverseDepthSum(input, 1, maxDepth);
    }

    // {{1,1},2,{1,1}}
    private static List<NestedInteger> getSample1() {
        return Arrays.asList(
                new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)),
                new NestedIntegerValue(2),
                new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)));
    }

    // {1,{4,{6

private static List<NestedInteger> getSample2() {
return Arrays.asList(
new NestedIntegerValue(1),
new NestedIntegerValues(new NestedIntegerValue(4), new NestedIntegerValues(new NestedIntegerValue(6))));
}


public static void main(String[] args) {
System.out.println(getSample1() + " -> " + reverseDepthSum(getSample1()));
System.out.println(getSample2() + " -> " + reverseDepthSum(getSample2()));
}

}

- terminator June 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node {
	public:
		vector<int> vals_;
		vector<Node> children_;
};

int ReversedDepthWeigtedSum(Node const *node, int &sum)
{
	int depth = 0;
	if (node) {
		for (Node const &child : node->children_) {
			depth = max(depth, ReversedDepthWeigtedSum(&child, sum));
		}
		++depth;

		for (int val : node->vals_) {
			sum += val * depth;
		}
	}
	return depth;
}

- Alex August 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use stack.

- Shirish M March 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class DepSum {
	public class NestedInteger{
		public Object value;
		public NestedInteger(List<NestedInteger> value){
			this.value = value;
		}
		public NestedInteger(Integer value){
			this.value= value;
		}
	}
	
	public class Dep{
		int dep;
		public Dep(int dep){
			this.dep = dep;
		}
	}
	
	public DepSum(){
//		List<NestedInteger> list = new ArrayList<>();
//		list.add(new NestedInteger(1));
//		list.add(new NestedInteger(1));
//		NestedInteger ni = new NestedInteger(list);
//		
//		List<NestedInteger> list1 = new ArrayList<>();
//		list1.add(new NestedInteger(1));
//		list1.add(new NestedInteger(1));
//		NestedInteger ni1 = new NestedInteger(list1);
//		
//		NestedInteger ni2 = new NestedInteger(new Integer(2));
//		
//		List<NestedInteger> listGlobal = new ArrayList<>();
//		listGlobal.add(ni);
//		listGlobal.add(ni2);
//		listGlobal.add(ni1);
		
		List<NestedInteger> list = new ArrayList<>();
		NestedInteger ni6 = new NestedInteger(6);
		list.add(ni6);
		NestedInteger nestedIntegerList = new NestedInteger(list);
		
		NestedInteger ni4 = new NestedInteger(4);
		List<NestedInteger> list1 = new ArrayList<>();
		list1.add(ni4);
		list1.add(nestedIntegerList);
		NestedInteger nestedIntegerList1 = new NestedInteger(list1);
		
		NestedInteger ni1 = new NestedInteger(1);
		List<NestedInteger> listGlobal = new ArrayList<>();
		listGlobal.add(ni1);
		listGlobal.add(nestedIntegerList1);
		
		System.out.println(reverseDepSum(listGlobal));
	}
	
	private int reverseDepSum(List<NestedInteger> list){
		Dep dep = new Dep(1);
		return getSum(list,dep);
	}
	
	private int getSum(List<NestedInteger> list, Dep dep){
		if(list==null || list.size()==0) return 0;
		int sum = 0;
		int listSum=0;
		int currDep = dep.dep;
		for(NestedInteger ni : list){
			if(ni.value instanceof Integer){
				sum += (int)ni.value;
			}else{
				Dep nextDep = new Dep(dep.dep);
				listSum += getSum((List)ni.value,nextDep);
				currDep = Math.max(currDep, nextDep.dep);
			}
		}
		dep.dep = currDep+1;
		return currDep*sum+listSum;
	}

}

- hg April 12, 2017 | Flag Reply


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