Flip array in chunks
arr = [1,2,3,4,5]
arr.each_slice(2).flat_map(&:reverse)
# => [2, 1, 4, 3, 5]
Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
Here's a summary of Dimitris Andreou's link.
Remember sum of i-th powers, where i=1,2,..,k. This reduces the problem to solving the system of equations
a1 + a2 + ... + ak = b1
a12 + a22 + ... + ak2 = b2
...
a1k + a2k + ... + akk = bk
Using Newton's identities, knowing bi allows to compute
c1 = a1 + a2 + ... ak
c2 = a1a2 + a1a3 + ... + ak-1ak
...
ck = a1a2 ... ak
If you expand the polynomial (x-a1)...(x-ak) the coefficients will be exactly c1, ..., ck - see Viète's formulas. Since every polynomial factors uniquely (ring of polynomials is an Euclidean domain), this means ai are uniquely determined, up to permutation.
This ends a proof that remembering powers is enough to recover the numbers. For constant k, this is a good approach.
However, when k is varying, the direct approach of computing c1,...,ck is prohibitely expensive, since e.g. ck is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp or Cantor-Zassenhaus.
High level pseudocode for constant k:
- Compute i-th powers of given numbers
- Subtract to get sums of i-th powers of unknown numbers. Call the sums bi.
- Use Newton's identities to compute coefficients from bi; call them ci. Basically, c1 = b1; c2 = (c1b1 - b2)/2; see Wikipedia for exact formulas
- Factor the polynomial xk-c1xk-1 + ... + ck.
- The roots of the polynomial are the needed numbers a1, ..., ak.
For varying k, find a prime n <= q < 2n using e.g. Miller-Rabin, and perform the steps with all numbers reduced modulo q.
EDIT: The previous version of this answer stated that instead of Zq, where q is prime, it is possible to use a finite field of characteristic 2 (q=2^(log n)). This is not the case, since Newton's formulas require division by numbers up to k.
Related Topics
I Need to Generate Uuid for My Rails Application. What Are the Options(Gems) I Have
How to Reinstall a Gem Using Bundler
What Is an Elegant Way in Ruby to Tell If a Variable Is a Hash or an Array
App Pushed to Heroku Still Shows Standard Index Page
Unit Test in Rails - Model with Paperclip
How to Set a Blank Value for an F.Select Form Field
No Implicit Conversion of String into Integer (Typeerror)
Define a Method That Is a Closure in Ruby
Ruby Class with Static Method Calling a Private Method
How to Get the Ruby Documentation from the Command Line
How to Switch to Older Versions of the Ruby/Rails Environment
How to Handle Exceptions with Ruby Rest-Client
Bundle Command Not Found in Linux Debian
How to Remove 4 Byte Utf-8 Characters in Ruby
Mongodb and Mongoid in Production