We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Lily's Homework
- Discussions
Lily's Homework
Lily's Homework
Sort by
recency
|
24 Discussions
|
Please Login in order to post a comment
Made this harder for myself by not seeing that the numbers in the array have to be distinct. This is mentioned in the introduction but not when stating the parameters. This typescript satisfies the test cases and all the examples with duplicates that I tested. Too long for a comment: https://gist.github.com/MullPointer/5ce0d0ef6b40ba5306e8cb69f2a9aa70 It could definitely be optimized more as the recursion will still go out of control if there are too many repeats, so too many possible cycles to test.
The provided examples are misleading. I was left with the understanding that the result of the series of swaps must be the array sorted in ascending order, because all examples given produce the array sorted in ascending order.
This caused me a lot of time to understand why the answer for [3, 4, 2, 5, 1] was 2 and not 4.
It would be really bad if such misleading problem stories happen actually at an interview.
To improve the performance - search complexity should be improved. Usual swap sorts have "n^2" complexity. Think about preparing some sorted array with faster complexity, "n* log n" should be ok. Then prepare some kind of map of the sorted array as a key and the original index in the given array as a value. That allows making swaps on the next stage with "n" complexity. This solution is not optimal in case of memory usage, but for this kind of task should be okay.
Swift