Merging arrays
Thanks to interviewpattern.com I discovered that one of the classical Amazon interview questions is writing a snippet of code to merge two sorted arrays:
"Suppose we have two sorted arrays A[] of m elements and B[] of n elements. Write a function merge which would merge this two arrays into new sorted array C[] in O(n) time as shown on the picture".
This problem is also a classical exercise for functional programming learners that shows the conciseness of functional code in comparison with imperative one.
The solution presented on the original page is written in C# and is longer than 40 lines of code, while we can solve the same problem in F# with less than 10 lines:
let rec merge_arrays a b =
match (a, b) with
| (a, []) -> a
| ([], b) -> b
| (x::xs, y::ys) -> if (x < y) then
(x :: (merge_arrays xs (y::ys)))
else
(y :: (merge_arrays (x::xs) ys))
Besides being shorter, I also find the functional code to be much easier to understand. Do you agree with me?
Facebook FizzBuzz
Have you ever tried looking for "FizzBuzz" on a search engine?
If you do, you'll surely land on this page on Coding Horror, the blog written by Jeff Atwood.
To make a long story short, Jeff states that the vast majority of the developers is unable to write a tiny program that should take no more than 10 minutes to code.
This is the famous FizzBuzz problem:
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”.
You should be outraged now, if you aren't I hope you don't make a living as a developer! 
I found out that Facebook also considers FizzBuzz as a good starting test for job applicants. There is a programming puzzles page, where you can find a set of good problems, ranging from blindingly easy to very hard.
The first one is called HoppityHop! and it is just a variation of the good old FizzBuzz:
The program should iterate over all integers (inclusive) from 1 to the number expressed by the input file. For example, if the file contained the number 10, the submission should iterate over 1 through 10. At each integer value in this range, the program may possibly (based upon the following rules) output a single string terminating with a newline.
* For integers that are evenly divisible by three, output the exact string Hoppity, followed by a newline.
* For integers that are evenly divisible by five, output the exact string Hophop, followed by a newline.
* For integers that are evenly divisble by both three and five, do not do any of the above, but instead output the exact string Hop, followed by a newline.
Being a developer myself I couldn't resist writing a solution for this problem, obviously in F#:
#light
let HoppityHop n =
let printHop x =
match x with
| x when (x % 15 = 0)-> printfn "Hop"
| x when (x % 3 = 0) -> printfn "Hoppity"
| x when (x % 5 = 0) -> printfn "Hophop"
| _ -> ()
[1 .. n] |> Seq.iter printHop
I know many of you will feel the urge to suggest a better solution, you're welcome, the comment area is yours to use!
Balanced parenthesis
Checking whether a series of parenthesis is balanced and valid is a classic puzzle in computer science and can be easily met during a job interview.
In my opinion, there is no better solution than using a regular expression and solve the problem with a single (but almost unreadable) line of code, however I'd like to describe an algorithm which can be easily implemented in any functional or imperative programming language.
The idea is simple: start from the first character and check if it is an opening parenthesis. In this case we have to push it on a LIFO data structure such as a stack and continue with the next character.
If the character is a closing parenthesis, we take (pop) the top element from the stack and check if it makes a valid couple of brackets with the examined element.
If this is not the case, the series is not balanced, otherwise we can discard both parenthesis and go on with the next character, until the series is over.
When there are no parenthesis left to examine, if the stack is empty our series is valid; if there are still elements on the stack we can conclude that the series is unbalanced.
Lets give a look at the F# implementation I wrote to answer Dev102's challenge:
#light
let brackets = [('(',')'); ('[',']'); ('{','}'); ('<','>')]
let is_opening bracket = List.exists ( fun (a,b) -> a = bracket) brackets
let is_closing bracket = List.exists ( fun (a,b) -> b = bracket) brackets
let is_valid (opening, closing) = List.exists (fun (a,b) -> (a,b) = (opening, closing)) brackets
let rec check_valid stack char_array =
match char_array with
| [] -> stack = List.Empty
| c::cs when is_opening c -> check_valid (c::stack) cs
| c::cs ->
match stack with
| [] -> false
| x::xs when is_valid (x, c) -> check_valid xs cs
| x::xs -> false
At the beginning I defined the list of valid couples and three functions to check respectively if a char is an opening or closing bracket or if a couple is valid.
After that there is a function implementing the algorithm explained above. The stack is just a normal list, where items are always added and removed from the front.
The missing number
There is an interesting series of programming job interview challenges proposed by Dev102.com, which is now at its tenth puzzle:
This week question is pretty easy. Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. According to those rules, one of the numbers is missing and you are asked to provide the most efficient method to find that missing number. Notice that you can’t allocate another helper list, the amount of memory that you are allowed to allocate is O(1). Don’t forget to mention the complexity of your algorithm…
I'm not sure I understood correctly the constraint related to the memory allocation.
In my opinion, when they say we are limited to O(1), they mean that we can only allocate a single numeric variable and not any other data structure.
According to this interpretation, the solution is quite easy.
First of all, we take our only variable and store into it the sum of all the numbers between 1 and n + 1, which can be easily computed remembering that 1 + 2 + ... + n = n (n + 1) / 2.
Then, we subtract each element of the array from this value, eventually the result is actually our missing number.
The functional implementation of this imperative algorithm is straightforward:
#light let sum n = ((n + 1) * (n + 2)) / 2 let answer nums = (nums |> List.length |> sum) - (List.reduce_left (+) nums)
Let's talk about the complexity of the algorithm.
If the length of the input list list is known, evaluating the sum of the first n natural numbers takes O(1), otherwise we have to scan the entire list, i.e. O(n).
Then we have to subtract each element of the list, and this takes another iteration, so another O(n).
Therefore we have O(n) + O(n), which is definitely O(n), and can be easily optimized a little by scanning the list only once.
The only problem left is: "am I following the instructions"?
Twitter Updates
- @Sabrina_Miso Che ne pensi di Community Manager per Google? In caso contattami ;) http://t.co/tBQ2e0N9 #stage #casaeditrice 1 week ago
- @MarcoEscher chi si rivede! In bocca al lupo per il tuo cammino e chissà che magari un giorno tu non mi raggiunga in Google! ;) 2 weeks ago
- @pigatss you should give one to me because I hosted you for lunch at the Googleplex :) #volunia 2012-01-13
- Avete visto quante posizioni per italiani sono aperte in Google a Dublino? http://t.co/ZlUfZ4uA 2012-01-10
- @thetarro congratulations, I gained 4 kg in 4 weeks :( 2012-01-08
- More updates...
Posting tweet...
Follow me
