theprimeagen / kata-machine Goto Github PK

Little confused here I have the same code in the lesson for BubbleSort but it's not modifying the array. Does anyone see something missing?

This passes the tests, but as it's different from the solution presented in the course, I'm not sure that my solution preservers the O(√n) time complexity.

export default function two_crystal_balls(breaks: boolean[]): number {
    const max = Math.floor(breaks.length / Math.sqrt(breaks.length));
    let low = 0;

    for (let i = 0; i < max; i++) {
        const high = low + Math.floor(Math.sqrt(breaks.length));

        if (!breaks[high]) {
            low = high + 1;
            continue;
        }

        for (let j = low; low < high; j++) {
            if (breaks[j]) {
                return j;
            }
        }
    }

    return -1;
}

Not sure if this is the right place to raise this but FrontendMasters suggested raising an issue in the repo.

In the Pseudo Code Binary Search lesson, shouldn't the else if condition specify n > v rather than v > m, where n = needle, v = value at midpoint, m = midpoint?

Thanks!

Hello, this is my first github issue and account so I don't know if I'm doing anything right.

You can just return from insertAt() when implementing a doubly linked list and pass, so I never know if I've implemented it correctly.

Hi!
That's not actually an issue, just want to share - I rewrote (not fully actually) this kata machine on Golang https://github.com/nacknime-official/kata-machine-go

Just contributing to opensource, you know.
Must to say that generics in Go is quite a pain in the ass, but anyways :)

If anyone is interested in helping to rewrite other DSA in Go - you are welcome :)

While running yarn generate there is error found
After I have cloned the code from github and run yarn install
Anyone can clarify and show me the steps

obviously it would be stupid to name a project some random name without it being an initialism.
this issue is just to document what that initialism is

I think with only one counter (i) it will be more easy to get the logic, and less memory used.
Looks like works in the same way...

export default function two_crystal_balls(breaks: boolean[]): number {
    const jump = Math.floor(Math.sqrt(breaks.length));

    let i = 0;

    for (; i < breaks.length; i += jump) {
        if (breaks[i]) break;
    }

    for (i -= jump + 1; i < breaks.length; i++ ){
        if (breaks[i]) return i;
    }

    return -1;
}

Hello,

When I tried to test the search linear algorithm by running the command npx jest Linear, I received the error message

Cannot find module '@code/LinearSearchList' or its corresponding type declarations.

Just wanted to check how BFS solution would look like, but it is much more convoluted :sad_pepe:

import Queue from "./Queue";

export default function compare(
  a: BinaryNode<number> | undefined,
  b: BinaryNode<number> | undefined,
): boolean {
  const queue = new Queue<
    [BinaryNode<number> | undefined, BinaryNode<number> | undefined]
  >();
  queue.enqueue([a, b]);

  while (queue.length) {
    const curr = queue.deque();
    if (!curr) {
      continue;
    }

    if (curr[0] === undefined && curr[1] === undefined) {
      continue;
    }

    if (curr[0] === undefined || curr[1] === undefined) {
      return false;
    }

    if (curr[0].value !== curr[1].value) {
      return false;
    }

    queue.enqueue([curr[0].left, curr[1].left]);
    queue.enqueue([curr[0].right, curr[1].right]);
  }
  return true;
}

In the linked list, or queue implementation you have two lines like this.

this.tail.next = node
this.tail = node

I can't get my head around this.

surely this.tail.next gets blown away by the next line where we're setting this.tail

FAIL src/tests/LinearSearchList.ts
● Test suite failed to run

src/day2/LinearSearchList.ts:1:76 - error TS2355: A function whose declared type is neither 'void' nor 'any' must return a value. 

Hello, I keep running into this error every time I run yarn generate

yarn run v1.22.19
$ ./scripts/generate
'.\scripts\generate' is not recognized as an internal or external command,
operable program or batch file.
error Command failed with exit code 1.

The error above is preventing the days folders from been generated.

Is this specific to my machine? I'd be glad if I could get a pointer on how to fix this.
Thank you

If true happens right at one of the jump points the current solution will return -1

test("two crystal balls", function () {
    const data = [
        false,
        false,
        false,
        true,
        true,
        true,
        true,
        true,
        true,
        true,
    ];
    const idx = 3;
    expect(two_crystal_balls(data)).toEqual(idx);
    expect(two_crystal_balls(new Array(821).fill(false))).toEqual(-1);
});

We just need to modify the second loop in TwoCrystalBalls.ts like this

for (let j = 0; j < jmpAmount + 1 && i < breaks.length; i++, j++) {
        if (breaks[i]) return i;
    }

Hi there, would you mind also adding in the solutions for when one is stuck? I.e. the Tries were never implemented in the course. Cheers

Hey I'm wondering if anyone has a solutions branch. I'm following along in the video but something won't pass.
Would be nice to copy paste and read the code after to understand.

When I run the npx jest Heap one test suite fails and says:
error TS2355: A function whose declared type is neither 'void' nor 'any' must return a value.

12     delete(): number {
                 ~~~~~~

Test Suites: 1 failed, 1 total

I can't find the error and every function that has to return a value returns a value. And delete is not even on line 12.

This is my code:

export default class MinHeap {
  public length: number;
  private data: number[];


  constructor() {
    this.data = [];
    this.length = 0;
  }

  insert(value: number): void {
    this.data[this.length] = value;
    this.heapifyUp(this.length);
    this.length++;
  }

  delete(): number {
    if (this.length === 0) {
      return -1;
    }

    const out = this.data[0];
    this.length--;

    if (this.length === 0) {
      this.data = [];
      return out;
    }

    this.data[0] = this.data[this.length];
    this.heapifyDown(0);
    return out;
  }

  private heapifyDown(idx: number): void {
    const Lidx = this.leftChild(idx);
    const Ridx = this.rightChild(idx);

    if (idx >= this.length || Lidx >= this.length) {
      return;
    }

    const lV = this.data[Lidx];
    const rV = this.data[Ridx];
    const v = this.data[idx];

    if (lV > rV && v > rV) {
      this.data[idx] = rV;
      this.data[Ridx] = v;
      this.heapifyDown(Ridx);
    } else if (rV > lV && v > lV) {
      this.data[idx] = lV;
      this.data[Lidx] = v;
      this.heapifyDown(Lidx);
    }
  }

  private heapifyUp(idx: number): void {
    if (idx === 0) {
      return;
    }

    const p = this.parent(idx);
    const parentV = this.data[p];
    const v = this.data[idx];

    if (parentV > v) {
      this.data[idx] = parentV;
      this.data[p] = v;
      this.heapifyUp(p)
    }
  }

  private parent(idx: number): number {
    return Math.floor((idx - 1) / 2);
  }

  private leftChild(idx: number): number {
    return idx * 2 + 1;
  }

  private rightChild(idx: number): number {
    return idx * 2 + 2;
  }
}

https://frontendmasters.com/courses/algorithms/implementing-two-crystal-balls/
In minute 5 (-1:58) somebody made a great question:

"Why don't we use ∛N instead of √N since it is smaller ?"

Prime responds that the jumps would be smaller so then we would be doing more jumps. But this goes against big O notation, If N gets infinitely bigger, it seems to be better to do more (smaller) jumps so that we can then do a smaller linear search.

Maybe my "wording" is confusing but simply put:

∛N < √N
☝️ which means that O(∛N) is more efficient (according to Big O Notation) than O(√N)

And for the same reasons:
O(∜N) is better than O(∛N)

So maybe we need to write:

$$\lim_{x\to \infty} \sqrt[x] N$$

But this is also nonintuitive to me: the bigger the root base, the lower the jumps will be (until we have jumps of 1 or less than one), which means that we are doing ... a linear search.

I guess that my doubt is how we should write the big O notation of this problem, and if the answer is O(√N), then "Why don't we use ∛N instead of √N?"

Maybe this helps visualize the relationship between N and the steps the algorithm will do. (Remember that we do discrete steps, on the Y axis 1,5 doesn´t exist, we are traversing an array so we are in position 1 or 2).

Hi!
From the course I understood that ring buffer should have set capacity, and then it may resize while inserting. In the test for ring buffer there the buffer is initialized without arguments. Am I missing something or is it a mistake?

I wrote a manual test to investigate this algo better since I found it very interesting.

This test fails and returns -1

test("custom test", () => {
    const data = [
        false,
        false,
        false,
        false,
        false,
        false,
        false,
        false,
        false,
        true,
        true,
        true,
    ];
    expect(two_crystal_balls(data)).toEqual(9);
});

The way I've found to make it pass was considering the extra/last step like:

// Note the `j <= jumpAmount` instead of ` j < jumpAmount`
for (let j = 0; j <= jumpAmount && i < breaks.length; ++j, ++i) {
    if (breaks[i]) {
        return i;
    }
}

Keeping that <= condition still passes the other default tests from Prime. Removing it will break my test case. Am I right or am I missing something?

Description

While generating your first day's katas, the generate script will run into an error in the following code block due to there being no found "day" directories, and then trying to access the 0'th index of the array containing these "day" directories.

// scripts/generate

day = +fs.readdirSync(src_path).
        filter(i => i.includes("day")).
        sort((a, b) => {
            return +b.substring(3) - a.substring(3);
        })[0].substring(3) + 1;

Proposed Solution

Wrote this up right quick. You can ditch the whole try catch block now.

// scripts/generate

const previousDayDirs = fs
    .readdirSync(src_path)
    .filter(dirName => dirName.includes("day"));

const day = previousDayDirs.length
    ? previousDayDirs.sort((a, b) => (
        +b.substring(3) - a.substring(3)
    ))[0].substring(3) + 1
    : 1;

Generated the day1 and added the LinearSearchList algo.While running the command "npx jest Linear", got this issue

FAIL ../tests/LinearSearchList.ts
● Test suite failed to run

../__tests__/LinearSearchList.ts:1:23 - error TS2307: Cannot find module '@code/LinearSearchList' or its corresponding type declarations.

1 import linear_fn from "@code/LinearSearchList";

I was thinking if we could solve the Two crystal ball with different appraoch.
What if we split the main array into 3 halves and treat the problem similar to binary search, and something like tertiary search.

This will work on time complexity log(n) with base 3
Logic:

Code:

export default function two_crystal_balls(breaks: boolean[]): number {
    let low = 0
    let high = breaks.length;

    do {
        const firstTertile = low + Math.floor((high - low) / 3);
        const secondTertile = low + Math.ceil((high - low) * 2 / 3);

        if (breaks[firstTertile]) {
            high = firstTertile;
        } else if (breaks[secondTertile]) {
            low = firstTertile + 1;
            high = secondTertile;
        } else {
            low = secondTertile + 1;
        }
    } while (low < high)

    return breaks[low] ? low : -1;
}

@ThePrimeagen What is your thought on the appraoch?

DoublyLinkedList (as well as all the other list types) don't have any testing for the function insertAt. Also, a few of the other functions could be tested more thoroughly. I added some tests to the file on a branch and could make a PR if I were given permission; otherwise, here's the updated file:

export function test_list(list: List<number>): void {
    list.append(5);
    list.append(7);
    list.append(9);

    expect(list.get(2)).toEqual(9);
    expect(list.removeAt(1)).toEqual(7);
    expect(list.length).toEqual(2);
    expect(list.get(1)).toEqual(9);

    list.append(11);
    list.append(15);
    expect(list.removeAt(1)).toEqual(9);
    expect(list.remove(9)).toEqual(undefined);
    expect(list.removeAt(0)).toEqual(5);
    expect(list.removeAt(1)).toEqual(15);
    expect(list.removeAt(0)).toEqual(11);
    expect(list.length).toEqual(0);

    list.prepend(5);
    list.prepend(7);
    list.prepend(9);

    expect(list.get(2)).toEqual(5);
    expect(list.get(0)).toEqual(9);
    expect(list.remove(9)).toEqual(9);
    expect(list.length).toEqual(2);
    expect(list.get(0)).toEqual(7);

    list.insertAt(10, 0);
    list.insertAt(13, 2);
    list.insertAt(1, 4);

    expect(list.get(0)).toEqual(10);
    expect(list.get(1)).toEqual(7);
    expect(list.get(2)).toEqual(13);
    expect(list.get(3)).toEqual(5);
    expect(list.get(4)).toEqual(1);
    expect(list.insertAt(6, 6)).toEqual(undefined);
    expect(list.length).toEqual(5);
}

It's a win 11 machine
running day cmd works though it generates new day

I'm following your course (thanks for it, it's helping me a lot), and I'm following the implementations along and, while doing the pop() method for the Stack class, I got stuck with the proposed implementation and, I came up with this implementation instead, that passed your tests:

pop(): T | undefined {
        if (!this.head) {
            return undefined;
        }
        this.length--
        const temp = this.head
        this.head = this.head.prev
        
        return temp.value
    }

What would be the difference with yours? Am I missing something? Thank you :)

Not sure where else to put this, follow suite of previous poster with regards to problems with the code in the class. I'm referring to the Doubly Linked List video "Linked list: remove, get, & removeAt".

At 1:52 ThePrimeagen takes a question about the last block of the insertAt method. You demonstrate correcting A to B
A)

if (curr.prev) {
    curr.prev.next = curr;
}

B)

if (node.prev) {
    node.prev.next = curr;
}

Shouldn't the assignment be node.prev.next = node?

Apologies if this is the wrong place to post this question!

I implemented merge sort. However, it would not pass the test my code is below. I change the return output of merge_sort from a void to a numbers array.

function merge(arr1: number[], arr2: number[]): number[] {
    let results = [];
    let i = 0;
    let j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr2[j] > arr1[i]) {
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j]);
            j++;
        }
    }

    while (i < arr1.length) {
        results.push(arr1[i]);
        i++;
    }

    while (j < arr2.length) {
        results.push(arr2[j]);
        j++;
    }

    return results;
}

export default function merge_sort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;

    let mid = Math.floor(arr.length / 2);

    let left = merge_sort(arr.slice(0, mid));
    let right = merge_sort(arr.slice(mid));

    return merge(left, right);
}

The original stub of code.

export default function merge_sort(arr: number[]): void {

}

I changed the test code from this

import merge_sort from "@code/MergeSort";

test("merge-sort", function () {
    const arr = [9, 3, 7, 4, 69, 420, 42];
    expect(arr).toEqual([3, 4, 7, 9, 42, 69, 420]);
});

To this and it passed.

import merge_sort from "@code/MergeSort";

test("merge-sort", function () {
    const arr = [9, 3, 7, 4, 69, 420, 42];
    const val = merge_sort(arr);
    expect(val).toEqual([3, 4, 7, 9, 42, 69, 420]);
});

I am not sure if the test is wrong or if my implementation is incorrect.

In the image:

In the code block -

deque(): T | undefined {
        if (!this.head) {
            return undefined;
        }

        this.length--;

        const head = this.head;
        this.head = this.head.next;

        head.next = undefined;

        return head.value;
    }

If the queue length is 1 and we dequeue the element, the tail will still point to the last element as we're not setting it to anything in the above deque function.

Now, if we enqueue another element:

• the head will be undefined as this.tail already exists and enqueue() will not set the head to any value.Attaching enqueue function code for reference:

enqueue(item: T): void {
        this.length++;

        const node = { value: item } as Node<T>;
       
       // below condition will be false after dequeueing the last element
        if (!this.tail) {
            this.tail = this.head = node;

            return;
        }

        this.tail.next = node;
        this.tail = node;
    }

• Now if you peek head, it will give undefined instead of last inserted element. The test written in src/__tests__/Queue.ts was also failing because of this issue.

Proposed solution:

Add this condition in dequeue function:

if (this.length === 1) {
            this.tail = this.head?.next
        }

I'm used to the Java type implementation of a LinkedList, with an inner private class named Node, and with the first property being of such type.

In this example, in TS, we're getting a generic type T, but this one does not have defined a property called next or previous.

Should we update the T type generic to extend from another interface that defined all the properties of a Node?

Does anyone have a working example of how the Single and Double LinkedList can be implemented using this TS boiler code?

Hi, this is not an issue, but more of an asking for help. I tried to implement the Doubly Linked List. However, I can't manage to pass the tests. Also, It's my first time working with typescript, and I'm finding it very frustrating at moments with types, nulls and so on. So I would like to ask if someone has a full implementation of the Doubly Linked List. I saw many implementations throughout GitHub and internet, but I want one that is specific to the course.

When I was comparing the solution presented in the Course to the solution I had come up with I noticed the second for loop was possibly excluding a value that needs to be checked (j < jmpAmount instead of j <= jmpAmount). For example, let's say jmpAmount is 3, if the first time you jump by 3 you meet the first floor for which the ball would break, you would then exit the loop go back 3 to index 0 then loop from 0 to 2 (because j < jmpAmount) never encountering the actual answer.

I coded my solution in C to challenge myself a bit and decided to make the problem a bit more fun by making the array have different breaking points (int) for each floor and then also passing the breaking point value of both crystal balls. Here's my code:

int two_crystal_balls(int* stories, int length, int breaking_point) {
  int jump = sqrt(length);
  int floor = -1;
  int i = jump;
  for (; i < length; i+=jump) {
    if (stories[i] >= breaking_point) {break;}
  }
  i -= jump;
  for (int j = 0; j <= jump; j++) {
    if (stories[i + j] >= breaking_point) {
      floor = i + j;
      break;
    }
  }
  return floor;
}

Hi @ThePrimeagen and folks,

I really appreciate your passionable cource.
By the way, I may found a bug in BFS Graph Matrix.
As for the BFSGraphMatrix function bfs, if arguments of source and needle are same number, it returns null. But I think it should return the exact number in array.

I mean for example,

// src/day1/DFSGraphList.ts
bfs(matrix, 1, 1)) // expected output  [1], but got null;

To solve this bug, I think the code should be modified like below.

- if (prev[needle] === -1) {
-     return null;
- }

+ if (prev[needle] === -1 && source !== needle) {
+    return null;
+}

Also the test like below should be added .

// src/__tests__/BFSGraphMatrix.ts
expect(bfs(matrix2, 0, 0)).toEqual([0]);

Hi there,

Just want to share implementation of this repo but in python: https://github.com/Andrei-Aksionov/TheLastAlgorithmsCourseYouWillNeed

Basically the same drill: implement algorithm, run tests. Stuck and don't know how to implement - check answers branch.

Don't know how relevant it is to anyone who visits this repo, still hope that someone finds it helpful.

After forking, cloning, and following the guide in the readme, when getting to the yarn generate step this is returned

$ yarn generate yarn run v1.22.19 $ ./scripts/generate '.\scripts\generate' is not recognized as an internal or external command, operable program or batch file. error Command failed with exit code 1. info Visit https://yarnpkg.com/en/docs/cli/run for documentation about this command.

Is there something missing in the readme ?

yarn version 1.22.19
node version 16.5.0