[Archive!] Pure mathematics, physics, chemistry, etc.: brain-training problems not related to trade in any way - page 583

New comment
 
MikeM:

About the clock:

4 minutes after the start flip 4 minutes after the start

after flipping in 4 mins 4 mins, in 7 mins 3 mins.

after another 3 minutes

in 4-minutes 1 min, in 7-minutes 0

turn over 7 minutes

in 4-minutes 1 min, in 7-minutes 7

after another minute.

4 minutes 0, 7 minutes 6

turn over the 7 minutes.

in 4-minutes 0, in 7-minutes 1

in another minute - the right time!

correctly)
 
The first pass counts the ones, twos and threes, and the second pass fills the "sorted" array with the right number of numbers
 
First pass count, second pass write. O(n) of course.
 
GaryKa:

Here is a puzzle.

Sure, it's boring, but at interviews it works as an apotheosis of array sorting knowledge.)


So, a sorting problem

There is an array of N cells, in which units, twos and threes are placed in random order.

Build the best sorting algorithm.


I.e. only 3 choices of data?

First pass: count how many ones, how many twos and how many threes.

Second pass: we fill.

Total 2 passes.

 
MikeM:
First pass - counting ones, twos and threes, second pass - filling "sorted" array with right amount of right numbers
Yes )) poor candidates clogged by previous questions on sorting what not to do for the fun of the public, and the bubble, and inserts, and all combinations with exceptions
 
GaryKa:
Yes )) poor candidates, too shackled by previous sorting questions, do what they do for the entertainment of the public, with bubbles, sampling and all sorts of combinations with exceptions
Whatever you need isn't complicated. Anything that is complicated is unnecessary!
 

A simple (for programmers) question:

A+B=...

 
lvalue expected :)
 
This is not an operator of any language. It is the left-hand side of the equality. What should be written on the right-hand side?
 
sand:


I.e. only 3 variants of data?

First pass: count how many ones, how many twos and how many threes.

Second pass: fill in.

Total 2 passes.

In one pass:

Create an empty copy of an array of the same size, initialise it with twos.

We go from the beginning of the array. If we encounter 1, we copy it from the beginning; if we encounter 3, we copy it from the end.

1...576577578579580581582583584585586587588589590...628
New comment