Skip to main content
Code Review

Questions tagged [memoization]

Ask Question

An optimization technique where function calls are cached to avoid duplicate computations.

86 questions
Newest Active Bountied Unanswered
Filter by
Sorted by
Tagged with
3 votes
1 answer
140 views

This is the third iteration of the code from Calculate optimal game upgrades, v2 and Calculate optimal game upgrades. I'm looking for suggestions to further optimize this code. A brief summary of the ...
ayaan098's user avatar
  • 125
5 votes
3 answers
1k views

How can the following recursion + memoization code be converted into a tabulation format dynamic programming solution? The code is working, but I want to improve it. The challenge I am facing is ...
Elias El hachem's user avatar
  • 51
4 votes
1 answer
161 views

This is the second iteration of the code I originally posted here: Calculate optimal game upgrades. Based on the feedback there, I chose to change the code to use a dynamic programming approach with ...
ayaan098's user avatar
  • 125
2 votes
1 answer
72 views

This is a contrived example of a question that came up in code review the other day about memoizing context values in React. Let's say I have a hook which returns a memoized value of an expensive ...
Asleepace's user avatar
  • 155
7 votes
2 answers
1k views

This algorithm encodes a 64 bit integer. As input I have a 64 bit integer a, for example: (a is a single 64 bit number,which I split in 8 bytes for readability) <...
tutizeri's user avatar
  • 173
1 vote
1 answer
632 views

On day 1, one person discovers a secret. You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the ...
jason's user avatar
  • 21
2 votes
1 answer
236 views

I'm trying to solve the following problem: You have a k-dice. A k-dice is a dice which have k-faces and each face have value written from 1 to k. Eg. A 6-dice is the normal dice we use while playing ...
driver's user avatar
  • 222
2 votes
2 answers
297 views

I've coded a program that calculates the number of partitions of n into at least two distinct parts, and is relatively quick too (about N^1.5 complexity). For input 30 000 it takes roughly 4 seconds. ...
svok's user avatar
  • 21
0 votes
1 answer
111 views

I have a simple cookie popup where the component technically runs on every page, giving the user the option to accept all or essential cookies. Once they accept an option, the popup no longer shows. ...
user8758206's user avatar
  • 557
2 votes
1 answer
184 views

I have written a function that randomly picks one element from a set with different probabilities for each element, anyway it takes a dictionary as argument, the keys of the dictionary are the choices ...
Ξένη Γήινος's user avatar
  • 3,704
3 votes
1 answer
224 views

...
avamsi's user avatar
  • 165
10 votes
1 answer
2k views

My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved? Can some form of memoization be used here? There are cases ...
python_user's user avatar
  • 165
3 votes
1 answer
348 views

So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values ...
Martin Boros's user avatar
  • 133
6 votes
2 answers
1k views

Compiler is g++ 4.2. I'm new to C++, but I've done a lot of data science, web scraping, and some socketing stuff in Python. This code generates the nth Fibonacci number, either with a naive ...
William Bradley's user avatar
  • 297
1 vote
3 answers
166 views

I'm an amateur programmer making a career change into web development. I've found Advent of Code challenges are great way to sharpen my skills. I've cleaned up this solution for Day 10, 2020 as much ...
Kevin Andrus's user avatar
  • 13
1 vote
1 answer
517 views

I need help to optimize my code for huge lists with approx. 10000000 elements. Is there a way to improve my algorithm or should I try to build a new one using a completely different approach? Task: ...
Luca Brasi's user avatar
  • 21
1 vote
1 answer
157 views

I need to perform some expensive calculation, such as determining a Fibonacci number: ...
marcprux's user avatar
  • 119
6 votes
1 answer
197 views

Given the following generic memoize utility for pure functions with type hints: ...
Ngoy Lufo's user avatar
  • 71
6 votes
1 answer
455 views

I have a simple binary tree that has no parent pointers. ...
Mark Karavan's user avatar
  • 223
3 votes
1 answer
199 views

File fibonacci.aec: ...
FlatAssembler's user avatar
  • 679
2 votes
2 answers
249 views

I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case. Problem statement There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of ...
Youssef13's user avatar
  • 167
3 votes
0 answers
105 views

note: You might be scared seeing the length of the post, but it's actually not that long because you don't need to read the compiler logs or the python code to understand my code (I wish StackExchange ...
Benoît P's user avatar
  • 809
3 votes
1 answer
136 views

I am trying to create a word-finder game. There will be an n-by-n Board filled with Tiles. ...
Kerry Huang's user avatar
  • 33
1 vote
1 answer
655 views

I am solving some problems from CodeChef but I am stuck on the Matches problem: Ari and Rich are playing a pretty confusing game. Here are the rules of the game: The game is played with ...
ADITYA JOSHI's user avatar
  • 13
3 votes
0 answers
127 views

I wrote code to (naively) perform lru memoisation. I tried to write it in a functional programming style, and so did not make use of any global variables. My Code ...
Tobi Alafin's user avatar
  • 1,792
1 vote
1 answer
53 views

I wrote code to (naively) perform automatic memoisation. I tried to write it in a functional programming style, and so did not make use of any global variables. My Code ...
Tobi Alafin's user avatar
  • 1,792
4 votes
3 answers
8k views

This post is based on the 0-1 Knapsack problem. I came across this problem in Assignment #4 of Professor Tim Roughgarden's course Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming on ...
user avatar
2 votes
1 answer
76 views

I made an algorithm to train my skill in dynamic programming and I would like to have feed back on it. This algorithm takes a money system (int) and have a certain ...
J. Toulmonde's user avatar
  • 21
2 votes
3 answers
433 views

Definition of Happy numbers taken from Wikipedia. A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits ...
vikrant's user avatar
  • 405
12 votes
2 answers
4k views

I'm trying to come up with an "elegant" way of calculating Fibonacci for number in Rust, using recursion and memoization (self-imposed requirements). This is what I have so far: ...
Armando Pérez Marqués's user avatar
  • 223
1 vote
1 answer
229 views

I am trying to find the longest Collatz Sequence: Which starting number, ≤ N, produces the longest chain? If many possible such numbers are there print the maximum one. (1 ≤ N ≤ 5×106) I tried ...
Shankar Shastri's user avatar
  • 109
3 votes
1 answer
2k views

This function word_break(s, dictionary) receives a string s and a set of all valid words ...
nycb's user avatar
  • 31
6 votes
2 answers
319 views

I am working on a little thread-safe, garbage collectible memoizer for Funcs in C#. The goals: Make it easy to Memoize deterministic functions. Make sure invocation of a memoized Func with a given ...
bopapa_1979's user avatar
  • 503
3 votes
0 answers
2k views

Problem statement The problem is defined in the book as following: 8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
Igor Soloydenko's user avatar
  • 3,540
2 votes
1 answer
101 views

I solved this problem using a Class, but thought I might try to figure out this memoization thing. Problem There are two printers that print pages at different speeds (X, Y). What is the minimum ...
Raystafarian's user avatar
  • 7,309
1 vote
1 answer
480 views

I just started learning recursion and memoization, so I decided to give a simple implementation a shot. Works with some simple test cases I came up with. Is there anything I can add to make this more ...
Togepi's user avatar
  • 127
7 votes
2 answers
780 views

I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks: Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, ...
Bor's user avatar
  • 507
2 votes
1 answer
259 views

I wrote the following code to solve this leetcode problem: ...
Fahd Ahmed's user avatar
  • 21
5 votes
1 answer
930 views

Here is my take on wild card pattern matching with memoization. I would appreciate comments on clarity of the code, as well as suggested ways to improve readability and maintainability (for bigger ...
CIsForCookies's user avatar
  • 351
2 votes
0 answers
622 views

Problem statement Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching ...
Jianmin Chen's user avatar
  • 2,486
2 votes
2 answers
327 views

You can perform the following operation on some string a: Capitalize zero or more of a's lowercase letters at some index i (i.e., make them uppercase). Delete all of the remaining lowercase ...
kumarmo2's user avatar
  • 261
5 votes
1 answer
322 views

The pusherr and poperr procedures maintain an internal stack as a lisp-like linked-list. It's a little slower than an earlier ...
luser droog's user avatar
  • 2,148
12 votes
2 answers
3k views

Update: I've implemented several of the features suggested below and packaged the improved code into a dedicated project: bash-cache. I display a number of expensive operations in my Bash prompt (e.g....
dimo414's user avatar
  • 415
6 votes
1 answer
643 views

Inspired by this question I wrote a memoized form of the collatz sequence calculator. The idea was to cache the sequence lengths for as many sequences as possible, from 0 to some value. I managed to (...
Der Kommissar's user avatar
  • 20.3k
3 votes
1 answer
5k views

I have been working on this problem for 3 days now. I wrote a piece of java code that works perfectly on my machine testing in Eclipse, but when I put it in Foobar, it either returns "Error(400) Bad ...
user avatar
5 votes
2 answers
735 views

I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem: $$P(n) = ...
phlummox's user avatar
  • 218
1 vote
1 answer
322 views

I shuffle a deck of cards(with an equal number of red and black cards) and start dealing them face up. After any card you can say “stop”, at which point I pay you $1 for every red card dealt and ...
tamraj_kilvish's user avatar
  • 135
4 votes
1 answer
258 views

Background Disclaimer: Skip if you are not interested in the background. The code is far far simpler than this. The problem is more about programming than math. Here is the definition of ...
rxu's user avatar
  • 141
3 votes
1 answer
623 views

This is kind of follow up of this question on stack overflow... I wrote the following to utilize memoization for functions that take a single parameter and return a value: ...
463035818_is_not_a_number's user avatar
  • 257
4 votes
2 answers
3k views

I wrote a Python module to learn about memoization, and I have some questions on what I did. How pythonic is this? Does it make a difference if I used a class attribute instead of a function attribute ...
BusyAnt's user avatar
  • 649

1
2