Problem Of The Day
"Asteroid Collision"
Solve the problem to win points
We are given an integer array asteroids of size N representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are of same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input:
N = 3
asteroids[ ] = {3, 5, -3}
Output: {3, 5}
Explanation: The asteroid 5 and -3 collide resulting in 5. The 5 and 3 never collide.
Example 2:
Input:
N = 2
asteroids[ ] = {10, -10}
Output: { }
Explanation: The asteroid -10 and 10 collide exploding each other.
Your Task:
You don't need to read input or print anything. Your task is to complete the function asteroid Collision() which takes the array of integers asteroids and N as parameters and returns the state of asteroids after all collisions.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/asteroid-collision/1
Powered by hirist.com
"Asteroid Collision"
Solve the problem to win points
We are given an integer array asteroids of size N representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are of same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input:
N = 3
asteroids[ ] = {3, 5, -3}
Output: {3, 5}
Explanation: The asteroid 5 and -3 collide resulting in 5. The 5 and 3 never collide.
Example 2:
Input:
N = 2
asteroids[ ] = {10, -10}
Output: { }
Explanation: The asteroid -10 and 10 collide exploding each other.
Your Task:
You don't need to read input or print anything. Your task is to complete the function asteroid Collision() which takes the array of integers asteroids and N as parameters and returns the state of asteroids after all collisions.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/asteroid-collision/1
Powered by hirist.com
practice.geeksforgeeks.org
Asteroid Collision | Practice | GeeksforGeeks
We are given an integer array asteroids of size N representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each astero
👍1
Must Do DSA Topics Day 76
Graph
Topological Sorting : Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.
Learn more : http://bit.ly/3IaMcPY
All topological sorts of a Directed Acyclic Graph : In a Directed acyclic graph many a times we can have vertices which are unrelated to each other because of which we can order them in many ways.
Learn more : https://bit.ly/3YTeggK
Kahn’s Algorithm for Topological Sorting : In this article, we will see another way to find the linear ordering of vertices in a directed acyclic graph (DAG).
Learn more : https://bit.ly/3IaMoia
Graph
Topological Sorting : Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.
Learn more : http://bit.ly/3IaMcPY
All topological sorts of a Directed Acyclic Graph : In a Directed acyclic graph many a times we can have vertices which are unrelated to each other because of which we can order them in many ways.
Learn more : https://bit.ly/3YTeggK
Kahn’s Algorithm for Topological Sorting : In this article, we will see another way to find the linear ordering of vertices in a directed acyclic graph (DAG).
Learn more : https://bit.ly/3IaMoia
👍1
Problem Of The Day
"Single valued subtree"
Solve the problem to win points
Given a binary tree, count the number of Single Valued Subtrees. A Single Valued Subtree is one in which all the nodes have same value.
Example 1
Input :
5
/ \
1 5
/ \ \
5 5 5
Output : 4
Explanation :
There are 4 subtrees with single values.
Example 2:
Input:
5
/ \
4 5
/ \ \
4 4 5
Output: 5
Explanation:
There are five subtrees with single values.
Your task :
You don't have to read input or print anything. Your task is to complete the function singlevalued() which takes the root of the tree as input and returns the count of single valued subtrees.
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(n)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/single-valued-subtree/1
Powered by hirist.com
"Single valued subtree"
Solve the problem to win points
Given a binary tree, count the number of Single Valued Subtrees. A Single Valued Subtree is one in which all the nodes have same value.
Example 1
Input :
5
/ \
1 5
/ \ \
5 5 5
Output : 4
Explanation :
There are 4 subtrees with single values.
Example 2:
Input:
5
/ \
4 5
/ \ \
4 4 5
Output: 5
Explanation:
There are five subtrees with single values.
Your task :
You don't have to read input or print anything. Your task is to complete the function singlevalued() which takes the root of the tree as input and returns the count of single valued subtrees.
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(n)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/single-valued-subtree/1
Powered by hirist.com
practice.geeksforgeeks.org
Single valued subtree | Practice | GeeksforGeeks
Given a binary tree, count the number of Single Valued Subtrees. A Single Valued Subtree is one in which all the nodes have same value.
Example 1
Input :
5
/ \
1 5
/ \ \
Example 1
Input :
5
/ \
1 5
/ \ \
👍3
Must Do DSA Topics Day 77
Graph
Find length of the largest region in Boolean Matrix : Consider a matrix, where each cell contains either a ‘0’ or a ‘1’, and any cell containing a 1 is called a filled cell.
Learn more : https://bit.ly/3YVVnd4
Count number of trees in a forest : Given n nodes of a forest (collection of trees), find the number of trees in the forest.
Learn more : https://bit.ly/3vrdx8R
A Peterson Graph Problem : Let’s consider a walk W in graph G, which consists of L vertices W1, W2, …, WL. A string S of L letters ‘A’ – ‘E’ is realized by walking W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.
Learn more : https://bit.ly/3GsEz6b
Get access to all the topics of Graph : https://www.geeksforgeeks.org/greedy-algorithms/?ref=gcse
Graph
Find length of the largest region in Boolean Matrix : Consider a matrix, where each cell contains either a ‘0’ or a ‘1’, and any cell containing a 1 is called a filled cell.
Learn more : https://bit.ly/3YVVnd4
Count number of trees in a forest : Given n nodes of a forest (collection of trees), find the number of trees in the forest.
Learn more : https://bit.ly/3vrdx8R
A Peterson Graph Problem : Let’s consider a walk W in graph G, which consists of L vertices W1, W2, …, WL. A string S of L letters ‘A’ – ‘E’ is realized by walking W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.
Learn more : https://bit.ly/3GsEz6b
Get access to all the topics of Graph : https://www.geeksforgeeks.org/greedy-algorithms/?ref=gcse
Problem Of The Day
"Find minimum number of Laptops required"
Solve the problem to win points
There are N jobs and the start and finish time of the jobs are given in arrays start[] and end[] respectively. Each job requires one laptop and laptops can't be shared. Find the minimum number of laptops required given that you can give your laptop to someone else when you are not doing your job.
Example 1:
Input:
N = 3
start[] = {1, 2, 3}
end[] = {4, 4, 6}
Output:
3
Explanation:
We can clearly see that everyone's supposed to
be doing their job at time 3. So, 3 laptops
will be required at minimum.
Example 2:
Input:
N = 3
start[] = {1, 5, 2}
end[] = {2, 6, 3}
Output :
1
Explanation:
All jobs can be done using 1 laptop only.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minLaptops() which takes an integer N and two arrays start and end denoting starting and ending time of N jobs and returns minimum laptops required.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/af49b143a4ead583e943ca6176fbd7ea55b121ae/1
Powered by hirist.com
"Find minimum number of Laptops required"
Solve the problem to win points
There are N jobs and the start and finish time of the jobs are given in arrays start[] and end[] respectively. Each job requires one laptop and laptops can't be shared. Find the minimum number of laptops required given that you can give your laptop to someone else when you are not doing your job.
Example 1:
Input:
N = 3
start[] = {1, 2, 3}
end[] = {4, 4, 6}
Output:
3
Explanation:
We can clearly see that everyone's supposed to
be doing their job at time 3. So, 3 laptops
will be required at minimum.
Example 2:
Input:
N = 3
start[] = {1, 5, 2}
end[] = {2, 6, 3}
Output :
1
Explanation:
All jobs can be done using 1 laptop only.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minLaptops() which takes an integer N and two arrays start and end denoting starting and ending time of N jobs and returns minimum laptops required.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/af49b143a4ead583e943ca6176fbd7ea55b121ae/1
Powered by hirist.com
practice.geeksforgeeks.org
Find minimum number of Laptops required | Practice | GeeksforGeeks
There are N jobs and the start and finish time of the jobs are given in arrays start[] and end[] respectively. Each job requires one laptop and laptops can't be shared. Find the minimum number of laptops required given that you can give your
Must Do DSA Topics Day 78
Greedy
Activity Selection Problem : If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming.
Learn more : https://bit.ly/3G9PXm2
Egyptian Fraction : A fraction is unit fraction if numerator is 1 and denominator is a positive integer, for example 1/3 is a unit fraction. Such a representation is called Egyptian Fraction as it was used by ancient Egyptians.
Learn more : https://bit.ly/3vuHlSg
Job Sequencing Problem : Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline.
Learn more : https://bit.ly/3VCmXt0
Greedy
Activity Selection Problem : If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming.
Learn more : https://bit.ly/3G9PXm2
Egyptian Fraction : A fraction is unit fraction if numerator is 1 and denominator is a positive integer, for example 1/3 is a unit fraction. Such a representation is called Egyptian Fraction as it was used by ancient Egyptians.
Learn more : https://bit.ly/3vuHlSg
Job Sequencing Problem : Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline.
Learn more : https://bit.ly/3VCmXt0
👍3
Problem Of The Day
"Count even length"
Solve the problem to win points
Given a number n, find count of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.
The anwer can be very large. So, you have to return answer modulo 109+7.
Example:
Input: n = 2
Output: 6
Explanation: There are 6 sequences of length
2*n, the sequences are 0101, 0110, 1010, 1001,
0000 and 1111.
Example:
Input: n = 1
Output: 2
Explanation: There are 2 sequence of length
2*n, the sequence are 00 and 11.
Your Task:
You don't need to read or print anyhting. Your task is to complete the function compute_value() which takes n as input parameter and returns count of all binary sequence of length 2*n such that sum of first n bits is same as sum of last n bits modulo 109 + 7.
Expected Time Complexity: O(n * log(n))
Expected Space Complexity: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/count-even-length1907/1
Powered by hirist.com
"Count even length"
Solve the problem to win points
Given a number n, find count of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.
The anwer can be very large. So, you have to return answer modulo 109+7.
Example:
Input: n = 2
Output: 6
Explanation: There are 6 sequences of length
2*n, the sequences are 0101, 0110, 1010, 1001,
0000 and 1111.
Example:
Input: n = 1
Output: 2
Explanation: There are 2 sequence of length
2*n, the sequence are 00 and 11.
Your Task:
You don't need to read or print anyhting. Your task is to complete the function compute_value() which takes n as input parameter and returns count of all binary sequence of length 2*n such that sum of first n bits is same as sum of last n bits modulo 109 + 7.
Expected Time Complexity: O(n * log(n))
Expected Space Complexity: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/count-even-length1907/1
Powered by hirist.com
practice.geeksforgeeks.org
Count even length | Practice | GeeksforGeeks
Given a number n, find count of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.
The anwer can be very large. So, you have to return answer modulo 109+7.
Example:
Input: n = 2
Output: 6
Explana
The anwer can be very large. So, you have to return answer modulo 109+7.
Example:
Input: n = 2
Output: 6
Explana
Must Do DSA Topics Day 79
Greedy
Huffman Coding : Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters.
Learn more : https://bit.ly/3Ze4UMO
Efficient Huffman Coding for sorted input : We recommend to read following post as a prerequisite for this.
Greedy Algorithms | Set 3 (Huffman Coding)
Time complexity of the algorithm discussed in above post is O(nLogn).
Learn more : https://bit.ly/3WNWgCC
Huffman Decoding : We have discussed Huffman Encoding in a previous post. In this post, decoding is discussed.
Learn more : https://bit.ly/3G7Em75
Greedy
Huffman Coding : Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters.
Learn more : https://bit.ly/3Ze4UMO
Efficient Huffman Coding for sorted input : We recommend to read following post as a prerequisite for this.
Greedy Algorithms | Set 3 (Huffman Coding)
Time complexity of the algorithm discussed in above post is O(nLogn).
Learn more : https://bit.ly/3WNWgCC
Huffman Decoding : We have discussed Huffman Encoding in a previous post. In this post, decoding is discussed.
Learn more : https://bit.ly/3G7Em75
Problem Of The Day
"Maximum Value"
Solve the problem to win points
Given a binary tree, find the largest value in each level.
Example 1:
Input:
1
/ \
2 3
Output:
1 3
Explanation:
At 0 level, values of nodes are {1}
Maximum value is 1
At 1 level, values of nodes are {2,3}
Maximum value is 3
Example 2:
Input:
4
/ \
9 2
/ \ \
3 5 7
Output:
4 9 7
Explanation:
At 0 level, values of nodes are {4}
Maximum value is 4
At 1 level, values of nodes are {9,2}
Maximum value is 9
At 2 level, values of nodes are {3,5,7}
Maximum value is 7
Your Task:
You don't need to read input or print anything.Your task is to complete the function maximumValue() that takes root node as input parameter and returns a list of integers containing the maximum value at each level. The size of the resultant list should be equal to the height of the binary tree and result[i] should store the maximum value at level i.
Expected Time Complexity: O(N), where N is the number of nodes.
Expected Auxiliary Space: O(H), where H is the height of binary tree.
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/ec277982aea7239b550b28421e00acbb1ea03d2c/1
Powered by hirist.com
"Maximum Value"
Solve the problem to win points
Given a binary tree, find the largest value in each level.
Example 1:
Input:
1
/ \
2 3
Output:
1 3
Explanation:
At 0 level, values of nodes are {1}
Maximum value is 1
At 1 level, values of nodes are {2,3}
Maximum value is 3
Example 2:
Input:
4
/ \
9 2
/ \ \
3 5 7
Output:
4 9 7
Explanation:
At 0 level, values of nodes are {4}
Maximum value is 4
At 1 level, values of nodes are {9,2}
Maximum value is 9
At 2 level, values of nodes are {3,5,7}
Maximum value is 7
Your Task:
You don't need to read input or print anything.Your task is to complete the function maximumValue() that takes root node as input parameter and returns a list of integers containing the maximum value at each level. The size of the resultant list should be equal to the height of the binary tree and result[i] should store the maximum value at level i.
Expected Time Complexity: O(N), where N is the number of nodes.
Expected Auxiliary Space: O(H), where H is the height of binary tree.
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/ec277982aea7239b550b28421e00acbb1ea03d2c/1
Powered by hirist.com
practice.geeksforgeeks.org
Maximum Value | Practice | GeeksforGeeks
Given a binary tree, find the largest value in each level.
Example 1:
Input:
1
/ \
2 3
Output:
1 3
Explanation:
At 0 level, values of nodes are {1}
Maximum value is 1
At 1 level, values of n
Example 1:
Input:
1
/ \
2 3
Output:
1 3
Explanation:
At 0 level, values of nodes are {1}
Maximum value is 1
At 1 level, values of n
👍1
Must Do DSA Topics Day 80
Greedy
Dial’s Algorithm : Dijkstra’s shortest path algorithm runs in O(Elog V) time when implemented with adjacency list representation (See C implementation and STL based C++ implementations for details).
Learn more : https://bit.ly/3Cgh1ir
Dijkstra’s Algorithm for Adjacency List Representation : We have discussed Dijkstra’s algorithm and its implementation for adjacency matrix representation of graphs. The time complexity for the matrix representation is O(V^2). In this post, O(ELogV) algorithm for adjacency list representation is discussed.
Learn more : https://bit.ly/3Qc0jGS
Prim’s MST for adjacency list representation : The idea is to traverse all vertices of graph using BFS and use a Min Heap to store the vertices not yet included in MST. Min Heap is used as a priority queue to get the minimum weight edge from the cut.
Learn more : https://bit.ly/3G6Nb0R
Greedy
Dial’s Algorithm : Dijkstra’s shortest path algorithm runs in O(Elog V) time when implemented with adjacency list representation (See C implementation and STL based C++ implementations for details).
Learn more : https://bit.ly/3Cgh1ir
Dijkstra’s Algorithm for Adjacency List Representation : We have discussed Dijkstra’s algorithm and its implementation for adjacency matrix representation of graphs. The time complexity for the matrix representation is O(V^2). In this post, O(ELogV) algorithm for adjacency list representation is discussed.
Learn more : https://bit.ly/3Qc0jGS
Prim’s MST for adjacency list representation : The idea is to traverse all vertices of graph using BFS and use a Min Heap to store the vertices not yet included in MST. Min Heap is used as a priority queue to get the minimum weight edge from the cut.
Learn more : https://bit.ly/3G6Nb0R
Hey Freshers! You no longer have to scroll through endless posts to find an opportunity. We got your back.😃
Unveiling your New Year Gift with the details of the companies that are hiring freshers in the 'Mega Job-A-Thon 2023' hiring challenge | 4th Jan.✨🙌:
Click on the following link to get more details- https://bit.ly/3PMA89y
Unveiling your New Year Gift with the details of the companies that are hiring freshers in the 'Mega Job-A-Thon 2023' hiring challenge | 4th Jan.✨🙌:
Click on the following link to get more details- https://bit.ly/3PMA89y
👍3
Looking for a better opportunity to switch? Here we are with a range of amazing opportunities.😌😃
Unveiling your New Year Gift with the details of the companies that are hiring experienced candidates in the 'Mega Job-A-Thon 2023' hiring challenge | 5th Jan.⭐🙌:
Click on the following link for more details- https://bit.ly/3Vv22Ip
Unveiling your New Year Gift with the details of the companies that are hiring experienced candidates in the 'Mega Job-A-Thon 2023' hiring challenge | 5th Jan.⭐🙌:
Click on the following link for more details- https://bit.ly/3Vv22Ip
Problem Of The Day
"Minimize number of Students to be removed"
Solve the problem to win points
N Students of different heights are attending an assembly. The heights of the students are represented by an array H[]. The problem is that if a student has less or equal height than the student standing in front of him, then he/she cannot see the assembly. Find the minimum number of students to be removed such that maximum possible number of students can see the assembly.
Example 1:
Input:
N = 6
H[] = {9, 1, 2, 3, 1, 5}
Output:
2
Explanation:
We can remove the students at 0 and 4th index.
which will leave the students with heights
1,2,3, and 5.
Example 2:
Input:
N = 3
H[] = {1, 2, 3}
Output :
0
Explanation:
All of the students are able to see the
assembly without removing anyone.
Your Task:
You don't need to read input or print anything. Your task is to complete the function removeStudents() which takes an integer N and an array H[ ] of size N as input parameters and returns the minimum number of students required to be removed to enable maximum number of students to see the assembly.
Expected Time Complexity: O(N logN)
Expected Auxiliary Space: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/7d0fa4007b8eabadc404fcc9fa917aa52982aa96/1
Powered by hirist.com
"Minimize number of Students to be removed"
Solve the problem to win points
N Students of different heights are attending an assembly. The heights of the students are represented by an array H[]. The problem is that if a student has less or equal height than the student standing in front of him, then he/she cannot see the assembly. Find the minimum number of students to be removed such that maximum possible number of students can see the assembly.
Example 1:
Input:
N = 6
H[] = {9, 1, 2, 3, 1, 5}
Output:
2
Explanation:
We can remove the students at 0 and 4th index.
which will leave the students with heights
1,2,3, and 5.
Example 2:
Input:
N = 3
H[] = {1, 2, 3}
Output :
0
Explanation:
All of the students are able to see the
assembly without removing anyone.
Your Task:
You don't need to read input or print anything. Your task is to complete the function removeStudents() which takes an integer N and an array H[ ] of size N as input parameters and returns the minimum number of students required to be removed to enable maximum number of students to see the assembly.
Expected Time Complexity: O(N logN)
Expected Auxiliary Space: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/7d0fa4007b8eabadc404fcc9fa917aa52982aa96/1
Powered by hirist.com
practice.geeksforgeeks.org
Minimize number of Students to be removed | Practice | GeeksforGeeks
N Students of different heights are attending an assembly. The heights of the students are represented by an array H[]. The problem is that if a student has less or equal height than the student standing in front of him, then he/she cannot see the as
👍2
Must Do DSA Topics Day 81
Greedy
Minimum product subset of an array : Given array a, we have to find the minimum product possible with the subset of elements present in the array. The minimum product can be a single element also.
Learn more : https://bit.ly/3X4U1Lr
Maximum product subset of an array : Given an array a, we have to find the maximum product possible with the subset of elements present in the array. The maximum product can be a single element also.
Learn more : https://bit.ly/3VA1Ebq
Maximize the sum of arr[i]*i : Given an Array of N integers, the task is to maximize the value of the product of each array element with their corresponding indices by rearranging the array.
Learn more : https://bit.ly/3WX2yQk
Greedy
Minimum product subset of an array : Given array a, we have to find the minimum product possible with the subset of elements present in the array. The minimum product can be a single element also.
Learn more : https://bit.ly/3X4U1Lr
Maximum product subset of an array : Given an array a, we have to find the maximum product possible with the subset of elements present in the array. The maximum product can be a single element also.
Learn more : https://bit.ly/3VA1Ebq
Maximize the sum of arr[i]*i : Given an Array of N integers, the task is to maximize the value of the product of each array element with their corresponding indices by rearranging the array.
Learn more : https://bit.ly/3WX2yQk
Your dream job is just a click away. Book your calendar | 4th and 5th January.🙌
Don't miss your chance!✨
Register for the hiring challenge Mega Job-A-Thon 2023. Get more details and register using the following link- http://bit.ly/3hIK9aS
Don't miss your chance!✨
Register for the hiring challenge Mega Job-A-Thon 2023. Get more details and register using the following link- http://bit.ly/3hIK9aS
👍2
Problem Of The Day
"Maximum Profit By Choosing A Subset Of Intervals"
Solve the problem to win points
Given a list intervals of n intervals, the ith element [s, e, p] denotes the starting point s, ending point e, and the profit p earned by choosing the ith interval. Find the maximum profit one can achieve by choosing a subset of non-overlapping intervals.
Two intervals [s1, e1, p1] and [s2, e2, p2] are said to be non-overlapping if [e1 <= s2] and [s1 < s2].
Example 1:
Input:
n = 3
intervals = {
{1, 2, 4},
{1, 5, 7},
{2, 4, 4}
}
Output:
8
Explanation:
One can choose intervals [1, 2, 4] and [2, 4, 4] for a
profit of 8.
Example 2:
Input:
n = 3
intervals = {
{1, 4, 4},
{2, 3, 7},
{2, 3, 4}
}
Output:
7
Explanation:
One can choose interval [2, 3, 7] for a profit of 7.
Your Task:
You don't need to print or output anything. Complete the function maximum_profit() which takes an integer n and a 2D integer array intervals and returns an integer, denoting the maximum profit which one can get by choosing the non-overlapping intervals.
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/649205908e04ac00f303626fa845261318adfa8f/1
Powered by hirist.com
"Maximum Profit By Choosing A Subset Of Intervals"
Solve the problem to win points
Given a list intervals of n intervals, the ith element [s, e, p] denotes the starting point s, ending point e, and the profit p earned by choosing the ith interval. Find the maximum profit one can achieve by choosing a subset of non-overlapping intervals.
Two intervals [s1, e1, p1] and [s2, e2, p2] are said to be non-overlapping if [e1 <= s2] and [s1 < s2].
Example 1:
Input:
n = 3
intervals = {
{1, 2, 4},
{1, 5, 7},
{2, 4, 4}
}
Output:
8
Explanation:
One can choose intervals [1, 2, 4] and [2, 4, 4] for a
profit of 8.
Example 2:
Input:
n = 3
intervals = {
{1, 4, 4},
{2, 3, 7},
{2, 3, 4}
}
Output:
7
Explanation:
One can choose interval [2, 3, 7] for a profit of 7.
Your Task:
You don't need to print or output anything. Complete the function maximum_profit() which takes an integer n and a 2D integer array intervals and returns an integer, denoting the maximum profit which one can get by choosing the non-overlapping intervals.
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/649205908e04ac00f303626fa845261318adfa8f/1
Powered by hirist.com
practice.geeksforgeeks.org
Maximum Profit By Choosing A Subset Of Intervals | Practice | GeeksforGeeks
Given a list intervals of n intervals, the ith element [s, e, p] denotes the starting point s, ending point e, and the profit p earned by choosing the ith interval. Find the maximu
Must Do DSA Topics Day 82
Greedy
First Fit algorithm in Memory Management : In the first fit, the partition is allocated which is first sufficient from the top of Main Memory.
Learn more : https://bit.ly/3WUlLSO
Best Fit algorithm in Memory Management : Best fit allocates the process to a partition which is the smallest sufficient partition among the free available partitions.
Learn more : https://bit.ly/3Z8eNvi
Worst Fit algorithm in Memory Management : Worst Fit allocates a process to the partition which is largest sufficient among the freely available partitions available in the main memory.
Learn more : https://bit.ly/3GzFFNv
Greedy
First Fit algorithm in Memory Management : In the first fit, the partition is allocated which is first sufficient from the top of Main Memory.
Learn more : https://bit.ly/3WUlLSO
Best Fit algorithm in Memory Management : Best fit allocates the process to a partition which is the smallest sufficient partition among the free available partitions.
Learn more : https://bit.ly/3Z8eNvi
Worst Fit algorithm in Memory Management : Worst Fit allocates a process to the partition which is largest sufficient among the freely available partitions available in the main memory.
Learn more : https://bit.ly/3GzFFNv
Get! Set! Go!!!🙌
Finally the most awaited Mega Job-A-Thon 2023 has begun for freshers/interns. Plus, just a day to go for experienced candidates.😃
Stop waiting and grab the best opportunities now.🤌
Hurry up!
Click on the following link to register - http://bit.ly/3hIK9aS
Finally the most awaited Mega Job-A-Thon 2023 has begun for freshers/interns. Plus, just a day to go for experienced candidates.😃
Stop waiting and grab the best opportunities now.🤌
Hurry up!
Click on the following link to register - http://bit.ly/3hIK9aS
👍1
Problem Of The Day
"Find the longest string"
Solve the problem to win points
Given an array of strings arr[]. You have to find the longest string which is lexicographically smallest and also all of its prefix strings are already present in the array.
Example 1:
Input: ab a abc abd
Output: abc
Explanation: We can see that length of the longest
string is 3. And there are two string "abc" and "abd"
of length 3. But for string "abc" , all of its prefix
"a" "ab" "abc" are present in the array. So the
output is "abc".
Example 2:
Input: ab a aa abd abc abda abdd abde abdab
Output: abdab
Explanation: We can see that each string is fulfilling
the condition. For each string, all of its prefix
are present in the array.And "abdab" is the longest
string among them. So the ouput is "abdab".
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestString() which takes the array arr[] as input parameter and returns the longest string which is also lexicographically smallest.And if there is no such string return empty string.
Expected Time Complexity: O(NlogN)
Expected Space Complexity: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/8d157f11af5416087251513cfc38ffc4d23be308/1
Powered by hirist.com
"Find the longest string"
Solve the problem to win points
Given an array of strings arr[]. You have to find the longest string which is lexicographically smallest and also all of its prefix strings are already present in the array.
Example 1:
Input: ab a abc abd
Output: abc
Explanation: We can see that length of the longest
string is 3. And there are two string "abc" and "abd"
of length 3. But for string "abc" , all of its prefix
"a" "ab" "abc" are present in the array. So the
output is "abc".
Example 2:
Input: ab a aa abd abc abda abdd abde abdab
Output: abdab
Explanation: We can see that each string is fulfilling
the condition. For each string, all of its prefix
are present in the array.And "abdab" is the longest
string among them. So the ouput is "abdab".
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestString() which takes the array arr[] as input parameter and returns the longest string which is also lexicographically smallest.And if there is no such string return empty string.
Expected Time Complexity: O(NlogN)
Expected Space Complexity: O(N)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/8d157f11af5416087251513cfc38ffc4d23be308/1
Powered by hirist.com
👍1