[Archive!] Pure mathematics, physics, chemistry, etc.: brain-training problems not related to trade in any way - page 584
You are missing trading opportunities:
- Free trading apps
- Over 8,000 signals for copying
- Economic news for exploring financial markets
Registration
Log in
You agree to website policy and terms of use
If you do not have an account, please register
In one pass:
Create an empty copy of an array of the same size, initialize it with twos.
Go from the beginning of the array. Encounter 1 - write to the copy from the beginning, encounter 3 - write to the copy from the end.
Plus you have to monitor three pointers at the same time!
I'll give you a little task.
Of course, it's a hack, but at job interviews it works as an apotheosis of array sorting knowledge ))
So, the task for sorting
There is an array of N cells, in which the ones, twos and threes are placed in random order.
Build the best sorting algorithm.
Count on one pass, fill in the array on the second pass.
In one pass:
Create an empty copy of an array of the same size, initialize it with twos.
Go from the beginning of the array. If 1 is encountered, write to the copy from the beginning; if 3 is encountered, write to the copy from the end.
Without copy (or you will say that filling the copy is a separate pass).
n=0, m=0
Start at the beginning of the array. If we meet 1 - change it with n-th element from the beginning, not equal to 1 (by construction it will always be 2), n++; if we meet 3 - change it with m-th element from the end, not equal to 3, m++, and if we meet 1, we follow steps of the first part.
Without copy (or you will say that filling the copy is a separate pass)
n=0, m=0
We go from the beginning of the array. If we meet 1, we change it with n-th element from the beginning not equal to 1 (by construction it will always be 2), n++; if we meet 3, we change it with m-th element from the end not equal to 3, m++, and if we meet 1, we proceed as described in the first part.
Without copy (or you will say that filling the copy is a separate pass)
n=0, m=0
We go from the beginning of the array. If we meet 1, we change it with n-th element from the beginning not equal to 1 (by construction it will always be 2), n++; if we meet 3, we change it with m-th element from the end not equal to 3, m++, and if we meet 1, we proceed as described in the first part.
That's a great way to go.
Reducing the number of passes does not always give an increase in speed.
A+B=...
Without copy (or you will say that filling the copy is a separate pass)
n=0, m=0
We go from the beginning of the array. If we meet 1, we change it with n-th element from the beginning not equal to 1 (by construction it will always be 2), n++; if we meet 3, we change it with m-th element from the end not equal to 3, m++, and if we meet 1, we proceed as described in the first part.
Good idea.