$1)$ Count nodes

Given a binary tree root, a node X is named max node if in the path from root to X there are no nodes with a value greater than X$.$

Return the number of max nodes in the binary tree.

$/**$

$*$ Definition for a binary tree node.

$*$ public class TreeNode $\{$

$*$ int val;

$*$TreeNode left;

$*$TreeNode right;

$*$ TreeNode$()\{\}$

$*$ TreeNode$($int val$)\{$this$.$val $=$ val; $\}$

$*$ TreeNode$($int val, TreeNode left, TreeNode right$)\{$

$*$ this.val $=$ val;

$*$ this.left $=$ left;

$*$ this.right $=$ right;

$*\}$

$*\}$

$*/$

class Solution $\{$

public int maxNodes$($TreeNode root$)\{$

$\}$

$\}$

$2)$ Encode$/$Decode a Binary Tree

Design an algorithm to encode $($turn it into a String$)$ and decode $($read it from String$)$ a binary search tree. There is no restriction on how your algorithm should work. You need to ensure that a binary search tree can be encoded to a string, and this string can be decoded to the original tree structure.

$/**$

$*$ Definition for a binary tree node.

$*$ public class TreeNode $\{$

$*$int val;

$*$TreeNode left;

$*$TreeNode right;

$*$TreeNode$($int x$)\{$ val $=$ x; $\}$

$*\}$

$*/$

import java.util.$*$;

public class Solution $\{$

$//$ Encodes a tree to a single string.

public static String encode $($TreeNode root$)\{$

$\}$

$//$ Decodes your encoded data to tree.

public static TreeNode decode$($String data$)\{$

$\}$

$\}$

$//$ String tree $=$ Solution.encode$($root$)$;

$//$ TreeNode ans $=$ Solution.decode$($tree$)$;

$3)$ Binary Search Tree Iterator

Apply the Iterator pattern over the Binary Search Tree implementation you have worked on$.$

The iterator should represent an in$-$order traversal of the BST$.$

$4)$ Trim Binary Search Tree

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in $[$low$,$ high$).$ Trimming the tree should not change the relative structure of the elements that will remain in the tree $($i$.$e$.,$ any node's descendant should remain a descendant$).$ It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example $1$:

Input: root $=[1,0,2],$ low $=1,$ high $=2$

Output: $[1,$null, $2]$

Example $2$:

Input: root $=[3,0,4,$null, $2,$ null, null, $1],$ low $=1,$ high $=3$

Output: $[3,2,$ null, $1]$

$5)$ Topmost frequent integers

Given an integer array nums and an integer k$,$ return the k most frequent integers. Return the answer in any order.

It is guaranteed that the answer is unique.

Your algorithm's time complexity must be better than O$($n log n$),$ where n is the array's size $($basically don't sort anything$)$

Example $1$:

Input: nums $=[1,1,1,2,2,3],$ k $=2$ Output: $[1,2]$

Example $2$:

Input: nums $=[1,2],$ k $=2$ Output: $[1,2]$

$6)$ Majority Elements

A$.$ Given an integer array of size n$,$ find all elements that appear more than Math.floor$($n$/3)$ times. Solve it in linear time using hash tables.

Example $1$:

Input: nums $=[3,2,3]$

Output: $[3]$

Example $2$:

Input: nums $=[1]$

Output: $[1]$

Example $3$:

Input: nums $=[1,2]$

Output: $[1,2]$

public List majorityElement$($int$[]$ nums$)\{$

$\}$

B$.$ Solve the same problem as in A$)$ but in O$(1)$ space. Consider using the Boyer$-$Moore majority vote algorithm that finds the majority of a sequence of elements using linear time and a constant space.

$7)$ Arabic to Roman numeral

Given an integer, convert it to a Roman numeral.

public String intToRoman$($int num$)\{$

$\}$

$8)$ Sort List

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

$/**$

$*$ Definition for singly$-$linked list.

$*$ public class ListNode $\{$

$*$ int val;

$*$ ListNode next;

$*$ ListNode$()\{\}$

$*$ ListNode$($int val$)\{$this$.$val $=$ val; $\}$

$*$ ListNode$($int val, ListNode next$)\{$ this.val $=$ val; this.next $=$ next; $\}$

$*\}$

$*/$ class Solution $\{$

public ListNode sortList$($ListNode head$)\{$

$\}$

$9)$ Sort Persons in Linear Time

Create a class Person with two properties: fullName as String and age as Integer. Knowing that the age of a person can't be greater than $960,$ sort in descending order an array of $1000$ Persons according to their age. Solve the problem in linear time complexity. Generate an array of $1000$ Persons using random values $($unless you want to manually create them$).$

public Person$[]$ sortPersons $($Person$[]$ persons$)\{$

$\}$

$10)$ Heap Sort

Implement heap sort algorithm.

Generate arrays of different sizes and compare the running time of heap sort with other sorting algorithms such as insertion sort, merge sort, quick sort, etc.

$11)$ Clone Graph

Given the reference of a node in a connected undirected graph, return a deep copy of the graph.

The graph is an adjacency list representation. Each node in the graph contains an integer value which is unique for each node, and a list $($List$)$ of its neighbors. There are no repeated edges and no self$-$

loops in the graph.

The graph is connected and all nodes can be visited starting from the given node. The emphasis is on the deep copy of the graph, don't return the same reference you

are given.

Use the graph Node definition below or one of the Node definitions you have worked on class.

$//$ Definition for a Graph Node.