Interview follow up

Ah yes I remember that part now. Did think it was a bit strange that I thought I could see an error after only a couple of seconds looking at something you had looked at for hours. Thought it must have been me going wrong somewhere and was interested to know where.

Jonathan Nethercott

This looks like correlation (autocorrelation?) to me. I would look for a solution along the lines of: num xor (num shift left 1) num xor (num shift left 2) etc. repeat until (number of bits / 2) Not a very good bit of pseudo code, but hopefully you get the idea ;) I'm not sure how you'd deal with leading and trailing parts of a sequence, but I'm sure there must be an elegant way of incorporating that...

Jon CodeWrite

Septimus Hedgehog

When will you hear if you've got the job? Best of luck.

"I do not have to forgive my enemies, I have had them all shot." — Ramón Maria Narváez (1800-68). "I don't need to shoot my enemies, I don't have any." - Me (2012).

Member 2053006

Is the simplistic solution of starting with length 1 and checking each character, then increasing to length 2 etc too processor intensive? e.g. for 11011011 1 1 0 O O - Not 1, so period is not 1. K K 11 01 10 11 OK - Not 11, so period is not 2 110 110 11 All OK - Period is 3. Failing that would a FFT work on this information?

leppie

Member 2053006 wrote:

Failing that would a FFT work on this information?

That was my first thought, but coding one from scratch with no external help is a bit tough I think :) That is probably the most efficient way to do it.

IronScheme
((λ (x) `(,x ',x)) '(λ (x) `(,x ',x)))

leppie

Jon Nethercott wrote:

I'm not sure how you'd deal with leading and trailing parts of a sequence, but I'm sure there must be an elegant way of incorporating that...

There are no leading parts (thank FSM!). As for the trailing bit, my elegant solution was to do a negative right shift (see line 11, when rs is negative) that fits into the rest (test on line 17). Brain too tired to remember exactly what I did there now ;p

IronScheme
((λ (x) `(,x ',x)) '(λ (x) `(,x ',x)))

leppie

PHS241 wrote:

When will you hear if you've got the job?

He wants to have another telephonic discussion next week and I guess an offer will be made at that stage, if they so desire.

IronScheme
((λ (x) `(,x ',x)) '(λ (x) `(,x ',x)))

Jonathan Nethercott

I think this should do it:

private int BinaryPeriod(int num)
{
int result = -1;
int numBits = (int)((Math.Log(num) / Math.Log(2))) + 1;

for (int i = 1; i <= numBits / 2 && result == -1; i++)
{
    if (((num & ((1 << (numBits - i)) - 1)) ^ (num >> i)) == 0)
        result = i;
}
return result;

}

I've done it in C#, but hopefully it should be fairly generic code. The important line is:

if (((num & ((1 << (numBits - i)) - 1)) ^ (num >> i)) == 0)

which strips the top i bits and XORs that with num right shifted. If the result is 0 then we have found an autocorrelation.

Jon CodeWrite

leppie

Very good! Wish I knew of it :(

IronScheme
((λ (x) `(,x ',x)) '(λ (x) `(,x ',x)))