Narasimha Karumanchi - Data Structures and Algorithms Made Easy: Data Structure and Algorithmic Puzzles

Copyright 2017 by CareerMonk.com

All rights reserved.

Designed by Narasimha Karumanchi

Copyright 2017 CareerMonk Publications. All rights reserved.

All rights reserved. No part of this book may be reproduced in any form or by any electronic or mechanical means, including information storage and retrieval systems, without written permission from the publisher or author.

Mother and Father, it is impossible to thank you adequately for everything you have done, from loving me unconditionally to raising me in a stable household, where your persistent efforts and traditional values taught your children to celebrate and embrace life. I could not have asked for better parents or role-models. You showed me that anything is possible with faith, hard work and determination.

This book would not have been possible without the help of many people. I would like to express my gratitude to all of the people who provided support, talked things over, read, wrote, offered comments, allowed me to quote their remarks and assisted in the editing, proofreading and design. In particular, I would like to thank the following individuals:

Mohan Mullapudi, IIT Bombay, Architect, dataRPM Pvt. Ltd.

Navin Kumar Jaiswal, Senior Consultant, Juniper Networks Inc.

A. Vamshi Krishna, IIT Kanpur, Mentor Graphics Inc.

Cathy Reed, BA, MA, Copy Editor

Narasimha Karumanchi

M-Tech, IIT Bombay

Founder, CareerMonk.com

Dear Reader,

Please hold on! I know many people typically do not read the Preface of a book. But I strongly recommend that you read this particular Preface.

It is not the main objective of this book to present you with the theorems and proofs on data structures and algorithms. I have followed a pattern of improving the problem solutions with different complexities (for each problem, you will find multiple solutions with different, and reduced, complexities). Basically, its an enumeration of possible solutions. With this approach, even if you get a new question, it will show you a way to think about the possible solutions. You will find this book useful for interview preparation, competitive exams preparation, and campus interview preparations.

As a job seeker, if you read the complete book, I am sure you will be able to challenge the interviewers. If you read it as an instructor, it will help you to deliver lectures with an approach that is easy to follow, and as a result your students will appreciate the fact that they have opted for Computer Science / Information Technology as their degree.

This book is also useful for Engineering degree students and Masters degree students during their academic preparations. In all the chapters you will see that there is more emphasis on problems and their analysis rather than on theory. In each chapter, you will first read about the basic required theory, which is then followed by a section on problem sets. In total, there are approximately 700 algorithmic problems, all with solutions.

If you read the book as a student preparing for competitive exams for Computer Science / Information Technology, the content covers all the required topics in full detail. While writing this book, my main focus was to help students who are preparing for these exams.

In all the chapters you will see more emphasis on problems and analysis rather than on theory. In each chapter, you will first see the basic required theory followed by various problems.

For many problems, multiple solutions are provided with different levels of complexity. We start with the brute force solution and slowly move toward the best solution possible for that problem. For each problem, we endeavor to understand how much time the algorithm takes and how much memory the algorithm uses.

It is recommended that the reader does at least one complete reading of this book to gain a full understanding of all the topics that are covered. Then, in subsequent readings you can skip directly to any chapter to refer to a specific topic. Even though many readings have been done for the purpose of correcting errors, there could still be some minor typos in the book. If any are found, they will be updated at .

I wish you all the best and I am confident that you will find this book useful.

Narasimha Karumanchi

M-Tech, I IT Bombay

Founder, CareerMonk.com

IT Interview Questions

Data Structures and Algorithms for GATE

Data Structures and Aigorithms Made Easy in Java

Coding Interview Questions

Peeling Design Patterns

Elements of Computer Networking

Data Structures and Algorithmic Thinking with Python

The objective of this chapter is to explain the importance of the analysis of algorithms, their notations, relationships and solving as many problems as possible. Let us first focus on understanding the basic elements of algorithms, the importance of algorithm analysis, and then slowly move toward the other topics as mentioned above. After completing this chapter, you should be able to find the complexity of any given algorithm (especially recursive functions).

Before going to the definition of variables, let us relate them to old mathematical equations. All of us have solved many mathematical equations since childhood. As an example, consider the below equation:

We dont have to worry about the use of this equation. The important thing that we need to understand is that the equation has names (x and y), which hold values (data). That means the names (x and y) are placeholders for representing data. Similarly, in computer science programming we need something for holding data, and