#code quiz

[jhr-python]

Coding Quiz: Binary Addition

Another common question is:

Write a program to add two binary numbers without the use of the + operator. 

Questions to Ask:

Are the numbers of arbitrary length or size?   If the numbers are of identical length; then the processing is significantly easier. I think this answer depends on what they are truly interested in seeing as well as how much time you are given to solve the problem.

Are there any other operators that can not be used? As pointed out by others; one can use the - operator to do this. You may get a pat on the back for an out of the box method.

Solution:   There are two distinct areas that you will need to right code in. First thing to realize is that this problem can be solved by recursion. Consider the lowest digits first then work your way up.

How to add two single digit binary numbers:  there are only three possible outcomes depending on the values of the numbers ( either 0 or 1): 

0 and 0 :  The result for this is always 0 with a carry of 0 

0 and 1 ( or 1 and 0):  The result for this is always 1 with a carry of 0 

1 and 1: the result for this is 0 with a carry value of 1 

What is a carry ?: When I talk about carry value I am referring to result of a calculation that requires an extra number to handle. This value needs to get passed along to the next calc. For example; if the test values were 1  and 1; we would report the result as 10 (that is 2 which is a 1 in the second digit)  since there are no additional digits to take into account. So the idea here is to use this same procedure to each of the digits in the numbers.

How to end the recursion?:

So now we need to think: how do we end it? We have checks put in such that  when it detects "0b" as one of the remaining numbers that it does the following:

If both numbers are now "0b": Then we can end the process. We need to be careful though and check to seei f there is a remaining carry and to prepend that to the result.

If either number is now "0b": If we have a non-zero carry; we append it onto the number that is currently "0b" and we repeat the process with one final call; also making sure to set the carry value to zero.  If there is no carry value; then we just prepend the remaining number to the result.

How to represent binary numbers?:  It made the most sense to me to consider both binary numbers as strings. I found it particularly useful since I was able to use various slice operations to streamline the solution. 

Here is the code that is checked into Github 

https://gist.github.com/6576421

[jhr-python]

Coding Quiz: Fibonacci Recursion: the bad (counter) and the better (lookup table and cache loop)

As I mentioned in the last blog; the main drawback of the standard fibonacci recursion is the multiple calculations of the same fibonacci number.  The calls grow faster than the actual value does. To illustrate this: please look at this program and its output:

https://gist.github.com/6338684

Please read the comments here to see the output

When this program is run; it is really apparent how much the extra calculations slow it down. The last five values on the list; especially 30; are agonizingly slow to come out. One can add  a lookup table ( the fancy term for this is memoization  ) to avoid the calculation of previously determined values.

To illustrate this: please look at this program and output:

https://gist.github.com/6338738

Please read the comments here to see the output. 

There is no noticeable performance hit to calculate any of those values unlike in the previous version.

According to the dynamic programming wiki  requires only O(n) time instead of exponential time (but requires O(n) space) for this top down approach :

  And yet another approach mentioned in dynamic programming wiki   is a bottom down approach where we calculate the lower values first and cache the last two and . via a loop; we work our way to the desired value. This method also uses O(n) time since it contains a loop that repeats n − 1 times, but it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(n) space to store the values. Here is the code I created ( and the output is given in the comments section of the Gist)

https://gist.github.com/6343758

[jhr-python]

Coding Quiz: Finding non repeatable alphabetical characters in a file

Problem:  Determine what alphabetical characters  are not repeated ( i.e. unique) in a file. Ignore any other characters.  Case is significant.

Personal Notes: As far as I can remember; this was my phone quiz from salesforce done via collabra edit. At that point in my search; I was still thinking that I was a better with perl than python given my more years of experience with it. What I have found out over due course is that python is far easier to remember than perl due to it being less cryptic and object based.  For simplicity and testing sake; I have varied slightly from the instructions by using a systems log file along with printing out character counts for non-unique letters.

https://gist.github.com/6336899