Problem:
You have two numbers represented by a linked list, where each node contains a single digit   The digits are stored in reverse order, such that the 1’s digit is at the head of
the list   Write a function that adds the two numbers and returns the sum as a linked
list
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
Solution:

1. Have pointer on each head of the two list
2. Add the data of two nodes along with carry.
3. create new result node and put the value, SUM % 10
4. assign SUM / 10 to carry
5. Repeat until any one list exhausts.
6. Then add the carry to the node, repeat till end of list

Complexity: O(n) where n>=m, m and n are length of two lists
Code:

Problem:
  Write code to remove duplicates from an unsorted linked list
Solution:

1. Have two pointers ptr1 and ptr2.
2. For each node ptr1 visits check from head [head  to node before ptr1] whether that data is already present.
3. If so, remove the ptr1 node.
4. return the new list without any duplicates

Complexity: O(n^2)
Code:

Problem:
 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes   Create an algorithm to decide if T2 is a subtree of T1
Solution:

1. Traverse the Tree T1.
2. For each node, call a method to do the following (Step 3),
3. traverse both the Tree T1 and T2, until tree T2 exhausts or until data of T1 and T2 does not match. 
4. Return true if T2 is a subtree of T1 else return false.

 

 Complexity: O(m*n) in the worst case
Code: