You are correct, the time complexity would be O(n + m). I'd kind of mentally filed it away as being O(2n) since the magnitudes of n and m aren't known to be meaningfully different from one another.
I've also clarified that the Nodes can be compared either by value or by identity.
the kind of data that the lists will hold should be told about (types and ranges), especially if you wanna the user to achieve O(n) time and O(1) space (edit: well... Seems I found somehting not really expected...)
I'm a little unclear on what the exact question is here, but the actual node values are sort of irrelevant. They exist to make the problem easier to understand, but it's perfectly possible to implement this challenge with Node objects that have no value attribute, only a next (based on identity alone).
why char strings in the sample tests and sintrged integers otherwise? I mean... I get why numebrs... But why as strings??
The test cases needed very long lists, so numbers were necessary. They're converted to strings so that the types are consistent with the example test cases.
I didn't want to catch anyone by surprise with the types of the values changing without notice.
are the perf requirement actual requirements or just a bonus? The description is misleading about that
The bonus is specifically in regards to the optimal solution. While there is a minimum performance threshold, (ie. the O(n^2) solutions will time out), other solutions exist that will run within required time.
This is as intended. It's meant to immitate similar instructions on real hardware. For example, consider the operation PUSHA (as part of the X86 instruction) set. It pushes registers in order
EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI
Whereas its corresponding restore instruction POPA pops registers in order
EDI, ESI, EBP, ESP, EBX, EDX, ECX, EAX
This way, a PUSHA will save all general registers to the stack, and a subsequent POPA will restore them in the exact order they were in previously.
I was unable to reproduce the issue, and submitted a solution successfully. It might've been a one-off bug. Could you try refreshing the page and sumbitting again?
This comment is hidden because it contains spoiler information about the solution
I've added two extra test cases, including one with an empty input list.
You are correct, the time complexity would be
O(n + m)
. I'd kind of mentally filed it away as beingO(2n)
since the magnitudes ofn
andm
aren't known to be meaningfully different from one another.I've also clarified that the Nodes can be compared either by value or by identity.
I've added
it
blocks to the test cases and grouped the performance tests into a single block.I'm unclear how best to use
it
blocks for the randomly generated test cases. It would be difficult to provide a useful description of the test case.Do you have any suggestions or a reference?
I'm a little unclear on what the exact question is here, but the actual node values are sort of irrelevant. They exist to make the problem easier to understand, but it's perfectly possible to implement this challenge with
Node
objects that have novalue
attribute, only anext
(based on identity alone).The test cases needed very long lists, so numbers were necessary. They're converted to strings so that the types are consistent with the example test cases.
I didn't want to catch anyone by surprise with the types of the values changing without notice.
The bonus is specifically in regards to the optimal solution. While there is a minimum performance threshold, (ie. the
O(n^2)
solutions will time out), other solutions exist that will run within required time.Fixed that. I've honestly not worked with MiniTest much (I assume this is MiniTest).
Yeah, just noticed that. Fixed.
Thank you kindly, accepted both.
Also, I'll throw up some random one myself in a bit, but thank you for the offer!
alright, thank you! Accepted.
This is as intended. It's meant to immitate similar instructions on real hardware. For example, consider the operation PUSHA (as part of the X86 instruction) set. It pushes registers in order
EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI
Whereas its corresponding restore instruction POPA pops registers in order
EDI, ESI, EBP, ESP, EBX, EDX, ECX, EAX
This way, a PUSHA will save all general registers to the stack, and a subsequent POPA will restore them in the exact order they were in previously.
The expected solution is a naive one. Basically, assume all input will be valid.
Make sure that your solution handles whitespace tokens correctly. That's the best I can suggest with the given information.
What? It's the most time efficient solution
I was unable to reproduce the issue, and submitted a solution successfully. It might've been a one-off bug. Could you try refreshing the page and sumbitting again?
Loading more items...