Vishwanath Krishnamurthi's blog

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

How to prepare for an Amazon interview ?

with one comment

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 !

Written by Vishwanath Krishnamurthi

March 15, 2014 at 8:50 pm

Is this thread-safe ? (Part 1)

with 2 comments

To learn and understand about thread-safety or concurrency in general, there can’t be a better book than “Java Concurrency in Practice

Even if you cannot find the time to read through the book, the booksite contains a lot of code snippets on thread-safe / non-thread-safe code, which I’d highly recommend going through.

In this blog post, I have added a few classes, some of them are thread-safe and some of them are not.  Take it up as a quick quiz or an exercise to identify which are thread-safe and which are not and see how well you fair :)

public class One {

public void aMethod() {
int a = 100;
a++;
System.out.println(a);
}
}

There's no "mutable-shared-state" in the above class. So yeah, it is thread-safe.

class Two {

private int a = 100;

public void aMethod() {
a++;
System.out.println(a);
}

}

In class Two, 'a' is a mutable shared state and the operation being done (a++) is not atomic. This could lead to race-conditions
and hence class Two is not thread-safe

class Three {

private boolean toggleSwitch = true;

public void aMethod() {
toggleSwitch = !toggleSwitch;
System.out.println(toggleSwitch);
}

}

When two threads are changing the state (toggleSwitch) you cannot guarantee that the change done by threadA is visible for the
other thread.  So we have got 'thread-visibility' problems in the above class.

class Four {

private volatile boolean toggleSwitch = true;

public void aMethod() {
toggleSwitch = !toggleSwitch;
System.out.println(toggleSwitch);
}

}

We've addressed the problem we had at 'class Three' by making 'toggleSwitch' volatile. So we are good for class Four. Class Four is thread-safe.  Update: Oops, wait ! Class Four is not thread safe.  As Pravin has pointed out in the comments-

class Five {

private volatile int a = 100;

public void aMethod() {
a++;
System.out.println(a);
}

}

This code looks pretty much like class Four. So is this thread-safe too ? Nope.
Visibility and atomicity are two separate things. Here a++ is not an atomic operation and you could have a race condition. So class Five is not thread safe.

class Six {

private AtomicInteger a = new AtomicInteger(100);

public void aMethod() {
a.incrementAndGet();
System.out.println(a);
}

}

We've addressed the atomicity problem. Atomic* operations are also documented to behave like 'volatile'. So visibility is covered too
so class Six here is thread-safe.

class Seven {

int a = 100;

public synchronized void aMethod() {
a++;
System.out.println(a);
}

}

Note that 'a' is not private. Nothing prevents a thread from directly accessing the field and modifying the state. So class Seven is not thread-safe

class Eight{

private int a = 100;

public synchronized void aMethod() {
a++;
System.out.println(a);
}

}

Well, only aMethod() could change the state of 'a' now. And it is synchronized.
So yeah, class Eight is thread-safe. But we did not make 'a' volatile !
Well, there's no need to.  'Synchronizing' addresses both 'atomicity' and 'thread visibility' problems so we are good here.

Resources:

Apart from the book, do check out the "concurrency animations" !

Written by Vishwanath Krishnamurthi

October 1, 2013 at 9:55 am

Why learn algorithms and data structures ?

with 2 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

Failing Fast / Assertive Programming

leave a comment »

I am not using this term “assertive programming” strictly on the basis of  using “assert” keyword, but a little loosely, to  fail-fast and expose bugs early. It is a great technique for programmers to shorten their debugging-time, but hardly do I ever see any ‘asserts’ in codebase.

Languages like Eiffel contain constructs for preconditions and postconditions and goes a step further in helping to program assertively, but at least we’ve got an “assert” keyword in Java.

Here is a nice usage of assert, I found in a merge-sort implementation.  The merge step merges two sorted halves into one.

For this to work correctly, the two halves must be sorted.


merge(int []a, int aux[], int low, int mid, int high)
{
assert isSorted(a,low,mid);
assert isSorted(a,mid+1,high);
// rest of the merging code
}

What better way to document our expectations and to expose the bugs early on ?

There are a couple of choices when it comes to "ways of asserting"

The assert keyword is handy, throws error on failing and could be switched off at production. The other way is to go towards an API (Spring-Assert, GoogleGuavaPreconditions) or a custom-class,that throws an Exception

but regardless of the ways, assertion as such is a great tool, not to be disregarded.

Assertions aren't the only ways ensure 'Fail Fast'. For example, when using transaction attributes, you could ensure that a transaction must be present using 'mandatory' rather than using a 'required' and stay away from a vague transaction attribute like 'supports'

While working with read-only values, you could use something from the programming language to ensures it. Marking references as, 'final', better yet, using Immutable objects, would go towards it.

So, hey ! Go assert !

Good Reads:

Here's a very good article on "failing fast".

To assert or not to assert

Written by Vishwanath Krishnamurthi

December 9, 2012 at 11:57 am

Where to place the Java EE descriptors ?

with one comment

No intro required – these are some of the standard descriptors used in a JavaEE application. However placing these descriptors in the wrong location is a common mistake.

So here’s a list of some descriptors and the correct location they are expected in – Might save some time searching around the net.

ejb-jar.xml

In a Jar, it would go in /META-INF directory
In a War, it would go in /WEB-INF directory

beans.xml

In a Jar, it would go in /META-INF directory
In a War, it would go in /WEB-INF directory.

But note that just because you have WEB-INF/beans.xml, the JARs in WEB-INF/lib do not become bean-archives.
The JAR would need a META-INF/beans.xml separately

persistence.xml

In a Jar, it would go in /META-INF directory
It would go under WEB-INF/classes/META-INF in a WAR

application.xml

In /META-INF directory of Ear

Written by Vishwanath Krishnamurthi

August 25, 2012 at 11:08 am

Spring Webflow – Tips

with one comment

Just a random list of tips – handy if you are using SWF

Passing a String in an evaluate expression:

To pass a string literal, enclose the string in single quotes ‘ ‘ as in


<evaluate expression="searchService.fetchSearchResult('hello')  result="flowScope.searchResult" />

Set a boolean 

Likewise to set a boolean value,

<set name="flowScope.isTicketAvailable" value=" 'true' "/>

Flush flow changes without restarting the server

While developing, do set, development=true as such and save yourself lots of time

<flow:flow-builder-services id="flowBuilderServices"
 view-factory-creator="viewFactoryCreator" development="true"/>


The RequestControlContext object

 On the rare cases where you need a requestControlContext in your bean, you can get hold of it by passing 'flowRequestContext' from the flow.

<evaluate expression="someBean.someMethod( flowRequestContext)">

public void someMethod(RequestControlContext context){ //your operation
}

The start state

During development, if you wanted to skip ahead a few states, just define the start-state in the <flow> element.

Want to trace the flow?

Its pretty simple to add a couple of methods in your listener that extends FlowExecutionListenerAdapter

@Override
 public void stateEntered(RequestContext context,
 StateDefinition previousState, StateDefinition newState) {
logger.debug("Entered State:" + newState.getId());
 }
  @Override
 public void transitionExecuting(RequestContext context, TransitionDefinition transition)
 {
 logger.debug("Executing transition:" + transition.getId());
 }

and trace the flow.

Written by Vishwanath Krishnamurthi

May 19, 2012 at 1:37 am

Posted in Spring

Tagged with , ,

A few things to avoid while writing unit tests

with 2 comments

Long back I wrote a post on some good practices to follow while writing unit tests.  I thought I’d add one on mistakes/practices to avoid while writing unit tests.

1) Reading a configuration file:

If for writing a unit test, you access a file, then strictly speaking, it is not a unit test.

For example,

class CarTest
{
Engine engine;
// your test for engine object
}

If you created the object under test by doing,

Engine engine = new Engine();

that's neat. Whereas if DI was used to create the 'engine' object, then it wouldn't have been a unit test. (DI involves reading an external file/ scanning for annotations )

Likewise, if for test data, you retrieved the data from a file, then its not really a unit test.

the main drawback being ?

Reading files takes time. A unit test has to be really fast. Something that's executed very often.

2) Mocking the wrong objects:

Mocking frameworks are great.  You could easily mock a 'dao' or a 'service' call and write a unit-test quickly. Mocking a 'value-object' like the one above is needless.

public void  AccountBalanceTest
{
@Mock AccountInfo accountInfo;
@Test
public void  debitShouldDecuctTheGivenAmount()
{
when(accountInfo.getCurrentBalance()).thenReturn(500);
Account account = new Account(accountInfo);
account.debit(100);
}
}

It turns out to be messy when a lot of such stub values are defined.

'Value-Objects' being easily constructible with a 'new' should rather be used like this:

@Test
public void  debitShouldDecuctTheGivenAmount()
{
AccountInfo accountInfo = new AccountInfo();
accountInfo.setCurrentBalance(500);
Account account = new Account(accountInfo);
account.debit(100);
}
}

This reads a lot better, doesn't it? And when there are a lot of test data to be prepared, there's of course the very useful builder pattern http://nat.truemesh.com/archives/000714.html

3) Ignoring the feedback

A great thing about writing tests is that you get "feedback" about your code.

For example,  if you started writing a test like this,

@Test
public void testValidateAddressShouldCheckForMandatoryPostCode()
{
Customer customer = new Customer();
Address address = new Address();
address.setPostCode("123456");
customer.setAddress(address);
Validator validator = new Validator();
validator.validateAddress(customer);
}

you should be seeing a "warning" here. You're spending some effort constructing the object required for test,

and this "warning" should hint you that, the validateAddress() method should be refactored to take an address parameter and not a customer parameter.

It is easy to set up the object like above and get the test passing - but that's not the point. The idea should be to take the feedback and refactor.

@Test
public void testValidateAddressShouldCheckForMandatoryPostCode()
{
Address address = new Address();
address.setPostCode("123456");
Validator validator = new Validator();
validator.validateAddress(address); // refactored method.
}

Yes, the above one was a simplified example, but hope the idea is clear.

Similarly, when a piece of code is hard to test, it is possible to overcome the pain by using some advanced mocking frameworks and finishing up the test. But "being hard to test" might be a feedback telling  you to take efforts to refactor the code and make it testable/loosely-coupled.

Here's a great post http://martinfowler.com/articles/modernMockingTools.html that explains it.

So to put it again, "the feedback should not be ignored"

 

Good TDD resources

http://misko.hevery.com/
http://www.growing-object-oriented-software.com/
http://vimeo.com/10569751

 

Written by Vishwanath Krishnamurthi

April 9, 2012 at 11:49 pm

Posted in Design

Tagged with , ,

Follow

Get every new post delivered to your Inbox.

Join 120 other followers