YozhEzhi

Владей собой среди толпы смятенной, 
Тебя клянущей за смятенье всех, 
Верь сам в себя, наперекор вселенной, 
И маловерным отпусти их грех; 
Пусть час не пробил - жди, не уставая, 
Пусть лгут лжецы - не снисходи до них; 
Умей прощать и не кажись, прощая, 
Великодушней и мудрей других. 
Умей мечтать, не став рабом мечтанья, 
И мыслить, мысли не обожествив; 

YozhEzhi

Median Maintenance algorithm implementation using TypeScript / JavaScript

The median maintenance problem is a common programming challenge presented in software engineering job interviews.

In this lesson we cover an example of how this problem might be presented and what your chain of thought should be to tackle this problem efficiently.

Lets first refresh what is a median

• The median is the middle element in the sorted list

YozhEzhi

Minimum / Maximum Maintenance algorithm implementation using JavaScript / TypeScript

How can you most efficiently maintain the lowest value in a list of items. How about maintaining the largest value?

In this lesson we cover a naïve solution to this problem followed by an efficient solution that utilizes a data structure we have already covered before.

• Assume that you are given numbers slowly one by one.
• And at any point you can be asked to give numbers back in an ascending order.

`
You are given numbers slowly

YozhEzhi

Implement the Heapsort algorithm using TypeScript / JavaScript

Once you are familiar with the Heap data structure, a number of programming challenges can magically become super simple. Sorting is just one of those challenges.

In this lesson we cover the heap sort algorithm, why is it called heap sort and how to implement it using JavaScript / TypeScript.

• Consider a simple array of numbers 9 4 2 7 5 3
• Our task is to sort these in ascending order. We can simplify this task as simple repeated extractions of the minimum item from the set.
• If we do that we get the sorted result 2 3 4 5 7 9 in ascending order.

YozhEzhi

Max items and max height of a completely balanced binary tree

A balanced binary tree is something that is used very commonly in analysis of computer science algorithms. In this lesson we cover how to determine the Maximum number of items it can accommodate.

We follow this with a discussion on the maximum height of a binary tree given we need to accommodate n items.

• Consider a perfectly balanced binary tree. In such a tree we never add items to a new level until all the positions in the previous level are filled up.
• We can easily and intutively determine the number of items at a given level as a power of two.
• Level 0 as only 1 item
• Level 1 has 2 items

YozhEzhi

Implement the heap data structure using JavaScript

Heap is a data structure that can fundamentally change the performance of fairly common algorithms in Computer Science.

The heap data structure is called a heap because it satisfies the heap property. The heap property states, that if P is a parent node of C, then the value of node P is less than the value of node C.

In this lesson we discuss the key operations of the Heap data structure along with their performance. We then implement the data structure using TypeScript / JavaScript.

• Here we have a graph of nodes A,B,C,D,E
• Its nice to have a mental model of a heap as a complete binary tree.
• This tree would satisfy the heap property if A is less than its children B and C Similarly B is less than its children D and E.

YozhEzhi

Parse a string to an integer

A common interview question is to write
 a
function
that
converts
 a
 string
into
an
integer e.g. "123" => 123.
 This
 function 
is commonly
 called
 atoi because
 we
 are
 converting
 an
 ASCII
 string
 into 
an 
integer.

In this lesson we cover the proper way to do this in JavaScript which is parseInt along with implementing it using basic ascii math.

A common interview question is to write a function that takes a string and parses it into its integer value. e.g. the string "123" to the integer 123

We start by creating our atoi function that takes a string and returns a number.

YozhEzhi

LinkedList is made of a bunch of nodes that point to the next one in the list. Every node in a LinkedLists has two properties, the value of whatever is being store and a pointer to the next node in the list.

LinkedLists have their ups and downs. On one hand, adding and removing is a breeze: you just have the change the next pointer on the previous node and that's it. Getting is a pain though: if .get is called you have to loop through the nodes until you get to the right node. And that's the tradeoff between LinkedList and ArrayList: LinkedList's adds and deletes are O(1) but the gets are O(n); ArrayList's adds and deletes are O(n) but the gets are O(1). So which one is better? It depends! If you're doing a bunch of adds and deletes but not many gets, stick to LinkedLists. Doing a bunch of gets? ArrayLists. Both? You decide!

YozhEzhi

Implement a singly linked list in TypeScript

In a singly linked list each node in the list stores the contents of the node and a reference (or pointer in some languages) to the next node in the list. It is one of the simplest way to store a collection of items.

A linked list is simply, a list of nodes. Each node has a value, and a link to a next node in this list, till we arrive at the end of the list where next will be undefined.

node {value,next} -> node {value,next} -> undefined

YozhEzhi

Queue implementation using TypeScript

A queue is an abstract data type that serves as a collection of elements, with two principal operations: enqueue, which adds an element to the collection, and dequeue, which removes the earliest added element. The order in which elements are dequeued is First In First Out aka. FIFO. The term queue takes it name from the real world queues e.g. "a queue at the ticket counter". A good target is to implement these operations with a time complexity of O(1).

We could naively, implement it using a JavaScript array.