Two-player X and Y are playing Pots of Gold Game where pots of gold arranged in a line, each containing some gold coins. Both players will get an alternating chance in which the player can pick a pot from one of the ends of the line. The winner is the player who has a higher number of coins at the end. The objective is to … Continue reading Pots of Gold Game – Dynamic Programming
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. It consists of three rods and several disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. We have to obtain the same stack on the third … Continue reading Tower of Hanoi
Give n*n matrix find minimum cost required to reach from source to destination. Lets consider source is Array [0][0] and destination is Array [n-1][ n-1] the each elements also represent as cost You can only move down, right and diagonally lower elements from a given element. For example: The path of minimum cost is 1 ->5->1 so minimum cost to reach destination is 7. Dynamic … Continue reading Minimum cost to reach destination – Dynamic Programming
There are two strings source and destination. The goal of the problem is to convert source to destination by applying minimum edit operations on string str1. The edit operations are following – Insert Remove Replace For example: We need only one operation to replace char ‘e’ with char ‘o’ Using Recursion Using Dynamic Programming Continue reading Edit Distance Problem (Levenshtein distance) – Dynamic Programming
Given an array find a subsequence of a given array in which the array’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible Example: From below give array a longest increasing subsequence is This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not the … Continue reading Longest Increasing Subsequence Problem – Dynamic Programming
Find nth fibonacci number. The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … The next number is found by adding up the two numbers before it. Let F[i] be the ith fibonacci number Solution using Recursion Solution Dynamic Dynamic Programming Continue reading Fibonacci Numbers Problem – Dynamic Programming
Given a rod of size n and values of various sizes of rod. The problem is to cut the rod in such a way that the sum of values of the pieces is maximum. For e.g. will consider size of rod is length of arr here i.e.5. Size’s of the road are 1,2,3,4,5 respectively. So, we can cut the rod in various ways like To … Continue reading Rod Cutting Problem – Dynamic Programming
Given a set of positive integers and a value sum write program to determine if there is a subset of the given set with sum equal to given sum. For e.g. subset {4,12,18} has the sum 34 Solution Using Dynamic Programming Approach We will find whether if there is exists any subset of with provided sum 1 if it’s existed store it in array and … Continue reading Subset Sum Problem – Dynamic Programming
Given an array write C# program to find the sum of all the possible sub-arrays. For.e.g. int [] a = {4, 2, 1}; Output: Possible subarrays – {4}, {2}, {1}, {4, 2}, {2, 1}, {4, 2, 1} So, sum = 4+ 2+ 1 + 6 + 3 + 7 = 23 Solution Brute force approach Problem with below program is iterating over all pairs of … Continue reading Sum of all sub arrays in O(n) Time
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Given weights and values of n items, put these items … Continue reading Knapsack Problem
Given a sequence of n real numbers A(1) … A(n), program to find a contiguous subarray with the largest sum For example, var arr = new int[] {-2, 1,-3, 4,-1, 2, 1,-5, 4 }; the contiguous sub array with the largest sum is [4, −1, 2, 1], with sum 6. Solution Solution via iterating over all array elements repeatedly, try each key elements Execute above … Continue reading Maximum sub array problem – Kadane’s Algorithm
Question: A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of brackets it encloses … Continue reading Balanced Brackets – HackerRank Problem Solution
Question: You have a string of lowercase English alphabetic letters. You can perform two types of operations on the string: 1. Append a lowercase English alphabetic letter to the end of the string. 2. Delete the last character in the string. Performing this operation on an empty string results in an empty string. Given an integer,k , and two strings, s and t, determine whether or not you can convert to by performing exactly k … Continue reading Append and Delete – HackerRank Problem Solution
Question: Given a base- 10 integer, n, convert it to binary (base-2). Then find and print the base-10 integer denoting the maximum number of consecutive 1’s in n Input: Output: Explanation Sample Case 1:The binary representation of 5 is 101, so the maximum number of consecutive 1’s is 1. Here is original problem from HackerRank Answer: Continue reading Binary Numbers – HackerRank Problem solution
Question: You have been asked to help study the population of birds migrating across the continent. Each type of bird you are interested in will be identified by an integer value. Each time a particular kind of bird is spotted, its id number will be added to your array of sightings. You would like to be able to find out which type of bird is … Continue reading Migratory Birds – HackerRank Problem Solution
Question Sunny and Johnny like to pool their money and go to the ice cream parlor. Johnny never buys the same flavor that Sunny does. The only other rule they have is that they spend all of their money. Given a list of prices for the flavors of ice cream, select the two that will cost all of the money they have. For example, they … Continue reading Ice Cream Parlor – HackerRank Problem Solution
Question: Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary’s hikes start and end at sea level and each step up or down represents a 1 unit change in altitude. We define the following terms: A mountain is … Continue reading Counting Valleys – HackerRank Problem solution
Question: Consider a staircase of size n=4: Observe that its base and height are both equal to n , and the image is drawn using # symbols and spaces. The last line is not preceded by any spaces. Write a program that prints a staircase of size n input: Output: Here is actual problem HackerRank. Answer: Solution Logic Take variable which stores value of white space, initialize it with array … Continue reading Staircase – HackerRank Problem solution
Question: John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are. For example, there are n=7 socks with colors ar = [1,2,1,2,1,3,2]. There is one pair of color 1 and one of color 2 . There … Continue reading Sock Merchant – HackerRank Problem Solution
Question: You are given a string containing characters and only. Your task is to change it into a string such that there are no matching adjacent characters. To do this, you can delete zero or more characters in the string. Your task is to find the minimum number of required deletions. For example, given the string s=AABAAB, remove an A at positions 0 and 3 … Continue reading Alternating Characters – HackerRank Problem Solution
Question: Princess Peach is trapped in one of the four corners of a square grid. You are in the center of the grid and can move one step at a time in any of the four directions. Can you rescue the princess? Input format The first line contains an odd integer N (< 100) denoting the size of the grid. This is followed by an … Continue reading Bot Saves Princess – HackerRank Problem Solution
