Practice Coding Questions DSA- ST-3
(By- Bharat and Kunal)
Q1 Find next greater element
We are given a circular array, print the next greater number for every element. If it is not found
print -1 for that number. To find the next greater number for element Ai , start from index i + 1
and go uptil the last index after which we start looking for the greater number from the starting
index of the array since array is circular.
Q2. Nearly sorted array
Given an array of N elements, where each element is at most K away from its target position,
devise an algorithm that sorts in O(N log K) time.
Q3. Nth Ugly Number
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer N, return the nth ugly number.
Q4. Find Maximum Height of binary Tree
A binary tree's maximum height is the number of nodes along the longest path from the root
node down to the farthest leaf node.
Q5. Check whether tree is balanced binary tree.
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every
node never differs by more than one.
Q6. Sum Root to Leaf Numbers
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
A leaf node is a node with no children.
Q7. Lowest Common Ancestor in Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
The lowest common ancestor is defined between two nodes p and q as the lowest node
in T that has both p and q as descendants (where we allow a node to be a descendant of itself).
Q8. Construct a Balanced Binary search Tree from sorted array -5 marks
Given an sorted array you need construct a balanced binary tree using every element of array
Balanced binary tree: difference between left and right sub tree must be less than or equal to 1
Q9. Delete a node in binary search Tree
Given a binary search tree, find the given node and delete it in BST and print whole BST after
deletion in level order traversal
Q10. Find the frequency of all unique elements in vector with lower to higher element order
Q11. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are
stored in reverse order, and each of their nodes contains a single digit. Add the two numbers
and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Q12 Kth Element form last Linked List
Given a linked list with n nodes. Find the kth element from last without computing the length of
the linked list.
Q13. Triplet From LinkedList
Given three linked lists, say a, b and c, find one node from each list such that the sum of the
values of the nodes is equal to a given number say, Target. As any number of answers can be
possible return the first one you get while traversing.
Q14. Remove All Adjacent duplicates in a string
You are given a string s consisting of lowercase English letters. A duplicate removal consists of
choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that
the answer is unique.
Q15. Diameter of a Binary Tree
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path
between two end nodes. The diagram below shows two trees each with diameter nine, the
leaves that form the ends of the longest path are shaded (note that there is more than one path
in each tree of length nine, but no path longer than nine nodes).
Q16. Right view of Binary tree
Given a binary tree , print its nodes from root to bottom as visible from right side of tree
Your task is to complete the rightView() function and return the right view of tree.
Q17.Largest BST in a binary tree
Given a Binary Tree, write a program that returns the size of the largest subtree which is also a
Binary Search Tree (BST)
Q18. Connect Ropes
Given an array of integers A representing the length of ropes.
You need to connect these ropes into one rope. The cost of connecting two ropes is equal to the
sum of their lengths.
Find and return the minimum cost to connect these ropes into one rope.
Q19. STOCK SPAN PROBLEM
The stock span problem is a financial problem where we have a series of n daily price quotes
for a stock and we need to calculate the span of stocks price for all n days.
The span Si of the stocks price on a given day i is defined as the maximum number of
consecutive days just before the given day, for which the price of the stock on the given day is
less than or equal to its price on the current day.
Q20. Top view of binary tree
Given a binary tree, print the nodes in left to right manner as visible from above the tree.
