Menu
You can't modify the length of an array, only can allocate a new array. "In place" means that you can't allocate a new array either. Keeping a separate Length variable is not uncommon, required in a language like C. It is the most efficient way to do it.
An in-place method modifies data structures or objects outside of its own stack frame ↴
There are many sorting algorithms that are using in-place approach. Some of them are insertion sort, bubble sort, heap sort, quicksort, and shell sort and you can learn more about them and check-out their Java implementations. Also, we need to mention comb sort and heapsort. All these have space complexity O(log n).
I am preparing for a software job interview, and I am having trouble with in-place array modifications.
For example, in the out-shuffle problem you interleave two halves of an array so that 1 2 3 4 5 6 7 8 would become 1 5 2 6 3 7 4 8. This question asks for a constant-memory solution (and linear-time, although I'm not sure that's even possible).
First I thought a linear algorithm is trivial, but then I couldn't work it out. Then I did find a simple O(n^2) algorithm but it took me a long time. And I still don't find a faster solution.
I remember also having trouble solving a similar problem from Bentley's Programming Pearls, column 2:
Rotate an array left by
ipositions (e.g.abcderotated by 2 becomescdeab), in timeO(n)and with just a couple of bytes extra space.
Does anyone have tips to help wrap my head around such problems?
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With