Solving Project Euler Problem 1

7 February 2016
In this series, we'll be solving Project Euler problems. First using brute force approach(if possible), then using optimized approach. Let's get started!





Project Euler Problem 1 states that:

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.

Let's make it more generic, instead of finding the sum of all the multiples of 3 or 5 below 1000, let's find the sum for any number. The number could range from 0 to millions. Our program should be able to handle it. We will verify this behavior with test cases.

Okay! I'm going to take object oriented approach here to organize the code, but feel free to skip the object oriented part, if you are not cool with it.

Let's quickly add the basic skeleton.

  class DivisibleBy3And5
    def initialize(number)
      @number = number
    end

    def sum
      23
    end
  end


Our test skeleton

  describe "divisible by 3 or 5" do
    def numbers(number)
      DivisibleBy3And5.new(number)
    end

    it "should return 23" do
      expect(numbers(10).sum).to eq(23)
    end
  end


Let's go through each chunk of code one by one.

First of all, we have a DivisibleBy3And5 class, which is taking a number on initialization and storing it @number instance variable, so that we don't have to pass the number around to each method.

Next we have 'sum method, which currently just returns a static value(1000).

Moving on to our test code. The numbers method is just there to initialize our class DivisibleBy3And5 so that we can use simply pass number to our numbers method, have it return an instance of our DivisibleBy3And5 class so, that we could easily call our other instance methods like sum to get the sum. This approach makes our test code concise and easier to read.

Our skeleton looks good and gives a clear picture of the overall system, but it's not very useful, so let's make it more useful.

Brute Force Solution


  class DivisibleBy3And5
    def initialize(number)
      @number = number
    end

    def sum
      return 0 if @number < 3
      calculate_sum
    end

    def calculate_sum
      sum = 0
      (3..@number-1).each do |number|
        sum += number if divisible?(number)
      end
      sum
    end

    def divisible?(number)
      number % 3 == 0 || number % 5 == 0
    end
  end


And our test suite:

describe "divisible by 3 or 5" do
  def numbers(num)
    DivisibleBy3And5.new(num)
  end

  it "should return 23" do
    expect(numbers(10).sum).to eq(23)
  end

  it "should return 2318" do
    expect(numbers(100).sum).to eq(2318)
  end
end


Run the tests and it's passing. Great!

This was simple enough. Our brute force approach helped us get started with the problem in hand without getting overwhelmed, but we can optimize this to improve performance.

What's the complexity of our brute force approach, you asked? Given the number N, we are iterating through each number, incrementing sum by adding the number, if the number is divisible by either 3 or 5.

Checking if the number is divisible by 3 or 5 takes constant time, so does the adding number to sum variable, but we are performing N number of constant operations for a given number N, so the big-oh complexity of our brute force approach is O(N). Simple!

Optimized Approach

Step back for a moment, and think about the problem. Does it follow some kind of pattern? I'll let you think before proceeding.


Hint: It's a mathematical problem, so it involves some kind of mathematical expression.


Okay! Let's start breaking down the problem statement.


List all the numbers below the number N that are multiples of 3 or 5. Let me rephrase it. List all the numbers below the number N  that are multiples of 3

3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...

or all the numbers below the number N that are multiple of 5

5, 10, 15, 20, 25, 30, 35, 40, ...


There are two things to notice here.

  1. Each sequence(let's call it S3 & S5) forms a series called arithmetic series.
  2. They have some numbers in common. 15, 30, 45, 60, ... in other words they have an arithmetic series in common with the difference between each element being(d) 15 and first element being 15(a).
So we need to add the sum of first series(S3) & sum of second series(S5) and finally subtract the sum of third series(S15) from the sum of first two(i.e. S3 & S5).

In mathematical term, it can be represented as Sum of S3 + Sum of S5 - Sum of S15


See, how dividing problem into smaller pieces, makes the solution easier?

Enough Math! Let's write some code.

  class DivisibleBy3And5
    def initialize(number)
      @number = number
    end

    def sum
      calculate_sum(3) + calculate_sum(5) - calculate_sum(15)
    end

    def calculate_sum(divisor)
      n = (@number - 1).div divisor
      divisor * n * (n + 1)/2
    end
  end


Everything looks simple enough except calculate_sum method, which requires some explaining.

For number 100, the value of N would be 99, as it's the largest number, which is divisible by 3 and is still less than 100. So, to the sum for S3 series would be (3 + 6 + 9 + ... + 99), since 3 is common we can extract it, so our series becomes 3 * (1 + 2 + 3 + 4 + ... + 33).

Now the (1 + 2 + 3 + 4 + ... + 33) part is particularly interesting. It forms a sequence of first N numbers, where N is 33. What's the sum of first N natural numbers? It is N(N+1)/2. So, to calculate the sum of (3 + 6 + 9 + ... + 99), we are simply multiplying 3 to N(N+1)/2, which is exactly what we are doing at line 15.


So, to achieve all of this, we are calculating the largest natural number for 1 + 2 + 3 + ... series at line 14, at line 15 we are simply multiplying divisor(3, 5 or 15) by N(N+1)/2 to get the sum of original series.

Using this approach we have been able to avoid iterating over N numbers, which results in constant time complexity i.e O(1). With our new and optimized code, we can easily handle millions of numbers.


PS: The code listed in this blog post is hosted on Github. Feel free to propose any change by submitting a pull request or by opening an issue.

Read more ...

Technology Agnostic Interview for Web Developers

20 January 2016
One of my friends works as a Java Developer and he was looking for a job change. As a result he was involved with a couple of startups, and for each startup he was learning and doing the assignments in Language/Framework supported by these companies.

One thing I noticed that he was preparing for Language/Framework oriented interviews rather than a generic one, even though he had no professional experience with those Languages & Frameworks.

Here is what's wrong with his approach. While knowing the Language/Framework might give you an edge over other candidates, you should be preparing for a generic web developer interview if you have never worked with [insert Language/Framework].


                                    


How I would conduct(or prepare for) such interviews? I would list out things which are common in web development irrespective of Language/Framework.

So, let's begin listing out these common concepts(this list isn't exhaustive, use it as a guidelines):

  1. Architecture: RESTful Architecture, MVC pattern etc. 
  2. Design Patterns 
  3. Refactoring Techniques
  4. Databases
  5. Client side stuff
  6. Basic Linux Commands, Server Management & Deployment Techniques 
  7. Version Control 
  8. Web Security
  9. Testing

1. Architecture

Here you can ask all sorts of questions related to scaling, code architecture, etc. depending on candidates experience.

Also, I would only expect them to know architecture they have been using all along. MVC architecture is a very good example of that. Example of frameworks which follows the MVC pattern are Ruby on Rails, Django, ASP.NET MVC, Laravel etc.

Here's a list of questions to begin with:
  • What is REST? Can you explain it with example? - I'll look out for basic understanding of how urls are organized using RESTful architecture, purpose of various HTTP requests types etc.
  • How does a typical monolithic application laid out? Can you describe the major components? - Here I expect them to describe various components of the application like databases, application servers, web servers, caching servers, etc.  
  • How would you scale a monolithic application? Where would you start? - Here I expect them to mention common performance issues. This is very generic. Common optimization technique includes Database optimization, microservices, caching, code cleanup, serving Static content etc.
  • What are the advantages of frameworks following patterns like MVC vs barebones framework which doesn't enforce any pattern? 
Note: I won't care if they don't know what these fancy words like monolithic, microservices etc the important thing is that have they ever thought about it? If not can they?

2. Design Patterns

I won't judge if they aren't aware of any pattern. It's quite possible for junior web developers to be not aware of design patterns that they been using all along.

If they are a fan of a particular design pattern, then I would ask them to explain it and understand why they like it over other design patterns or in which situation a particular design pattern fits in?

3. Refactoring Techniques

You generally want to understand how would they go about refactoring their code base. What are the general techniques they employ to improve their code. I expect them to mention basic techniques like DRY, KISS, YAGNI, keeping variable names readable, keeping methods short and concise, keeping return data predictable etc.

4. Databases

As a backend developer, you should know the basics of SQL, but if you've been working with ORMs like ActiveRecord and you can write relatively complex queries (using joins, includes, associations & methods provided by ORM) then it's fine too! This is one of the things which depends on requirements as well as candidate's experience. If your code base has lots of complex non ORM SQL queries, then you can focus on SQL part as well.

5. Client Side Stuff

Since the focus of this post is on Web Developers rather than Web Designers I would ask things like how cookies & sessions work, CORS, when to use local storage, web sockets, javascript basics etc. Here's a small list of questions to test against:

  • Difference between Sessions & Cookies? And How they work?
  • Explain CORS?
  • What is web sockets and polling? Use case for web sockets?
  • How do you organize your JavaScript code?

6. Basic Linux Commands, Server Management & Deployment Techniques 

The candidate should not be scared of terminals. You should have basic knowledge of Linux commands, if you don't, then try this The Command Line Crash Course

Here's a small list of questions you can use to evaluate them:

  • How to navigate between directories, create them, remove them using command line.
  • Creating, deleting, updating files from command line.
  • How to ssh into remote machine? What the steps required?
  • Handy server management tools? Backups, Snapshots, releases, symlinks, shared directories etc
  • Why do you need deployment scripts? Favorite deployment tools.
  • How to setup a server from scratch?
  • Difference between app server & web server.


7. Version Control 

I would ask which version control system they have been using and what was their usual work flow. How often they commit, how they keep commit message short and concise, and other basic tasks performed. Here's the basic starting point for git:

  • How would you setup a repository using git(or your favorite version control system)? - If they have ever used a version control, then should be able to explain it.
  • Why do you use version control system? Advantages & Disadvantages?
  • How do you create branches? Why do you need them?
  • How do you resolve merge conflicts?
  • How would you revert a commit that has already been pushed?
  • Do you use aliases? 
  • How do you check logs and diffs?
  • Difference between merge, squash merge & rebase?
  • Most handy and least popular feature of git?
The basic idea is to check if they have been using version control effectively or not and learn a thing or two from them.


8. Web Security

The candidate should be aware of basic security issues like SQL Injection Attack, Cross-site Request Forgery, Why should you keep your libraries up to date and how to manage this? Server side validations vs Client side validations and why client side validations can't be trusted? Whitelisting attributes, etc.

Checkout Ruby on Rails Security Guide to get the general idea. Ignore Rails specific stuff, most of it applies to general web development.

9. Testing

If you're still very early in your career, then testing won't make much sense to you (trust me, I've been there), but over time it'll grow on you I know it because it certainly has for me and some of my friends in similar domains.

Ideally you should be able to describe basic testing setup, how to write unit tests, when to test, and basic ideas behind unit testing. Integration tests are important too, but they are bit advance, so I'll leave that up to you to.



I know these are fairly basic stuff, but these are the most generic things I can think of in web domain. You can always dig down deeper, but this list should give you a starting point, and that's the whole point.  You can use this list to conduct telephonic round, then ask them to solve a real world problem at their own time.



Here are the techniques you can use to dig deeper:
Assignment: You could ask candidates to build a quick prototype of some idea, so that you can get the feel of their coding style and standards.

Pair Programming Session: This will allow you to have a closer look at how the candidate behaves in a real world scenario.

Contract based work: How about hiring them on a contract? This way you'll definitely know, if they'll fit in your team or not.

That's it!


Your Turn?
As always feel free to suggest more generic stuff that I might have missed and how would you go about it?

Read more ...

Optimising Git workflow with Git Aliases

29 April 2014
Git aliases is a good way to save few keystrokes and improve your productivity. So, in this post I will show you how to improve your productivity with git aliases.

Optimising Git workflow with Git Aliases


To customize git commands, you need to edit .gitconfig file located in your home directory(valid for *nix system, not sure about windows). So, without further ado let's get started.

Open .gitconfig file with your favorite text editor.

subl ~/.gitconfig


Now inside this file add the following lines


[alias]
    st = status
    aa = add -A
    cl = clone
    ci = commit
    df = diff
    br = branch
    co = checkout
    cob = checkout -b


Now you can use these aliases to save few keystrokes. For example you can use "git co feature_branch" instead of "git checkout feature_branch" to switch  to feature_branch, "git st" instead of "git status" to determine the current status of your working directory.

Now let's customize  one of  the most used git command i.e 'git log'.

lo = log


but this default log command is boring, so let's improve it.

lol = log --oneline


Much more use concise, but I'm not happy with formatting, so let's customize it even further.

lola = log --pretty=oneline --decorate --abbrev-commit -all


Looks good, but let's improve it even further with --graph option.

lola = --graph --pretty=oneline --decorate --abbrev-commit-all

git log ailas lola














Cool! You can even customize it even further with colors and more information like auther name, email, time etc.  Use this guide to customize it even further.


It would be nice to set an alias to list all the alias, so let's do it. Add following line in your .gitconfig file.

la = "!git config -l | grep alias | cut -c 7-"



Now running "git la" will list all of your git aliases. That's it. Are you using git aliases to improve your productivity? If so, then let me know what's your favorite git alias.


Reference: https://git.wiki.kernel.org/index.php/Aliases
Read more ...

Basic Skills Every Good Programmer Should Have

15 March 2014
A first year CS student asked for career advice, even though I'm a terrible person to ask this question I have some advice for every aspiring Computer Science student and programmers in general.

Intended audience: Aspiring Computer Science students and New programmers.

So, without further ado, let's make a list:
1. Learn to Type Properly: As basic as it seems, it's quite common to see people typing inefficiently. As a programmer, you will be typing as much as you can throughout your career and it would be impossible to improve your productivity if you don't know how to type properly.

2. Learn to Read: If you are not a good reader, then you probably won't be a good programmer either. How to be a good reader? Read as much as you can. Read blog posts, read comments, read new and interesting books about the topic of your choice(as a programmer you should choose Programming books). Prefer Ruby? find a recommended list of Good Ruby and Ruby on Rails Books.

3. Learn to Write: As a programmer, you are required to interact with other programmers, customers, higher authorities etc. and more often than not you will be communicating with them over email, so writing is one of the must have skills. How to improve your writing skills? Leave a comment or two on your favorite blog post, start participating in relevant discussions, and finally start blogging.

4. Learn to Learn: I know it sound silly, but it's not. Learning is the most important skill every programmer should have. You should learn how to learn interesting technologies quickly and efficiently. Be a good learner.

5. Learn to Think: This is the hardest skill you'll ever acquire. It's not easy to learn how to think because no one will tell how to think you just have to learn it by yourself. Learning "how to think" can be hard and time consuming, but don't get frustrated by it, in time you'll get better. Progress is more important than anything.

6. Learn how to use Google and other search engines: This is the most important skill for programmers. Googling is probably as important as learning debugging and understanding error messages.

7. Learn when to use Google, when to ask for help, and when to stop programming: Errors are inevitable and you as a programmer should know when to to Google, when to ask for help and when to stop programming.

8. Learn how to stop Procrastinating: Procrastination is a normal habit among programmers and don't get frustrated when you find yourself procrastinating for no reasons. We all procrastinate, learning when to stop procrastinating is another skill every programmer should have.

9. Learn to Read & Understand Error Messages: Whenever you get an error message, try to understand what these error messages are trying to say. Error messages aren't there to scare you, but to help you, and you should be able to understand these messages and act accordingly.

10. Learn how to get Help: You are supposed to get stuck, if you are not, then you probably are not working hard. Getting help is another important skill that every programmer should have. How to get help effectively? Ask good questions, twist your question and make it more general, Use Google and StackOverflow, hangout on IRC etc.

Have fun improving yourself and always remember this.

one does not simply become a programmer overnight



PS: Because I'm a fan of short and concise blog post I'll elaborate each point in a separate blog post.
Read more ...

Recommended Books for Ruby and Rails Developers

27 February 2014

I was planning to write this post for a long, long time, but procrastination won't let me. I finally wrote this post. What's the point of writing this post? Well, lots of people ask for a recommended list of good Ruby and Rails book, so in order to DRY my efforts I had to write this post so that I can point them here.

Read all the programming books


So without further ado, let's make a list.

Ruby

1. Learn to Program by Chris Pine: If you need a gentle introduction to Ruby, then this is the best book for you. The online version of this book is free, and you can read it here.

2. Programming Ruby 1.9 & 2.0: This is more of a reference book than a tutorial book, so be prepared to dive into the details. Also, this might be the only Ruby book you'll ever need.

3. Eloquent Ruby: This is definitely one of the best programming books I've ever read. The book is so concise and easy to read that anyone who is blessed with little to no knowledge of Ruby can finish it within 24 hours.

4. Practical Object Oriented Design in Ruby: This book is all about writing changeable code. Code that will be easy to change without being the pain in the ass. Sandi will show you code that sucks and isn't easy to change and replace it with more elegant and changeable code.

Rails


5. Learn Ruby on Rails by Daniel Kehoe: This book is for absolute newbies, but if you are a more advanced developer who is new to Rails you will be tremendously benefited from this book: After reading this you will be ready to learn and understand more advanced books like Rails Tutorial.

6. Agile Web Development with Rails 4: This is one the best book for web development and is so interesting that I read it cover to cover(well almost). If you are new to Ruby and Rails then you should start with this book instead of starting with Ruby on Rails Tutorial by Michael Hartl.

7. Ruby on Rails Tutorial: If you are serious about Ruby on Rails, then you will read it a couple of times. This book is filled with useful information. Michael Hartl will teach you web development by building sample application(Twitter Clone).

8. Ruby on Rails Guides: I know this isn't a book, but it is available in the mobi(kindle) version. Yay!

9. The Rails 4 Way: This book has been recommended so many times by so many good developers that I had to include it and to be honest, I've not spent enough time on this book to comment on its content.


Others
10. The RSpec Book: If you are interested in testing the behavior of your application, then this is the only book you'll ever need. This book is more about BDD than Rspec

11. Pro Git: This is by far the best Git book out there, plus it is freely available in pdf, mobi and epub formats. This book is easy to read, easy to understand (via visual representations) and is so concise that you'll understand it in one read even if you are an absolute newbie. Also available on amazon.

Bonus:
12. The Bastards Book of Ruby if you are interested in web scraping and stuff.

Recommended Order for Rails developers: 1, 5, 6, 7, 8, 10, 11, 3, 2, 4, 9, 12 or something similar to this depending on your preference.

If I had you start over today, then I'd blindly follow this list.
Read more ...

Gmail will Show Images by Default

14 December 2013

From now on Gmail will automatically show you images in your messages. This is a killer feature. Why is that? because from now on your emails won't look like a complete crap because of default email behavior. Google will render images without asking for your permission.

Wait? showing images without permissions? what about my privacy and security? an attacker might send harmful content via images? what about that? Fear not Google is deliberately solving this problem. In the next paragraph I'll tell you how.

So, how Google is doing this without compromising my Security?
what is happening here is that the Google is caching every image on their secure proxy server to protect you from any harmful content. This way an attacker won't be able to harm your device. How cool is that?


I usually don't write blog posts about these things, but I found it so awesome that I could not resist myself :D

Here's how my emails looks like.





Now my emails don't suck. Thanks you Google.
Read more ...

How to Install Ruby on Rails on Windows

17 November 2013
Some of my friends keep asking me the same question "How to Install Ruby on Rails on Windows". So, I'm writing this post to save myself some time in the long run.
(If you are using Ubuntu then just use this Guide by Ryan Bigg)

Head over to Rails Installer and download "Ruby Installer" for appropriate Ruby version and also download Devkit.

Things to remember while installing Ruby via Ruby Installer:
1. Select "Add Ruby executable's to your PATH": This option will let you execute ruby files from command prompt.
2. Select "Associate .rb and .rbw files with the ruby installation"

Now double click on Ruby Installer and follow the instructions.

Install Devkit
1. Double click on devkit and extract to c:\devkit
2. Now open command prompt and change the directory to install path cd\devkit
3. Now run ruby dk.rb init
4. ruby dk.rb install


Installing Rails
1. Type "gem install rails" in command prompt
2. md c:\apps
3. cd\apps
4. rails new myRailsApp
5. rails server

Done. Congratulations you have successfully installed Rails and created a new Rails application.

By the way if you run into "JavaScript Runtime environment missing" error then just install Node.js
Read more ...