Must Do DSA Topics day 35
Stack
Design a stack with operations on middle element : Please note that we need to find and delete the middle element. Deleting an element from the middle is not O(1) for the array. Also, we may need to move the middle pointer up when we push an element and move down when we pop().
Learn more : http://bit.ly/3EXrgKi
How to efficiently implement k stacks in a single array : Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing elements.
Learn more : http://bit.ly/3OxgtK0
How to create mergeable stack : We can use a linked list with two pointers, one pointer to the first node (also used as a top when elements are added and removed from the beginning). The other pointer is needed for the last node so that we can quickly link the linked list of s2 at the end of s1.
Learn more : http://bit.ly/3Vp1nZ9
Stack
Design a stack with operations on middle element : Please note that we need to find and delete the middle element. Deleting an element from the middle is not O(1) for the array. Also, we may need to move the middle pointer up when we push an element and move down when we pop().
Learn more : http://bit.ly/3EXrgKi
How to efficiently implement k stacks in a single array : Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing elements.
Learn more : http://bit.ly/3OxgtK0
How to create mergeable stack : We can use a linked list with two pointers, one pointer to the first node (also used as a top when elements are added and removed from the beginning). The other pointer is needed for the last node so that we can quickly link the linked list of s2 at the end of s1.
Learn more : http://bit.ly/3Vp1nZ9
👍1
Black Friday Sale is Live📢📢
Go big on savings with 25% on all courses plus assured cashbacks!
Grab all you can, till Saturday midnight!✨✨
Click on the following link-
https://practice.geeksforgeeks.org/courses?utm_source=telegram&utm_medium=marketingteam_gfgmain&utm_campaign=blackfriday22
Go big on savings with 25% on all courses plus assured cashbacks!
Grab all you can, till Saturday midnight!✨✨
Click on the following link-
https://practice.geeksforgeeks.org/courses?utm_source=telegram&utm_medium=marketingteam_gfgmain&utm_campaign=blackfriday22
Problem Of The Day
"Construct Binary Tree from String with bracket representation"
Solve the problem to win points
Construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the roots value and a pair of parenthesis contains a child binary tree with the same structure. Always start to construct the left child node of the parent first if it exists.
Example 1:
Input: "1(2)(3)"
Output: 2 1 3
Explanation:
1
/ \
2 3
Explanation: first pair of parenthesis contains
left subtree and second one contains the right
subtree. Inorder of above tree is "2 1 3".
Example 2:
Input: "4(2(3)(1))(6(5))"
Output: 3 2 1 4 5 6
Explanation:
4
/ \
2 6
/ \ /
3 1 5
Your Task:
You don't need to read input or print anything. Your task is to complete the function treeFromString() which takes a string str as input parameter and returns the root node of the tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Solve the problem and submit your answer here: https://practice.geeksforgeeks.org/problems/construct-binary-tree-from-string-with-bracket-representation/1
"Construct Binary Tree from String with bracket representation"
Solve the problem to win points
Construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the roots value and a pair of parenthesis contains a child binary tree with the same structure. Always start to construct the left child node of the parent first if it exists.
Example 1:
Input: "1(2)(3)"
Output: 2 1 3
Explanation:
1
/ \
2 3
Explanation: first pair of parenthesis contains
left subtree and second one contains the right
subtree. Inorder of above tree is "2 1 3".
Example 2:
Input: "4(2(3)(1))(6(5))"
Output: 3 2 1 4 5 6
Explanation:
4
/ \
2 6
/ \ /
3 1 5
Your Task:
You don't need to read input or print anything. Your task is to complete the function treeFromString() which takes a string str as input parameter and returns the root node of the tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Solve the problem and submit your answer here: https://practice.geeksforgeeks.org/problems/construct-binary-tree-from-string-with-bracket-representation/1
practice.geeksforgeeks.org
Construct Binary Tree from String with bracket representation | Practice | GeeksforGeeks
Construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the roots value and a pair of par
Problem Of The Day
“Add Binary Strings”
Solve the problem to win points
Given two binary strings A and B consisting of only 0s and 1s. Find the resultant string after adding the two Binary Strings.
Note: The input strings may contain leading zeros but the output string should not have any leading zeros.
Example 1:
Input:
A = "1101", B = "111"
Output: 10100
Explanation:
1101
+ 111
10100
Example 2:
Input:
A = "10", B = "01"
Output: 11
Explanation:
10
+ 01
11
Your Task:
You don't need to read input or print anything. Your task is to complete the function addBinary() which takes 2 binary string A and B and returns a binary string denoting the addition of both the strings.
Expected Time Complexity: O(max(|A|, |B|)).
Expected Auxiliary Space: O(max(|A|, |B|)) (for output string).
Solve the problem and submit your answers here : https://practice.geeksforgeeks.org/problems/add-binary-strings3805/1
“Add Binary Strings”
Solve the problem to win points
Given two binary strings A and B consisting of only 0s and 1s. Find the resultant string after adding the two Binary Strings.
Note: The input strings may contain leading zeros but the output string should not have any leading zeros.
Example 1:
Input:
A = "1101", B = "111"
Output: 10100
Explanation:
1101
+ 111
10100
Example 2:
Input:
A = "10", B = "01"
Output: 11
Explanation:
10
+ 01
11
Your Task:
You don't need to read input or print anything. Your task is to complete the function addBinary() which takes 2 binary string A and B and returns a binary string denoting the addition of both the strings.
Expected Time Complexity: O(max(|A|, |B|)).
Expected Auxiliary Space: O(max(|A|, |B|)) (for output string).
Solve the problem and submit your answers here : https://practice.geeksforgeeks.org/problems/add-binary-strings3805/1
practice.geeksforgeeks.org
Add Binary Strings | Practice | GeeksforGeeks
Given two binary strings A and B consisting of only 0s and 1s. Find the resultant string after adding the two Binary Strings.
Note: The input strings may contain leading zeros but the output string should not have any leading zeros.
E
Note: The input strings may contain leading zeros but the output string should not have any leading zeros.
E
👍3
Problem Of The Day
“Maximum Sub Array”
Solve the problem to win points
Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be contiguous i.e., a sub-array created by choosing the second and fourth element and skipping the third element is invalid.
Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).
Example:
a = [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5] [2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]
NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length.
If there is still a tie, then return the segment with minimum starting index.
If no such subarray is present return "-1"
Example 1:
Input:
n = 3
a[] = {1, 2, 3}
Output: 1 2 3
Explanation: In the given array every
element is non-negative.
Example 2:
Input:
n = 2
a[] = {-1, 2}
Output: 2
Explanation: The only subarray [2] is
the answer.
Your Task:
Complete the function findSubarray() which takes the array a and the size of the array, n, as input parameters and returns an array representing the answer. If there is no subarray return an array of length 1 containing -1 only. You don't to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve the problem and submit your answers here :
https://practice.geeksforgeeks.org/problems/maximum-sub-array5443/1
“Maximum Sub Array”
Solve the problem to win points
Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be contiguous i.e., a sub-array created by choosing the second and fourth element and skipping the third element is invalid.
Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).
Example:
a = [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5] [2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]
NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length.
If there is still a tie, then return the segment with minimum starting index.
If no such subarray is present return "-1"
Example 1:
Input:
n = 3
a[] = {1, 2, 3}
Output: 1 2 3
Explanation: In the given array every
element is non-negative.
Example 2:
Input:
n = 2
a[] = {-1, 2}
Output: 2
Explanation: The only subarray [2] is
the answer.
Your Task:
Complete the function findSubarray() which takes the array a and the size of the array, n, as input parameters and returns an array representing the answer. If there is no subarray return an array of length 1 containing -1 only. You don't to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve the problem and submit your answers here :
https://practice.geeksforgeeks.org/problems/maximum-sub-array5443/1
practice.geeksforgeeks.org
Maximum Sub Array | Practice | GeeksforGeeks
Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be contiguous i.e., a sub-array created by choosing the second and fourth element and skipping the third element is invalid.
Maximum sub-array is defined
The sub-array should be contiguous i.e., a sub-array created by choosing the second and fourth element and skipping the third element is invalid.
Maximum sub-array is defined
👍4
Must Do DSA Topics day 36
Stack
Design a stack that supports getMin() in O(1) time and O(1) extra space : Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack.
Learn more : http://bit.ly/3icRJKR
Implement a stack using single queue : We are given queue data structure, the task is to implement stack using only given queue data structure. We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue.
Learn more : http://bit.ly/3gJcHRd
How to implement stack using priority queue or heap : In priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in Last in First Out manner. The idea is to associate a count that determines when it was pushed.
Learn more : http://bit.ly/3gHKV7y
Stack
Design a stack that supports getMin() in O(1) time and O(1) extra space : Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack.
Learn more : http://bit.ly/3icRJKR
Implement a stack using single queue : We are given queue data structure, the task is to implement stack using only given queue data structure. We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue.
Learn more : http://bit.ly/3gJcHRd
How to implement stack using priority queue or heap : In priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in Last in First Out manner. The idea is to associate a count that determines when it was pushed.
Learn more : http://bit.ly/3gHKV7y
👍2
Problem Of The Day
“Count the Number of Full Binary Trees”
Solve the problem to win points
Given an array arr[] of n integers, where each integer is greater than 1. The task is to find the number of Full binary tree from the given integers, such that each non-leaf node value is the product of its children value.
Note: Each integer can be used multiple times in a full binary tree. The answer can be large, return answer modulo 1000000007
Example 1:
Input:
n = 4
arr[] = {2, 3, 4, 6}
Output:
7
Explanation:
There are 7 full binary tree with
the given product property.
Four trees with single nodes
2 3 4 6
Three trees with three nodes
4
/ \
2 2 ,
6
/ \
2 3 ,
6
/ \
3 2
Example 2:
Input:
n = 3
arr[] = {2, 4, 5}
Output: 4
Explanation: There are 4 full binary tree
with the given product property.
Three trees with single nodes 2 4 5
One tree with three nodes
4
/ \
2 2
Your Task:
You don't need to read input or print anything. Your task is to complete the function numoffbt() which takes the array arr[]and its size n as inputs and returns the number of Full binary tree.
Expected Time Complexity: O(n. Log(n))
Expected Auxiliary Space: O(n)
Solve the problem and submit your answers here : https://practice.geeksforgeeks.org/problems/count-the-number-of-full-binary-trees2525/1
“Count the Number of Full Binary Trees”
Solve the problem to win points
Given an array arr[] of n integers, where each integer is greater than 1. The task is to find the number of Full binary tree from the given integers, such that each non-leaf node value is the product of its children value.
Note: Each integer can be used multiple times in a full binary tree. The answer can be large, return answer modulo 1000000007
Example 1:
Input:
n = 4
arr[] = {2, 3, 4, 6}
Output:
7
Explanation:
There are 7 full binary tree with
the given product property.
Four trees with single nodes
2 3 4 6
Three trees with three nodes
4
/ \
2 2 ,
6
/ \
2 3 ,
6
/ \
3 2
Example 2:
Input:
n = 3
arr[] = {2, 4, 5}
Output: 4
Explanation: There are 4 full binary tree
with the given product property.
Three trees with single nodes 2 4 5
One tree with three nodes
4
/ \
2 2
Your Task:
You don't need to read input or print anything. Your task is to complete the function numoffbt() which takes the array arr[]and its size n as inputs and returns the number of Full binary tree.
Expected Time Complexity: O(n. Log(n))
Expected Auxiliary Space: O(n)
Solve the problem and submit your answers here : https://practice.geeksforgeeks.org/problems/count-the-number-of-full-binary-trees2525/1
practice.geeksforgeeks.org
Count the Number of Full Binary Trees | Practice | GeeksforGeeks
Given an array arr[] of n integers, where each integer is greater than 1. The task is to find the number of Full binary tree from the given integers, such that each non-leaf node value is the product of its children value.
Note: Each integer can b
Note: Each integer can b
👍2
Must Do DSA Topics day 37
Stack
Convert Infix expression to Postfix expression : The compiler scans the expression either from left to right or from right to left.
Consider the expression: a + b * c + d
The compiler first scans the expression to evaluate the expression b * c, then again scans the expression to add a to it.
Learn more : http://bit.ly/3ASwXqw
Prefix to Infix Conversion : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2).
Learn more : http://bit.ly/3ihI71w
Prefix to Postfix Conversion : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Learn more : http://bit.ly/3ieZTCp
Stack
Convert Infix expression to Postfix expression : The compiler scans the expression either from left to right or from right to left.
Consider the expression: a + b * c + d
The compiler first scans the expression to evaluate the expression b * c, then again scans the expression to add a to it.
Learn more : http://bit.ly/3ASwXqw
Prefix to Infix Conversion : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2).
Learn more : http://bit.ly/3ihI71w
Prefix to Postfix Conversion : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Learn more : http://bit.ly/3ieZTCp
👍2
Must Do DSA Topics day 38
Stack
Reverse a stack using recursion : The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.
Learn more : http://bit.ly/3AT5fty
Sort a stack using recursion : The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order. and then print the stack.
Learn more : http://bit.ly/3ELI3P9
Sort a stack using a temporary stack : Given a stack of integers, sort it in ascending order using another temporary stack.
Learn more : http://bit.ly/3VEVYgR
Stack
Reverse a stack using recursion : The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.
Learn more : http://bit.ly/3AT5fty
Sort a stack using recursion : The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order. and then print the stack.
Learn more : http://bit.ly/3ELI3P9
Sort a stack using a temporary stack : Given a stack of integers, sort it in ascending order using another temporary stack.
Learn more : http://bit.ly/3VEVYgR
Problem Of The Day
“Reorder List”
Given a singly linked list: A0→A1→...→An-2→An-1, reorder it to: A0→An-1→A1→An-2→A2→An-3→...
For example: Given 1->2->3->4->5 its reorder is 1->5->2->4->3.
Note: It is recommended do this in-place without altering the node's values.
Example 1:
Input:
LinkedList: 1->2->3
Output: 1 3 2
Explanation:
Here n=3, so the correct
order is A0→A2→A1
Example 2:
Input:
Explanation: 1->7->3->4
Output: 1 4 7 3
Explanation:
Here n=4, so the correct
order is A0→A3→A1→A2
Your Task:
The task is to complete the function reorder list() which should reorder the list as required. The reorder list is automatically printed by the driver's code.
Note: Try to solve without using any auxilliary space.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/reorder-list/1
“Reorder List”
Given a singly linked list: A0→A1→...→An-2→An-1, reorder it to: A0→An-1→A1→An-2→A2→An-3→...
For example: Given 1->2->3->4->5 its reorder is 1->5->2->4->3.
Note: It is recommended do this in-place without altering the node's values.
Example 1:
Input:
LinkedList: 1->2->3
Output: 1 3 2
Explanation:
Here n=3, so the correct
order is A0→A2→A1
Example 2:
Input:
Explanation: 1->7->3->4
Output: 1 4 7 3
Explanation:
Here n=4, so the correct
order is A0→A3→A1→A2
Your Task:
The task is to complete the function reorder list() which should reorder the list as required. The reorder list is automatically printed by the driver's code.
Note: Try to solve without using any auxilliary space.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/reorder-list/1
practice.geeksforgeeks.org
Reorder List | Practice | GeeksforGeeks
Given a singly linked list: A0→A1→...→An-2→An-1, reorder it to: A0→An-1→A1→An-2→A2→An-3→...
For example: Given 1->2->3->4->5 its reorder is 1->5->2->4->3.
Note: It is recom
For example: Given 1->2->3->4->5 its reorder is 1->5->2->4->3.
Note: It is recom
👍1
Must Do DSA Topics day 39
Stack
Merge Overlapping Intervals : A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from the list and merge the other into the first interval.
Learn more : http://bit.ly/3VFoXkJ
Print ancestors of a given binary tree node without recursion : Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
Learn more : http://bit.ly/3FbprJP
Reverse a string using stack : The idea is to create an empty stack and push all the characters from the string into it. Then pop each character one by one from the stack and put them back into the input string starting from the 0’th index.
Learn more : http://bit.ly/3insPIq
Get access to more topics of Stack : http://bit.ly/3ubkryx
Stack
Merge Overlapping Intervals : A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from the list and merge the other into the first interval.
Learn more : http://bit.ly/3VFoXkJ
Print ancestors of a given binary tree node without recursion : Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
Learn more : http://bit.ly/3FbprJP
Reverse a string using stack : The idea is to create an empty stack and push all the characters from the string into it. Then pop each character one by one from the stack and put them back into the input string starting from the 0’th index.
Learn more : http://bit.ly/3insPIq
Get access to more topics of Stack : http://bit.ly/3ubkryx
👍1
Must Do DSA Topics day 40
Queue
Introduction to Queue in Data Structures and Algorithms : We define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. The element which is first pushed into the order, the operation is first performed on that.
Learn more : http://bit.ly/3ENxkUw
Implementations of Queue Data Structure : Similar to Stack, Queue is a linear data structure that follows a particular order in which the operations are performed for storing data.
Learn more : http://bit.ly/3GSg6b8
Applications, Advantages and Disadvantages of Queue : Similar to stacks, multiple operations can be performed on the queue. When an element is inserted in a queue, then the operation is known as Enqueue and when an element is deleted from the queue, then the operation is known as Dequeue.
Learn more : http://bit.ly/3UethGd
Queue
Introduction to Queue in Data Structures and Algorithms : We define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. The element which is first pushed into the order, the operation is first performed on that.
Learn more : http://bit.ly/3ENxkUw
Implementations of Queue Data Structure : Similar to Stack, Queue is a linear data structure that follows a particular order in which the operations are performed for storing data.
Learn more : http://bit.ly/3GSg6b8
Applications, Advantages and Disadvantages of Queue : Similar to stacks, multiple operations can be performed on the queue. When an element is inserted in a queue, then the operation is known as Enqueue and when an element is deleted from the queue, then the operation is known as Dequeue.
Learn more : http://bit.ly/3UethGd
👍1
Problem Of The Day
“Rearrange Array Alternately”
Solve the problem to win points
Given a sorted array of positive integers. Your task is to rearrange the array elements alternatively i.e first element should be max value, second should be min value, third should be second max, fourth should be second min and so on.
Note: Modify the original array itself. Do it without using any extra space. You do not have to return anything.
Example 1:
Input:
n = 6
arr[] = {1,2,3,4,5,6}
Output: 6 1 5 2 4 3
Explanation: Max element = 6, min = 1,
second max = 5, second min = 2, and
so on... Modified array is : 6 1 5 2 4 3.
Example 2:
Input:
n = 11
arr[]={10,20,30,40,50,60,70,80,90,100,110}
Output:110 10 100 20 90 30 80 40 70 50 60
Explanation: Max element = 110, min = 10,
second max = 100, second min = 20, and
so on... Modified array is :
110 10 100 20 90 30 80 40 70 50 60.
Your Task:
The task is to complete the function rearrange() which rearranges elements as explained above. Printing of the modified array will be handled by driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately-1587115620/1
“Rearrange Array Alternately”
Solve the problem to win points
Given a sorted array of positive integers. Your task is to rearrange the array elements alternatively i.e first element should be max value, second should be min value, third should be second max, fourth should be second min and so on.
Note: Modify the original array itself. Do it without using any extra space. You do not have to return anything.
Example 1:
Input:
n = 6
arr[] = {1,2,3,4,5,6}
Output: 6 1 5 2 4 3
Explanation: Max element = 6, min = 1,
second max = 5, second min = 2, and
so on... Modified array is : 6 1 5 2 4 3.
Example 2:
Input:
n = 11
arr[]={10,20,30,40,50,60,70,80,90,100,110}
Output:110 10 100 20 90 30 80 40 70 50 60
Explanation: Max element = 110, min = 10,
second max = 100, second min = 20, and
so on... Modified array is :
110 10 100 20 90 30 80 40 70 50 60.
Your Task:
The task is to complete the function rearrange() which rearranges elements as explained above. Printing of the modified array will be handled by driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately-1587115620/1
practice.geeksforgeeks.org
Rearrange Array Alternately | Practice | GeeksforGeeks
Given a sorted array of positive integers. Your task is to rearrange the array elements alternatively i.e first element should be max value, second should be min value, third should be second max, fourth should be second min and so on.
Note:&nb
Note:&nb
👍2
Must Do DSA Topics Day 41
Queue
Implement Queue using Stacks : We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.
Learn more : http://bit.ly/3udaCzZ
LRU Cache Implementation : We are given the total possible page numbers that can be referred. We are also given a cache (or memory) size (The number of page frames that the cache can hold at a time). The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in the cache.
Learn more : http://bit.ly/3gMkOwz
Implement Stack using Queues : Given a Queue data structure that supports standard operations like enqueue() and dequeue(). The task is to implement a Stack data structure using only instances of Queue and Queue operations allowed on the instances.
Learn more : https://bit.ly/3V2ay24
Queue
Implement Queue using Stacks : We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.
Learn more : http://bit.ly/3udaCzZ
LRU Cache Implementation : We are given the total possible page numbers that can be referred. We are also given a cache (or memory) size (The number of page frames that the cache can hold at a time). The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in the cache.
Learn more : http://bit.ly/3gMkOwz
Implement Stack using Queues : Given a Queue data structure that supports standard operations like enqueue() and dequeue(). The task is to implement a Stack data structure using only instances of Queue and Queue operations allowed on the instances.
Learn more : https://bit.ly/3V2ay24
Must Do DSA Topics Day 42
Queue
How to efficiently implement k Queues in a single array : Create a data structure kQueues that represents k queues. Implementation of kQueues should use only one array, i.e., k queues should use the same array for storing elements.
Learn more : http://bit.ly/3gOFjIL
Implement a stack using single queue : We are given queue data structure, the task is to implement stack using only given queue data structure. We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue.
Learn more : https://bit.ly/3gJcHRd
Implementation of Deque using circular array : Deque or Double Ended Queue is a generalized version of the Queue data structure that allows insert and delete at both ends
Learn more : http://bit.ly/3UionIh
Queue
How to efficiently implement k Queues in a single array : Create a data structure kQueues that represents k queues. Implementation of kQueues should use only one array, i.e., k queues should use the same array for storing elements.
Learn more : http://bit.ly/3gOFjIL
Implement a stack using single queue : We are given queue data structure, the task is to implement stack using only given queue data structure. We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue.
Learn more : https://bit.ly/3gJcHRd
Implementation of Deque using circular array : Deque or Double Ended Queue is a generalized version of the Queue data structure that allows insert and delete at both ends
Learn more : http://bit.ly/3UionIh
👍2
Problem Of The Day
“Check if it is possible to convert one string into another with given constraints”
Solve the problem to win points
Given two strings S and T, which contains three characters i.e 'A', 'B' and '#' only. Check whether it is possible to convert the first string into another string by performing following operations on string first.
1- A can move towards Left only
2- B can move towards Right only
3- Neither A nor B should cross each other
Note: Moving i'th character towards Left one step means swap i'th with (i-1)'th charecter [ i-1>=0 ]. Moving i'th character towards Right one step means swap i'th with (i+1)'th charecter [ i+1< string's length ].
Example 1:
Input:
S=#A#B#B#
T=A###B#B
Output:
1
Explanation:
A in S is right to the A in T
so A of S can move easily towards
the left because there is no B on
its left positions and for first B
in S is left to the B in T so B
of T can move easily towards the
right because there is no A on its
right positions and it is same for
next B so S can be easily converted
into T.
Example 2:
Input:
S=#A#B#
T=#B#A#
Output:
0
Explanation:
Here first A in S is left to the
A in T and according to the condition,
A cant move towards right,so S cant
be converted into T.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isItPossible() which takes the two strings S, T and their respective lengths M and N as input parameters and returns 1 if S can be converted into T. Otherwise, it returns 0.
Expected Time Complexity: O(M+N) where M is size of string S and N is size of string T.
Expected Auxillary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/check-if-it-is-possible-to-convert-one-string-into-another-with-given-constraints4116/1
“Check if it is possible to convert one string into another with given constraints”
Solve the problem to win points
Given two strings S and T, which contains three characters i.e 'A', 'B' and '#' only. Check whether it is possible to convert the first string into another string by performing following operations on string first.
1- A can move towards Left only
2- B can move towards Right only
3- Neither A nor B should cross each other
Note: Moving i'th character towards Left one step means swap i'th with (i-1)'th charecter [ i-1>=0 ]. Moving i'th character towards Right one step means swap i'th with (i+1)'th charecter [ i+1< string's length ].
Example 1:
Input:
S=#A#B#B#
T=A###B#B
Output:
1
Explanation:
A in S is right to the A in T
so A of S can move easily towards
the left because there is no B on
its left positions and for first B
in S is left to the B in T so B
of T can move easily towards the
right because there is no A on its
right positions and it is same for
next B so S can be easily converted
into T.
Example 2:
Input:
S=#A#B#
T=#B#A#
Output:
0
Explanation:
Here first A in S is left to the
A in T and according to the condition,
A cant move towards right,so S cant
be converted into T.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isItPossible() which takes the two strings S, T and their respective lengths M and N as input parameters and returns 1 if S can be converted into T. Otherwise, it returns 0.
Expected Time Complexity: O(M+N) where M is size of string S and N is size of string T.
Expected Auxillary Space: O(1)
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/check-if-it-is-possible-to-convert-one-string-into-another-with-given-constraints4116/1
practice.geeksforgeeks.org
Check if it is possible to convert one string into another with given constraints | Practice | GeeksforGeeks
Given two strings S and T, which contains three characters i.e 'A', 'B' and '#' only. Check whether it is possible to convert the first string into another string by performing following operations on string fir
👍2
Must Do DSA Questions Day 43
Queue
Check if a queue can be sorted into another queue using a stack : Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack.
Learn more : http://bit.ly/3P2czZN
Breadth First Traversal or BFS for a Graph : Breadth-First Traversal (or Search) for a graph is similar to Breadth-First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles, so we may come to the same node again.
Learn more : http://bit.ly/3gRtemh
Level Order Tree Traversal : Given the root of the Binary Tree. The task is to print the Level order traversal of a tree is breadth first traversal for the tree.
Learn more : http://bit.ly/3EUF9HN
Queue
Check if a queue can be sorted into another queue using a stack : Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack.
Learn more : http://bit.ly/3P2czZN
Breadth First Traversal or BFS for a Graph : Breadth-First Traversal (or Search) for a graph is similar to Breadth-First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles, so we may come to the same node again.
Learn more : http://bit.ly/3gRtemh
Level Order Tree Traversal : Given the root of the Binary Tree. The task is to print the Level order traversal of a tree is breadth first traversal for the tree.
Learn more : http://bit.ly/3EUF9HN
Must Do DSA Topics Day 44
Queue
Reverse a path in BST using queue : Take a queue and push all the element till that given key at the end replace node key with queue front element till root, then print inorder of the tree.
Learn more : http://bit.ly/3OUxXjw
Construct Complete Binary Tree from its Linked List Representation : Given Linked List Representation of Complete Binary Tree, construct the Binary tree. A complete binary tree can be represented in an array in the following approach.
Learn more : http://bit.ly/3B3vcXx
Number of siblings of a given Node in n-ary Tree : Given an N-ary tree, find the number of siblings of given node x. Assume that x exists in the given n-ary tree.
Learn more : http://bit.ly/3UkXzHu
Queue
Reverse a path in BST using queue : Take a queue and push all the element till that given key at the end replace node key with queue front element till root, then print inorder of the tree.
Learn more : http://bit.ly/3OUxXjw
Construct Complete Binary Tree from its Linked List Representation : Given Linked List Representation of Complete Binary Tree, construct the Binary tree. A complete binary tree can be represented in an array in the following approach.
Learn more : http://bit.ly/3B3vcXx
Number of siblings of a given Node in n-ary Tree : Given an N-ary tree, find the number of siblings of given node x. Assume that x exists in the given n-ary tree.
Learn more : http://bit.ly/3UkXzHu
👍4
Problem Of The Day
“Aggressive Cows”
Solve the problem to win points
You are given an array consisting of n integers which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. You are given the task of assigning stalls to k cows such that the minimum distance between any two of them is the maximum possible.
The first line of input contains two space-separated integers n and k.
The second line contains n space-separated integers denoting the position of the stalls.
Example 1:
Input:
n=5
k=3
stalls = [1 2 4 8 9]
Output:
3
Explanation:
The first cow can be placed at stalls[0],
the second cow can be placed at stalls[2] and
the third cow can be placed at stalls[3].
The minimum distance between cows, in this case, is 3,
which also is the largest among all possible ways.
Example 2:
Input:
n=5
k=3
stalls = [10 1 2 7 5]
Output:
4
Explanation:
The first cow can be placed at stalls[0],
the second cow can be placed at stalls[1] and
the third cow can be placed at stalls[4].
The minimum distance between cows, in this case, is 4,
which also is the largest among all possible ways.
Your Task:
Complete the function int solve(), which takes integer n, k, and a vector stalls with n integers as input and returns the largest possible minimum distance between cows.
Expected Time Complexity: O(n*log(10^9)).
Expected Auxiliary Space: O(1).
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/aggressive-cows/1
“Aggressive Cows”
Solve the problem to win points
You are given an array consisting of n integers which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. You are given the task of assigning stalls to k cows such that the minimum distance between any two of them is the maximum possible.
The first line of input contains two space-separated integers n and k.
The second line contains n space-separated integers denoting the position of the stalls.
Example 1:
Input:
n=5
k=3
stalls = [1 2 4 8 9]
Output:
3
Explanation:
The first cow can be placed at stalls[0],
the second cow can be placed at stalls[2] and
the third cow can be placed at stalls[3].
The minimum distance between cows, in this case, is 3,
which also is the largest among all possible ways.
Example 2:
Input:
n=5
k=3
stalls = [10 1 2 7 5]
Output:
4
Explanation:
The first cow can be placed at stalls[0],
the second cow can be placed at stalls[1] and
the third cow can be placed at stalls[4].
The minimum distance between cows, in this case, is 4,
which also is the largest among all possible ways.
Your Task:
Complete the function int solve(), which takes integer n, k, and a vector stalls with n integers as input and returns the largest possible minimum distance between cows.
Expected Time Complexity: O(n*log(10^9)).
Expected Auxiliary Space: O(1).
Solve and submit your answer here : https://practice.geeksforgeeks.org/problems/aggressive-cows/1
www.geeksforgeeks.org
Aggressive Cows | Practice | GeeksforGeeks
You are given an array with unique elements of stalls[], which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. Your task is to assign stalls to k cows such that the minimum distance between
Must Do DSA Topics Day 45
Queue
Reversing a Queue : For reversing the queue one approach could be to store the elements of the queue in a temporary data structure in a manner such that if we re-insert the elements in the queue they would get inserted in reverse order.
Learn more : http://bit.ly/3F1Zzi2
Reversing a queue using recursion : Given a queue, write a recursive function to reverse it.
Standard operations allowed :
enqueue(x) : Add an item x to rear of queue.
dequeue() : Remove an item from front of queue.
empty() : Checks if a queue is empty or not.
Learn more : http://bit.ly/3EVeYAZ
Reversing the first K elements of a Queue : Given an integer k and a queue of integers, The task is to reverse the order of the first k elements of the queue, leaving the other elements in the same relative order.
Learn more : http://bit.ly/3iziTvK
Queue
Reversing a Queue : For reversing the queue one approach could be to store the elements of the queue in a temporary data structure in a manner such that if we re-insert the elements in the queue they would get inserted in reverse order.
Learn more : http://bit.ly/3F1Zzi2
Reversing a queue using recursion : Given a queue, write a recursive function to reverse it.
Standard operations allowed :
enqueue(x) : Add an item x to rear of queue.
dequeue() : Remove an item from front of queue.
empty() : Checks if a queue is empty or not.
Learn more : http://bit.ly/3EVeYAZ
Reversing the first K elements of a Queue : Given an integer k and a queue of integers, The task is to reverse the order of the first k elements of the queue, leaving the other elements in the same relative order.
Learn more : http://bit.ly/3iziTvK