Retired

Searching massive numerical arrays (retired)

Description
Loading description...
Algorithms
Arrays
Data Types
  • Please sign in or sign up to leave a comment.
  • JohanWiltink Avatar

    My solution uses flawed logic, but it only very occasionaly bombs a ( random ) test.

    There should be a fixed test that my solution would fail.

    I'm too lazy to figure out the exact edge case - this kata has too many other issues.

  • FArekkusu Avatar

    This may be accomplished with a BST, and will most likely fail through traditional iteration

    Except a linear solution doesn't have an O(n * log(n)) time complexity and will most likely return the result faster. This "hint" should be removed.

    • JohanWiltink Avatar

      It would probably make more sense to improve testing, requiring an O(log n) solution, failing anything O(n) or worse.

      With per test performance measuring, that should be doable.

  • FArekkusu Avatar

    The reference solution returns [undefined, undefined] instead of [null, null] when the array is empty.

    • James1x0 Avatar

      Function is guaranteed an array length > 1

      Issue marked resolved by James1x0 6 years ago
    • FArekkusu Avatar

      This is not mentioned anywhere, and sounds more like you're too lazy to fix your solution and add a corresponding test.

    • James1x0 Avatar

      It is. bigArray => [ Number, Number, ... ] Reading through the description carefully would've netted you seeing that and spared me an insult.

    • Unnamed Avatar

      It's too subtle. (And if every detail should be understood literally, a function that "should return an array with 2 elements that are integers" should never be expected to return null as an item.)

    • James1x0 Avatar

      Thank you for presenting an actionable issue, and not calling me lazy. I've tweaked the description. :)

  • FArekkusu Avatar

    The user can modify the input.

  • FArekkusu Avatar

    No sample tests.

    • James1x0 Avatar

      This has also been fixed - my bad!

      Issue marked resolved by James1x0 6 years ago
    • FArekkusu Avatar

      Stop closing the issues until somebody verifies that it's working. As of now, nothing has been fixed.

    • James1x0 Avatar

      https://user-images.githubusercontent.com/6146261/62568587-c98c0c00-b84a-11e9-9549-8c8d0a9061a6.png This is my current state of publishing. Validating works, but I cannot publish.

    • JohanWiltink Avatar

      Yeah, that happens. Just keep trying.

      But please control yourself and don't close the issue until the fix has been published ( and even then, try to wait for confirmation. We're practically working with you in realtime here ).

    • James1x0 Avatar

      It was published!

    • JohanWiltink Avatar

      Unfortunately, retirement is final.

      You get a second chance at publishing your first kata though.

    • James1x0 Avatar

      This process has been really crappy, and not supportive at all, in which I recieved insults from a user. I doubt my comments will make much of a difference, and I understand that, which is why I doubt I would waste time submitting anything else, unless I had an abstract idea for a "story style" problem. Pretty much anything algorithmic in nature is probably a "duplicate". This is asimilar to the fact you'd never return to a makerspace in which people just called you lazy for forgetting about a small part of a project, and then threw your project in the garbage. It was a good go at learning about generating random tests, though.

  • FArekkusu Avatar

    Duplicate.

    • James1x0 Avatar

      Please reference a kata?

    • JohanWiltink Avatar

      Oh, there's Binary Search right from the Similar Kata section of this one's Description ..

      Note that a kata doesn't have to be identical to be a duplicate - having the same underlying concept ( i.e., binary searching ) is enough.

      The added touch of having to find neighbours instead of an index where to insert does not convince - and it's not tested adequately either.

    • James1x0 Avatar

      So, I was unaware of the alternative definition of "Duplicate" that you suggest. Typically duplicate is an synonym of "identical". This kata requires some additional logic inside a bst algo, which should spur some identity. All of this is somewhat bike shedding - if it's a duplicate, let's kill it, if it's not, let me improve it and use your energy on this conversation to help me do so.

      Saying it's not tested adequately is also not helpful or constructive, please tell me why and what I can do to improve that. I did attempt to override the Array indexOf prototype in the suite, but chai or mocha uses it under the hood and it breaks the test. Any ideas?

    • JohanWiltink Avatar

      I have commented somewhere above here with a buggy algorithm that ( mostly ) isn't caught by your testing. That is what I was referring to.

      The problem people refer to when shouting "Duplicate" is the one referenced in Wiki - Kata Best Practices - Make Sure Content is New. If the concept behind a kata isn't novel, it needs some additional oomph to not be a duplicate. Actually, the additional logic you require does spur a bit of identity, but publishing a first kata without sample tests, with input that can be modified and with problems in the reference solution ( even if - kudos - it has random tests. but all of its problems aren't new to us ) makes us think you have not read available documentation, not learned enough from solving existing kata ( and reading their tests and comments ) and generally not spent enough effort that we should be required to spend effort explaining in detail what we think you did wrong. This can be counterproductive, and often is, but publishing kata that feel unfinished is also counterproductive - experienced people on here will not tend to think "let's explain the new author the ropes .. again".

      I don't know if this kata can still be saved. You really have to get most everything right before you hit Publish, or you will accumulate downvotes fast, and people may not come back to change their vote even if you fix the problem. Truly original ideas are hard to come by these days, with 6 000 preexisting JS kata. But, especially if you publish a new one that looks vaguely like an existing one, get as many things as you can right, right from the get go.

      O(n) solutions passing tests should never have happened either. I think that one can be fixed by tweaking the performance parameters on a couple of large tests. 100 ms probably is just too much time still.

    • JohanWiltink Avatar

      OK, it's now retired so it can't be saved anymore. When redoing this ( which I think is worthwhile ), fix all reported problems before publishing and you have a shot at a survivable first kata.

      Closing this now.

      Good luck!

      Issue marked resolved by JohanWiltink 6 years ago
    • FArekkusu Avatar

      When redoing this

      I don't see any point in this. There're plenty of katas asking you to implement a binary search either explicitly or implicitly, and creating any more of these will not benefit anybody. If the author thinks he's going to make something worthwhile by coming up with a generic idea after having completed 30(!) katas, I have bad news for him...

    • JohanWiltink Avatar

      I was hoping having to find neighbours was enough added twist. But, thinking about it again, generic binary searching finds the index at which to insert the new value, and from there it's really a trivial addition.

      Afraid you're right.