Vishwanath Krishnamurthi's blog

A blog on Java EE, clean code, open source and TDD

Archive for the ‘Algorithmic’ Category

How to prepare for an Amazon interview ?

with 6 comments

I joined Amazon a few months back. I did spend a few months on preparation. In this post, I’ll list out some resources that I liked and some tips. Hope that helps.

Divide the preparation into two parts – Theory and Code

Interview specific books are good to give you an idea on how the questions would be and get you started. But to be really confident and skillful, you’d also have to know a lot of theory and concepts behind. By theory I mean data structures, algorithm paradigms, complexity analysis techniques etc. Knowing the concepts helps you to analyze better and brainstorm for different ideas for solving the same problem. Present various ideas in the interview – that can only be good. Switch between these two modes of preparation every now and then.

Theory preparation:

There are a lot of great Moocs. You could use one or two reference books, but most of the theory could be learnt just by watching free videos online.

Coursera: Algorithms course, Princeton university by Robert Sedgewick (Part I and Part II )

Great course ! View as many videos as you can ! Starting from the basics, the author explains the must know algorithms and the concepts behind them. What’s great is, you’d start “appreciating algorithms” – one of the biggest motivating factors 🙂  And it’s far easier to watch videos than to read books, right ?

Book: Algorithms, 4th Edition by Robert Sedgewick

I liked the coursera course a lot. Almost everything in this book is explained by the videos in the course. This book became a very handy reference, when I wanted to learn the implementation details.

Coursera: Algorithms Design and Analysis, Part I and II, Stanford University

Great content, once again. Probably the most “lively” set of lectures in this list. Complements the Princeton course so well.

Book: Introduction to Algorithms, CLRS  

A classic – Used this more as a reference or to read certain parts not covered in “Algorithms, 4th Ed”

IIT Videos: Video lectures here

A good series of lectures – contains lectures on disk based data structures, dictionaries etc which are not covered in any other “mooc”s

MIT OCW : Video lectures here

Good lectures, lengthy though. I skipped the parts where “proofs” were derived. But watched them in general.

Code Preparation

Learning theory is good – but that’s not enough. Reading a lot of code is important.

GeeksforGeeks : Website link here

Contains lots and lots of problems and solutions. Also has “interview sets” where many have shared their interview experiences. The problems are really well organized. No book contains so many problems categorized under “dynamic programming” or “backtracking” etc.

Book: Elements of Programming Interview (EPI)

300+ problems and solutions – just what you’d want to get into the “problem solving” mode. The quality / standard of the questions are great. The problems are way tougher than the ones presented in “Cracking the Coding Interview” (book described below). I spent most of the problem solving from this book.

It’d be great to solve a problem in different ways right ? After going through most of the problems in this book, you’d be able to do just that.  Finishing this book cover to cover might not be possible. I might have done about 70% of this.

This book does not have lengthy explanations to each problem – only the gist is explained and the rest is left to you to “read the code” and understand – So you are made to read a lot of code and the book is small enough to carry around.

Comparing with CCTI:

  • Number of questions: More
  • Are questions tougher or simpler ? : Tougher
  • Lengthy explanations ? : No
  • Are questions more like actual interview questions: Not all of them are
  • What happens when you finish this book ? :  You’d be well prepared and confident

Book: Cracking the Coding Interview, 5th Ed (CCTI)

This book is easy to read compared to EPI. Each solution is explained in great detail. A lot of interview specific tips too.

Comparing with EPI

  • Number of questions: Lesser
  • Are questions tougher or simpler ? : Simpler
  • Lengthy explanations ? : Yes ! You’d love the book for how well the solutions are explained.
  • Are questions more like actual interview questions: Yes
  • What happens when you finish this book ? :  You’d be somewhat prepared and somewhat confident

Book: Coding Interviews

Certainly a good book. If you wish to go through an additional set of problems, here it is. The good thing about this book is, it provides “test cases” for each and every problem. Yes, you have to test the code that you write in the interviews. So you’d develop an idea for test cases reading this book.

Comparing with CCTI

  • Number of questions: Almost the same
  • Are questions tougher or simpler ? :  Almost the same level of toughness
  • Lengthy explanations ? :  More than EPI, lesser than CCTI
  • Are questions more like actual interview questions: Yes
  • What happens when you finish this book ? :  You’d be somewhat prepared and somewhat confident

Youtube videos: Suarabh School videos

Look for the algorithm specific playlists. Numerous problems – solved and explained. I liked these videos a lot.

What books did I skip ?

  • Algorithm Design Manual
  • Programing Pearls

These books are classics. I’ve got these books now and intend to read them sometime. But I don’t think they are essential from an interview preparation perspective.

Remember – The objective is certainly not to “know” all solutions. The objective should be to become “skillful” enough to arrive at one or more solutions.

How to get a call ?

Well, preparing for the interviews is just one part. Getting a call for an interview is a completely different story.

Two good books I’d recommend:

Well, Good luck !

Advertisements

Written by Vishwanath Krishnamurthi

March 15, 2014 at 8:50 pm

Why learn algorithms and data structures ?

with 4 comments

The question is – Why learn algorithms and data-structures ? 

and here are some thoughts. Probably you’d find this question answered in the preface of any algorithms book but anyway, here’s my take.

1) To not be constrained by the programming language for data-structure

Without a good knowledge of various data structures, it is easy to be constrained to thinking for solutions in terms of the data structures directly provided by the language.

If you were a Java programmer, you’d probably be thinking on solutions just in terms of what is provided in java.lang.util package.

Well, there’s lots more. Take for instance a simple need:  In a low end, basic phone, as the user types something, you’d like to present the user with “auto complete” feature. Thinking in terms of the data structures readily provided by the language /libraries doesn’t help much.

A simple trie  would help here. For another example, to think of any networking website that we use-

How does Facebook suggest you friends, How does LinkedIn tell personX is a 2nd level contact ?

A graph data structure helps here.

Or when there’s a steady stream of numbers coming in – and you want to maintain the largest 10 numbers. (You don’t have the
luxury of storing all the numbers and sorting them)  Min heap is the one to go to.

The list goes on..

2) Better hardware is not a solution

No amount of additional hardware is going to compensate for an inefficient algorithm. Super computer takes 1 week to sort a billion numbers using insertion sort whereas a home computer takes 18 minutes sort a billion numbers using merge sort.

Insertion Sort: O(n2)
Merge Sort: O(n logn)

3) You’ll come across some very interesting, non intuitive ways of solving problems

Given an array with n/2 distinct elements and n/2 copies of another element. Find the missing element.

Well, the normal solution we  would all think of is to do a linear scan through the array and to find the missing element after reading through  n/2+2  elements at the worst case. [ Worst case = all n/2 distinct numbers appear first in the array and then the number-which-repeats appears n/2 times]

Interestingly, this could be solved faster this way:


while(true) do

i = Rand.numberWithinRange(1 to n)

j = Rand.numberWithinRange(1 to n)

if(i!=j) and a[i]=a[j] then return i;

And the probability that the algorithm does not quit in 10 iterations is 0.1074 !

“Randomization” turns out to be an amazing practical way of solving some section of problems.

And to give a more “real-world”ish application for “randomization” -The randomized version of quicksort is one of the most practical/ efficient sorting algorithms !

Get ready to be surprised by lots of cool, non-intuitive-yet-amazing ways of solving problems

4) Refresh a little bit on probability, logarithm and some fun math

It’s interesting to get back to some math, – specifically on probability, expectations, logarithm..

5) Learn some interesting design paradigms

While learning different algorithms, you’d also be grasping the different algorithm design paradigms.

(Divide and Conquer, Greedy method, Backtracking, Dynamic Programming)

When there’s a new problem to be solved, this knowledge helps to come up with an efficient solution.

6) It’s a skill

Certain things are just “knowledge” – that could be learned-along-the-way when a need arises.

For example: There’s not really a need to know all the “MVC” frameworks out there. Knowing one is just enough. There’s a need to use some other MVC framework  ? Well that could be learned along the way..

But algorithms and data structures don’t fall into that category. It’s a skill, to deduce an algorithm for a problem  / It’s a skill to analyse the complexity and tell which algorithm is the better one / It’s good to learn in advance. Acquiring a skill is interesting, right ?

7) Quadratic complexity when O(n) solution exists

Without some learning of algorithms, it’s quite possible that we come up with inefficient solutions when an efficient one already exists !

8)  Understanding what’s behind the everyday tools..

Almost every tool that we use, day after day, applies some cool algorithms.

It can be an interesting exercise to find which algorithms are applied where !

Written by Vishwanath Krishnamurthi

March 27, 2013 at 10:27 pm