The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

Input: nums = [0]

Output: [[],[0]]

Let’s use backtracking to create our subsets. We’ll use a Set to know if the subset if already in our return array (key is simply concatenated version of the array).

[1, 2, 1]

Index 3: []

Index 2: [] [1]

Index 1: [][1] [2][2,1]

Index 0: [][1][2][2,1] ~~[1]~~[1,1][1,2][1,2,1]

Notice what happened here. The same subset [1, 2] and [2, 1] get counted as different subsets. To avoid this we run the same algorithm on the sorted version of the input.

[1, 1, 2]

Index 3: []

Index 2: [] [2]

Index 1: [][2] [1][1,2]

Index 0: [][2][1][1,2] ~~[1][1,2]~~[1,1][1,1,2]

```
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
return subsetsWithDupCalc(0, nums.sort(), new Set());
};
var subsetsWithDupCalc = function(i, nums, retSet) {
if (i === nums.length) return [[]];
let ret = subsetsWithDupCalc(i+1, nums, retSet);
let newRet = [...ret];
ret.forEach((arr) => {
let curr = [nums[i], ...arr];
if (!retSet.has(curr.join(''))) {
newRet.push(curr);
retSet.add(curr.join(''));
}
});
return newRet;
};
```

]]>– The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

– The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Recursively run through the whole tree. During return of the recursion, root.right is set to left_linked_list (return from left recursion) and the end of left_linked_list.right is set to right_linked_list (return from right recursion). One gotcha, is the need to account for left_linked_list being empty/null. Also, don’t forget to set root.left to null.

```
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var lastEl = function(root) {
let curr = root;
while (curr.right !== null) curr = curr.right;
return curr;
}
var flatten = function(root) {
if (!root) return null;
let leftLL = flatten(root.left);
let rightLL = flatten(root.right);
root.left = null;
//root.right = null;
if (leftLL) {
root.right = leftLL;
lastEl(leftLL).right = rightLL;
} else {
root.right = rightLL;
}
return root;
};
```

]]>Take two numbers, say 3 and 30. How would you decide which one would come first? You would simply compare ‘330’ and ‘303’ and decide.

Given the above comparison function, we simply sort these numbers using a custom comparator which compares two numbers in the above way. Then, just concat array and return number.

One gotcha: the system expects you to remove leading zeros. We use a regex for that.

```
/**
* @param {number[]} nums
* @return {string}
*/
var largestNumber = function(nums) {
nums.sort((a, b) => Number(a+""+b) > Number(b+""+a) ? -1 : 1);
return nums.join("").replace(/^0*(.+)/, '$1');
};
```

]]>Use a recursive algorithm to keep traversing tree, while building the path. Once you reach a leaf node calculate the sum(path + leaf node) and store it in the totalSum.

```
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function(root) {
const sumRef = [0];
sum(root, [], sumRef);
return sumRef[0];
};
var sum = function(root, path, sumRef) {
if (root === null) return;
if (root.left === null && root.right === null) {
sumRef[0] += Number(path.join('') + root.val);
return;
}
sum(root.left, [...path, root.val], sumRef);
sum(root.right, [...path, root.val], sumRef);
}
```

]]>The algorithm is as follows:-

- Segregate nodes into
- Reverse the nodes_to_reverse (recursive algorithm)
- Merge

```
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
// 1. Segregate nodes into
```
let leftNode = null, reverseNode = null, rightNode = null;
let i = 1;
let curr = head;
while (curr !== null) {
let tmp = curr;
curr = curr.next;
tmp.next = null;
if ( i < left ) {
if ( leftNode === null ) leftNode = tmp
else getEnd(leftNode).next = tmp
} else if ( i >= left && i <= right ) {
if ( reverseNode === null ) reverseNode = tmp
else getEnd(reverseNode).next = tmp
} else {
if ( rightNode === null ) rightNode = tmp
else getEnd(rightNode).next = tmp
}
i++;
}
// 2. Reverse the nodes_to_reverse
const reversedNodes = reverse(reverseNode);
// 3. Merge
let ret = null;
if (leftNode !== null) ret = leftNode;
if (ret === null) ret = reversedNodes
else getEnd(ret).next = reversedNodes
if (ret === null) ret = rightNode
else getEnd(ret).next = rightNode
return ret;
};
var getEnd = function(head) {
let tmp = head;
while (tmp.next !== null) tmp = tmp.next;
return tmp;
}
var reverse = function(head) {
if (head === null || head.next === null) return head;
const ret = reverse(head.next);
let curr = ret;
while (curr.next !== null) curr = curr.next;
head.next = null;
curr.next = head;
return ret;
}

]]>Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]

Output: 2

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]

Output: 2

At every step jump and update values (if smaller) in the landing step. Let’s take the example of [2, 3, 1, 1, 4]. We start by initializing the ret array with MAX_VALUE’s. Then for position 0, we update position 1 and 2 with updated minimum value of 1. We keep doing this for the full array.

```
[2, 3, 1, 1, 4]
Initialize -> [ 0, 1.797e+308, 1.797e+308, 1.797e+308, 1.797e+308 ]
Jump from position 0 -> [ 0, 1, 1, 1.797e+308, 1.797e+308 ]
Jump from position 1 -> [ 0, 1, 1, 2, 2 ]
Jump from position 2 -> [ 0, 1, 1, 2, 2 ]
Jump from position 3 -> [ 0, 1, 1, 2, 2 ]
Jump from position 4 -> [ 0, 1, 1, 2, 2 ]
```

```
[3, 0, 0, 1, 4]
Initialize -> [ 0, 1.797e+308, 1.797e+308, 1.797e+308, 1.797e+308 ]
Jump from position 0 -> [ 0, 1, 1, 1, 1.797e+308 ]
Jump from position 1 -> [ 0, 1, 1, 1, 1.797e+308 ]
Jump from position 2 -> [ 0, 1, 1, 1, 1.797e+308 ]
Jump from position 3 -> [ 0, 1, 1, 1, 2 ]
Jump from position 4 -> [ 0, 1, 1, 1, 2 ]
```

```
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
const ret = [0].concat(new Array(nums.length-1).fill(Number.MAX_VALUE));
for (let i = 0 ; i < nums.length ; i++ ) {
let currStep = nums[i];
//console.log(i, currStep)
for (let jump = 1 ; jump <= currStep ; jump++) {
//console.log("jump", jump, i + jump)
if ( ret[i + jump] > ret[i] + 1 ) {
ret[i + jump] = ret[i] + 1
}
}
}
//console.log(ret)
return ret[nums.length-1]
};
```

]]>- [4,5,6,7,0,1,4] if it was rotated 4 times.
- [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

**Example 1:**

Input: nums = [1,3,5]

Output: 1

**Example 2:**

Input: nums = [2,2,2,0,1]

Output: 0

We use a `modified` binary search to find the minimum element:-

- At every point, compare (‘i’, ‘mid’) with (‘mid+1’, ‘j’). Whichever section has the lower value, let’s move that direction. Because of duplicates, we might be in a situation where there’s no one clear winner. In that case, move in both directions.
if ( (a < c && a < d) || (b < c && b < d) ) // go left else if ((c > a && c > b) || (d > a && d > b)) // go right else // go both directions.

- Return the last number remaining in the recursion (when i === j)

```
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
return findMinRecursive(nums, 0, nums.length-1);
};
var findMinRecursive = function(nums, i, j) {
if (i === j) return nums[i];
let mid = i + Math.floor((j-i)/2);
const a = nums[i];
const b = nums[mid];
const c = nums[mid + 1];
const d = nums[j];
let left = Number.MAX_VALUE;
let right = Number.MAX_VALUE;
if ((a < c && a < d) || (b < c && b < d)) {
// go left
left = findMinRecursive(nums, i, mid);
} else if ((c > a && c > b) || (d > a && d > b)) {
right = findMinRecursive(nums, mid+1, j);
} else {
// go both
left = findMinRecursive(nums, i, mid);
right = findMinRecursive(nums, mid+1, j);
}
return Math.min(left, right);
};
```

]]>- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

**Example 1:**

Input: nums = [3,4,5,1,2]

Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

**Example 2:**

Input: nums = [4,5,6,7,0,1,2]

Output: 0

Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

**Example 3:**

Input: nums = [11,13,15,17]

Output: 11

Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

We use a `modified` binary search to find the minimum element:-

- At every point, compare (‘i’, ‘mid’) with (‘mid+1’, ‘j’). Whichever section has the lower value, let’s move that direction.
if ( (a < c && a < d) || (b < c && b < d) ) // go left else // go right

- Return the last number remaining in the recursion (when i === j)

```
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
return findMinRecursive(nums, 0, nums.length-1)
};
var findMinRecursive = function(nums, i, j) {
// one or two digits
if ( i === j ) return nums[i];
let mid = i + Math.floor((j-i)/2);
let a = nums[i];
let b = nums[mid];
let c = nums[mid+1];
let d = nums[j];
if ( (a < c && a < d) || (b < c && b < d) ) {
// go left
return findMinRecursive(nums, i, mid);
} else {
// go right
return findMinRecursive(nums, mid+1, j);
}
}
```

]]>```
class FooBar {
public void foo() {
for (int i = 0; i < n; i++) {
print("foo");
}
}
public void bar() {
for (int i = 0; i < n; i++) {
print("bar");
}
}
}
```

The same instance of FooBar will be passed to two different threads:

- thread A will call foo(), while
- thread B will call bar().

Modify the given program to output "foobar" n times.

**Example 1**:

Input: n = 1

Output: "foobar"

Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar().

"foobar" is being output 1 time.

**Example 2**:

Input: n = 2

Output: "foobarfoobar"

Explanation: "foobar" is being output 2 times.

Why use Semaphore and not ReentrantLock?

A semaphore initialized to one, and which is used such that it only has at most one permit available, can serve as a mutual exclusion lock. This is more commonly known as a binary semaphore, because it only has two states: one permit available, or zero permits available. When used in this way, the binary semaphore has the property (unlike many Lock implementations), that the * "lock" can be released by a thread other than the owner (as semaphores have no notion of ownership). This can be useful in some specialized contexts, such as deadlock recovery*.

```
class FooBar {
private int n;
private final Semaphore mutexFoo = new Semaphore(1);
private final Semaphore mutexBar = new Semaphore(1);
public FooBar(int n) {
this.n = n;
try {
mutexBar.acquire();
} catch ( Exception e ) {}
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
// printFoo.run() outputs "foo". Do not change or remove this line.
mutexFoo.acquire();
printFoo.run();
mutexBar.release();
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
// printBar.run() outputs "bar". Do not change or remove this line.
mutexBar.acquire();
printBar.run();
mutexFoo.release();
}
}
}
```

]]>- Solution here is to add some `ordering` on the resources (i.e. forks) requested by the processes (i.e. the philosophers).
- Identify the resource id’s (or fork id’s) that a philosopher is surround with
- We make sure the process requests the `lower` id fork before the `higher` id fork to avoid deadlocks
- Identify which fork (left or right) is the lower id fork and request in that order (i.e. first left then right
first right then left) - Make sure mutex’s are held until forks are released

```
class DiningPhilosophers {
private static ReentrantLock[] mutex = new ReentrantLock[] {
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
};
public DiningPhilosophers() {
}
// call the run() method of any runnable to execute its code
public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
int left = philosopher;
int right = (philosopher-1) == -1 ? 4 : philosopher-1;
if (Math.min(left, right) == left) {
DiningPhilosophers.mutex[left].lock();
DiningPhilosophers.mutex[right].lock();
pickLeftFork.run();
pickRightFork.run();
} else {
DiningPhilosophers.mutex[right].lock();
DiningPhilosophers.mutex[left].lock();
pickRightFork.run();
pickLeftFork.run();
}
eat.run();
putLeftFork.run();
putRightFork.run();
DiningPhilosophers.mutex[left].unlock();
DiningPhilosophers.mutex[right].unlock();
}
}
```

]]>