Dynamic programming interview questions

Count of binary strings without consecutive 1’s

Given a positive integer N, find the count of distinct binary strings of length N that have no consecutive 1’s. For example, Input: N = 2 Output: 3. Explanation: There ...
Read More

Optimal Binary Search Trees

BSTs are used to organize a set of search keys for fast access: the tree maintains the keys in-order so that comparison with the query at any node either results ...
Read More

Largest sum of non-adjacent numbers

Given an array of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.For example, Input: [2, 4, 6, 2, 5] Output: ...
Read More

Is subsequence

Given a string s and a string t, check if s is subsequence of t. A subsequence of a string is a new string which is formed from the original ...
Read More

Cutting rods problem

Given a rod of length ‘n’ units and list of prices of pieces of lengths ‘1’ to ‘n’, the problem is to determine the maximum value that can be obtained ...
Read More

Digit sum of n-digit numbers

Find the count of n-digit numbers whose sum of digits is equal to given sum s. For example, Input: n=2 and s=5 Output: 14, 23, 32, 41, 50 Explanation: we ...
Read More

Super Egg drop problem

Egg dropping problem goes like given n eggs and f floors, our task is to find the minimum number of trials required to find the highest floor from which it ...
Read More

Climbing the staircase

We have to climb a staircase and it takes N steps to reach the top. Given that we can climb 1 or 2 steps at a time, in how many ...
Read More

Fibonacci series and dynamic programming

Find nth Fibonacci number Given a Fibonacci series: 1, 1, 2, 3, 5, 8, 13 ... which is defined as fib(n) = fib(n-1) + fib(n-2), find Nth number in this ...
Read More

Fill 4xN wall with 4×1 and 1×4 bricks

Fill 4xN wall with 4x1 and 1x4 bricks There is a wall with 4 x N dimensions and we have a brick with 4 x 1 dimension. We have to ...
Read More
Loading...