gdsc-igdtuw-autumn-of-code-2022 / dsa-foundation Goto Github PK

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. The task is to complete the function leftView(), which accepts root of the tree as argument.

Left View of the tree : 1 2 4

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

Output: 4

Please assign this issue to me.

A sentence is a list of words that are separated by a single space with no leading or trailing spaces.

For example, "Hello World", "HELLO", "hello world hello world" are all sentences.
Words consist of only uppercase and lowercase English letters. Uppercase and lowercase English letters are considered different.

A sentence is circular if:

The last character of a word is equal to the first character of the next word.
The last character of the last word is equal to the first character of the first word.
For example, "leetcode exercises sound delightful", "eetcode", "leetcode eats soul" are all circular sentences. However, "Leetcode is cool", "happy Leetcode", "Leetcode" and "I like Leetcode" are not circular sentences.

Given a string sentence, return true if it is circular. Otherwise, return false.

Given an expression with only ‘}’ and ‘{‘. The expression may not be balanced. Find minimum number of bracket reversals to make the expression balanced.
Examples:
Input: exp = "}{"
Output: 2
We need to change '}' to '{' and '{' to
'}' so that the expression becomes balanced,
the balanced expression is '{}'

Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Example: Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

You are given a sorted array in increasing order, you are required to remove the duplicates [in-place] such that each unique element appears only once. The relative order of the elements should be kept the same.

Return N- no of unique elements after placing the final resultant unique elements in the first n slots of input array.

Constraints: You must do this by modifying the input array [in-place with O(1) extra memory.

Kindly assign me this issue @gdsc-igdtuw @Parul-Mann

Given an array arr[] of size N. The task is to find the sum of the contiguous subarray within a arr[] with the largest sum.
pls assign me this issue.

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Input: root = [1,2,2,3,4,4,3]
Output: true
Constraints:
The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

Problem-
Place N chess queens on an N×N chessboard so that no two queens attack each other.

Example : if n=4 then the following is a solution for the 4 Queen problem.
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
Where 1 represents the positions in which queen is placed

You are given two strings s and t consisting of only lowercase English letters.

Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.

The chemistry of a team is equal to the product of the skills of the players on that team.

Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players into teams such that the total skill of each team is equal.

Given a string, we have to find out all subsequences of it. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.
Examples:
Input : abc
Output : a, b, c, ab, bc, ac, abc

Input : aaa
Output : a, a, a, aa, aa, aa, aaa

Given a binary tree, print the bottom view from left to right.
A node is included in bottom view if it can be seen when we look at the tree from bottom.

Bottom view will be: 4 2 6 3 7

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.

Example 1:
Input:
N = 3
A[] = {1,2,3}
Output:
-1
Explanation:
Since, each element in
{1,2,3} appears only once so there
is no majority element.

You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match.

Return a list answer of size 2 where:

answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.
The values in the two lists should be returned in increasing order.

Given the root of a binary tree, calculate 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.

Return the vertical order traversal of the binary tree.

Vertical order traversal is : [[4],[2],[1,5,6],[3],[7]]

Given an unsorted integer array , return the smallest missing positive integer.

Constraints: TC- O(N) and uses constant extra space only

@gdsc-igdtuw @Parul-Mann kindly assign me the issue

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Kindly assign me the issue @gdsc-igdtuw @Parul-Mann

Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Aditya is playing with red coloured and blue coloured balls each having n balls labelled 1-n integers. He realizes by mistake he has mixed one blue ball with the red balls and lost one red ball such that there is one repeating number and one missing number in the red balls. Determine the missing and repeating numbers for aditya to sort all the balls.
You are given n and arr(numbers labeled on all red balls)

Example-
n=3
arr=[1,3,3]
missing=2
repeating=3

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. Note that the overall run time complexity should be O(log (m+n))

Example:

Input:

nums1 = [1,3]
nums2 = [2,4]

Output:
2.50000

Explanation:
Merged array = [1,2,3,4]
Median = (2+3)/2 = 2.5

You are given the head of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the head of the modified linked list.

Given two positive integers X and Y. Let’s define W such that Y AND W = W. The task is to maximize the expression X XOR Y.

Examples
Example 1 : Input: X = 11 Y = 4 Output: 15
Example 2 : Input: X = 9 and Y = 13 Output: 13

@Parul-Mann please assign this issue to me

Given below is a binary tree. The task is to print the top view of binary tree. Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. For the given below tree

Top view will be: 4 2 1 3 7

Given a positive integer n, find the pivot integer x such that:

The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.
Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input

You are given a string s consisting of only lowercase English letters. In one operation, you can:

1. Delete the entire string s, or
2. Delete the first i letters of s if the first i letters of s are equal to the following i letters in s, for any i in the range 1 <= i <= s.length / 2.
   For example, if s = "ababc", then in one operation, you could delete the first two letters of s to get "abc", since the first two letters of s and the following two letters of s are both equal to "ab".

Return the maximum number of operations needed to delete all of s

Given a square matrix, turn it by 90 degrees in an anti-clockwise direction without using any extra space
Examples:
Input:
Matrix: 1 2 3
4 5 6
7 8 9
Output: 3 6 9
2 5 8
1 4 7

Given a string S1 of length N consisting of lowercase English alphabet letters. You are allowed to perform the following operation on the string S1 any number of times:
Select a non-empty subsequence X of the array [1,2,3,…,N] and any lowercase English alphabet α.
Change Ai to α for all i∈X.
Find the minimum number of operations required to convert S1 into a given string S2 of length N consisting of lowercase English alphabet letters.

Example:
Input:
3
aaa
bab
4
abcd
aaab

Output:
2
1
2

Given integers X and Y, generate a palindrome of length X consisting of lowercase English alphabets such that the number of distinct characters in the palindrome is exactly Y.
If it is impossible to do so, print -1 instead.

Example:
Input:
1 1
2 1
3 3
4 2

Output:
z
aa
-1
xyyx

Please assign me this code @gdsc-igdtuw

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Given a string s, you are to return the longest palindromic substring in s.

@Parul-Mann Please could you assign to me this issue

Given a string str consisting only of lowercase English letters. In one move, you can select any two adjacent characters of s and swap them. Return the minimum number of moves required to make str a palindrome. A string is said to be palindrome if it remains the same on reading from both ends.

Example:

Input:
“xxyy”

Output:
2

Explanation:
Swap indices 1 and 2 -> “xyxy”
Swap indices 0 and 1 -> “yxxy”
2 moves

Q1. Harshit and Aditya are playing a number game. They possess a list of n integers in arr stored in strictly increasing order.
Harshit has to follow these steps
Start from left and move towards right by removing the first and every 3rd consecutive number until he reaches the end.
Repeat the previous step again, but this time move from right to left, remove the rightmost number and every 3rd number from the remaining numbers.
He has to keep repeating the steps again, alternating left to right and right to left, until two numbers remain.
Now Aditya has to guess the last two remaining numbers in sorted order. Help him win this game against Harshit.
Example-
Input =[2,6,9,10,13,16,19]
Step 1 =[2,6,9,10,13,16,19]
step-2=[6,9,13,16]
ans=9,13

You are given a linked list of size N,
where n is even, the i-th node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Given two lists sorted in increasing order, create a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.
Note: The list elements are not necessarily distinct.
Input:
L1 = 1->2->3->4->6
L2 = 2->4->6->8
Output: 2 4 6
Explanation: For the given first two
linked list, 2, 4 and 6 are the elements
in the intersection.

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

@Parul-Mann please assign this reverse linked list issue to me so that I can contribute in this in c++ language.

To find if a 9*9 sudoku board can be solved or not. It contains non zero and zero values. Non zero values lie in the range: [1, 9]. Cells with zero value indicate that the particular cell is empty and can be replaced by non zero values.
You need to find out whether the sudoku board can be solved.
If the sudoku board can be solved, then print true, otherwise print false.

Constraints:
The cell values lie in the range: [0, 9]
Time Limit: 1 second

For example:

Sample Input:
9 0 0 0 2 0 7 5 0
6 0 0 0 5 0 0 4 0
0 2 0 4 0 0 0 1 0
2 0 8 0 0 0 0 0 0
0 7 0 5 0 9 0 6 0
0 0 0 0 0 0 4 0 1
0 1 0 0 0 5 0 8 0
0 9 0 0 7 0 0 0 4
0 8 2 0 4 0 0 0 6

Sample Output :
true

Given two equally sized 1-D arrays A, B containing N integers each.

A sum combination is made by adding one element from array A and another element of array B.

Return the maximum C valid sum combinations from all the possible sum combinations.

Please assign me this issue