kata-machine's People
Forkers
mgdotdev hacksore nartc paulber33 farhanmobashir zestsystem ptsoup nikhilkuyya-workshop-fork-for-learning prowlinglynx adamxrodriguez ohmyjersh g94angel mocktech ernestweems nip10 rasendragori lin-dev devhusnain mrabaney-nikoandco pluppen masoodgit rohankokane chadelofson dantraztrev j-mad-08 typeerrordev bortolottidev adambremholm daltondiaz jkarage felixfrz bishwajitdey itslewisndungu paul-ciorogar thecornisians iamcuriousdeveloper vijaygenius123 omar2205 rbaumgardner93 jesseokeya thenathanlovell ricardoaguiar sisi-in-tech akogit simon-rad codesolomon ohansfavour krosvick ryanohcodes edevars adepeju4 ruthv1k tch4lla michaelpachec0 thafishdance chann44 gregnicholas german-dev jesusdoza helpme-pls ttrei bumpylumps codestafa daniel-hampton adamdilger lnhunt11 javigong abubakrilaitan ramlis1 knudtty oreillyross c-ehrlich juukohenry13 nathanmackeans liliyavoloshina miqvo webmekanic abrahamterfie abisola-morohunfolu huff-and-martin diegochappedelaine sazzy-josh nick-cb dhhz19 enslinn8 doms jmontinard kathalysth aleemaheer ravilmc cnov20 djbedford moaboabdo zohebshaikh samji smartinsantos rakicodes bkimmm hamidify bitgeek29kata-machine's Issues
Kata machine in Python
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.
tail not getting set to undefined when queue.length === 1 in dequeue() function
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
asthis.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 insrc/__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
}
No tests for insertAt for lists
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);
}
TwoCrystalBalls: doing jumps of ∛N (or any other root base)
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:
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).
Pseudo Code Binary Search lesson: v > m
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!
Doubly Linked List implementation?
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.
npx jest Bubble test keeps on running
Test suite fail with MinHeap
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;
}
}
Lig-Machine hasn't currently documented the complex initialism that defines it's name
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
generate from scripts is not working , and @code path is showing error in test , in config file the path for code is day2 i dont know why
FrontEndMasters Demonstration Doubly Linked List insertAt issue
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!
TwoCrystalBalls Solution Edge Case
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;
}
Question: Linked list implementation
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
Yarn generate fails
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
Kata machine for Golang
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 :)
Generate Script > Cannot read properties of undefined (reading 'substring')
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;
Why not simplify TwoCrystalBalls to this?
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;
}
Off by one error in Two Crystal Ball Solution?
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;
}
TwoCrystalBalls: Different appraoch
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?
yarn generate returns an error
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
Adding solutions?
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
BubbleSort not working like the lesson
Implementation code for Single and Doubly LinkedList?
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?
Shouldn't ring buffer test init ring buffer object with capacity as an argument?
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?
Derivation/Proof for square root of n in Two Crystal Ball problem
Two Crystal balls failing for a custom test
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?
correct implementation of insertAt() is not checked, for doubly linked list
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.
Running the day1 LinearSearchlist, test suit failed to run
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";
Is this a valid solution to the Two Crystal Balls problem?
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;
}
BFS Graph Matrix bug?
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]);
My Merge Sort impl would not pass the test?
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.
what must be the issue here?
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.
What about this implementation of pop() for Stack?
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 :)
Compare Binary Trees BFS solution
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;
}
Cannot find module '@code/LinearSearchList'
Solutions
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.
Error
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
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.