ZocDoc

www.zocdoc.com
Engaged Employer

## Interview Question

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.

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