Meenakshi - Dynamic Programming for Coding Interviews

DEDICATION

This book is dedicated to a yogi

MASTER MAHA SINGH

who mended relations and excelled in each role he lived

SON | BROTHER | FRIEND | HUSBAND | FATHER | FATHER-IN-LAW | TEACHER | FARMER | CITIZEN | DEVOTEE

the most upright, conscientious, and able man.

We miss you in every possible way Papa.

Notion Press

Old No. 38, New No. 6

McNichols Road, Chetpet

Chennai - 600 031

First Published by Notion Press 2017

Copyright Meenakshi & Kamal Rawat 2017

All Rights Reserved.

ISBN 978-1-946556-70-7

This book has been published with all efforts taken to make the material error-free after the consent of the author. However, the author and the publisher do not assume and hereby disclaim any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from negligence, accident, or any other cause.

No part of this book may be used, reproduced in any manner whatsoever without written permission from the author, except in the case of brief quotations embodied in critical articles and reviews.

The contents of this book including but not limited to the views, representations, descriptions, statements, informations, opinions and references [Contents] are the sole expression and opinion of its Author(s) and do not reflect the opinion of the Publisher or its Editors. Neither Publisher nor its Editors endorse the contents of this book or guarantees the accuracy or completeness of the content published herein and shall not be liable whatsoever for any errors, misrepresentation, omissions, or claims for damages, including exemplary damages, arising out of use, inability to use, or with regard to the accuracy or sufficiency of the information contained in this book.

To write a book, one need to be in a certain state of mind where one is secure inside himself so that he can work with single minded focus.

A guru helps you be in that state. We want to thank our ideological guru, Shri Rajiv Dixit Ji and Swamy Ramdev Ji.

The time spent on this book was stolen from the time of family and friends. Wish to thank them, for they never logged an FIR of their stolen time.

We also wish to thank each other, but that would be tantamount to one half of the body thanking the other half for supporting it. The body does not function that way.

We have been teaching students How to prepare for Coding Interviews for many years now.

A Data Structure problem like reverse a linked list or add operation getMinimum() to a Stack or implement a thread safe Queue are relatively easy to solve, because there are theoretical reference to start in such problems. The most difficult category of problems asked in coding competitions or interview of companies like Google, Amazon, Facebook, Microsoft etc. fall under the umbrella of Dynamic Programming (DP).

Most DP problems do not require understanding of complex data structure or programming design, they just need right strategy and methodical approach.

A solution is first visualized in the mind before it takes formal shape of an Algorithm that finally translates into a computer program. DP problems are not easy to visualize and hence not easy to solve.

The best way to visualize a DP problem is using recursion because DP problems demonstrates optimal substructure behavior. Recursion gives the right solution but usually takes exponential time. This unreasonably high time is taken because it solves sub problems multiple times.

DP is a bottom-up approach to problem solving where one subproblem is solved only once. In most cases this approach is counter-intuitive. It may require a change in the way we approach a problem. Even experienced coders struggle to solve DP problems.

This book is written with an intention that if a teacher reads it, he will make dynamic programming very interesting to his students. If this book is in the hands of a developer, he will feel super confident in answering algorithm questions in interviews, and anyone who read it will get a robust tool to approach problems asked in coding competitions.

Being a good coder is not about learning programming languages, it is about mastering the art of problem solving.

Code in this book is written in C language, If you have never written any program in C language, then we suggest you to read first few chapters of C from any good book and try writing some basic programs in C language.

We have discussed only simple problems in first six chapters. The idea is to explain concepts and not let the reader lost in complexity of questions. More questions are discussed in last three chapters with last chapter completely dedicated to practice questions.

If you have the luxury of time, then we strongly recommend you to read this book from cover to cover.

If you do not have time, then, how you read this book depends on how good you are in coding and how comfortable you are with recursion.

If you are good at forming logic and can write reasonably complex programs of Binary Tree and Linked List comfortably, then you may choose to skip the first chapter. I think the below logic may help you find a starting point

IF (one day left for Interview) IF (champion of DP) READ Chapter 8,9 ELSE IF (Good @ Programming) READ Chapter 3, 4, 5, 6, 7. ELSE Pray to God, Start from Chapter 1.ELSE IF (more than one week left for interview) IF (champion of DP) READ Chapter 2, 7, 8, 9 ELSE IF (Student OR Researcher) READ complete bookELSE IF (Reading to learn DP) READ complete Book

Most computer concepts have their origin in Mathematics, Recursion is no exception. If you have studied mathematics at high school level, then you must have come across equations like.

is a symbol for summation. It is read as Sum of first n numbers is equal to n plus Sum of first (n-1) numbers. When n becomes 1, Sum(1) has a fixed value, . n, in this case is positive integer.

In plain words, Sum is defined in terms of Sum itself. This is called Recursion.

In computer programming, when a function calls itself either directly or indirectly it is called a Recursive Function and the process is called Recursion.

Typically the function performs some part of the task and rest is delegated to the recursive call of the same function, hence, there are multiple instances of same function each performing some part of the overall task. Function stops calling itself when a terminating condition is reached.

Recursion is a problem solving technique, where solution of a larger problem is defined In terms of smaller Instances of itself.

Points to note in recursion are the following:

1. Recursion always have a terminating condition (else it will be infinite recursion). In Sum function, the condition, if n=1, then, stop recursion and return , is the terminating condition.
2. Recursive function performs some part of task and delegate rest of it to the recursive call. In above example, the function performs addition of n with the return value of the Sum(n-1) but delegate the computation of Sum(n-1) to recursive call.

Writing recursive code is not as difficult as it may appear, in fact, in most cases it is relatively simpler because we are not solving the complete problem. Recursive function code is a two-step process

Next page