This is going to be a short story, hopefully this trick will allow someone to optimize their algorithm further during an onsite interview. The main tenet of Dynamic Programming is to break down a complex problem into sub-problems, memoize those solutions in order not to recompute the same things multiple time, henceforth reducing the algorithm complexity.
This is going to be a short story, hopefully this trick will allow someone to optimize their algorithm further during an onsite interview. The main tenet of Dynamic Programming is to break down a complex problem into sub-problems, memoize those solutions in order not to recompute the same things multiple time, henceforth reducing the algorithm complexity.
To put it into perspective, one can compare two solutions to the very simple problem of finding Fibonacci numbers. Using recursion, the single function call breaks down to many more function calls which are all revolved around the same values. Even though it reaches a solution, the resulting algorithm has exponential time complexity. Solving the same problem using DP leads to a solution with linear time complexity, saving both time and computational power.
With the problems that are concerned with dynamic programming, the frequent approach is to use maps or arrays to store the partial solutions.
While most of the valid solutions will use a data structure to keep the results of computation memoized, I have seen in many code snippets that that data structure is re-created on every new function call. Since this happens on every new test-case, it might not be the most optimal way. This is also wrong as in case of concurrent execution of the function against different outputs there is no performance improvement and the computation will be re-done redundantly. To avoid this, simply move the data structure out of the function, as below.
The 9th line is just verifying that the key does not yet exist in the map in order not to recompute it. Since the value is not relevant and we only care whether the map contains the key, it is assigned to the _ throwaway variable.
Note that there is not pointer to the map m. Since maps in Golang are reference types you don’t need to include a pointer to the map address, it is referenced automatically under the hood. In case of a slice it would be required, though.
Good Luck!
Share with your friends and followers
Start blogging about your favorite technologies, reach more readers and earn rewards!
Join other developers and claim your FAUN account now!
User Popularity
17
Influence
2k
Total Hits
1
Posts
Read, Learn, Know, Teach
Hand curated newsletters for Developers, private Slack with like minded people, podcasts, job offers, news and more!
Only registered users can post comments. Please, login or signup.