Software Developer

This question can be solved by doing a level order traversal of the tree. While doing the traversal, process nodes of different levels separately. For every level being processed, calculate the sum of nodes in each level and keep track of the maximum sum. At the end, return the maximum sum. 
Time Complexity: O(N)
Auxiliary Space: O(w) where w is the maximum width of the tree

A modified Kadane’s algorithm can be used for this problem. Using kadane’s, find the minimum contiguous subarray sum and the maximum contiguous subarray sum in the array and then check for the maximum value between the max_value and the value left after subtracting min_value from the total sum. 
Example 1:-
A = [1, -2, 3, -2]
Max_value = 3 (This means max subarray sum for normal array)
Min_value = -2 (This means min subarray sum for normal array)
Total_sum = 0 (total array sum)
Maximum Sum = 3 (max)

Example 2 :-
A = [5, -3, 5]
Max_value = 7
Min_value = -3
Total_sum = 7
maximum subarray sum = 7 - (-3) = 10

Algorithm :
1. Find maximum subarray sum using kadane's algorithm (max_value) 
2. Find minimum subarray sum using kadane's algorithm (min_value)
3. Find total sum of the array (total_sum). 
4. Now, if total_sum == min_value i.e. all values are negative, return max_value
5. Otherwise, return maximum ( max_value, total_sum – min_value )

Time Complexity: O(N)
Auxiliary Space: O(1)

Since the numbers are large, we store the numbers in string type. To add the two numbers, basic school mathematics can be applied. 
Traverse both the strings from end, one by one add digits and keep track of carry. 
Steps : 
1) Reverse both strings. 
2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10. 
3) Finally reverse the resultant string.

The brute force approach would be to consider all substrings one by one and check for each substring whether it contains all unique characters or not. There will be n*(n+1)/2 substrings. Time complexity of this solution would be O(n^3).

For an efficient solution, a hashmap can be used. Maintain a hashmap which stores the characters in string as keys and their indexes(positions) as values, and keep two pointers which define the max substring. move the right pointer to traverse through the string, and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Keep updating the max length Non-Repeating Character Substring seen so far.

Hashing can be used to solve this question. Keep the count of words of the dictionary in a hash map. Iterate the string and for each word, check if is present in the map. If present, then decrease the count of that word in the map. If it is not present, then it is not possible to make the given string from the given dictionary of words.

One approach could be to calculate the number of spaces in the given string. Calculate the new length of the string as original length + 2*(number of spaces). Create a new string of the length calculated. Traverse the original string and keep appending all characters except spaces in the new string. As soon as a space is encountered, append '%20' in the string. Return the new string created.

Firstly, we calculate the sum of all the elements in the array. If the sum is odd (sum%2!=0), then we cannot divide the array elements into 2 subsets with equal sum, but if the sum is even, we might be able to divide the array into 2 equal subsets. If the sum is even, we check if there is a subset with the sum of elements = sum/2. If it exists, that means the other subset also has elements with sum = sum/2, so we return true. If we're not able to find any such subset, we finally return false.
Now, we need to find approach to find subset with sum/2. 
The brute force approach would be to use recursion. We can consider each item in the given array one by one. For each item, there are two possibilities:
• We can find a subset with sum/2 which includes the current element, so we include the current item in the subset and recur for remaining items with the remaining sum (sum - array[index]).
• We cannot find a subset with sum/2 with the current index value included. So, we exclude the current item from the subset and recur for remaining items.
Time Complexity of this approach would be O(2^n). 
• Dynamic programming can be used to optimize this. Bottom up approach can be used to compute dp[i][j]. dp[i][j] means whether the specific sum j can be gotten from the first i numbers. If we can pick such a series of numbers from 0-i whose sum is j, dp[i][j] is true, otherwise it is false.
• dp[i][j] is true if dp[i-1][j] is true (meaning that we skipped this element, and took the sum of the previous result) or dp[i-1][j-array[i]], i.e we're searching for a subset with sum = sum - array[i].
• If dp[n][sum/2] is true that means we were able to find a sum of sum/2 out of n elements which is what we want to check.
Time Complexity : O(nxsum/2)