Coding Quiz: better solutions @jhr-python - Tumblr Blog

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

#code quiz #binary #Interviews

Coding Quiz: Comparison of the speed of various Fibonacci methods

This is not really a interview quiz question; but just an addenda to my previous fibonacci blogs to illustrate how much better the adaptive and memoization methods are compared to the standard. Numbers are obtained through the use of the Timeit module. Note that it is standard to run the method to be time multiple times to allow for variations in time due to various external factors. In the program included below I picked 100; just since it seems to good enough to illustrate the speed differences.

https://gist.github.com/6357439

#Python #fibonacci #interviews #performance

Coding Quiz: Printing out all the possible letter combinations for a seven digit phone number

This is actually a slight variation on a question that I got asked at an interview: print out all possible letter combinations for a keypad.

I really wonder how one would solve this cold if you had never seen the problem ( or a variation on it) previously. What I outline here is a solution involving recursion; though there are versions that used nested loops; which are from intuitive.

I had gotten as far as setting up the dict and working on the recursion process ( which I had tried writing in perl before I learned that python is a far easier language to remember under pressure).

needless to say; its much easier to setup and test with a compiler.

Here is the process in main():

Setup the keypad dict: Use the digit values as the the keys and the letters on the keypad as values. I decided to keep an accurate phone mapping which has four letters for 8 and 9. I did though have the values for 0 (aka Operator) be 0 and 1 be 1. There are no character mappings for these values on phone. I have gotten into the habit of using characters as opposed to integers for keys; unless I have a precise need for the keys to have integer values.

Initialize Variables: Define the phone number and initialize the loop list.

Setup the loop list: This will be a list of character strings corresponding the phone number that will be used to determine the combinations.

Initialize the combo list: Set this equal to the character string that corresponds to the first digit in the phone number. In the example used; this is 'TUV'

Call the combo loop that returns the new combo list: I will detail that seperately.

Check/test the results: By printing out the list of all the combinations along with counting them. For the sake of this example; I picked numbers that all had three character mappings. Note that 3**7 =2187 which matches the count we get back.

Here is the process for combo(): Note that we pass in the loop and combo lists along with an integer level which is the digit that is be looked at or the current level of the recursion

initialize variables: the newcombo variable

Start the level loop: This will cycle through the loop variable for this level which is the character string of the current level ( or digit)

Start the combo loop (this is a nested loop): this will go through all the current values in the combo list.

Create the newcombo list: There are two operations going on at once: creation of the new string with the current character being added to the end of the current string. The result is then appended to the new combo list.

After both loops have finished:

Increment the level variable

conditional: If we still have more digits to look at

set combo equal to newcombo

call combo again ( noting that this time both combo and level are different)

return the newcombo variable back to main() once level equals 8

Here is the code and output:

https://gist.github.com/6350187

#Python #Interviews #Quizzess #recursion #keypad #phonenumber

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

#Python #code quiz #fibonacci #memoization

jhr-python

Here is the question:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Things to pay attention to:

...

jhr-python

Theory: The Fibonacci numbers (series or sequence) are the numbers in the integer sequence: 0,1,1,2,3,5,8,12,21.. which can be defined more compactly by:

with seed values

This, along with the factorial , are often used as a way to introduce people to concept of...

#Python #interviews #quizzes #fibonacci

The Fibonacci sequence : Recursion: The Good; the Bad and the really kind of ugly

Theory: The Fibonacci numbers (series or sequence) are the numbers in the integer sequence: 0,1,1,2,3,5,8,12,21.. which can be defined more compactly by:

with seed values

This, along with the factorial , are often used as a way to introduce people to concept of recursion; which I assume the reader is already familiar with. Further more; one can also talk about adaptive methods when dealing the most resource effective ways of calculating it.

The big idea: Here is the standard recursion implementation of calculating a fibonacci number

if n is less than 2 ( i.e. 0 or 1) return 1

else call the function again for the next two lowest values:

Writing the code:

https://gist.github.com/6324950

Why is this bad? While to code is pretty straightforward to read and understand; the resource usage here is bad due to the inherent repeated calculation. This function is asymptotically O(2n).

To make this better; the fix is to somehow keep track of the values that are already calculated instead of determining them as need. I will show the two more popular methods in future write ups.

#Python #fibonacchossequence #Interviews #quizzes

Coding Quiz: Team Names ( part 2)

Problem: You are given a list of team names} ['team1','team2','team3','team4','team5','team6']

Write a program that will add a suffix consisting of an underscore and a letter (A,B,C). The letters must follow sequential order. Once ‘C” is used; go back and repeat the process. Your output should look like:

Name is team1_A

Name is team2_B

Name is team3_C

Name is team4_A

Name is team5_B

Name is team6_C

Part 2: I sent a copy of the previous blog to the person who asked me the original question. He promptly sent me two more methods of solving the problem. They are interesting in that they use two very different approaches.

https://gist.github.com/6331283

Coding Quiz: An okay way and a much better way to add suffixes to team names

Problem: You are given a list of team names} ['team1','team2','team3','team4','team5','team6']

Write a program that will add a suffix consisting of an underscore and a letter (A,B,C). The letters must follow sequential order. Once 'C" is used; go back and repeat the process. Your output should look like:

Name is team1_A

Name is team2_B

Name is team3_C

Name is team4_A

Name is team5_B

Name is team6_C

The original way I did this was through use of a function; which is way too clunky. The better way to do this is to treat the letters list like a queue. Pop the 0th element from the list: use it to create the new team name; and then append it back into the list. So the final program should look like this:

https://gist.github.com/6331593

Compare this to the clunky way I did it before:

https://gist.github.com/6331600

Roughly twice the amount of code and far harder to understand

#Python #interviews #lists #quizzes

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

#Python #interviews #salesforce #code quiz

Coding Quiz: the FizzBuzz problem

Here is the question:

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

Things to pay attention to:

Read the problem a few times before attempting to code: In our rush to finish on time we can often miss things. Being nervous will also make you rush too.

Clarity should always trump brevity: It will often be the case that an engineer will ask you followup what if functionality questions. So try and think big picture first

Testing Testing Testing: Be prepared to answer "How would test it" even on the simple programs. Don't assume that you will be given access to a computer to check for syntax errors so unless you are 100% sure you remember some obscure python fu; don't risk it.

Think of the future: Many engineers don't code for the next person who will be reading their code. So having easy to read code will also be looked kindly upon

https://gist.github.com/6331688

Nobody will expect you to write comments every five lines for something this simple; but a summary of what the program does is a good idea and will help you focus as well.

#Python #fizzbuzz #Interviews #coding #quizzes

Coding Quiz: Tricks with Strings

Starting out with string foo='abcd':

String length:

>>> len(foo) ->

Make String Upper Case: >>> foo.upper() -> "ABCD"

Make String Lower case: >>> foo.lower() -> 'abcd'

Print out the Lower or Uppper Case characters in a string: Use islower() and isupper() for case testing: e.g. goo='ABCDefg'

>>> for i in goo:

... if i.islower():

... print i

Note that isdigit() can be used to test to see for digits (0-9) in a string or test individual characters like above.

#Python #interviews #quizzes

Coding Quiz: Reversing yourself: Strings and Lists

Some useful one-liners from interview questions I was asked:

reverse a string: use the slice functionality

>>> foo="123"

>>> print foo[::-1]

321

reverse a list: You can use the slice functionality just like we did on the string but you can also use the reverse builtin method:

>>> goo=[4,5,6]

>>> for i in goo:

... print i

...

>>> goo.reverse()

>>> for i in goo:

... print i

...

Coding Quiz: Finding the missing element in an Array/List or a ball of differing mass

I have seen this asked both in perl and in python. You are told that you have an array/list of the numbers 0- 12 ( or any elements). It is an ordered list; but one of them is missing. How do you determine which one is missing in the optimal method. The brute force approach of checking each element in the list is NOT what is called for here. Depending on your technical background; the solution that I will describe will be known to you as either a binary search or Newton's Method.

Something to remember for the interview : A binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log2 n + 1 time units are needed to return an answer.

Key point: realizing that if all the elements in the array/list are still ordered; then the value of the 0th element should be zero and so on. Once the missing value is reached; this mapping will break.

So we begin with examining the middle: so in this case 1/2 of 12 is 6. So we examine the value the sixth element. If it is six; then we realize that the missing value must be in upper reaches of the list ; if its 5; then we realize that the location of the missing element is somewhere between element 0 and element #5 . z If it's 6; then we realize we have to examine the upper interval: elements 7 to 12. So we pick the half way point of the next interval depending on this answer and repeat the process.

Variation: A variation on this same method also works on a problem where you are given 10 balls and old style balance; and you are asked to find the ball that is a different mass (lighter or heavier) than the others in the least amount of steps. This is more a testing experiment that a coding quiz: You first divide the balls into 2 piles of 4 and one pile of 2. Place the two piles of four on either side of the old fashioned scale. For argument's sake; say one ball is heavier than the others. Just reverse the logic if the ball is lighter There are three possible outcomes:

the scales balance: The remove the balls from either side; and repeat the process with the two balls that you put aside; one on each side of the scale.

the left side is heavier: Remove the balls from the right side of the scale and place two of the balls from the left hand side on the right.

the right side is heavier: Remove the balls from the left side of the scale and place two of the balls from the right hand side on the right.

For steps 2 and 3: repeating the process will eliminate two balls from consideration; leaving two final balls to test.

the problem often asks what is minimum number of tests that you need to do: There are two possible answers:

Going from 4<->4 to 2<->2 to finally 1-1; This means that you need to do three mass measurements.

Equal balance case : going from 4<->4 to 1<->1: You need to do two.

Many people just do the equal split method and don't realize the trick to getting it done in two.

#Python #interviews #quiz

jhr-python

My tendency was a coder with a QA background was to write scripts that are “quick and dirty”. I was short on time and need to get something working fast; without really caring about resource usage. During my job interviews; I would often answer using one of my standard rote methods that I...

#Python

A Better Way to Parse Large Files

My tendency was a coder with a QA background was to write scripts that are "quick and dirty". I was short on time and need to get something working fast; without really caring about resource usage. During my job interviews; I would often answer using one of my standard rote methods that I developed over the years ; not thinking that I would be graded on more than " does it run" and get downgraded without even realizing what I did wrong.

Here is a question that I got asked during a technical phone screen with a much more resource friendly way of solving it .

One of my phone screen questions gave me the scenario of needing to parse through a large text file for test results for a test named NiteTest. I was warned that the file could be ~ 2GB so reading it into memory was not a good idea. Note the use of hashing allows me a resource friendly way of keeping track of what lines were already inspected; without saving the lines in memory. Note that this is easily expandable to keep track of the number of duplicate lines through the use of a dict or a custom class.

#Python #testing #code #interviews

Trending Blogs

Recently Viewed Blogs

Coding Quiz: better solutions