Dynamic programming interview questions

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

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

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

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

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

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

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

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

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 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