Today this is a dynamic programming knowledge share from AlgoMonster following. We hope to provide you with a more comprehensive dynamic programming knowledge by taking into account theoretical foundations and effective experience summaries rather than theoretical descriptions by the book. At the same time, we also hope it can provide you with a shortcut to help you master dynamic programming problems faster and deal with interviews with ease.
The following content is shared by Lux, a describer who has many years of dynamic programming experience.
Self-introduction
Hi, I’m Lux, and I’m glad to meet you. Let me open the door and introduce myself first.
In the beginning, I worked at Cisco Systems. I was involved in designing and developing the core data exchange services for next-generation video conferencing systems. My work covered protocol stack development, microservice design, distributed system orchestration, and resilient algorithm design. This experience made me realize that algorithms are essential for designing critical services that determine the system’s stability, resilience, and scalability.
Later, I joined Autodesk as a framework and platform software engineer for a flagship 3D design software. I was responsible for developing a high-performance search engine based on large-scale structured data, bringing a flexible, multi-threaded, and asynchronous framework to the product framework level for the first time. And using an improved search engine on top of the original underlying memory model to achieve a performance improvement of over 300 times compared to the actual search functionality.
I also improved and maintained data processing systems to improve the user experience, and my work at the platform framework level gave me a lot of hands-on engineering experience. Now, I work at Autodesk Data Platform, where I design and develop analytics, enrichment, and streaming distributed services for large-scale data. I find that my career has been moving forward around data. With this in mind, one of the things I always say is, “data is justice.”
Then, until today, my attitude remains the same. Data is the medium, algorithms are the intermediary, and dynamic programming is a significant part of the fundamental algorithms.
Do interviewers ask about dynamic programming?
Yes. Suppose you usually pay attention to the extensive factory interviews. In that case, you will find that. Still, in all the R&D positions, whether recruiting junior or senior engineers, large companies tend to arrange one or more rounds of the particular algorithm interview session. The trend of asking dynamic programming-related questions in interview sessions has become more and more prominent.
Let me talk about my opinion. Let’s start with the algorithm thing. Please think back to when you were dealing with a data structure-related problem. You instinctively went to a tool function or library function to find out if there was an off-the-shelf tool.
If we solved a work problem quickly, did it quickly become a thing of the past? If the problem seems tricky and it’s not a typical algorithmic problem. Do you seek the help of a search engine or visit a “think tank” like Stack Overflow to find the solutions? Although you usually work well in your work, when you want to change jobs and attend interviews in big companies, you find yourself struggling to solve the algorithm problem asked by the interviewer. And you can’t get started, facing the blank.
You are not alone! This phenomenon is widespread. In fact, for developers, algorithms and data structures are our basic skills. We often laugh at ourselves that the job of software developers is to copy and paste. Moving bricks is the whole of our daily work. But when a company asks you to research a brand-new technology or quickly read the code of an open-source project that has been developed for years. The pressure will make you understand how vital basic knowledge is!
Is dynamic programming useful for interviews?
Yes, it is. The algorithm is like the cornerstone of a technical field. Its stability directly determines the ultimate height of the building. And what role does dynamic programming play?
As an interviewer, I have come across many excellent candidates who have a variety of backgrounds, potential, and hard work but have little idea of how to solve algorithmic problems and never make it to the next level. Unfortunately, dynamic programming is a fundamental methodology for solving problems. It has become the focus of an investigation because it reduces time complexity in many data processing application scenarios.
Not only that. But dynamic programming problems can also be an excellent way to examine the interviewee’s ability to abstract mathematical models and logical thinking. These can reflect the individual’s comprehensive ability in algorithms. So I think big companies are interested in an interviewee’s algorithmic foundation, especially the ability to solve dynamic programming problems. However, they are more interested in an interviewee’s problem-solving ideas and logical thinking ability. Not just the proficiency of tools and skills.
How to solve dynamic programming interview questions？
I want to address just one thing: having a good grasp of the basics can significantly broaden our ability to learn more new things and new technologies.
The best way to test the results of your learning is to keep practicing the exercises. Applying your theoretical knowledge to the activities is to check the gaps.
I’ll give you an example to understand. The cloud computing platform on a solution undoubtedly limited computing power (capacity). So what should we do? So that we can efficiently serve those customers with the highest degree of importance or priority, but who does not want to waste computing resources (to save money)?
This problem can be a simple orchestration using a distribution like queues. But that’s not good enough. Suppose we know the importance of a computational task and the required computational time. In that case, we can perform a pre-evaluation through dynamic programming to mathematically derive a rigorous orchestration result from maximizing the use of limited resources.
You see, the seemingly unreachable dynamic programming problem is the problem of finding the optimal solution. It is all around us all the time. Once again, this highlights why big manufacturers favor dynamic programming problems, and it becomes an invisible threshold that distinguishes interviewees. You could even say that mastering dynamic programming ideas is central to job interviews and technical grade promotions.