Python Quick Interview Guide

Top Expert-Led Coding Interview Question Bank for Python Aspirants (English Edition)

Shyamkant Limaye

• Verlag: BPB Publications
• Jahr: 2021
• ISBN:
  9789389423303
• Thema: Computer Science
• Thema: Programming Algorithms

Quick solutions to frequently asked algorithm and data structure questions.

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

CHAPTER 1

Lists, Binary Search, and Strings

Most of the coding interview questions are based on lists, binary search, and strings. In this chapter, we will solve many problems on these. If you have brushed up your knowledge on these topics, it is good. But even if you haven’t, don’t worry we will give you tips as we proceed.

Structure

The concepts of time complexity and space complexity are very important in competitive coding. We will introduce these concepts first and do some warm up exercises during that process. After you have mastered a few problems, we will take a little diversion and present a wonderful topic on practical measurement and the plotting of time complexity.

Then, we will end the chapter with some more problems. In the course of solving these problems, you will be introduced to binary search and sliding window algorithms. We will cover the topics in the following order:

• Time and space complexity
• Linear data structures in Python
• Searching and sorting
• Question 1: What is the position of a target in a given sorted array?
• Question 2: Is the given integer a valid square?
• Question 3: How will you move zeroes in a given array to the end?
• Question 4: How many boats are required to save people?
• Question 5: Is the given array a valid mountain array?
• Question 6: Which container can store maximum water?
• Question 7: Which was the first faulty version of the software?
• Question 8: What are all the subsets of a given set of integers?
• Background: Measuring execution time and time complexity
• Question 9: What is the maximum sum of a sub-array of a given array?
• Question 10: What is the integer part of the square root of a given integer?
• Question 11: What are the first and last positions of a target number in a given sorted array?
• Question 12: What is the position of a search target in a 2D matrix?
• Question 13: How will you convert an integer into a roman numeral?
• Question 14: How will you construct Pascal’s triangle?

Objectives

After studying this chapter, you will be able to understand the concepts of time and space complexities; practically measure time complexity; acquire the skills to analyze and solve questions on lists, binary search, and strings

1.1 Time and Space Complexity

There are always different approaches to solve a problem. All of them produce the same result, but some are smart, that is, they consume fewer resources, like time and memory. We need to find the approaches that are smart. When we execute a student program on a PC, we don’t bother how long it takes to execute it or how much memory it consumes. We always find the computer memory to be big enough for us and also that we get the answer in a few seconds. But real-life problems are bigger. They will test the limitations of the hardware. Therefore, we should be interested in knowing how the execution time of an algorithm behaves when the size of the input – n, becomes arbitrarily large. A practical thumb rule is if the execution time is proportional to n, then a typical computer can solve a problem of size n = 1 million in a reasonable time. But, if the execution time is proportional to n², then the reasonable size reduces to n = 1000, and if the execution time is proportional to 2ⁿ, then the reasonable size reduces to n = 20 only.

Suppose a function f(n), describes the relationship between the execution time and the size of the input to be processed. We want to find a simplified function g(n), which can compare the performance of various approaches. The function should be independent of the CPU speed and it should estimate the order of growth of the execution time for large values of n. Such estimates are called asymptotic estimates. But the execution time does not depend on n alone. It also depends on the nature of the data. For example, if the input to a Bubble Sort algorithm is already sorted, then the function just makes one pass through the data and finishes. The time required is proportional to n. But if the input data is sorted in the reverse order, then the function has to do a lot of work in rearranging it. The time required here is proportional to n². A typical input will be partially ordered. Thus, there is a best case timing, a worst case timing, and an average case...