The Problem Solver’s Guide To Coding Nhut Nguyen, Ph. February, 2024 The Problem Solver’s Guide To Coding First edition. ISBN 9788797517413 (PDF) Copyright © 2024 Nhut Nguyen. All rights reserved.com To my dearest mother, Nguyen Thi Kim Sa.
iii iv PREFACE Welcome to The Problem Solver’s Guide To Coding, a comprehensive journey to mas- ter problem-solving, data structures, algorithms, and programming techniques using C++. This book results from my experiences, challenges, failures and successes in my programming career. One of the most critical phases in software developer hiring process is the coding interview, a rigorous process where candidates are tested on their problem-solving skills and technical proficiency. Companies like FAANG (Facebook, Amazon, Apple, Netflix, and Google) often subject candidates to three to four rounds of interviews, making preparation essential for success.
My journey with coding interviews began during a pivotal career change in the summer of 2021. During this transitional period, I discovered LeetCode, a platform that soon became my daily companion in honing my programming skills. What started as a means to practice new languages (Golang and C#) quickly evolved into a deep exploration of my strongest language, C++. One day, I decided to write an article for each challenge and share it on my blog leet- solve.
Over time, my daily practice transformed into more than 70 challenges, each accompanied by a detailed article encompassing problem statements, various approaches, C++ code implementations, thorough explanations, and complexity analyses. As I delved into these coding challenges, I realized their potential to empower as- piring programmers, students, and junior developers to excel in interviews and master problem-solving and algorithmic thinking. v Overview of the book The Problem Solver’s Guide to Coding presents challenges covering fundamental data structures, algorithms, and mathematical problems. Challenges are grouped in top- ics, starting with the simplest data structure - Array.
Most are arranged in order of increasing difficulty, but you can pick any chapter or any challenge to start since I write each independently to the other. Challenges in this book are curated from LeetCode.com, focusing on those that are not difficult but provide valuable learning experiences. You might encounter some simple challenges I go directly to the code without saying much about the idea (intuition) since their solution is straightforward. I also keep the problems’ original constraints (inputs’ size, limits, etc.) as the code in this book is the ones I submitted on Leetcode.
It explains why I usually focus on the core algorithm and do not consider/handle corner cases or invalid inputs. The problems in each chapter comes with a detailed solution, explaining the logic behind the solution and how to implement it in C++, my strongest programming language. At the end of some problems, I also provide similar problems on leetcode.com for you to solve on your own, as practicing is essential for reinforcing understanding and mastery of the concepts presented in the book. By engaging in problem-solving exercises, you can apply what you have learned, develop your problem-solving skills, and gain confidence in your ability to tackle real-world challenges.
In this book, I focus on readable code rather than optimal one, as most of you are at the beginner level. Some of my solutions might need to be in better runtime or memory. But I keep my code in my style or coding convention, where readability is vital. Moreover, my weekly sharing of articles with various developer communities has re- fined the content and established a connection with a diverse group of programming enthusiasts.
vi Who is this book for? This book is tailored to benefit a wide audience, from students beginning their programming journey to experienced developers looking to enhance their skills. Regardless of your experience level, whether you’re preparing for coding inter- views or simply seeking to improve your problem-solving abilities, this book is designed to meet your needs. As a minimum requirement, you are supposed to have some basic background in C++ programming language, data structures and algorithms like a second-year undergraduate in Computer Science. What sets this book apart is its focus on practicality.
The challenges presented here are not just exercises; they mirror real coding interviews from top companies like FAANG. As you work through the coding challenges in this book, you’ll learn new skills, im- prove your problem-solving abilities, and develop your confidence as a programmer. Acknowledgement I am deeply grateful to my invaluable previewers, especially Alexander Volkodav, Phung Phu Tai, Le Nhat Tung, Tran Anh Tuan A, Bui Nguyen Cong Duy, Cao Minh Thinh, Nguyen Trung Tuan, Nguyen Tuan Hung, Nguyen Hoang Nhat Minh, Nhan Nguyen, Phan Dinh Thai and Nguyen Quang Trung, whose dedication and insights have shaped this book into its final form. Your contributions and unwavering sup- port are truly appreciated.
I would like to express my heartfelt gratitude to Ninh Pham, Hoang Thanh Lam, Dinh Thai Minh Tam and Tran Anh Tuan B, whose invaluable feedback contributed to the refinement of this book in future versions. Your insightful comments and con- structive criticism have played a pivotal role in shaping its content and enhancing its quality. Thank you for your dedication and generosity in sharing your expertise. Your input will undoubtedly pave the way for future improvements and iterations of this work.
vii Students and developers! By immersing yourself in the challenges and insights shared in this book, you will not only prepare for coding interviews but also cultivate a mindset beyond the scope of a job interview. You will become a problem solver, a strategic thinker, and a proficient C++ programmer. As you embark on this journey, remember that every challenge you encounter is an opportunity for growth. Embrace the complexities, learn from each solution, and let the knowledge you gain propel you to new heights in your programming career.
Thank you for joining me on this expedition. May your code be elegant, your algorithms efficient, and your programming journey genuinely transformative. Happy coding! Copenhagen, February 2024. Nhut Nguyen, Ph.
viii CONTENTS 1 Introduction 1 1.2 A brief about algorithm complexity .3 Why readable code? .2 Valid Mountain Array .4 Find All Numbers Disappeared in an Array .6 Spiral Matrix II .1 Merge Two Sorted Lists .2 Remove Linked List Elements .3 Intersection of Two Linked Lists .4 Swap Nodes in Pairs .5 Add Two Numbers .1 Roman to Integer .2 Maximum Erasure Value .3 Find and Replace Pattern .3 Unique Morse Code Words .4 Unique Email Addresses .5 Longest Substring Without Repeating Characters .6 Compare Version Numbers .3 Backspace String Compare .4 Remove All Adjacent Duplicates in String II .1 Last Stone Weight .2 Kth Largest Element in a Stream .3 Kth Smallest Element in a Sorted Matrix .4 Construct Target Array With Multiple Sums .2 Power of Four .3 Find the Duplicate Number .4 Maximum Product of Word Lengths .2 Merge Sorted Array .3 Remove Covered Intervals .5 Remove Duplicates from Sorted Array II .1 Can Place Flowers .2 Minimum Deletions to Make Character Frequencies Unique .4 Partitioning Into Minimum Number Of Deci-Binary Numbers .5 Maximum Units on a Truck .3 Largest Divisible Subset .5 Unique Paths II .2 First Unique Character in a String .3 Max Number of K-Sum Pairs .1 Running Sum of 1d Array .3 Product of Array Except Self .4 Subarray Sum Equals K .1 Middle of the Linked List .2 Linked List Cycle .3 Sort Array By Parity II .4 Container With Most Water .5 Remove Nth Node From End of List .6 Shortest Unsorted Continuous Subarray .1 Excel Sheet Column Number .2 Power of Three .3 Best Time to Buy and Sell Stock .5 Minimum Moves to Equal Array Elements II .7 Count Sorted Vowel Strings .8 Concatenation of Consecutive Binary Numbers. 356 16 Conclusion 365 xi A Coding challenge best practices 367 A.1 Read the problem carefully .2 Plan and pseudocode .3 Test your code .4 Optimize for time and space complexity .5 Write clean, readable code .6 Submit your code and learn from feedback. 368 xii CONTENTS CHAPTER ONE INTRODUCTION 1.1 Why LeetCode? Coding challenges are a great way to practice problem-solving, algorithm develop- ment, and logical thinking. They showcase your creativity and innovation while improving your coding techniques.
This book offers diverse coding challenges to help you develop your skills. Coding challenges could be programming puzzles or mathematical problems that require coding solutions. Each challenge requires different coding skills and is de- signed to challenge and develop a particular set of skills. The coding challenges in this book are picked from LeetCode.
It is a popular online platform for programmers and software engineers that provides many coding chal- lenges and problems. The website was launched in 2015 and has since grown to become one of the go-to resources for coding practice, technical interview prepara- tion, and skills enhancement. LeetCode offers diverse coding challenges, ranging from easy to hard, covering a wide range of topics such as algorithms, data structures, databases, system design, and more. The problems are created by industry experts and are designed to sim- ulate real-world scenarios, allowing you to gain practical experience in problem- solving.
One feature that makes LeetCode stand out is its extensive discussion forum, where you can interact, share your solutions, and learn from one another. This fosters community and collaboration, as you can receive feedback on their solutions and ask for clarification on difficult problems. 1 LeetCode also provides premium services like mock interviews with real-world com- panies, career coaching, and job postings. These premium services are designed to help you prepare for technical interviews, sharpen your skills, and advance your careers.
LeetCode has become a popular resource for technical interview preparation, as many companies use similar problems to screen and evaluate potential candidates. The platform has helped many users to secure job offers from top companies in the technology industry, including Google, Microsoft, and Facebook. In summary, LeetCode is a valuable resource for programmers and software engi- neers looking to improve their coding skills, prepare for technical interviews, and advance their careers. Its extensive collection of coding challenges, community dis- cussion forums, and premium services make it an all-in-one platform for coding practice and skills enhancement.2 A brief about algorithm complexity Algorithm complexity, also known as runtime complexity, is a measure of how the running time of an algorithm increases as the input size grows.
It is an essential concept in computer science, as it helps programmers evaluate and optimize their algorithms’ performance. The complexity of an algorithm is usually measured in terms of its Big O notation, which describes the upper bound of the algorithm’s running time as a function of the input size. For example, an algorithm with a time complexity of O(n) will have a running time proportional to the input size. In contrast, an algorithm with a time complexity of O(n^2) will have a running time proportional to the square of the input size.
Algorithm complexity is important because it helps programmers determine their al- gorithms’ efficiency and scalability. In general, algorithms with lower complexity are more efficient, as they require less time and resources to process larger inputs. By analyzing the time complexity of an algorithm, programmers can identify potential performance bottlenecks and optimize their code accordingly. In addition to time complexity, algorithms may also have space complexity, which measures the memory required to execute the algorithm.
Space complexity is also measured in Big O notation and is important for optimizing the memory usage of 2 Chapter 1. Introduction an algorithm. While it is important to optimize the performance of algorithms, it is also important to balance this with readability and maintainability. A highly optimized algorithm may be difficult to understand and maintain, which can lead to problems in the long run.
Therefore, it is important to balance performance and readability when designing and implementing algorithms. In summary, algorithm complexity is an essential concept in computer science that helps programmers evaluate and optimize their algorithms’ performance.