SDE - Intern

You are given a binary tree where each node contains an integer value. Your task is to count the number of nodes in the tree that satisfy a specific property: the sum of all node values in the node's left subtree must be equal to the node's own value, AND the sum of all node values in its right subtree must also be equal to the node's own value.

Definitions:

The sum of an empty subtree (i.e., if a child is null) is considered to be 0.

A leaf node has a left subtree sum of 0 and a right subtree sum of 0.

You are given the head of a singly linked list with n nodes. Your task is to modify the values of the nodes in-place according to a specific "mirrored difference" rule.

The update rule is as follows:

The value of the 1st node should be updated to (Value of Last Node) - (Original Value of 1st Node).

The value of the 2nd node should be updated to (Value of 2nd to Last Node) - (Original Value of 2nd Node).

The value of the 3rd node should be updated to (Value of 3rd to Last Node) - (Original Value of 3rd Node).

...and so on.

This pattern continues until the pointers from the start and the end of the list meet or cross. If the list has an odd number of nodes, the middle node's value remains unchanged.

After modifying the list, your function should return its head.

You are given an array/list 'asteroids' representing asteroids in a row.

For each element of the given array, its absolute value denotes the size of that asteroid, and its sign denotes the direction it moves in(+ve meaning right and -ve meaning left).

An asteroid with a weight of 0 denotes a massless asteroid that moves in the right direction.

All asteroids are moving at the same speed. Whenever two asteroids collide, the smaller asteroid gets destroyed.

If both asteroids are the same size, then both asteroids get destroyed. Two asteroids moving in the same direction never collide.

You are supposed to find the state of the asteroids after all collisions.

Example :

Input: ‘asteroids’ = [3,-2,4]

Output: [3, 4]

Explanation: The first asteroid will destroy the second asteroid. Hence, after the collision, the state of the asteroids will be [3,4].

Note:

You don’t need to print anything. Just implement the given function.

You are given a binary tree where each node contains an integer value. Your task is to find the second largest unique value at each level of the tree.

You must return a list of these second-largest values, ordered from the root level to the deepest level.

Rules for determining the second largest value:

If a level has two or more unique node values (e.g., [5, 5, 3]), the second largest is the second highest distinct value (in this case, 3).

If a level has fewer than two unique node values (e.g., [10] or [20, 20, 20]), there is no second largest value. In such cases, you should use -1 as a placeholder for that level's result.

You are given the head of a singly linked list and an integer X. Your task is to partition the linked list around the value X such that:

All nodes with values less than X come first.

All nodes with values equal to X come next.

All nodes with values greater than X come at the end.

Crucially, the original relative order of the nodes within each of these three partitions must be preserved.

Your function should rearrange the nodes in-place (or by creating new lists and linking them) and return the head of the newly formed partitioned list.

You are given a linked list of 'n' nodes and an integer 'k', where 'k' is less than or equal to 'n'.

Your task is to reverse the order of each group of 'k' consecutive nodes, if 'n' is not divisible by 'k', then the last group of nodes should remain unchanged.

For example, if the linked list is 1->2->3->4->5, and 'k' is 3, we have to reverse the first three elements, and leave the last two elements unchanged. Thus, the final linked list being 3->2->1->4->5.

Implement a function that performs this reversal, and returns the head of the modified linked list.

Example:

Input: 'list' = [1, 2, 3, 4], 'k' = 2

Output: 2 1 4 3

Explanation:
We have to reverse the given list 'k' at a time, which is 2 in this case. So we reverse the first 2 elements then the next 2 elements, giving us 2->1->4->3.

Note:

All the node values will be distinct.

You are given a binary tree. Return the count of unival sub-trees in the given binary tree. In unival trees, all the nodes, below the root node, have the same value as the data of the root.

For example: for the binary tree, given in the following diagram, the number of unival trees is 5.

You are given a singly linked list and an integer K. A node in the list is considered "k-balanced" if the absolute difference between the sum of values of all nodes before it and the sum of values of all nodes after it is less than or equal to K.

| (Sum of values before the node) - (Sum of values after the node) | <= K

The sum of nodes before the head of the list is 0. The sum of nodes after the tail of the list is also 0.

Your task is to determine if every node in the linked list is k-balanced. If all nodes satisfy this condition, return true. If even one node fails the check, return false. An empty list or a list with a single node is considered balanced by definition.

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to return the size of the largest subtree of the binary tree which is also a BST.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Example:

Given binary tree:

In the given binary tree, subtree rooted at 2 is a BST and its size is 3.

You’re given an array 'arr' of size 'n' and an integer 'k'.

Your task is to split 'arr' into 'k' sub-arrays such that the maximum sum achieved from the 'k' subarrays formed must be the minimum possible.

A subarray is a contiguous part of the array.

Return the minimum possible value of the maximum sum obtained after splitting the array into 'k' partitions.

Example:

Input: ‘arr’ = [1, 1, 2] and ‘k’ = 2 

Output: 2

Explanation: If we want to make two subarrays, there are two possibilities: [[1], [1, 2]] and [[1, 1], [2]]. We can see that the maximum sum of any subarray is minimized in the second case. Hence, the answer is 2, which is the maximum sum of any subarray in [[1, 1], [2]].

You are given a string 'str' of length 'n'.

Find the minimum number of partitions in the string so that no partition is empty and every partitioned substring is a palindrome.

Example :

Input: 'str' = "aaccb"

Output: 2

Explanation: We can make a valid partition like aa | cc | b. 

You are given a special linked list that is sorted in ascending order. Each node in this list is a doubly linked list node, containing data, a next pointer to the next node, and a prev pointer to the previous node.

Your task is to convert this sorted doubly linked list into a height-balanced Binary Search Tree (BST).

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. The BST property must also be maintained: for any given node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

Your function should take the head of the doubly linked list and return the root of the newly constructed BST.