Interview Question

Senior Software Engineer Interview New York, NY

Given an integer array, write a program that returns an

  array with elements = product of the integers in input array except the one in its position. Ex: Given input: [2, 3, 10, 4, 5], output: [600, 400, 120, 300, 240] What is the complexity of your program? When will your program not work? Below is what I presented (O(n)), but it did not qualify me for the next round.
Answer

Interview Answer

5 Answers

1

public int product(List<int> input)
{
    int product = 1;
    foreach(int i in input)
    {
        product = product * i;
    }
    return product;
}

public void printOutput(List<int> input)
{
    foreach(int i in input)
        Console.WriteLine(i);
}

public List<int> multiply(List<int> input)
{
    List<int> output = new List<int>{};

    int total_product = product(input);
    foreach(int i in input)
    {
        output.Add(total_product/i);
    }
    return output;
}

public void main()
{
    List<int> input = new List<int>{"2","3","10","4","5"};
    printOutput(multiply(input));
        Console.ReadLine();
}

Interview Candidate on Jun 9, 2014
0

If the pre condition is none zero integer list then I think the answer is correct.

h on Jul 28, 2014
0

This is not O(n). Your product() function alone is O(n). This is actually O(2n).

Anonymous on Sep 25, 2014
0

While the above solution does iterate the list twice, that doesn't matter for asymptotic runtime - it's still O(n).

Anonymous on Apr 5, 2015
0

There can be a slight improvement. Instead of having to iterate through the list again in the multiply step, you can do that directly in the printOutput method.

public int product(List<int> input)
{
    int product = 1;
    foreach(int i in input)
    {
        if(i== 0)
            return 0; // You don't need to read the rest of the array
        else // if you encounter a 0.
            product = product * i;
    }
    return product;
}

public void printOutput(int totalProduct)
{
    if(totalProduct != 0)
    {
        foreach(int i in input)
        {
            Console.WriteLine(totalProduct/i);
        }
    }
    else
        Console.WriteLine(0);
}

public void main()
{
    List<int> input = new List<int>{"2","3","10","4","5"};
    int totalProduct = product(input);
    printOutput(totalProduct);
    Console.ReadLine();
}

Anonymous on May 11, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.