Linkedin Interview Question
Backend DevelopersCountry: United States
Interview Type: Phone Interview
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()));
}
}
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()));
}
}
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;
}
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;
}
}
- X May 29, 2017