Given a boolean 2D array of n x m dimensions where each row is sorted. Find the 0-based index of the first row that has the maximum number of 1's.

Input:
N = 4 , M = 4
Arr[][] = {{0, 1, 1, 1},
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}}
Output: 2

Explanation: Row 2 contains 4 1's (0-based indexing)

Hint: use Binary Search (https://www.youtube.com/watch?v=GU7DpgHINWQ)

Write a code to reverse a Linked List using recursion

Input

5
1 2 3 4 5

Output:

5 4 3 2 1

Complexities

Time Complexity - O(n)

Space Complexity - O(n) // used for recursion stack

You must implement this on a linked list.

You are given the root node of a binary tree. Print its preorder traversal.

preorder is: Root Left Right

Function Template: void preOrder(BinaryTreeNode *root)

Given an integer array (of length n), find and print all the subsets of input array.
Subsets are of length varying from 0 to n, that contain elements of the array. But the order of elements should remain same as in the input array.

Note : The order of subsets are not important. Just print the subsets in different lines.

Input format :
Line 1 : Integer n, Size of array
Line 2 : Array elements (separated by space)

Sample Input:
3
15 20 12
Sample Output:
[] (this just represents an empty array, don't worry about the square brackets)
12
20
20 12
15
15 12
15 20
15 20 12

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 span of stock’s price for all n days.
The span Si of the stock’s 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 current day is less than or equal to its price on the given day.

Function template: void calculateSpan(int price[], int n)
Input: price[] = {100, 80, 60, 70, 60, 75, 85}, n = 7
Output: 1 1 1 2 1 4 6

Explanation:

Given an array of distinct integers, find if there are two pairs (a, b) and (c, d) such that a+b = c+d, and a, b, c and d are distinct elements. If there are multiple answers, then print any of them.

Input: {3, 4, 7, 1, 2, 9, 8}
Output: (3, 8) and (4, 7)
Explanation: 3+8 = 4+7

Note: Name the file Four_Element_Sum.cpp

For a given Binary Tree of type integer, update it with its corresponding mirror image.

Output Format:
The only line of output prints the mirrored tree in a level-wise order.
Each level will be printed on a new line. Elements printed at each level will be separated by a single line.

Example:
1
3 2
7 6 5 4

Function template:
void mirrorBinaryTree(BinaryTreeNode* root)

class BinaryTreeNode {
public:
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;

BinaryTreeNode(int data) {
    this->data = data;
    left = NULL;
    right = NULL;
}

};

Given an array of integers, find the length of the longest sub-array with a sum that equals 0.

Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
Output: 5
Explanation: The longest sub-array with
elements summing up-to 0 is {-2, 2, -8, 1, 7}

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

lefti is the x coordinate of the left edge of the ith building.
righti is the x coordinate of the right edge of the ith building.
heighti is the height of the ith building.
You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]

Sample Test Case

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Visualization

Given a linked list sorted in increasing order, write a function that removes duplicate nodes from the list by traversing it only once, using O(1) auxiliary memory

Input

An integer n (n>0), denoting size of Linked List
Next line will contain n elements

Output

Print the unique elements present in linked list. (You should modify the original linked list, and it should not contain any duplicate elements.)

Sample Input1

5
1 2 2 3 4

Sample Output1

1 2 3 4

First PR Video (5-7 mins)
Instructions and links to system setup (VSCode, Gitlens)

GIven a linked list of length n, you should find the kth element from the end of the linked list
You can assume that n>=k

Input

Two space seperated integers n, k
Next line will contain n elements, denoting elements of linked list.

Output

An integer denoting the kth element from the end of the linked list

Sample Input 1

5 2
1 2 3 4 5

Sample Output 1

4

Sample Input 2

9 7
1 2 3 4 5 6 7 8 9

Sample Output 2

3

Design a stack, that can give you minimum element in O(1) auxiliary space and O(1) time.

You should implement following functions on stack:
push(int x) // insert an integer x in the stack
pop() // removes the last inserted element of stack
getSize() // returns an integer, which denotes the number of elements currently present in stack
getMin() // returns an integer denoting the minimum element present in stack
top() // returns an integer denoting the value of topmost element in stack

We encourage you to also include a brief explanation of your approach.

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Sample Test Case 1

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Sample Test Case 2

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Reverse every group of "k" nodes in a linked list of size n. You can assume that k<=n.

Input

Two space separated integers n, and k
n elements, denoting a linked list

Output

Print the resultant linked list

Sample Input 1

10 2
1 2 3 4 5 6 7 8 35 21

Sample Output 1

2 1 3 4 6 5 7 8 21 35

Sample Input 2

14 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14

Sample Output 2

3 2 1 4 5 6 9 8 7 10 11 12 14 13

Complexities

Time Complexity: - O(n)

Space Complexity: - O(n)

Given an integer N, count and return the number of zeros that are present in the given integer using recursion.

Input Format : Integer N
Output Format : Number of zeros in N

Sample Input : 00010204
Sample Output : 2

Given a string and set of words (strings) , determine ,how many and which words can be segmented out by separating the string by spaces , like for example
set : { this, th, is, famous, Word, break, b, r, e, a, k, br, bre, brea, ak, problem }
string : Wordbreakproblem
output :
Word , break , b , r , e , a , k , br , bre , brea , ak , problem
no of words : 11
solve this question in minumum time and space, if u can ...

hint : ( recursion (good) , or dynamic programming )

Print "Hello World"

Issues related to DSA, CP, JS, HTML+CSS, operating system

Start with 6 Issues per DSA - 2x{Easy, Medium, Hard} :

• Arrays
• Stacks
• Queues & priority queue
• Linked List
• Hashmap
• Trees
• Recursion
• Dynamic Programming
• Graphs
• General algorithm

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Implement your own hashmap, without using library function (of hashmap).
Design such hash function, that can have less probability of collision

A child is running up a staircase with N steps, and can hop either 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up to the stairs. You need to return number of possible ways W.

Sample Input : 4
Sample Output: 7

Explanation (contributed by @satvikDesktop) :

1. 1,1,1,1
2. 2,1,1
3. 1,2,1
4. 1,1,2
5. 3,1
6. 1,3
7. 2,2

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window (vector).

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Explanation:
Window position Max

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

Write a program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in A[] whose sum is exactly x.

Input: arr[] = {0, -1, 2, -3, 1}
sum = -2
Output: -3, 1
Valid pair exixts.

Given a positive number 'n', efficiently generate binary numbers between 1 and n using the queue data-structure in linear time.

Input

You are given an integer n (n>0)

Output

An array containing n elements, representing binary representation of integers from 1 to n

Sample Input 1

16

Sample Output 1

1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Input

An integer n, denoting the number of linked lists.
Then we will take input of n lists, with each list in following format:

1. An integer p, denoting the size of linked list
2. Next line will contain p elements, sorted in ascending order

Output

You should print elements of final sorted linked list, containing all elements.

Sample Input 1

3
3
1 4 5
3
1 3 4
2
2 6

Sample Output 1

1 1 2 3 4 4 5 6

Note: You must store the input and final answer in form of Linked List and print answers accordingly.

Given an array of integers, find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Input: arr[] = {1, 9, 3, 10, 4, 20, 2}
Output: 4
Explanation:
The subsequence 1, 3, 4, 2 is the longest
subsequence of consecutive elements

Input: arr[] = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42}
Output: 5
Explanation:
The subsequence 36, 35, 33, 34, 32 is the longest
subsequence of consecutive elements.

Maximum Tiles cleaned by a robot in a 2D matrix

Given a 2D matrix of m rows and n columns. A cleaner robot is placed at position (0,0). The robot moves in the forward direction cleaning the tiles ('.') until an obstacle ('#') or the border of the matrix is encountered. It then turns around in clockwise direction and moves forward until another obstacle is encountered. Following the above rules, the robot forms a cleaning path for itself. Output the maximum number of tiles the robot can clean for a given matrix.

Constraints:

• arr[i][j]=='#' || arr[i][j] =='.'
• 1<=m<=20, 1<=n<=20
• The starting point will always be a tile ('.')

Example case 1:

Input string : {"...#","....","#...","..#.","...."}
Output: 7

Example case 2:

Input string : {"...#...#..","..........",".#...#.#..","..........","......#...","#..#......"}
Output: 36

Basics and Benefits of Open-source workshop (Sun - 14th Sep - 5 pm)

Given a binary tree with N number of nodes, check if that input tree is BST (Binary Search Tree). If yes, return true, return false otherwise.

Note: Duplicate elements should be kept in the right subtree.

Output: The first and only line of output contains either true or false.

Function template: bool isBST(BinaryTreeNode *root)

Note: you can modify the function template

Check whether a given String S is a palindrome using recursion. Return true or false.

Sample Input: racecar
Sample Output: true

Given a linked list of size n, sort it using merge sort technique

Sample Input

8 // integer n
5 9 8 7 4 5 2 1 // elements of linked list

Sample Output

1 2 4 5 5 7 8 9

Expected Time Complexity - O(n.log(n))

Expected Space Complexity - O(n)

A rooted binary tree is called “nice”, if every node is either a leaf, or has exactly two children.

The leaves of a nice binary tree are labeled by the letter ‘l’, and other nodes are labeled by the letter ‘n’.
Given the pre-order traversal of a nice binary tree as a string, you are required to find the depth of the tree.
Output one line for each test case, containing a single integer, the depth of tree.

Input: nlnll
Output: 2

Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.

Input

First line will contain an integer n, which denotes the size of an array
Next n lines will contain an integer, which denotes the value present at the ith index of an array where 0<=i<n;

Output

Output will contain n values, which denotes the nearest smaller element present on the left.
If there no smaller element on the left then you should output '_' for that particular element.

Sample Input 1

6
1 6 4 10 2 5

Sample Output 1

_ 1 1 4 1 2

Sample Input2

5
1 3 0 2 5

Sample Output 2

_ 1 _ 0 2

Expected Complexities:

Space Complexity - O(n)
Time Complexity - O(n)

Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side.

Assume function and node template and mention it in comments

you have to write a program to print Hello World.

Given an array of integers nums, return the number of good pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Question Statement

Implement two stack using a single array. You can assume that at any instant, the total number of elements present in both the stacks will not be more than 1000.

You should be able to implement following functions on stacks:

1. getSize1() // returns the number of elements present in stack 1
2. getSize2() // returns the number of elements present in stack 2
3. push1(int x) // insert a new element to stack 1
4. push2(int x) // insert a new element to stack 2
5. pop1() // deletes the topmost element of stack 1
6. pop2() // deletes the topmost element of stack 2
7. top1() // returns the value of topmost element of stack 1
8. top2() // returns the value of topmost element of stack 2

Input

1. First line will contain an integer n, which stores the number of operations that we need to perform
2. Next n lines will contain input in following format:
   2.1) An integer s, which denotes the stack number. (1<=s<=2)
   2.2) If operation is Push(x, y), then input will be a ( boolean = 0, integer = x),
   2.3) If operation is Pop, then input will be a (boolean = 1)

Output:

After performing n operations, Print the size and top element of each stack.

Sample Input 1:

6
1 0 15
1 0 25
1 1
2 0 35
2 0 33
2 1

Sample Output 1:

Final size of stack1 is: 1
Top element of stack1 is: 15
Final size of stack2 is: 1
Top element of stack2 is: 35

Sample Input 2:

2
1 0 15
1 0 25

Sample Output 2:

Final size of stack1 is: 2
Top element of stack1 is: 25
Final size of stack2 is: 0
Top element of stack2 is: Doesn't Exist // Or some similar message

Expected Complexities

Time Complexities for each operation : -
Push - O(1)
Pop - O(1)
Size - O(1)
Top - O(1)
Space complexity - O(n)

Note: - Implementation of two Stacks should be space efficient.

Given the root of a binary tree, print the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Input: root = [1,2,3,4,5,6,7]
Output:
4
2
1 5 6
3
7

Question Statement

Implement a stack using arrays. You can assume that at any instant, stack will not have more than 1000 elements.

Your stack should have following functions:

1. getSize() // returns the number of elements present in stack
2. push(int x) // insert a new element to stack
3. pop() // deletes the topmost element of stack
4. top() // returns the value of topmost element of stack

Input

1. First line will contain an integer n, which stores the number of operations that we need to perform
2. Next n lines will contain input in following format:
   2.1) If operation is Push(x), then input will be a ( boolean = 0, integer = x),
   2.2) If operation is Pop, then input will be a (boolean = 1)

Output:

Print the size and top element of stack, after performing n operations

Sample Input 1:

6
0 15
0 25
1
0 35
0 33
1

Sample Output 1:

Final size of stack is: 2
Top element of stack is: 35

Sample Input 2:

2
0 15
1

Sample Output 2:

Final size of stack is: 0
Top element of stack is: Not Possible // Or some similar message

Expected Complexities

Time Complexities for each operation : -
Push - O(1)
Pop - O(1)
Size - O(1)
Top - O(1)
Space complexity - O(n)

Rearrange a given linked list such that every even node will be moved to the end of the list in reverse order.

Sample Input

7 // size of linked list
1 2 3 4 5 6 7 // elements of linked list

Sample Output

1 3 5 7 6 4 2

Time complexity - O(n)

Space complexity - O(1)

You must implement it using linked list

You are given an array of unique integers that contain numbers in random order. You have to find the longest possible sequence of consecutive numbers using the numbers from given array.
You need to return the output array which contains starting and ending element. If the length of the longest possible sequence is one, then the output array must contain only single element.
Note:

1. Best solution takes O(n) time.
2. If two sequences are of equal length, then return the sequence starting with the number whose occurrence is earlier in the array.
   Input format:
   The first line of input contains an integer, that denotes the value of the size of the array. Let us denote it with the symbol n.
   The following line contains n space separated integers, that denote the value of the elements of the array.
   Output format:
   The first and only line of output contains starting and ending element of the longest consecutive sequence. If the length of longest consecutive sequence, then just print the starting element.
   Constraints :
   0 <= n <= 10^6
   Time Limit: 1 sec

Sample Input 1 :
13
2 12 9 16 10 5 3 20 25 11 1 8 6
Sample Output 1 :
8 12

Sample Input 2 :
7
3 7 2 1 9 8 41
Sample Output 2 :
7 9
Explanation: Sequence should be of consecutive numbers. Here we have 2 sequences with same length i.e. [1, 2, 3] and [7, 8, 9], but we should select [7, 8, 9] because the starting point of [7, 8, 9] comes first in input array and therefore, the output will be 7 9, as we have to print starting and ending element of the longest consecutive sequence.
Sample Input 3 :
7
15 24 23 12 19 11 16
Sample Output 3 :
15 16

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input

First line contains an integer n, denoting the size of array.
Next n lines will contain elements of array

Output

A single integer, denoting the maximum possible area of rectangle that can be made from the histogram

Sample Input 1

6
2 1 5 6 2 3

Sample Output 1

10

Explaination

Expected Complexities

Space Complexity - O(n)
Time Complexity - O(n)

Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false.

Input: array = {12, 3, 4, 1, 6, 9}, sum = 24;
Output: 12, 3, 9

Given a generic tree, print the input tree in level wise order.
For printing a node with data N, you need to follow the exact format -

Function template: void printLevelWise(TreeNode* root)

class TreeNode {
public:
int data;
vector<TreeNode*> children;

TreeNode(T data) { this->data = data; }

};

Output Format :
The first and only line of output contains the elements of the tree in level wise order, as described in the task.

You are given a string s. You need to reverse the string.

You only need to complete the function reverseWord() that takes s as parameter and returns the reversed string.

Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).

Input: s = string
Output: gnirts

Resources related to:

• Previous year papers for subjects
• Language - how you learned a particular language and the resources you used
• Different Tech resources for appropriate folders
• New Issues are also welcome

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Given an array of random numbers, Push all the zero’s of a given array to the end of the array.
For example, if the given arrays is {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, it should be changed to {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}.
The order of all other elements should be same.

Expected time complexity is O(n) and extra space is O(1).

Implement a queue data-structure using Linked List
Your should implement the following functions:

1. enqueue (int x) // Insert an element to queue
2. deque() //removes an element from queue
3. size() //returns the number of elements present in the queue

Desired Complexities:

Time Complexity

enqueue - O(1)
deque - O(1)
size - O(1)

Space Complexity - O(n)