Hey everyone! Hope you enjoyed solving last week’s challenge. In case you haven’t seen it, I’ll link last week’s article so you can go check it out...
For further actions, you may consider blocking this person and/or reporting abuse
Small code review regarding the solution: I would refrain from using the term "pointers" - both on explanation and implementation - since the solution does not use actual pointers. Suggestion: rename to pivots (or indexes) instead.
Agree, most appropriate term would be
index
.Pointer
reminds me of memory allocation.Good point! :)
Not the fastest algorithm but this is what I came up with.
Good work!
I like this solution as it is very straight forward. Defining normalize was great going in.
This solution allows n-amount of inputs and uses Set to check all items are the same.
made the function to support also other data types of input..
changed naming and simplified return statement (new Set() is not ran if result.length > 1 fails first).
Doesn't Set remove duplicates?
yes.. that is why end result size should be 1
[1,1,1] => [1]
the code checks first that the initial array has more than 1 input so
[1] => [1]
would fail on the first length check
Nice!
Stack solution using JavaScript array methods push and pop. O(n).
I'm learning clojure, which isn't supported by Coderbyte :-(
Here's my clojure solution:
One of the benefits of having a close relationship with our community is hearing what you all want and building it! Like this comment if you'd be interested in Coderbyte supporting clojure!
I can't think of anything else other than a stack-based solution.
You can try to go in backward direction whule comparing char by char without strings creation. In best case you will determine that strings are different at first iteration. At worst - iterate for max(n, m) times. And in any case you will only need constant extra memory allocation
I think a stack-based solution is the most efficient and readable method, to be fair...
If we think about the complexity it should be around O(n)
(n (to compute first) + n (to compute second) + n(to go once over both))
Which is ofc not as good as the O(log(n)), but I am not sure there's a way to cut times.
Also we can do a sneaky trick such as
But... to be 100% correct, in order to determine if this is helpful or just added time for our average case we would need to know the context a bit more in depth.
Love the stack based approach!
I'm not convinced this works with every case; You're missing some edge cases such as
Hi Simon,
You are correct, well spotted. I changed the solution to reflect your case and hopefully all cases :-)
Couldn't do it with one regex though :-(
This is actually awesome, it shouldn't take long to make this into something that works with multiple lines
Not the "code golf" solution, but I think is more readable and avoids nested looping (plus I think the ternaries are more readable once they get a little long using multiple lines).
"Clever" solutions are fun... maintainable ones save time :D
If you wanted to split this out to handle multiple cases or non-compliant arrays (say with spaces or non-string content) I would add additional functions to handle those cases, but not as the spec exists now.
Localization for non-English languages could be handled by adding a language code param to the function or a constant.
Changed, only cause when I submitted on coderbyte, the test cases showed that "-B" cases were possible in the first string (IE: comparing vs an edited string as opposed to a base-string, so... egg on my face haha)
(And I edited again... because code review matters, and there's code to be removed...)
Here's the modified solution:
O(s+b) is good. s for small( to search for) and b for big (to search in). But I guess, using O(s log b) is a better approach, esp if b>>s. Instead of the linear search, going with a modified binary search that indicates whether the element being searched is outside the other array's bounds would be much faster. In that case, you can get rid of the condition of the smaller array being sorted.
Some Java code that:
I came up with this simple solution :D
function checkEquivalentKeypresses(strArr) {
var x = strArr[0].split(",");
var y = strArr[1].split(",");
function backSpace(arr) {
for(var i = 0; i <= arr.length - 1; i++) {
if(arr[i] === "-B") {
delete arr[i];
delete arr[i-1];
}
}
}
backSpace(x);
backSpace(y);
if(x.join("") === y.join("")) {
return true;
} else {
return false;
}
}
checkEquivalentKeypresses(["a,b,c,d", "a,b,c,c,-B,d"])
true
checkEquivalentKeypresses(["-B,-B,-B,c,c", "c,c"]);
true
checkEquivalentKeypresses(["-B,-B,-B,c,c", "c,c,e"]);
false
checkEquivalentKeypresses(["", "a,-B,-B,a,-B,a,b,c,c,c,d"]);
false
Got this recommended via Google and gave it a try :)
Nice! Glad you found us :)
Just compare starting from the end of the strings. When you see "-B" (possibly consecutively), you know you can skip stuff. O(n) time and O(1) space.
The fact that backspace is two characters and the keypresses are separated by commas is gross. It would be so much nicer (and realistic) for the input be an ASCII string with literal backspace characters.
Important thing when just skipping:
lets say we have "a,c,-B,-B" and we start from the back: we see a -B, so we skip the next character, now there is a c and then an a so we get ca (reversed), which is wrong. You need to count the -B s that are back to back and then remove as many "chars". also agree, real chars would be far better, also returning literal "true" and "false" hurts a lot
A rust solution without using a stack and any number of strings:
play.rust-lang.org/?version=stable...
Ill proably make one that fails as soon as there is a difference between the arrays, maybe it will be done tomorrow
Done, also feels way less hacky and doesn't spin strings around:
play.rust-lang.org/?version=stable...
Thank you, these articles are really useful.
Enjoy!!
Hi there, this is the solution I came up with :)
The insight here should be that this is a variation upon Merge Sort.
Here is my solution