joshmomel/algoexpert_ts

Algoexpert Solutions

algoexpert_ts's Issues

Thoughts on question `nonConstructibleChange`

Task

As shown below, we need to find out the non-Constructible Change from giving list of coins

How to approach?

1. 🐨 Sort

It makes sense to sort an array when we deal with array questions.

start from short array

let's consider a single array [number] (number from 1 to infinity)
In this case, it will return 1 or number + 1

let's consider array [1,2]
It can generate:
[1] -> 1
[1, 2] -> 1, 2, 3

2. 🐨 Let's consider array [1,1,2,3,5]

from	to	range
[1]	1	[1]
[1, 1]	1, 2	[1, 2]
[1, 1, 2]	1, 2, 2+1, 2+2	[1, 4]
[1, 1, 2, 5]	1, 2, 3, 4, ..., 5, 5+1, 5+2, .. , 9(5+4)	[1, 9]
[1, 1, 2, 5, 7]	1, 2, 3, 4, ..., 7, 7+1, ..., 16(7+9)	[1, 16]
[1, 1, 2, 5, 7, 22]	1, 2, 3, 4, ..., 16, 22, 22+1 🤔 Wait! 17 is missing	[1, 9]

3. 💰Findings

1. we sum up list from smallest [1, ..., sum]
2. the last element in the list shouldn't larger than the sum + 1

Thoughts on question removeDuplicatesFromLinkedList

Task 🗒️

This task is to remove the duplicate node in the Linked list

How to approach? 🔢

💰 In general, most tasks related to Linked list are about altering node.next.

In this task, we also need to come up with an approach to alter node.next, which ensures node.value NOT equal to node.next.vale

Example

1 -> 1 -> 1 -> 2 -> 3 => 1 -> 3

So, it's not hard to think that we need an loop

while(...) {
  if(!valueDuplicated) {
	...
  } else {
	`alter node.next`
  }
}

The trick

💬 We can look ahead

But how?

Instead of checking linkedlist is null as the while loop condition like below

  while (currentNode) {
	let nextNode = currentNode.next
    while(currentNode.value === nextNode.value) {
		nextNode = currentNode.next
  	}
	currentNode.next = nextNode
 	currentNode = nextNode
  }

We can check the next node like below

  const list: Array<number> = [linkedList.value];
  let pointer = linkedList

  while (pointer.next) {
    const v = pointer.next.value;
	...
    pointer.next = pointer.next.next

  }

Summary

In summary, by looking ahead, pointer only move to the right place instead moving one by one. However, both approach have same complexity

Thoughts on question Permutations

Task 📖

Get the array of all permutations. i.e.
[1,2,3] => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

How to approach? 🔢

**Let's start from some simple cases **
0 numbers [] => [] total = 0
1 numbers [1] => [1] total = 1
2 numbers [1,2] => [1,2] [2,1] total = 2 * 1 = 2
3 numbers [1,2,3] => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] total = 3 * 2
n numbers [1,2,3...n] => [...] total = n * total(n-1)

details
[1,2] can be seen as 2 insert into all positions of [1] (in the front and back) => [1,2] [2,1]
[1,2,3] can be seen as 3 insert into all positions of the Permutations [1,2], which includes
- 3 insert into all positions of [1,2] => [3,1,2],[1,3,2],[1,2,3]
- 3 insert into all positions of [2,1] => [3,2,1],[2,3,1],[2,1,3]

Coding

As discussed above, we can build the permutation from [].

let's assumed that we need to find the permutation of [1,2,3..n]

Sudo code can be

for eachNumber in n:
	insert eachNumber into all positions of Permutation of [1..n-1]