SDE - 1

You are given the root node of a binary tree consisting of ‘N’ nodes. Your task is to find the number of good nodes in the given binary tree.

A good node is defined as good if there are no nodes with a value greater than X’s value in the path from the root to X.

You are given a root node ‘ROOT’.Your task is to return the number of good nodes.

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. 

The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

You are given a string ‘expression’ consists of characters ‘+’, ‘-’, ‘*’, ‘/’, ‘(‘, ‘)’ and ‘0’ to ‘9’, that represents an Arithmetic Expression in Infix Notation. Your task is to evaluate this Arithmetic Expression.

In Infix Notation, operators are written in-between their operands.

Note :

1. We consider the ‘/’ operator as the floor division.

2. Operators ‘*’ and ‘/’ expression has higher precedence over operators‘+’ and ‘-’ 

3. String expression always starts with ‘(‘ and ends with ‘)’.

4. It is guaranteed that ‘expression’ represents’ a valid expression in Infix notation.

5. It is guaranteed that there will be no case that requires division by 0.

6. No characters other than those mentioned above are present in the string. 

7. It is guaranteed that the operands and final result will fit in a 32-bit integer.

For example :

Consider string ‘expression’ = ‘((2+3)*(5/2))’. 
Then it’s value after evaluation will be ((5)*(2)) = 10. 

You are given two non-negative numbers 'num1' and 'num2' represented in the form of linked lists.

The digits in the linked lists are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit.

Calculate the sum of the two numbers and return the head of the sum list.

Example :

Input:
'num1' : 1 -> 2 -> 3 -> NULL
'num2' : 4 -> 5 -> 6 -> NULL

Output: 5 -> 7 -> 9 -> NULL

Explanation: 'num1' represents the number 321 and 'num2' represents 654. Their sum is 975.

Given an infinite grid, implement Tic tac toe with following functionalities -
1. Save progress.
2. Finish the game as soon as any player wins.
3. N will be provided where N refers to number of items required to win the game (generally this is 3 when we play this game but in problem it could be any number >= 3)

Walk through a program which is designed to make a system super slow.