Stock Exchange Losses puzzle discussion

Puzzles
#82

I found a Solution in JavaScript. I had to optimze (read completely redo) my code, after finding myself in the exact situation you described.

#83

Test 5 says that is not optimal :frowning:

#85

In Scala the problem of the test5 was the use of var stocks = List[Int]() when i changed the List for an array var stocks = Array[Int]() the performance improved and the test passed. And probably using an mutable Array val stocks = scala.collection.mutable.ArrayBuffer[Int]() instead of a mutable Array the performance will improve a little

#86

To anyone that comes back to this looking for help (and I doubt there will be), know that you can solve this with literally three lines of code or less. No need to build lists or arrays or keep track of the whole number series. It’s really a simple logic problem so think it through first.

#87

This is what I did too but its not optimized enough for test 5.

#88

Hi, I passed all test cases but failed at validator 6 – Varied (1 5 4 10 8 4 5 42 41).
Cloud anyone tell me what that means and why it failed. Thank you.

#89

This would be > O(n) because lets say n = 9999. And lets say that out of all of n there are X low values. That means that you have O(n*X) which will significantly increase your runtime. The way I did it is to keep track of the highest value while in the loop and compare all values ahead of it to the highest value taking the max loss. This solution is O(n) because you don’t have to run back through the list.

#90

It is O(N) because I’m only looking at the lowest point in the values, the global minimum, and going back, I’m not looking at the X local minima you mention. The solution I describe was only working because of a flaw in the test cases though. What I did was incorrect as I mentionned in my post.

#91

I didn’t get performance problems with list using a set of (min,max) representing the different decreases, so you can avoid completely mutable variable or structure.

Here the algorithm I used :

with the input
[3; 2; 10; 7; 15; 14]
I transform this list in
[(3,2); (10,7); (15,14)]
I convert it calculating the difference
[-1; -3; -2]
And finally I search the minimum wich is -3

I parse 3 different lists, performance is enough to pass all the tests

#92

Does anyone know why a code I wrote in C++ doesn’t pass a single case when translated from my Python 3 code that got 100%?

#93

Problem solved by expressing a value as 2000000 instead of 2*(pow(10,6))

#96

I recommend moving this puzzle to Easy section.

1 Like
#97

I really liked this one. Test 5 is the only test that matters.

For those who are struggling:

  1. It helped me to think of it in terms of mountains and valleys.
  2. There is an O(N) solution that is actually quite simple.

My suggestion is to not overthink it.

2 Likes
#99

Since my first brute force attempt backfired, i stupidly did a 180 and used recursion. First check if the index of the max is to the left of the min if so return the simple subtraction. Else
split the array in two from zero to the index-1 of max, and from there to length. Rinse and repeat with the two new arrays, compare and return result. Plus some tweaks for max== min and 1 element arrays.

#100

My solution was to divide-and-conquer with a recursive algorithm that takes advantage of the the fact that if list.Min() is the last element in the list, then maxLoss = list.Min() - list.Max(). If the min was not the last element, I split the list at the min value and returned the Min() of the results of the two separate lists.

The first of the sub-lists always had the min value as last index, so it would calculate in 1 call. The other half would most often need multiple calls.

I believe the complexity is O(nlogn), but not exactly sure. It’s definitely not as fast as the best solution, but it is fast enough.

#101

I used brute force. Test num. 5 was passed after deleting “System.err.print” statements in code

#102

I liked this puzzle but as simple feedback I would say the test case names in the IDE could be more descriptive.
Examples could be “No Loss” for a test case that expects “0” and for a testcase with a large input you could put “Large Number Of Values”. :slight_smile:

1 Like
#103

prices = { 5, 3, 2, 20, 6, 14 }

First I iterated forward through the list and kept a running max at each index

maxes_before = { 5, 5, 5, 20, 20, 20 }

Then I iterated backward through the list and kept a running minimum at each index

mins_after = { 2, 2, 2, 6, 6, 14 }

Then find the minimum of subtracting the elements in these two arrays

min( { -3, -3, -3, -14, -14, -6 } ) = -14

1 Like
#105

So I did something, it all passes except test5.
Someone can give me a hint to make something more optimized

#106

tell us what you did, it will be easier for us to know how to help you