Given an array that contains numbers and/or other nested arrays, write an algorithm to come up with a sum of these elements, multiplied by the depth (or how many arrays deep) you are.

For example, what would you do with an input array that looks like:

[ 2, 3, [ 9, [ 1, 2 ]], 4]

Question

Given an array that contains numbers and/or other nested arrays, write an algorithm to come up with a sum of these elements, multiplied by the depth (or how many arrays deep) you are.

For example, what would you do with an input array that looks like:

[ 2, 3, [ 9, [ 1, 2 ]], 4]

Sigiloso · Accepted Answer

For an input array of [ 2, 3, [ 9, [ 1, 2 ]], 4],

The deepest array consists of [1, 2].  So summed, up we would get 1+2 (for the deepest array), multiplied by depth 3 = 9.  

The next level up, we’d have (9 + 9) * 2 = 36

And for the top level, (2 + 3 + 36 + 4) * depth level 1 = 45 (which is the ultimate result for this algorithm).

I wrote this as an Objective-C NSArray extension.

@implementation NSArray (DepthSum)
{
	- (int) depthSum
	{
		return [self depthSum: self atDepth: 1];
	}

	- (int) depthSum: (NSArray *)inputArray atDepth: currentDepth
	{
		int sum;

		for anObject in inputArray
		{
			// assuming the only objects that can be in the array 
			// are either numbers or other arrays
			if ([anObject isKindOf: [NSArray class]])
			{
				NSArray *subArray = (NSArray *)anObject;
				sum += [self depthSum: subArray atDepth: currentDepth+1];
			} else {
				NSNumber *numberObject = (NSNumber *)anObject;
				sum += numberObject.intValue;
			}
		}

		return (sum * currentDepth);
	}
}

I Dev TV · Answer

func sumOfItemsAndEmbeddedArraysMultipliedByDepth(in array: [Any]) -> Int
{
    return sumOfItemsAndEmbeddedArraysMultipliedByDepth(in: array, depth: 1)
}

func sumOfItemsAndEmbeddedArraysMultipliedByDepth(in array: [Any], depth: Int) -> Int
{
    var sum = 0
    
    for item in array {
        if item is Int {
            sum += item as! Int
        } else if item is Array {
            sum += sumOfItemsAndEmbeddedArraysMultipliedByDepth(in: item as! Array, depth: depth + 1)
        } else {
            fatalError("Inside sumOfItemsAndEmbeddedArraysMultipliedByDepth(in:depth:) - Item is not of type Int or Array")
        }
    }
    
    return sum * depth
}

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas