Let's solve them, here is the list.

- Longest Common Subsequence
- Shortest Common Supersequence
- Longest Increasing Subsequence problem
- The Levenshtein distance (Edit distance) problem
- Matrix Chain Multiplication
- 0–1 Knapsack problem
- Partition problem
- Rod Cutting
- Coin change problem
- Word Break Problem

- LONGEST COMMON SUBSEQUENCE

Understanding the question:

for each letter, we will check whether this letter equals to the letter in the other string, if so we will take it, otherwise, we will continue advancing with one of the strings

**// Method1()- recursive solution(Top- down approach)**

// time complexity - O(2^(m+n))

// space complexity - O(m+n)…

How can you sort a LinkedList in O(n*logn) running time and less than O(n) space?

Use merge sort.

we will start with 2 subproblems and then combine it all for a valid solution.

Firstly,** merge two sorted list**:

If one of the lists is null then return the other one,

else create a dummy node as a place-holder, iterate both of the lists, and always add the smaller node first, if one is smaller than the other, the append the longer one to the end. Simple.

**public static ListNode merge(ListNode left, ListNode right) {**

if (left ==…

So what exactly is serialization?**Serialization** is a mechanism of converting the state of an object into a byte stream. Deserialization is the reverse process where the byte stream is used to recreate the actual **Java** object in memory. This mechanism is used to persist the object. … To make a **Java** object **serializable** we implement the **java**.

Most impressive is that the entire process is JVM independent, meaning an object can be serialized on one platform and deserialized on an entirely different platform.

When we should use serialization?

Answer: Whenever an object has to sent over the network, those objects…

First the code

**public class SingletonDemo {**

private static SingletonDemo singleton = null;

private SingletonDemo() {

System.out.println("singleton created");

}

public static SingletonDemo getInstance() {

if (singleton == null) {

singleton = new SingletonDemo();

}

return singleton;

}

}

The code above is an example of a lazy singleton.

When we should use singleton?

A **singleton should be used** when managing access to a resource that is shared by the entire application, and it would be destructive to potentially have multiple instances of the same class. Making sure that access to shared resources thread-safe is **one** very good example of where this kind of **pattern** can be vital.

**Counting sort**Counting sort is base on the assumption that the array contains only integers, and they are between 0 to k, where k is known!.

The idea is simple, for each item in the array we will count how many items are lower or equals to him, hence if there are m items that are less or equal than item x, the x will be in place m.

Counting Sort is a stable sort.

We will use 3 arrays in the process, A is our Original, C is for counting, B is the output array.

Creating the arrays, and…

A quick word about sorting using comparisons, each array with n items has n! permutations, if we look at the algorithm as a binary tree that each node to leaf is a premutation then the are n! node to leaf routes since each binary tree leaf routes is no more than 2^h where h is the height.

than 2^h > n! , and h > log n! , log n! is = n*logn.

**MergeSort algorithm:**

the algorithm takes nlogn since the recursive call to mergesort will be applied log n times since we can only divide the length of the…