Good morning! Here's your coding interview problem for today.
This problem was asked by Uber.
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
You program fucking division. from additions and byteshifts etc. If they ask questions like that, they wouldn't understand its a division anyway.
I'd probably just walk away from the interview if they start asking stupid stuff like this. I mean. This stuff really is trivial. And I can't be bothered to work at a level like that.
At the moment I'm working on machine learning, which I also hate because.of.all the arrogant fucks around me who think they're good scientists, while they're just copy pasting each others github. Of course they design bad algorithms and don't even know how to test it properly. (There are a few intellogent people, but not enough)
Joseph Rivera
no wonder their app is so shit
Jose Miller
products :: (Fractional a) => [a] -> [a] products xs = map (n /) xs where n = product xs
Brody Robinson
Multiply by x^-1, interviewers won’t know the difference
Christian Wright
>You program fucking division >Of course they design bad algorithms
So you just make a O(N^2) loop that multiplies everything else but the index you're in. Even a female should be able to do this.
Lucas Barnes
Create an array of products before each index. Go through it in reverse multiplying with product accumulator of original values starting from the end. O(n) space, O(n) time. Everyone ITT should drink bleach, especially the 60 IQ „machine learner“.
how did I do #returns the product of all elements #except the one at $index def prod_lst(lst, index): res = 1 for i in range(len(lst)): if i != index: res *= lst[i] return res
def solve(lst): return [prod_lst(lst,i) for i in range(len(lst))]
` 0 #include 1 #include 2 3 int *uber(int *array, int len); 4 5 int main() { 6 int array[] = {1, 2, 3, 4, 5}; 7 int *newArray = uber(array, 5); 8 9 for(int i = 0; i < 5; i++) { 10 printf("%d\n", newArray[i]); 11 } 12 return 0; 13 } 14 15 int *uber(int *array, int len) { 16 int *newArray = (int *) malloc(len*sizeof(int)); 17 18 for(int i = 0; i < len; i++) { 19 int product = 1; 20 21 for(int j = 0; j < len; j++) { 22 if(j != i) { 23 product *= array[j]; 24 } 25 } 26 newArray[i] = product; 27 } 28 return newArray; 29 }`
I'm happy with it. Tell me why it's shit Jow Forums.
Oliver Morris
That was my first guess, though the division seems more obvious once you think about it
Henry Hill
Just got done with studying this variation on my daily mock interview Leetcode session before coming to the thread, which I unfortunately didn't get but I went and studied the problem and explanation and feel like I can explain it now.
The algorithm is simple. Initialize your result arrray, r, to 1 for all elements, and then do two traversals. The traversal, left to right, first sets at your result array at i a temp variable which contains the product of all elements multiplied by each other in your input array except for the current element in the input, which you then multiply to temp after setting result[i] to temp. You then do another traversal, multiplying from right to left in the same fashion. Those two products multiplied together then are what you want which is then inside the result array and you've done the problem in O(n) time and O(1) if you don't count the result array as space needed.
Code is the following in C. int *product_array_except_self(int array[], int n) { int i, temp = 1; int *result = (int *)malloc(sizeof(int) * n);
for(i = n - 1; i >= 0; i--) { result[i] *= temp; temp *= array[i]; }
return result; } [\code]
Christian Price
>loop that multiplies everything else but the index you're in What's wrong with this solution? I'm a mathlet. >knowing mathematical formulas for highly specific operations that are rare is the norm I'm not going to make it
Robert Price
It's slower. But that fits perfectly in the current coding paradigm.
Jeremiah Anderson
>optimizing fucking array passes for time >knowing mathematical formulas for highly specific operations Fuck off back to /v/ and stay there, turbonigger.
Evan Powell
>this whole fucking thread
I guess you really DO need to know math to get into programming. Kill me.
Ryan Martinez
Only slower for arrays of 20 elements or more in x86.
Jackson Bell
Corner case detected: what about zero? Ambiguous wording detected: how does "all the numbers except the one at i" handle duplicates? At first glance it looks like it's intended the simpler way; answer[i] is the product of all other input positions. But if it's not, and the actual number at input[i] is what counts, then given [2,2,1] the answer is [1,1,4] instead of [2,2,4]. And then that leads to the issue of multiple zeroes, because then the output might be all zeroes or not.
Of course they could specifically be hoping that applicants do ask these questions, which shows the applicant is thinking both about the logic and the spec...
Alexander Price
while(1){ printf("i will not do your homework for you.\n"); }
Daniel Thompson
>create an array of products >then go through it in reverse That's O(n^2), thanks for your time & we would like to keep your resume at hand.
Kayden Ward
#returns the product of all elements def prod_lst(lst): res = 1 for i in range(len(lst)): res *= lst[i] return res
def solve(lst): prod = prod_lst(lst) return [prod // i for i in lst]