Python Quick Interview Guide: Top Expert-Led Coding Interview Question Bank for Python Aspirants

Length: 430 pages
Edition: 1
Language: English
Publisher: BPB Publications
Publication Date: 2021-04-10
ISBN-10: 9389423309
ISBN-13: 9789389423303
Sales Rank: #0 (See Top 100 Books)

Quick solutions to frequently asked algorithm and data structure questions.

Key Features

Learn how to crack the Data structure and Algorithms Code test using the top 75 questions/solutions discussed in the book.
Refresher on Python data structures and writing clean, actionable python codes..
Simplified solutions on translating business problems into executable programs and applications..

Description
Python is the most popular programming language, and hence, there is a huge demand for Python programmers. Even if you have learnt Python or have done projects on AI, you cannot enter the top companies unless you have cleared the Algorithms and data Structure coding test.

This book presents 75 most frequently asked coding questions by top companies of the world. It not only focuses on the solution strategy, but also provides you with the working code. This book will equip you with the skills required for developing and analyzing algorithms for various situations. This book teaches you how to measure Time Complexity, it then provides solutions to questions on the Linked list, Stack, Hash table, and Math. Then you can review questions and solutions based on graph theory and application techniques. Towards the end, you will come across coding questions on advanced topics such as Backtracking, Greedy, Divide and Conquer, and Dynamic Programming.

After reading this book, you will successfully pass the python interview with high confidence and passion for exploring python in future.

What you will learn

Design an efficient algorithm to solve the problem.
Learn to use python tricks to make your program competitive.
Learn to understand and measure time and space complexity.
Get solutions to questions based on Searching, Sorting, Graphs, DFS, BFS, Backtracking, Dynamic programming.

Who this book is for
This book will help professionals and beginners clear the Data structures and Algorithms coding test. Basic knowledge of Python and Data Structures is a must.

Table of Contents
1. Lists, binary search and strings
2. Linked lists and stacks
3. Hash table and maths
4. Trees and graphs
5. Depth first search
6. Breadth first search
7. Backtracking
8. Greedy and divide and conquer algorithms
9. Dynamic programming

About the Authors
Professor Shyamkant Limaye spent 18 years in the computer industry and 30 years in teaching electronics engineering students. His experience includes a two-year stint as a system analyst in the USA. In 1971, he graduated from Visvesvaraya National Institute of Technology in Electrical Engineering with a gold medal. He did masters from IIT Kanpur and Doctorate in electronics from RTM Nagpur University. He has guided ten students for PhD. He published a text book on VHDL programming in 2007. He has also published a thriller novel titled “Dual reality” in 2011. Currently, he is a Professor in the Electronics and Telecomm Department at St. Vincent Pallotti College of Engineering and Technology, Nagpur.

LinkedIn profile: https://www.linkedin.com/in/shyam-limaye-35816ba/
Blog links: limayesir.wordpress.com

Cover Page
Title Page
Copyright Page
Dedication Page
About the Author
About the Reviewer
Acknowledgements
Preface
Errata
Table of Contents
1. Lists, Binary Search, and Strings
    Structure
    Objectives
    1.1 Time and Space Complexity
        1.1.1 O(n)
        1.1.2 O(1)
        1.1.3 O(n2)
        1.1.4 O(n3)
        1.1.5 O(n log n)
        1.1.6 O(2n)
        1.1.7 Space complexity
    1.2 Linear Data Structures in Python
        1.2.1 The list class
        1.2.2 NumPy arrays
        1.2.3 Strings
    1.3 Sorting and Searching
        Searching
    1.4 Question 1: What is the position of a target in a given sorted array?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Linear Search
            Python code
            Complexity Analysis
            Approach 2 – Binary Search
            Python code
            Complexity Analysis
    1.5 Question 2 – Is the given integer a valid square?
        Problem statement
            Solution format
        Strategy
            Approach 1: Linear Search
            Python code
            Complexity Analysis
            Approach 2 – Summation of Arithmetic Progression
            Python code
            Complexity Analysis
    1.6 Question 3 – How will you move zeroes in a given array to the end?
        Problem statement
        Solution format
        Strategy
            Pseudo code
            Python code
            Complexity Analysis
    1.7 Question 4 – How many boats are required to save people?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    1.8 Question 5 – Is the given array a valid mountain array?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    1.9 Question 6 – Which container can store maximum water?
        Problem statement
        Strategy
            Brute force approach
            Pinching window approach
            Answer format
            Python code
            Complexity Analysis
    1.10 Question 7 – Which was the first faulty version of the software?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    1.11 Question 8 – What are all the subsets of a given set of integers?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Growing from seeds
            Python code
            Complexity Analysis
            Approach 2: Binary Representation
            Python code
            Complexity Analysis
            Python code
            Complexity Analysis
    1.12 Background – Measuring the execution time and the time complexity
        1.12.1 Introduction
        1.12.2 Using perf_counter
        1.12.3 Use of timeit
        1.12.4 Plotting the time complexity graphs
            Python code
            Plotting a graph for the sort function
            Python code
            Plotting a graph for the subsets of a set problem
            Python code
    1.13 Question 9 – What is the maximum sum of a subarray of a given array?
        Problem statement
        Solution format
        Strategy
            Brute force method
            Python code
            Complexity Analysis
            Python code
            Efficient method
            Python code
            Python code
    1.14 Question 10 – What is the integer part of the square root of a given integer?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Linear search
            Python code
            Complexity Analysis
            Approach 2 – Binary search
            Python code
            Complexity Analysis
    1.15 Question 11 – What are the first and last positions of a target number in a given sorted array?
        Problem statement
        Solution format
        Strategy
            Linear search (Brute force)
            Python code
            Complexity Analysis
            Binary search
            Python code
            Python code
            Complexity Analysis
    1.16 Question 12 – What is the position of a search target in a 2D matrix?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Linear search
            Complexity Analysis
            Approach 2 – 2D Linear search
            Python code
            Complexity Analysis
            Approach 3 – 2D Binary search
            Python code
            Complexity Analysis
    1.17 Question 13 – How will you convert an integer into a roman numeral?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    1.18 Question 14 – How will you construct Pascal’s triangle?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    Conclusion
    Points to Remember
    MCQs
        Answers to MCQs
    Questions
    Key Terms
2. Linked Lists and Stacks
    Structure
    Objectives
    2.1 Basics of Linked Lists
        2.1.1 Node, the basic building block
        2.1.2 Creating and displaying a linked list
            Python code
        2.1.3 Adding a node in the beginning
            Python code
        2.1.4 Adding a node at the end
            Python code
        2.1.5 Creating a list from an array
            Python code
    2.2 Question 15 – How will you merge two sorted lists?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    2.3 Question 16 – How will you detect a cycle in a linked list?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    2.4 Question 17 – How will you reverse a linked list?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    2.5 Question 18 – How will you add two linked lists?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    2.6 Question 19 – How will you remove the nth node from the right?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    2.7 Question 20 – How will you create odd and even linked lists?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    2.8 Question 21 – How will you evaluate the reverse polish postfix expression?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    2.9 Question 22 – How will you achieve the minimum implementation of a stack using a list?
        Problem statement
        Solution format
        Strategy
            Approach 1: O(n)
            Python code
            Approach 2 – O(1)
            Python code
            Complexity Analysis
    Conclusion
    Points to Remember
    MCQs
        Answers to MCQs
    Questions
    Key terms
3. Hash Table and Maths
    Structure
    Objectives
    3.1 Implementation of Hash Table in Python
        Using “defaultdict”
        Using “set”
    3.2 Question 23 – How will you find if an array contains duplicates?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Brute force
            Python code
            Complexity Analysis
            Approach 2 – Sorting
            Python code
            Complexity Analysis
            Approach 3 – Using the “set” method
            Python code
            Complexity Analysis
            Approach 4: Using hash tables
            Python code
            Complexity Analysis
    3.3 Question 24 – How will you find if an array contains duplicates in the vicinity?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    3.4 Question 25 – How will you find the majority element in an array?
        Problem statement
        Solution format
        Strategy
            Approach 1 – From basics
            Python code
            Approach 2 – Using the “count” method of the list class
            Python code
            Approach 3 – Using the “get” method of the dictionary with default
            Python code
            Approach 4 – Using the “Counter” method from the collections module
            Python code
            Complexity Analysis
    3.5 Question 26 – How will you find if the string of brackets is valid?
        Problem statement
        Solution format
        Strategy
            Pseudo code
            Python code
            Complexity Analysis
    3.6 Question 27 – How will you find two numbers whose sum equals the target?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Brute force method
            Python code
            Complexity Analysis
            Approach 2 – Hash table
            Python code
            Complexity Analysis
    3.7 Question 28 – How will you count the primes less than n?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Brute force method
            Python code
            Complexity Analysis
            Approach 2 – Eratosthenes sieve method
            Python code
            Complexity Analysis
    3.7 Question 29 – How will you find the longest substring without the repeating characters?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Brute force
            Python code
            Complexity Analysis
            Approach 2 – Sliding window
            Python code
            Complexity Analysis
    3.8 Question 30 – How will you convert a roman numeral into a decimal numeral?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    3.9 Question 31 – How will you identify a single number in an array?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Using a list
            Python code
            Complexity Analysis
            Approach 2 – Using a hash table
            Python code
            Complexity Analysis
            Approach 3 –Algebraic method
            Python code
            Complexity Analysis
    Conclusion
    Points to Remember
    MCQs
        Answers to the MCQs
    Questions
    Key terms
4. Trees and Graphs
    Structure
    Objectives
    4.1 Basics of Graph Theory
    4.2 Representation and Manipulation of Graphs
        4.2.1 Representation
        4.2.2 Manipulation of graphs
        Python code
    4.3 Representation and Manipulation of Trees
        4.3.1 Representation of binary trees in memory
        4.3.2 Creation and display
            Python code
            Python code
            Python code
    4.4 Recursion
    4.5 Question 32 – How will you detect a redundant road connection?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity
    4.6 Question 33 – How will you find the lowest common ancestor in a binary tree?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    4.7 Question 34 – Who is the town judge?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    4.8 Question 35 – How will you select flowers so that the adjacent gardens are not the same?
        Problem statement
        Solution format
        Strategy
        Python code
            Complexity Analysis
    Conclusion
    Points to remember
    MCQs
        Answers to MCQs
    Questions
    Key terms
5. Depth First Search
    Structure
    Objectives
    5.1 DFS Traversal of Graphs and Trees
        Python code
        Python code
            Complexity Analysis
        DFS Traversal of Trees
    5.2 Question 36 – How will you reconstruct the itinerary from tickets?
        Problem statement
        Solution format:
        Strategy
            Python code
            Complexity Analysis
    5.3 Question 37 – How will you validate a symmetric binary tree?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Recursive
            Python code
            Complexity Analysis
            Approach 2 – Iterative
            Python code
            Complexity Analysis
    5.4 Question 38 – How will you find the maximum height of a binary tree?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.5 Question 39 – How will you find the path sum in a binary tree?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.6 Question 40 – What is the Kth smallest element in a binary search tree?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis:
    5.7 Question 41 – How will you find the maximum path sum in a binary tree?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.8 Question 42 – How will you validate a balanced binary tree?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.9 Question 43 – How will you validate a binary search tree?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.10 Question 44 – What is the number of islands?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.11 Question 45 – How will you remove the surrounded islands?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.12 Question 46 – Is the course schedule valid?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    5.13 Question 47 – How will you reward a sales manager?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    Conclusion
    Points to Remember
    MCQs
        Answers to the MCQs
    Questions
    Key Terms
6. Breadth First Search
    Structure
    Objectives
    6.1 Basic BFS graph class
        Python code
        Recursive approach
            Python code
    6.2 Question 48 – How will you print a tree level-wise?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity
    6.3 Question 49 – How will you build a word ladder between two words by changing one letter at a time?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity
    6.4 Question 50 – How will you find a course sequence according to pre-requisites?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity
    6.5 Question 51 – How will you test if two nodes of a tree are cousins?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity
    6.6 Question 52 – How will you find the shortest bridge across two islands?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity
    Conclusion
    Points to remember
    MCQs
        Answers to MCQs
    Questions
    Key terms
7. Backtracking
    Structure
    Objectives
    7.1 Backtracking principle
        Some famous backtracking problems
            Place N-Queens
            Find a Hamiltonian circuit in the graph
    7.2 Question 53 – How will you search a word in a grid?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    7.3 Question 54 – How will you traverse a maze?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    7.4 Question 55 – How will you find all the combinations of n numbers taken k at a time?
        Problem statement
            Solution format
        Strategy
            Python code
            Complexity Analysis
    7.5 Question 56 – How will you partition a string into palindrome segments?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    7.6 Question 57 – What is the sum of the elements of the BST within a range?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    7.7 Question 58 – How will you partition a set into k subsets having equal sum?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    Conclusion
    Points to Remember
    MCQs
        Answers to MCQs
    Questions
    Key terms
8. Greedy and Divide-and-Conquer Algorithms
    Structure
    Objectives
    8.1 Some famous problems on greedy methodology
    8.2 Some famous applications of divide-and-conquer strategy
    8.3 Question 59 – How will you maximize the value in a knapsack?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    8.4 Question 60 – How will you remove k digits from a number to get the smallest number?
        Problem statement
        Solution format
        Strategy
            Python code
        Complexity Analysis
    8.5 Question 61 – Can you provide the correct change to lemonade customers?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    8.6 Question 62 – How will you use the divide-and-conquer strategy for sorting?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    8.7 Question 63 – How will you find the k closest points to the origin?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Sorting
            Python code
            Complexity Analysis
            Approach 2 – Selection sort
            Python code
            Complexity Analysis
    Conclusion
    Points to Remember
    MCQs
        Answers to the MCQs
    Questions
    Key terms
9. Dynamic Programming
    Structure
    Objectives
    9.1 Principles of dynamic programming
        Problem statement
            Python code
            Python code
        Problem statement
        Strategy
            Python code
    9.2 Question 64 – How will you maximize the value in a 0/1 knapsack?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    9.3 Question 65 – How to maximize the sales of a door-to-door salesman?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    9.4 Question 66 – What is the best time to buy and sell stock?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Brute force
            Python code
            Complexity Analysis
            Approach 2 – Dynamic programming
            Python code
            Complexity Analysis
    9.5 Question 67 – What is the best time to buy and sell stock, part 2?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    9.6 Question 68 – In how many ways can you climb the stairs?
        Problem statement
        Solution format
        Strategy
            Approach 1 – Pure dynamic programming
            Python code
            Complexity Analysis
            Approach 2 – Compact array
            Python code
            Complexity Analysis
            Approach 3 – Matrix exponentiation
            Python code
            Python code
            Complexity Analysis
            Approach 4 – Binet’s formula
            Python code
            Complexity Analysis
    9.7 Question 69 – How will you minimize the cost of climbing stairs?
        Problem statement
        Solution format
        Strategy
            Consider i = 1
            Consider i = 2
            Python code
            Complexity Analysis
    9.8 Question 70 – What is the minimum number of coins to dispense the change?
        Problem statement
        Solution format
        Strategy
            Consider i = 1
            Consider i = 2
            Consider i = 3
            Consider i = 4
            Consider i = 5
            Python code
            Python code
            Complexity Analysis
    9.9 Question 71 – How many coin patterns to dispense the change?
        Problem statement
        Solution format
        Strategy
        Consider i= first coin and value = 1
            Now consider i=2
            Now consider i=5
            Consider i = 2 (Only one value)
            Python code
            Complexity Analysis
    9.10 Question 72 – How many unique paths exist in a square grid?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    9.11 Question 73 – How many unique paths exist in a square grid having obstacles?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    9.12 Question 74 – What is the longest palindromic substring of a given string?
        Problem statement
        Solution format
        Strategy
            Consider j=1
            Consider j=2
            Consider j=3
            Consider j=4
            Python code
            Complexity Analysis
    9.13 Question 75 – How much rain water can be trapped in the ridges?
        Problem statement
        Solution format
        Strategy
            Python code
            Complexity Analysis
    Conclusion
    Points to Remember
    MCQs
        Answers to MCQs
    Questions
    Key terms
Index