Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
----
We don't actually need a computer to solve this problem, but why not?
The formula for the sum of the squares of the first n natural numbers is: n*(n+1)*(2n+1)/6 .
The formula for the sum of the first n natural numbers is: n(n+1)/2 .
We can write this in ruby:
def sumToN(n)
(n*(n+1))/2
end
def sumOfSquares(n)
(n*(n+1)*(2*n+1))/6
end
puts sumToN(100)**2 - sumOfSquares(100)
Note that you don't need an explicit return statement. The last expression in any function will be returned by default.
Every interview is difficult, because on both sides, you know you're about to make an important decision based on very little information. But it seems to me that interviewing a recent college grad can be especially difficult for an industry veteran. There typically isn't much to say about the candidate's past software experience or framework knowledge, so the interviewer is left evaluating the candidate only on intelligence and personal qualities, rather than on real-world software development competence. So what are the most useful questions to ask in this scenario?
Here are some of the memorable questions I've been asked in interviews for an intern or junior software developer role: the good, the bad, and the ugly.
Q: A Microsoft puzzle, such as: How many gas stations are there in the USA?, or How many golf balls fit into a school bus?
My verdict: Bad. If the candidate doesn't display her cluelessness by being flabbergasted, how exactly do you judge the creativity or accuracy of her reasoning?
Q: Write a function to reverse a string.
My verdict: Good. Discussing solutions that optimize for space or speed can show a candidate's understanding of the basics (or lack thereof).
Q: There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.
My verdict: Bad. Either the candidate has heard this question before, or he hasn't. Even the unlikely case where he comes up with the solution on the spot doesn't tell you much about his prowess with a compiler or a customer.
Q: Does object-oriented Square extend Rectangle?
My verdict: Good. What does resize(3,5) do to a Square : Rectangle? If a brand-new developer can see this pitfall to the naive approach to object-oriented design from CS 101, that's pretty good.
Q: The typical HR-type questions: What is your weakness; Where do you want to be in five years?
My verdict: Ugly. Unless the candidate, instead of reciting the typical canned answer, admits a fondness for underage girls, or his plan to take over your business and become your boss.
Q: Design an elevator system for a 100-story office building.
My verdict: Good. Opens the discussion to technical and UI factors, and lets you assess your candidate's creative and problem solving skills. Can he see the big picture?
Next time: more ideas for effectively interviewing entry-level developers.
Last week, I went to Eric Ivancich's awesome AACS talk on Using Ruby to Create Domain-Specific Languages here at the SRT Solutions office. I'd been lazy before, but that day I decided to finally pay my $20 AACS dues and become an official member. As more validation for the fact that I'm the luckiest girl in the world*, I ended up more than recouping my loss when I won the Borders gift card in the members-only drawing at the end of the night! Now I'm faced with a serious dilemma... what to spend it on, from my mile-long Books To Read list? My educational options:
A new ruby book, maybe The Best of Ruby Quiz? Inspiration after learning more about ruby's metaprogramming features
or:
The software engineering book everyone's been talking about: Beautiful Code
I'm earmarking this hard-earned money for tech, and making myself stay away from the fiction section (mmm, very tempting). What does everyone think? I love reading recommendations.
* Other evidence: I get to work with not just one, but three Microsoft MVPs!
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
----
To solve this problem easily, we need to remember that the smallest number that is evenly divisible by two numbers is their least common multiple. Armed with this knowledge (and the fact that ruby already has a least common multiple function!), we can write:
numbers=(1..20).to_a
puts numbers.inject{ |x,n| x.lcm(n) }
So for those of you at SRT (or elsewhere) that still harbor any doubts about ruby, can you beat that?! Fine, ok, so you might say that using a built-in lcm function is kind of lame. So as a bonus, here's how I implemented lcm myself in a cute way using the greatest common divisor:
def gcd(a,b)
if b==0 : a
else
gcd(b, a % b )
end
end
def lcm(a,b)
(a*b)/gcd(a,b)
end
A while ago, we had a discussion here at the office about nerdy t-shirts. We all know what I'm talking about: usually worn by a male geek/programmer with a neckbeard, a black shirt with a "witty" technical reference. Opinions about these shirts vary among SRT employees: some of us find them funny and even wear them on dates [no report on the results, though], some are skeptical. You might guess that I fall into the second camp. Here are the worst offenders in my book:
The geek love poem...
It's so bad it's good.
The worst one of all. Nearly ubiquitous in computer science buildings on campuses nationwide, but yet still considered brilliant and unique by the wearer.
And of course, I can't leave out geeky women's gear -- in some ways even more horrifying than the men's stuff. Evidence presented:
HTML tags -- get it?!
I have no words. Instead I'll leave you with ThinkGeek's description of these: "... we bring you HTTPanties
for the discriminating woman who would prefer a web-savvy and somewhat-direct
approach in the romance department. Feeling frisky? Well then don the black "200 OK" panties and see where they take
you. Alternatively, the white "403 Forbidden" style sends a very different
and hopefully clear message. We think "411 Length Required" and "413 Requested Entity Too Large" are pretty self-explanatory."
Find the largest palindrome made from the product of two 3-digit numbers.
-----
First, I defined a palindrome recursively: a number is one if its first and last digits are the same, and if the inside is also a palindrome.
def palindrome?(digitArr)
if digitArr.empty?
true
elsif digitArr.length == 1
true
else
(digitArr.first == digitArr.last && palindrome?(digitArr[1..-2]))
end
end
Note that in Ruby, methods can end with a question mark, a convention that really helps readability. Also note that the "else if" keyword is elsif, which is weird and unhelpful to me. I want that 20 minutes of staring at my code like "wtf?!" (before figuring that out) back.
Then we do a search of all the multiples of two three-digit numbers until we find the biggest palindrome:
def search(i,j)
maxPal=0
while i > 99 do
j=999
while j > 99 do
if palindrome?((i*j).to_s.split("")) then
if(i*j)> maxPal then maxPal = i*j
end
end
j-=1
end
i-=1
end
return maxPal
end
puts search(999,999)
There's probably a prettier way to do this.
What is the largest prime factor of the number 600851475143 ?
-----
I wrote this piece of disgusting, un-Rubylike Ruby to get the answer by creating a list of a number's prime factors:
def factor(composite)
i=1
flag=false
primefactors =[]
while (i < composite)
i=i+1
primefactors.each{|p| flag=true if (i%p).zero?}
if flag then flag=false
else # if it is a prime
primefactors.push(i) #add the prime (since it's a prime factor)
while (composite%i).zero? # as long as n is divisbible by the prime
composite /= i # divide n by the prime
end
end
end
primefactors
end
puts factor(600851475143).last
And then I learned that ruby has a prime number generator. All I need to do is:
require 'mathn'
n = 600851475143
factor = 0
primes = Prime.new
while n > 1
factor = primes.next
while (n % factor).zero?
n /= factor
end
end
puts factor
I am slightly ashamed.
The problem:
Find the sum of all the even-valued terms in the [Fibonacci] sequence which do not exceed four million.
Here's my fibonacci function:
def fib(limit =nil)
f1 = 0
f2 = 1
while (not limit or f2 <= limit)
yield f2
f1,f2 = f2, f1+f2
end
end
And here's how I use it to get the answer:
evens=[]
fib { |x| if x%2==0 : evens.push(x) end ; if x>4000000: break end}
puts evens.inject {|sum, n| sum+n}
I learned about the awesomeness of 'yield' by doing this problem, so it was totally worth it. yield let me calculate as many fibonacci terms as I needed, but not more, and without having to calculate any term more than once.
I'm taking Bill Wagner up on his Project Euler challenge, but in Ruby. I've secretly wanted to learn Ruby for a long time, and this looks like the perfect chance. So if my code makes your eyes bleed, it's cause I'm a total n00b. Without further ado (because the excitement was becoming unbearable... I agree, Ruby is sexy!), here's my code that prints the answer to Problem 1:
If we list all the natural numbers below 10 that are multiples of 3
or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
answer = (0..999).select { |a| a%3 ==0 || a%5==0 }
puts answer.inject { |sum, n| sum+n }
I love the built-in ruby function inject, which is like foldl in some functional languages. (See a cute demo here.) Overall the code is very similar to Bill's C# version. I wonder if that'll still be the case as we get to the more complex problems.
[4/08/08: correction of a typo in the code]
I know I'm not the only one with tons of my data stored somewhere on Google's servers these days (frightening, I know.) Luckily, there's the Google Data API, which lets us access and modify our Google data programmatically, should we decide to, say, display it on our websites or build custom applications to process it.
The API uses HTTP requests to transfer data, building on top of RSS and Atom the ability to send a query and receive a feed of matching results. This is cool, because it means we can access our data easily, just by creating the appropriate HTTP query. Here's what I mean:
This is the XML feed of our SRT Events Google Calendar: http://www.google.com/calendar/feeds/v2433p4md2226qtd3ja1annifc%40group.calendar.google.com/public/basic
We can add query parameters to the end of this URL: http://www.google.com/calendar/feeds/v2433p4md2226qtd3ja1annifc%40group.calendar.google.com/public/basic?max-results=10&orderby=starttime
That new-and-improved feed is the full calendar feed of events, filtered to leave only 10 results and ordered by the start date of the event. Note that in addition to a standard set of parameters for all
Google Data, there are some special ones defined for each app, like
"racy" in YouTube.
Here's the metadata for the most-viewed YouTube videos:
http://gdata.youtube.com/feeds/api/standardfeeds/most_viewed
and adding these query parameters gives us just the family-friendly ones, ordered by rating.
http://gdata.youtube.com/feeds/api/standardfeeds/most_viewed?orderby=rating&racy=exclude
Now that we've got these custom feeds, we can just use any standard libraries to parse or display them. Pretty cool.