Interview follow up
-
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 => 110101010101 => 2
111011011101101110 => 7
111111111111111110 => -1My 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[^].
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?
-
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?
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.
-
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
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
-
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).
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.
-
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
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
-
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
Very good! Wish I knew of it :(
-
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
And here we have it in Scheme :) http://eval.ironscheme.net/?id=59[^] Thanks again!
-
Very good! Wish I knew of it :(
Thank you :) I love solving problems like this - although that has distracted me a bit from what I'm supposed to be doing ;P Good luck with the job!
Jon CodeWrite
-
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 => 110101010101 => 2
111011011101101110 => 7
111111111111111110 => -1My 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[^].
Heh, I had to do that in University.
Need custom software developed? I do custom programming based primarily on MS tools with an emphasis on C# development and consulting. I also do Android Programming as I find it a refreshing break from the MS. "And they, since they Were not the one dead, turned to their affairs" -- Robert Frost
-
Heh, I had to do that in University.
Need custom software developed? I do custom programming based primarily on MS tools with an emphasis on C# development and consulting. I also do Android Programming as I find it a refreshing break from the MS. "And they, since they Were not the one dead, turned to their affairs" -- Robert Frost
Was that some kind of homework or other task? Perhaps thesis? ;p
-
Was that some kind of homework or other task? Perhaps thesis? ;p
Well my degree was computer science. All we did was learn stuff like this. Wouldn't say I knew much about "programming" until after school. But solving problems with code, easy.
Need custom software developed? I do custom programming based primarily on MS tools with an emphasis on C# development and consulting. I also do Android Programming as I find it a refreshing break from the MS. "And they, since they Were not the one dead, turned to their affairs" -- Robert Frost
-
Well my degree was computer science. All we did was learn stuff like this. Wouldn't say I knew much about "programming" until after school. But solving problems with code, easy.
Need custom software developed? I do custom programming based primarily on MS tools with an emphasis on C# development and consulting. I also do Android Programming as I find it a refreshing break from the MS. "And they, since they Were not the one dead, turned to their affairs" -- Robert Frost
Not even in my 2nd year course (just before I decided to go back to working class) we did stuff like this... I left when when we were busy with Data Structures and Algorithms.