Problem Solving in Data Structures Algorithms Using C (Hemant Jain [Jain, Hemant]) (Z-Library)

📄 File Format: PDF

💾 File Size: 6.1 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Problem Solving in Data Structures & Algorithms Using C First Edition By Hemant Jain

📄 Page 3

Book Title: Problems Solving in Data Structures & Algorithms Using C Book Author: Hemant Jain Published by Hemant Jain HIG 4, Samarth Tower, Sarvadharm, D Sector, Bhopal, India, Pin Code: 462042 Published in Bhopal, India This edition published March 2017 Copyright © Hemant Jain 2017. All Right Reserved. Hemant Jain asserts the moral right to be identified as the author of this work. All rights reserved. No part of this publication may be reproduced, stored in or introduced into a retrieval system, or transmitted, in any form, or by any means (electrical, mechanical, photocopying, recording or otherwise) without the prior written permission of the author, except in the case of very brief quotations embodied in critical reviews and certain other non- commercial uses permitted by copyright law. Any person who does any unauthorized act in relation to this publication may be liable to criminal prosecution and civil claims for damages.

📄 Page 4

(This page has no text content)

📄 Page 5

ACKNOWLEDGEMENT The author is very grateful to GOD ALMIGHTY for his grace and blessing. Deepest gratitude for the help and support of my brother Dr. Sumant Jain. This book would not have been possible without the support and encouragement he provided. I would like to express profound gratitude to my guide/ my friend Naveen Kaushik for his invaluable encouragement, supervision and useful suggestion throughout this book writing work. His support and continuous guidance enable me to complete my work successfully. Finally yet importantly, I am thankful to Love Singhal, Anil Berry and Others who helped me directly or indirectly in completing this book. Hemant Jain

📄 Page 6

(This page has no text content)

📄 Page 7

(This page has no text content)

📄 Page 8

TABLE OF CONTENTS TABLE OF CONTENTS CHAPTER 0: HOW TO USE THIS BOOK WHAT THIS BOOK IS ABOUT PREPARATION PLANS SUMMARY CHAPTER 1: INTRODUCTION - PROGRAMMING OVERVIEW INTRODUCTION VARIABLE POINTERS ARRAY TWO DIMENSIONAL ARRAY ARRAY INTERVIEW QUESTIONS STRUCTURE POINTER TO STRUCTURE DYNAMIC MEMORY ALLOCATION FUNCTION CONCEPT OF STACK SYSTEM STACK AND FUNCTION CALLS PARAMETER PASSING, CALL BY VALUE PARAMETER PASSING, CALL BY REFERENCE RECURSIVE FUNCTION EXERCISES CHAPTER 2: ALGORITHMS ANALYSIS INTRODUCTION ASYMPTOTIC ANALYSIS BIG-O NOTATION OMEGA-Ω NOTATION THETA-Θ NOTATION COMPLEXITY ANALYSIS OF ALGORITHMS TIME COMPLEXITY ORDER DERIVING THE RUNTIME FUNCTION OF AN ALGORITHM TIME COMPLEXITY EXAMPLES MASTER THEOREM MODIFIED MASTER THEOREM EXERCISE CHAPTER 3: APPROACH TO SOLVE ALGORITHM DESIGN PROBLEMS INTRODUCTION CONSTRAINTS IDEA GENERATION

📄 Page 9

COMPLEXITIES CODING TESTING EXAMPLE SUMMARY CHAPTER 4: ABSTRACT DATA TYPE ABSTRACT DATA TYPE (ADT) DATA-STRUCTURE ARRAY LINKED LIST STACK QUEUE TREES BINARY TREE BINARY SEARCH TREES (BST) PRIORITY QUEUE (HEAP) HASH-TABLE DICTIONARY / SYMBOL TABLE GRAPHS GRAPH ALGORITHMS SORTING ALGORITHMS COUNTING SORT END NOTE CHAPTER 5: SEARCHING INTRODUCTION WHY SEARCHING? DIFFERENT SEARCHING ALGORITHMS LINEAR SEARCH – UNSORTED INPUT LINEAR SEARCH – SORTED BINARY SEARCH STRING SEARCHING ALGORITHMS HASHING AND SYMBOL TABLES HOW SORTING IS USEFUL IN SELECTION ALGORITHM? PROBLEMS IN SEARCHING EXERCISE CHAPTER 6: SORTING INTRODUCTION TYPE OF SORTING BUBBLE-SORT MODIFIED (IMPROVED) BUBBLE-SORT INSERTION-SORT SELECTION-SORT MERGE-SORT

📄 Page 10

QUICK-SORT QUICK SELECT BUCKET SORT GENERALIZED BUCKET SORT HEAP-SORT TREE SORTING EXTERNAL SORT (EXTERNAL MERGE-SORT) COMPARISONS OF THE VARIOUS SORTING ALGORITHMS. SELECTION OF BEST SORTING ALGORITHM EXERCISE CHAPTER 7: LINKED LIST INTRODUCTION LINKED LIST TYPES OF LINKED LIST SINGLY LINKED LIST DOUBLY LINKED LIST CIRCULAR LINKED LIST DOUBLY CIRCULAR LIST EXERCISE CHAPTER 8: STACK INTRODUCTION THE STACK ABSTRACT DATA TYPE STACK USING ARRAY (MACRO) STACK USING ARRAY (DYNAMIC MEMORY) STACK USING ARRAY (GROWING CAPACITY IMPLEMENTATION) STACK USING ARRAY (GROWING-REDUCING CAPACITY IMPLEMENTATION) STACK USING LINKED LIST PROBLEMS IN STACK PROS AND CONS OF ARRAY AND LINKED LIST IMPLEMENTATION OF STACK. USES OF STACK EXERCISE CHAPTER 9: QUEUE INTRODUCTION THE QUEUE ABSTRACT DATA TYPE QUEUE USING ARRAY QUEUE USING LINKED LIST PROBLEMS IN QUEUE EXERCISE CHAPTER 10: TREE INTRODUCTION TERMINOLOGY IN TREE BINARY TREE

📄 Page 11

TYPES OF BINARY TREES PROBLEMS IN BINARY TREE BINARY SEARCH TREE (BST) PROBLEMS IN BINARY SEARCH TREE (BST) EXERCISE CHAPTER 11: PRIORITY QUEUE INTRODUCTION TYPES OF HEAP HEAP ADT OPERATIONS OPERATION ON HEAP HEAP-SORT USES OF HEAP PROBLEMS IN HEAP EXERCISE CHAPTER 12: HASH-TABLE INTRODUCTION HASH-TABLE HASHING WITH OPEN ADDRESSING HASHING WITH SEPARATE-CHAINING PROBLEMS IN HASHING EXERCISE CHAPTER 13: GRAPHS INTRODUCTION GRAPH REPRESENTATION ADJACENCY MATRIX ADJACENCY LIST GRAPH TRAVERSALS DEPTH FIRST TRAVERSAL BREADTH FIRST TRAVERSAL PROBLEMS IN GRAPH DIRECTED ACYCLIC GRAPH TOPOLOGICAL SORT MINIMUM SPANNING TREES (MST) SHORTEST PATH ALGORITHMS IN GRAPH EXERCISE CHAPTER 14: STRING ALGORITHMS INTRODUCTION STRING MATCHING DICTIONARY / SYMBOL TABLE PROBLEMS IN STRING MEMMOVE FUNCTION EXERCISE

📄 Page 12

CHAPTER 15: ALGORITHM DESIGN TECHNIQUES INTRODUCTION BRUTE FORCE ALGORITHM GREEDY ALGORITHM DIVIDE-AND-CONQUER, DECREASE-AND-CONQUER DYNAMIC PROGRAMMING REDUCTION / TRANSFORM-AND-CONQUER BACKTRACKING BRANCH-AND-BOUND A* ALGORITHM CONCLUSION CHAPTER 16: BRUTE FORCE ALGORITHM INTRODUCTION PROBLEMS IN BRUTE FORCE ALGORITHM CONCLUSION CHAPTER 17: GREEDY ALGORITHM INTRODUCTION PROBLEMS ON GREEDY ALGORITHM CHAPTER 18: DIVIDE-AND-CONQUER, DECREASE-AND-CONQUER INTRODUCTION GENERAL DIVIDE-AND-CONQUER RECURRENCE MASTER THEOREM PROBLEMS ON DIVIDE-AND-CONQUER ALGORITHM CHAPTER 19: DYNAMIC PROGRAMMING INTRODUCTION PROBLEMS ON DYNAMIC PROGRAMMING ALGORITHM CHAPTER 20: BACKTRACKING AND BRANCH-AND-BOUND INTRODUCTION PROBLEMS ON BACKTRACKING ALGORITHM CHAPTER 21: COMPLEXITY THEORY AND NP COMPLETENESS INTRODUCTION DECISION PROBLEM COMPLEXITY CLASSES CLASS P PROBLEMS CLASS NP PROBLEMS CLASS CO-NP NP–HARD: NP–COMPLETE PROBLEMS REDUCTION END NOTE

📄 Page 13

CHAPTER 22: INTERVIEW STRATEGY INTRODUCTION RESUME NONTECHNICAL QUESTIONS TECHNICAL QUESTIONS CHAPTER 23: SYSTEM DESIGN SYSTEM DESIGN SYSTEM DESIGN PROCESS SCALABILITY THEORY DESIGN SIMPLIFIED FACEBOOK DESIGN FACEBOOK FRIENDS SUGGESTION FUNCTION DESIGN A SHORTENING SERVICE LIKE BITLY STOCK QUERY SERVER DESIGN A BASIC SEARCH ENGINE DATABASE DESIGN A BASIC SEARCH ENGINE CACHING DUPLICATE INTEGER IN MILLIONS OF DOCUMENTS ZOMATO YOUTUBE DESIGN IRCTC ALARM CLOCK DESIGN FOR ELEVATOR OF A BUILDING VALET PARKING SYSTEM OO DESIGN FOR A MCDONALDS SHOP OBJECT ORIENTED DESIGN FOR A RESTAURANT OBJECT ORIENTED DESIGN FOR A LIBRARY SYSTEM SUGGEST A SHORTEST PATH EXERCISE APPENDIX APPENDIX A

📄 Page 14

(This page has no text content)

📄 Page 15

CHAPTER 0: HOW TO USE THIS BOOK

📄 Page 16

(This page has no text content)

📄 Page 17

What this book is about This book is about usage of data structures and algorithms in computer programming. Data structures are the ways in which data is arranged in computers memory. Algorithms are set of instructions to solve some problem by manipulating these data structures. Designing an efficient algorithm to solve a computer science problem is a skill of Computer programmer. The skill which tech companies like Google, Amazon, Microsoft, Facebook, Adobe and many others are looking for in an interview. Once we are comfortable with a programming language, the next step is to learn how to write efficient algorithms. This book assumes that you are a C language developer. You are not an expert in C language, but you are well familiar with concepts of pointers, functions, arrays and recursion. At the start of this book, we will be revising the C language fundamentals that will be used throughout this book. We will be looking into some of the problems in arrays and recursion too. Then in the coming chapter we will be looking into Complexity Analysis. Followed by the various data structures and their algorithms. Will look into a linked list, stack, queue, trees, heap, Hash-Table and graphs. We will also be looking into sorting, searching techniques. Moreover, we will be looking into analysis of various algorithm techniques, such as brute force algorithms, greedy algorithms, divide & conquer algorithms, dynamic programming, reduction & backtracking. In the end, we will be looking into system design that will give a systematic approach to solve the design problems in an Interview.

📄 Page 18

Preparation Plans Given the limited time you have before your next interview, it is important to have a solid preparation plan. The preparation plan depends upon the time and which companies you are planning to target. Below are the three-preparation plan for 1 Month, 3 Month and 5 Month durations. 1 Month Preparation Plans Below is a list of topics and approximate time user need to take to finish these topics. These are the most important chapters that must to be prepared before appearing for an interview. This plan should be used when you have a limited time before an interview. These chapters cover 90% of data structures and algorithm interview questions. In this plan since we are reading about the various ADT in chapter 4 so we can use these datatype easily without knowing the internal details how they are implemented. Chapter 24 is for system design, you must read this chapter if you are three or more years of experienced. Anyway, reading this chapter will give the reader a broader perspective of various designs. Time Chapters Explanation Week 1 Chapter 1: Introduction - Programming Overview Chapter 2: Algorithms Analysis Chapter 3: Approach To Solve Algorithm Design Problems Chapter 4: Abstract Data Type You will get a basic understanding of how to find complexity of a solution. You will know how to handle new problems. You will read about a variety of datatypes and their uses. Week 2 Chapter 5: Searching Chapter 6: Sorting Chapter 14: String Algorithms Searching, Sorting and String algorithm consists of a major portion of the interviews. Week 3 Chapter 7: Linked List Chapter 8: Stack Chapter 9: Queue Linked lists are one of the favourites in an interview. Week 4 Chapter 10: Tree Chapter 23: Interview Strategy Chapter 24: System Design This portion you will read about Trees and System Design. You are good to go for interviews. Best of luck. 3 Month Preparation Plan This plan should be used when you have some time to prepare for an interview. This preparation plan includes nearly everything in this book except various algorithm techniques. Algorithm problems that are based on dynamic programming, divide & conquer etc. Which are asked in vary specific companies like Google, Facebook, etc. Therefore, until you are planning to face interview with them you can park these topics for some time and focus on the rest of the topics. Again, same thing here with system design problems, the more experience you are, the more important this chapter becomes. However, if you are a fresher from college, then also you should read this chapter. Time Chapters Explanation

📄 Page 19

Week 1 Chapter 1: Introduction - Programming Overview Chapter 2: Algorithms Analysis Chapter 3: Approach To Solve Algorithm Design Problems Chapter 4: Abstract Data Type You will get a basic understanding of how to find complexity of a solution. You will know how to handle new problems. You will read about a variety of datatypes and their uses. Week 2 & Week 3 Chapter 5: Searching Chapter 6: Sorting Chapter 14: String Algorithms Searching, sorting and string algorithm consists of a major portion of the interviews. Week 4 & Week 5 Chapter 7: Linked List Chapter 8: Stack Chapter 9: Queue Linked lists are one of the favourites in an interview. Week 6 & Week 7 Chapter 10: Tree Chapter 11: Heap This portion you will read about trees and heap data structures. Week 8 & Week 9 Chapter 12: Hash-Table Chapter 13: Graphs Hash-Table are used throughout this book in various places but now it is time to understand how Hash-Table are actually implemented. Graphs are used to propose a solution many real life problems. Week 10 Chapter 23: Interview Strategy Chapter 24: System Design Interview strategy and system design chapter are the final chapters of this course. Week 11 & Week 12 Revision of the chapters listed above. At this time, you need to revise all the chapters that we have seen in this book. Whatever is left needs to be completed and the exercise that may be left needing to be solved in this period. 5 Month Preparation Plan This preparation plan is made on top of 3-month plan. In this plan, the students should look for algorithm design chapters. In addition, in the rest of the time they need to practice more and more from www.topcoder.com and other resources. If you are targeting google, Facebook, etc., then it is highly recommended to join topcoder and practice as much as possible. Time Chapters Explanation Week 1 Week 2 Chapter 1: Introduction - Programming Overview Chapter 2: Algorithms Analysis Chapter 3: Approach To Solve Algorithm Design Problems Chapter 4: Abstract Data Type You will get a basic understanding of how to find complexity of a solution. You will know how to handle new problems. You will read about a variety of datatypes and their uses. Week 3 Week 4 Week 5 Chapter 5: Searching Chapter 6: Sorting Chapter 14: String Algorithms Searching, sorting and string algorithm consists of a major portion of the interviews. Week 6 Week 7 Week 8 Chapter 7: Linked List Chapter 8: Stack Chapter 9: Queue Linked lists are one of the favourites in an interview. Week 9 Week 10 Chapter 10: Tree Chapter 11: Heap This portion you will read about trees Week 11 Week 12 Chapter 12: Hash-Table Chapter 13: Graphs Hash-Table are used throughout this book in various places but now it is time to understand how Hash-Table are actually implemented.

📄 Page 20

Graphs are used to propose a solution many real life problems. Week 13 Week 14 Week 15 Week 16 Chapter 15: Algorithm Design Techniques Chapter 16: Brute Force Chapter 17: Greedy Algorithm Chapter 18: Divide-And-Conquer, Decrease- And-Conquer Chapter 19: Dynamic Programming Chapter 20: Backtracking And Branch-And- Bound Chapter 21: Complexity Theory And Np Completeness These chapters contain various algorithms types and their usage. Once the user is familiar with most of this algorithm. Then the next step is to start solving topcoder problems from https://www.topcoder.com/ Week 17 Week 18 Chapter 22: Interview Strategy Chapter 23: System Design Interview strategy and system design chapter are the final chapters of this course. Week 19 Week 20 Revision of the chapters listed above. At this time, you need to revise all the chapters that we have seen in this book. Whatever is left needs to be completed and the exercise that may be left needing to be solved in this period.