Interview follow up

leppie

Was given a problem that was suppose to come from the 'easy' bin. Two hours later I was still not finished... On the plus side, the interviewer attempted the problem at the same time, and also got stuck :) He said the problem must have been miscategorized. He told me to finish at home and to send the solution when done ;p Anyways, after a good nights sleep (with some wack apocalyptic dream I had), I started from scratch and coded a solution in about an hour this morning. The given problem: Binary period (dont bother googling for answers as you will likely just end up getting astronomy results or if you have google foo, a few very mathematical papers mostly related to cryptography) Given a number N larger than 0 (range was given, but does not matter), find the minimum period of repeating bit sequences or -1 if none is found. Examples

110110110 => 3 (as 110 repeats)
11011011 => 3 (still 3 and valid as the remaining subset, 11, is in 110)
110110111 => -1 (no period)
101 => -1 (no repeats, repeat implies at least 2 sequences)
10101 => 2 (repeat at least over 2 sequences)
11 => 1

10101010101 => 2
111011011101101110 => 7
111111111111111110 => -1

My answer in Scheme can be viewed and run here[^]. Edit: Web host seems to be down now... Edit 2: Seems to be back up again, please only look one at a time ;p Damn you shared hosting. If above link is down, view here[^].

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

NormDroid

404 - Web Page not found. Seems a strange answer to this particular question ;)

Software Kinetics Wear a hard hat it's under construction
Metro RSS

DaveAuld

leppie wrote:

My answer in Scheme can be viewed and run here[^].

What 404 response is the answer? Or did you not find the solution :laugh:

Dave Find Me On: Web|Facebook|Twitter|LinkedIn

Folding Stats: Team CodeProject

DaveAuld

Leppie couldn't find the solution then!

Dave Find Me On: Web|Facebook|Twitter|LinkedIn

Folding Stats: Team CodeProject

leppie

Norm .net wrote:

404 - Web Page not found.

:wtf: Worked when I pasted it, webhost must be down...

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

leppie

Seems to be working again now. Guess 3 concurrent users are too much for it to handle...

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

leppie

Seems to be working again now. Sorry.

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

TPFKAPB

leppie wrote:

101 => -1 (no repeats, repeat implies at least 2 sequences)

Shouldn't that be 1 repeat and still valid? ie 10 and then 1.. Especially given your answer to the second pattern

leppie wrote:

11011011 => 3 (still 3 and valid as the remaining subset, 11, is in 110)

leppie

TPFKAPB wrote:

Shouldn't that be 1 repeat and still valid? ie 10 and then 1..

Ooops yes, thanks :) Will fix.

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

leppie

TPFKAPB wrote:

Shouldn't that be 1 repeat and still valid? ie 10 and then 1..

Nope, that is correct. "repeat implies at least 2 (complete) sequences"

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

TPFKAPB

Ok so then what about the line below that. 11 => 1 That is only one sequence is it not? Or two sequences but then it should read 11 => 2

leppie

You made a small interpretation mistake (I do it all the time too). The result is the minimum period, not the number of repeats :)

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

TPFKAPB

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