Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
else sum += getSum(ni.getList(), depth + 1);
Shouldnt this line be
else sum += getListSum(ni.getList(), depth + 1);
define a recursive function:
int valueit(NestedInteger root, depth) {
int val=0;
if(root.isInteger()) {
val+=n.getInteger();
}
else {
List<NestedInteger> nlist=n.getList();
for n in nlist {
if(n.isInteger()) {
val+=n.getInteger();
}
else {
val+=valueit(n,depth+1);
}
}
}
return val;
}
def foo(A):
return _aux(A, 1)
def _aux(A, weight):
res = 0
for item in A:
if type(item) is list:
res += _aux(item, weight + 1)
else:
res += item * weight
return res
private static int GetSum(NestedInteger item, int weight)
{
if (item.IsInteger())
{
return (int)item.GetInteger()*weight;
}
else
{
int sum = 0;
var list = item.GetList();
foreach (var subItem in list)
{
if (subItem.IsInteger())
sum += GetSum(subItem, weight);
else
sum += GetSum(subItem, weight + 1);
}
return sum;
}
}}
public class SumOfNestedLists {
public static int getSum(List<Object> list) {
int sum = 0;
for(Object o : list) {
if(o.getClass() == Integer.class)
sum += (int)o;
else if(o.getClass() == LinkedList.class)
sum += getNestedSum(o, 2);
}
return sum;
}
private static int getNestedSum(Object o, int level) {
if(o.getClass() != LinkedList.class) return -1;
List<Object> list = (List<Object>)o;
int tempSum = 0;
for(Object io : list) {
if(io.getClass() == Integer.class)
tempSum += (level*(int)io);
else if(io.getClass() == LinkedList.class)
tempSum += getNestedSum(io, level+1);
}
return tempSum;
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class FindSumByListFlattening {
@SuppressWarnings("unchecked")
public static int findSumByDepth(ArrayList<Object> inputList) {
int sum = 0;
int currentElementDepth = 1;
ListIterator<Object> listIterator = inputList.listIterator();
int currentPosition = 0;
int resetPoint = 0;
ArrayList<Object> tempList;
while (listIterator.hasNext()) {
Object i = listIterator.next();
if (!(i instanceof List)) {
if (resetPoint % 2 == 0)
currentElementDepth = 1;
else
resetPoint++;
sum += (currentElementDepth * (int) i);
currentPosition++;
} else {
tempList = (ArrayList<Object>) i;
listIterator.remove();
currentElementDepth++;
resetPoint++;
for (Object obj : tempList) {
listIterator.add(obj);
}
}
listIterator = inputList.listIterator(currentPosition);
}
return sum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Object> inputList = new ArrayList<Object>();
ArrayList<Object> List1 = new ArrayList<Object>();
inputList.add(1);
List1.add(4);
ArrayList<Object> List2 = new ArrayList<Object>();
List2.add(6);
List1.add(List2);
inputList.add(List1);
// inputList.add(4);
for (Object obj : inputList) {
System.out.print(obj + " ");
}
System.out.println("Sum: " + findSumByDepth(inputList));
}
}
#include <stdio.h>
using namespace std;
int getWeightedSum(const char* str)
{
int sum = 0;
int depth = 0;
for(;*str; str++)
{
if (*str == '{')
{
depth++;
}
else if (*str == '}')
{
depth--;
}
else if (*str != ',')
{
int nested_sum = 0;
while(*str >= '0' && *str <= '9')
{
nested_sum += nested_sum * 10 + (*str - '0');
str++;
}
sum+=nested_sum * depth;
}
}
return sum;
}
int main() {
printf("%d\n", getWeightedSum("{1, {1,{1,2,{1,2
}"));
return 0;
}
private static int findSumByWt(ArrayList<Object> inputList, int depth,int sum){
// sum=0;
// depth=1;
for(int i=0;i<inputList.size();i++){
Object obj=inputList.get(i);
if(obj instanceof List){
sum=findSumByWt((ArrayList<Object>)obj, (depth+1),sum);
}
if(obj instanceof Integer){
sum+=((int)obj*depth);
}
}
return sum;
}
private static int findSumByWt(ArrayList<Object> inputList, int depth,int sum){
// sum=0;
// depth=1;
for(int i=0;i<inputList.size();i++){
Object obj=inputList.get(i);
if(obj instanceof List){
sum=findSumByWt((ArrayList<Object>)obj, (depth+1),sum);
}
if(obj instanceof Integer){
sum+=((int)obj*depth);
}
}
return sum;
}
public class NestedIntegerSum {
public int sum(NestedInteger root) {
if (root.isInteger()) {
return root.getInteger();
}
return sum(root.getList(), 1);
}
private int sum(List<NestedInteger> nodes, int depth) {
if (nodes == null || nodes.isEmpty()) {
return 0;
}
int sum = 0;
for (NestedInteger node : nodes) {
if (node.isInteger()) {
sum += node.getInteger() * depth;
} else {
sum += sum(node.getList(), depth + 1);
}
}
return sum;
}
}
The thought is DFS:
- uuuouou February 23, 2014