All Questions
29 questions
12
votes
2
answers
640
views
Dynamic Programming: Fibonacci-like recurrence relation
This is a problem from my Introduction to Algorithms textbook.
Consider the infinite sequence of numbers An|n>0 = (1,1,3,4,8,11,...) defined recursively as follows.
$$
A_n = \left\{\begin{aligned}
&...
- 9,839
8
votes
5
answers
2k
views
Repeatedly partitioning an array equally as far as possible
I solved HackerRank Nikita and the Game. The implementation is correct as program passes all test cases.
Nikita just came up with a new array game. The rules are as follows:
Initially, ...
8
votes
2
answers
913
views
Quick Sum TopCoder (Brute Force solution)
Given a string of digits, find the minimum number of additions
required for the string to equal some target number. Each addition is
the equivalent of inserting a plus sign somewhere into the ...
8
votes
1
answer
2k
views
Assembly line scheduling
This is solution to the assembly line problem. Here is complete description, which is too big and verbose to re-describe. I apologize for the inconvenience of the hyperlink.
Note: I do understand ...
- 8,451
7
votes
2
answers
4k
views
Finding alternating sequence in a list of numbers
Please be brutal and treat this as me coding this up for an interview.
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between ...
- 2,236
6
votes
1
answer
3k
views
Coin change algorithm
I've implemented the coin change algorithm using Dynamic Programming and Greedy Algorithm w/ backtracking. The description is as follows:
Given an amount of change (n) list all of the possibilities ...
- 181
5
votes
2
answers
124
views
Calculate the rates at which users get stuck at each stage
I completed an algorithm problem just as a personal study, and I can't help but feel like my solution is a bit needlessly complicated, although I can't figure out a better way to do it. Here's the ...
- 151
5
votes
1
answer
573
views
Snakes and Ladders using a magic die
This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game.
...
- 51
4
votes
1
answer
164
views
Searching for an idiomatic Rust implementation of Minimum Edit Distance (LeetCode #72)
I am solving LeetCode Dynamic Programming challenges (this one is #72, at https://leetcode.com/problems/edit-distance).
Here below, I've implemented a Rust solution for the minimum edit distance ...
- 143
4
votes
2
answers
702
views
The Three-machine proportionate flow shop problem with unequal machine
As part of an Academic project I wrote the following code, according to the algorithm (verbal). When I checked the rest of the article I notice that the efficiency should be \$O(n^2)\$ and I wrote \$...
- 119
4
votes
2
answers
342
views
Returning all the LIS of given array of int
I have this assignment where I'm supposed to code an algorithm for finding the quantity of Longest Increasing Subsequences from an array of (different) integers and print them all.
I developed one ...
- 41
4
votes
2
answers
3k
views
Optimal matrix chain multiplication in Java
Preliminaries
Given two matrices
$$
A = \begin{pmatrix}
a_{11} & a_{12} & \dots & a_{1q} \\
a_{21} & a_{22} & \dots & a_{2q} \\
\vdots & \vdots & \ddots & \vdots \\
...
- 30.3k
3
votes
2
answers
833
views
Optimal burger-eating challenge
Little history to give context to the problem:
The Krusty-Burgers
Homer Simpson is a smart guy who likes to eat Krusty-Burgers, and it takes m minutes for Homer ...
- 401
3
votes
2
answers
1k
views
Counting the number of ways to decode a string
I am working on problem where I need to decode a string:
A message containing letters from A-Z is being encoded to numbers
using the following mapping:
'A' -> 1
'B' -> 2
...
'...
- 499
3
votes
1
answer
442
views
Find the maximum possible summation of differences of consecutive elements
Array A contains the elements, \$A_1,A_2, \ldots, A_N\$.
And array B contains the elements, \$B_1,B_2, \ldots, B_N\$.
There is a relationship between \$A_i\$ and \$B_i\$: any element \$A_i\$ ...
- 261