[set up a challenge ring] has an integer array with n elements, and finds the maximum product of N-1 elements

  ios, question

This is a Google pen test, which I saw five years ago.

There is an integer array with n elements, and the maximum product of N-1 elements is obtained.

For example: input array [2,4,5,3]; Then 60 is returned (the corresponding N-1 elements are [3,4,5], which is larger than the product of [2,3,4],[2,3,5],[2,4,5].

Requirements:
1. The time complexity is as low as possible
2. You cannot use any array function that PHP comes with. You can use control structures such as if, for, switch, and basic type checking functions such as isset/is_array/is_int.

Function template:

<?php
class NumUtil
{
	 /**
	 * @param array  $arr
	 * @return integer
	 */
	static public function findMaxProd(){/*你的代码*/}
}

分割线

I have written the unit tests. Those who dare to enter the challenge arena, paste the codes below. I will check whether I can pass several unit tests. Ha ha.

挑擂结果(有两个测试用例我只占了个位,没写具体的数据。下面的结果都不包含这两个用例)

updated @ 2013-3-22 16:32

JoyQi is currently closest to the standard answer. Only two test cases failed, and the time complexity is not the lowest. However, what I wrote with me is also too close to call. If it is implemented in C language, it is difficult to say whether the cycle takes more time or the division of large numbers takes more time.

Sunyanzi still has three test cases to pass.

公布答案了:单元测试

/**
 * 函数名释义:
 * az: Amount of Zero, 零的个数
 * ap: Amount of Positive, 正整数个数
 * an: Amount of Negative, 负数个数
 *
 * gt: Greater Than, 大于
 * eq: Equal, 等于
 * lt: Less Than, 小于
 *
 * o: odd, 奇数
 * e: even, 偶数
 *
 * #################### MECE Tree ####################
 *参数输入正确的正常流程
 * 	零的个数大于1			@see TestCaseNumUtil::test_amountOfZeroGreaterThanOne()
 * 	零的个数等于1
 *		负数个数为偶数
 *			有正数		@see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsEven_existsPositive()
 * 			无正数	   @see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsEven_notExistsPositive()
 * 		负数个数为奇数
 * 			有正数		@see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_existsPositive()
 *			无正数		@see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_notExistsPositive()
 * 	零的个数小于1
 *		负数个数为偶数
 *			有正数		@see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsEven_existsPositive()
 * 			无正数	   @see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsEven_notExistsPositive()
 * 		负数个数为奇数
 * 			有正数		@see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_existsPositive()
 *			无正数		@see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_notExistsPositive()
 *
 *参数输入错误的异常流
 *	输入的参数不是数组		@see TestCaseNumUtil::test_inputIsNotArray()
 * 	是个数组
 * 		元素个数小于2个	@see TestCaseNumUtil::test_ArrayContainLessThanTwoInteger()
 *		元素多于2个
 * 			不全是整数	@see TestCaseNumUtil::test_ArrayContainNonInteger()
 *
 *白盒测试
 *	元素个数超过int型上限 @see TestCaseNumUtil::test_amountOfZeroGreaterThanMaxInt()
 *	元素的乘积超过PHP上限	@see TestCaseNumUtil::test_prodGreaterThanMaxInt()
 *
 * #################### MECE Tree ####################
 */
class TestCaseNumUtil extends PHPUnit_Framework_TestCase
{
	/**
	 * 零的个数大于1
	 * 本来根据根据负数个数奇偶性、正数有无可以分成四种情况
	 * 但这四种情况明显可以归并到这一种,因此不再分成四个条件来写
	 */
	public function test_amountOfZeroGreaterThanOne()
	{
		$arr = array_merge(
			$this->produceIntArray(rand(2, 10), self::INT_SIGN_ZERO),
			$this->produceIntArray(rand(10, 20), self::INT_SIGN_RAND)
		);
		$this->assertEquals(0, NumUtil::findMaxProd($arr));
	}

	/**
	 * 零的个数等于1 偶数个负数 有正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsEven_existsPositive()
	{
		$this->execTest(200, array(0, -1, -2, 10, 5, 2));
	}

	/**
	 * 零的个数等于1 偶数个负数 无正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsEven_notExistsPositive()
	{
		$this->execTest(100, array(0, -1, -2, -10, -5));
	}

	/**
	 * 零的个数等于1 奇数个负数 有正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_existsPositive()
	{
		$arr = array_merge(
			$this->produceIntArray(11, self::INT_SIGN_NEGA),
			array(0),
			$this->produceIntArray(rand(1,10), self::INT_SIGN_POSI)
		);
		$this->assertEquals(0, NumUtil::findMaxProd($arr));
	}

	/**
	 * 零的个数等于1 奇数个负数 无正数
	 */
	public function test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_notExistsPositive()
	{
		$arr = array_merge(
			$this->produceIntArray(11, self::INT_SIGN_NEGA),
			array(0)
		);
		$this->assertEquals(0, NumUtil::findMaxProd($arr));
	}

	/**
	 * 零的个数小于1 偶数个负数 有正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsEven_existsPositive()
	{
		$this->execTest(100, array( -1, -2, -10, -5, 10));
	}

	/**
	 * 零的个数小于1 偶数个负数 无正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsEven_notExistsPositive()
	{
		$this->execTest(-10, array( -1, -2, -1024, -5));
	}

	/**
	 * 零的个数小于1 奇数个负数 有正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_existsPositive()
	{
		$this->execTest(200, array(-2, -10, -5, 4), self::INT_SIGN_POSI);
	}

	/**
	 * 零的个数小于1 奇数个负数 无正数
	 */
	public function test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_notExistsPositive()
	{
		$this->execTest(50, array(-2, -10, -5), self::INT_SIGN_POSI);
	}

	public function test_inputIsNotArrayDataProvider()
	{
		return array(
			array(NULL),
			array(TRUE),
			array(1024),
			array(3.14),
			array("not an array"),
			array(new TestCaseNumUtil),
		);
	}

	/**
	 * 输入的参数不是数组
	 * @dataProvider test_inputIsNotArrayDataProvider
	 * @expectedException PHPUnit_Framework_Error
	 */
	public function test_inputIsNotArray($arg)
	{
		NumUtil::findMaxProd($arg);
	}

	/**
	 * 数组元素个数小于2个
	 */
	public function test_ArrayContainLessThanTwoInteger()
	{
		$this->assertFalse(NumUtil::findMaxProd(array(10)));
	}

	/**
	 * 数组元素不全是整数
	 */
	public function test_ArrayContainNonInteger()
	{
		$this->assertFalse(NumUtil::findMaxProd(array(-2, TRUE, -5)));
	}

	/**
	 * 如果代码中用整形来记录【零、正数、负数】的个数,输入的数组元素个数超过int型上限,就会造成数据溢出
	 */
	public function test_amountOfZeroGreaterThanMaxInt()
	{
		//这种极端情况不支持,也不测试,写在这里仅仅表示我考虑到这点了
	}

	/**
	 * N-1个元素的乘积超过PHP能表达的上限,就会造成数据溢出
	 */
	public function test_prodGreaterThanMaxInt()
	{
		//这种情况暂时不支持,也不测试,写在这里仅仅表示我考虑到这点了
	}

	const INT_SIGN_POSI = "positive";
	const INT_SIGN_NEGA = "negative";
	const INT_SIGN_ZERO = "zero";
	const INT_SIGN_RAND = "RAND";

	private function  produceIntArray($length, $sign)
	{
		$int_arr = array();
		switch($sign)
		{
			case self::INT_SIGN_POSI :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = rand(1, 99);
				}
				break;
			case self::INT_SIGN_NEGA :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = 0 - rand(1, 99);
				}
				break;
			case self::INT_SIGN_ZERO :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = 0;
				}
				break;
			case self::INT_SIGN_RAND :
				for($i = 0; $i < $length; $i++)
				{
					$int_arr[$i] = $i % 2 ? rand(1, 99) : 0 - rand(0, 99);
				}
				break;
		}
		return $int_arr;
	}

	private function execTest($exp, array $arr, $sign = self::INT_SIGN_NEGA)
	{
		$randInt = self::INT_SIGN_POSI == $sign ? rand(1, 100) : 0 - rand(1, 99);
		$arr[] = $randInt;
		$arr[] = $randInt;
		shuffle($arr);
		$this->assertEquals($exp * $randInt * $randInt, NumUtil::findMaxProd($arr));
	}
}

公布答案了:我的函数实现

class NumUtil
{
	/**
	 * @param array $arr
	 * @return integer
	 */
	static public function findMaxProd(array $arr)
	{

		$arr_len = count($arr);
		if (2 > $arr_len)
		{
			return false;
		}

		/*
		 * 先遍历数组找出零、负数、正数的数量
		 * 只做统计,不排序,不做乘法
		 */
		$amount_zero = 0;//零的个数
		$amount_negative = 0;//负数个数
		$amount_positive = 0;//正数个数
		$min_positive_index = null;
		$min_negative_index = null;
		$max_negative_index = null;
		$the_only_zero_index = null;

		for($i = 0; $i < $arr_len; $i++)
		{
			if (!is_int($arr[$i]))
			{
				return false;
			}
			if (0 > $arr[$i])
			{
				$amount_negative += 1;
				if (is_null($min_negative_index) || $arr[$i] < $arr[$min_negative_index])
				{
					$min_negative_index = $i;
				}
				if (is_null($max_negative_index) || $arr[$i] > $arr[$max_negative_index])
				{
					$max_negative_index = $i;
				}
			}
			else if (0 == $arr[$i])
			{
				$amount_zero += 1;
				$the_only_zero_index = $i;
			}
			else
			{
				$amount_positive += 1;
				if (is_null($min_positive_index) || $arr[$i] < $arr[$min_positive_index])
				{
					$min_positive_index = $i;
				}
			}
		}

		/**
		 * Logical control start
		 */
		if (1 < $amount_zero)
		{
			/*
			 * 0的个数大于1,任意取N-1个元素,其乘积都是0
			 * 故无须再判断正数和负数的个数
			 */
			return 0;
		}
		else if (1 == $amount_zero)
		{
			if (1 == $amount_negative % 2)
			{//奇数个负数
				/*
				 * 最大乘积只能是0,无需判断正数个数
				 */
				return 0;
			} else {//偶数个负数
				/*
				 * 除0之外的N-1个整数乘积最大
				 */
				$pick_out_index = $the_only_zero_index;
			}
		}
		else// if (1 > $amount_zero)
		{
			if (1 == $amount_negative % 2)//奇数个负数
			{
				/*
				 * 除【绝对值最小的负数】之外的N-1个整数乘积最大
				 */
				$pick_out_index = $max_negative_index;
			}
			else//偶数个负数
			{
				if (0 < $amount_positive)
				{//存在正数
					/*
					 * 除【绝对值最小的正数】之外的N-1个整数乘积最大
					 */
					$pick_out_index = $min_positive_index;
				}
				else
				{
					/*
					 * 除【绝对值最大的负数】之外的N-1个整数乘积最大
					 * 乘积为负
					 */
					$pick_out_index = $min_negative_index;
				}
			}
		}

		/**
		 * 若需要计算N-1个元素的乘积
		 */
		$prod = 1;
		for($i = 0; $i < $arr_len; $i++)
		{
			if ($i != $pick_out_index)
			{
				$prod *= $arr[$i];
			}
		}
		return $prod;
	}
}

Several notes:

  1. This is a code demonstration for my training on “How to Design Complete and Reliable Test Cases”. It is open source on github:https://github.com/qinjx/lotusphp/blo …, will continue to update, please pay attention to
  2. The test cases I pasted only “normal process of correct parameter input” are 100% MECE (completely exhaustive and independent of each other), “abnormal flow of incorrect parameter input” has not yet been MECE, let alone “white box test” in extreme cases, and no test method body has been written.

Php is too hard to write code, so I will not write it. The main points to note are for reference:

1. The product may be very large, so large integer multiplication is required. Even so, direct multiplication of a large integer and an int may overflow, so int must first be converted to a large integer. Php’s integer base is (signed) long. The maximum number of 32-bit and 64-bit is different. The topic is not clear. Be conservative.

2. There will be 0. Two or more 0 results will directly return 0; 1 0 and even negative numbers without positive numbers can also directly return 0.

3. There will be negative numbers. The odd/even numbers of negative numbers should be considered separately and deleted separately.Absolute valueThe smallest negative/positive number.

4. If there are even negative numbers, the negative number with the largest absolute value should be deleted.

The logic of the latter three (and perhaps missing cases) can be simplified by violence. the input can be divided into three categories: positive number, zero and negative number. one zero, the largest positive number, the smallest positive number, the largest negative number and the smallest negative number (up to n, N<=5) can be removed respectively to calculate the result. then the result can be multiplied by any N-1 of the n, compared, and the largest one can be output. this efficiency is also high enough.

Thinking about writing a python version, I think I should be able to pass most of the tests, which is much more comfortable than writing in php.

#!/usr/bin/python

def pop_min_max(l):
    if len(l) == 0:
        return []

    max_item = max(l)
    min_item = min(l)

    l.remove(max_item)

    if max_item == min_item:
        return [max_item]
    else:
        l.remove(min_item)
        return [max_item, min_item]


def findMaxProd(nums):
    if not isinstance(nums, list) or len(nums) == 0:
        raise Exception('bad input')

    if len(nums) == 1:
        return 1

    positive = filter(lambda x: x > 0, nums)
    negtive  = filter(lambda x: x < 0, nums)
    n_zero   = len(nums) - len(positive) - len(negtive)

    if n_zero > 1:
        return 0

    check_list = pop_min_max(positive) + pop_min_max(negtive)
    if n_zero:
        n_zero -= 1
        check_list = [0] + check_list

    pre_ans = reduce(lambda a, b: a * b, [0] * n_zero + positive + negtive, 1)

    ans = []
    for i in check_list:
        ans.append(reduce(lambda a, b: a * b, filter(lambda x: x != i, check_list), pre_ans))
    return max(ans)

print findMaxProd([2, 3, -1, -2, -3])

测试结果

According to the unit test of the subject, a group of test cases were output, and the result was that there were two groups that failed (the last two groups). One of them was the case of [10]. I think the multiplication of 0 numbers should return 1 (similar to the 0 power of x =1, this is different opinions, and cannot be calculated wrong). The other was that the case of non-int in the array was not considered.

Since python inherently supports large integer operations, this code should also be able to do the right thing by the way if there is more than int in the test.

tests = [ 
    (0, [0,0,0,0,0,0,0,-38,8,-28,86,-12,93,-3,3,-74,81,-57]), 
    (39200, [-1,-14,2,5,-14,0,10,-2]), 
    (62500, [-5,-2,0,-1,-25,-25,-10]), 
    (0, [-5,-21,-35,-64,-36,-72,-71,-64,-59,-83,-58,0,86,33,44,43,46,81,87]), 
    (0, [-50,-23,-60,-68,-72,-84,-16,-66,-50,-54,-74,0]), 
    (324900, [-10,-2,-5,-1,-57,-57,10]), 
    (-86490, [-1,-1024,-93,-5,-2,-93]), 
    (819200, [64,-5,4,-2,-10,64]), 
    (451250, [-5,-2,95,-10,95]), 
    (None, [10]), 
    (None, [-2,True,-5]), 
]

for answer, arr in tests:
    if answer != findMaxProd(arr):
        print 'failed for:', str(arr)

Run test output

failed for: [10]
failed for: [-2, True, -5]