Skip to main content

Posts

Showing posts with the label dynamic programming

Full Stack Developer Without Degree: How to Become One

By
If you're interested in becoming a Full Stack Developer without a degree, we've put together some tips and resources to help you get started. Learn the Fundamentals The first step to becoming a Full Stack Developer is to learn the fundamentals of coding. You can start with HTML, CSS, and JavaScript, which are the building blocks of web development. There are plenty of free resources available online, such as Codecademy and FreeCodeCamp, which offer interactive courses that teach you the basics of web development. Once you have a solid understanding of the basics, you can move on to more advanced topics such as back-end development, databases, and frameworks. You can learn these topics through online courses or by working on personal projects. Build a Portfolio One of the most important things you can do as a Full Stack Developer is to build a portfolio. Your portfolio should showcase your skills and experience and demonstrate your ability to build real-world applications. You c...
Post a Comment
Read more

Stock buy and sell (DSA)

By
  Problem Statement :(👈click here for GFG) The cost of stock on each day is given in an array  A [] of size  N . Find all the segments of days on which you buy and sell the stock so that in between those days  for which profit can be generated . Note:   Since there can be multiple solutions ,  the driver code will print 1 if your answer is correct, otherwise, it will return 0. In case there's no profit the driver code will print the string " No Profit " for a correct solution. Example 1: Input: N = 7 A[] = {100,180,260,310,40,535,695} Output: 1 Explanation: One possible solution is (0 3) (4 6) We can buy stock on day 0, and sell it on 3rd day, which will give us maximum profit. Now, we buy stock on day 4 and sell it on day 6. Example 2: Input: N = 5 A[] = {4,2,2,2,4} Output: 1 Explanation: There are multiple possible solutions. one of them is (3 4) We can buy stock on day 3, and sell it on 4th day, which will give us maximum profit. Your Task...
Post a Comment
Read more

0 - 1 Knapsack Problem (DSA)

By
  Problem Statement :(👈click here for GFG) You are given weights and values of  N  items, put these items in a knapsack of capacity  W  to get the maximum total value in the knapsack. Note that we have only  one quantity of each item . In other words, given two integer arrays  val[0..N-1]  and  wt[0..N-1]  which represent values and weights associated with  N  items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of  val[]  such that sum of the weights of this subset is smaller than or equal to  W.  You cannot break an item,  either pick the complete item or dont pick it (0-1 property) . Example 1: Input: N = 3 W = 4 values[] = {1,2,3} weight[] = {4,5,1} Output: 3 Example 2: Input: N = 3 W = 3 values[] = {1,2,3} weight[] = {4,5,6} Output: 0 Your Task: Complete the function knapSack() which takes maximum capacity W, weight array wt[], value ar...
Post a Comment
Read more

Trapping Rain Water (DSA)

By
  Problem Statement: (👈click here for GFG) Given an array  arr[]  of  N  non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.    Example 1: Input: N = 6 arr[] = {3,0,0,2,0,4} Output: 10 Explanation: Example 2: Input: N = 4 arr[] = {7,4,0,9} Output: 10 Explanation: Water trapped by above block of height 4 is 3 units and above block of height 0 is 7 units. So, the total unit of water trapped is 10 units. Example 3: Input: N = 3 arr[] = {6,9,9} Output: 0 Explanation: No water will be trapped. Your Task: You don't need to read input or print anything. The task is to complete the function trappingWater() which takes arr[] and N as input parameters and returns the total amount of water that can be trapped. Expected Time Complexity: O(N) Expected Auxiliary Space: O(N) Constraints: 3 < N < 106 0 < Ai < 108 Solut...
Post a Comment
Read more

Kadane's Algorithm (DSA)

By
Problem statement :(👈click here for GFG) Given an array   Arr[]  of   N   integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum. Example 1: Input: N = 5 Arr[] = {1,2,3,-2,5} Output: 9 Explanation: Max subarray sum is 9 of elements (1, 2, 3, -2, 5) which is a contiguous subarray. Example 2: Input: N = 4 Arr[] = {-1,-2,-3,-4} Output: -1 Explanation: Max subarray sum is -1 of element (-1) Your Task: You don't need to read input or print anything. The task is to complete the function  maxSubarraySum () which takes Arr[] and N as input parameters and returns the sum of subarray with maximum sum. Expected Time Complexity:  O(N) Expected Auxiliary Space:  O(1) Constraints: 1 ≤ N ≤ 10 6 -10 7  ≤ A[i] ≤ 10 7 Solution: One of the efficient approaches to solve this problem in O(N) time complexity and O(1) space complexity is to use Kadane's algorithm. Algorithm: Initialize tw...
Post a Comment
Read more