Dynamic Programming for Coding Interviews: A Bottom-Up approach to problem solving

·
· Notion Press
3.9
16 reviews
Ebook
142
Pages
Ratings and reviews aren’t verified  Learn More

About this ebook

I wanted to compute 80th term of the Fibonacci series. I wrote the rampant recursive function,

int fib(int n){

  return (1==n || 2==n) ? 1 : fib(n-1) + fib(n-2);

}

and waited for the result. I wait… and wait… and wait…

With an 8GB RAM and an Intel i5 CPU, why is it taking so long? I terminated the process and tried computing the 40th term. It took about a second. I put a check and was shocked to find that the above recursive function was called 204,668,309 times while computing the 40th term. 

More than 200 million times? Is it reporting function calls or scam of some government?

The Dynamic Programming solution computes 100th Fibonacci term in less than fraction of a second, with a single function call, taking linear time and constant extra memory.

A recursive solution, usually, neither pass all test cases in a coding competition, nor does it impress the interviewer in an interview of company like Google, Microsoft, etc. 

The most difficult questions asked in competitions and interviews, are from dynamic programming. This book takes Dynamic Programming head-on. It first explain the concepts with simple examples and then deep dives into complex DP problems.

Ratings and reviews

3.9
16 reviews
Brian Murray
March 21, 2021
Thorough explanations, but lots of sloppy typos. Does not explicitly cover the need to topologicly sort the problem space.
Did you find this helpful?
Suman Ghosh
April 10, 2017
there is error for the first example of head recursio n we are checking head!=null but we have to check head.next!=null
6 people found this review helpful
Did you find this helpful?
shivam soni
March 14, 2018
Good book to start with. Basics are covered in depth.
2 people found this review helpful
Did you find this helpful?

About the author

Kamal Rawat is a software developer, trainer, author and an entrepreneur. He has first-hand experience of implementing full life cycle of large scale desktop, Cloud and Mobile applications across various domains and platforms.  

He had been a technical architect in complex projects like Microsoft OneNote, Adobe Photoshop and Samsung GalaxyConnect. He has also been in the core interview panel of Microsoft, Adobe and many start-ups. 

Since 2006, he is coaching students on how to crack programming interviews. Before leaving his job to pursue his passion full-time, Kamal was working as Senior SDE at Microsoft. 


Meenakshi hold master’s degree in Computer science. She left her job and co-founded Ritambhara Technologies (www.ritambhara.in).

She maintains an amazing work-life balance, wearing multiple hats, be it head of a technical start-up, a certified yoga trainer or mother to two kids at home. 

Problem-solving and optimizing comes naturally to her. 

Rate this ebook

Tell us what you think.

Reading information

Smartphones and tablets
Install the Google Play Books app for Android and iPad/iPhone. It syncs automatically with your account and allows you to read online or offline wherever you are.
Laptops and computers
You can listen to audiobooks purchased on Google Play using your computer's web browser.
eReaders and other devices
To read on e-ink devices like Kobo eReaders, you'll need to download a file and transfer it to your device. Follow the detailed Help Center instructions to transfer the files to supported eReaders.