DEV Community: Masaki Fukunishi

Crypto Chart: Full-Stack MERN App

Masaki Fukunishi — Sat, 09 Sep 2023 18:15:26 +0000

Demo

https://crypto-chart-1r7g.onrender.com

GitHub Repository

https://github.com/masakifukunishi/crypto-chart

Summary

Crypto Chart is a full-stack MERN app that lets users view candlestick charts of cryptocurrencies for selected asset pairs and periods.

About Settings

Data is retrieved every 8 hours from Cryotowatch
You can change the exchange and the asset pairs by changing the settings in config/default.json
Only UTC Time Zone is supported for now

Motivation

Demonstrating my development skills

This app is built using TypeScript for the language, React and Redux for the frontend, Tailwind CSS for styling, and Express with Node.js for the backend. Additionally, I've implemented batch processing using node-cron. I believe this project effectively demonstrates my skills.
Expandable and Practical

While the app currently offers basic functionality, there is potential to enhance its practicality by incorporating features such as acquiring candlestick data for shorter periods, integrating technical indicators, and more.

Language and Libraries

TypeScript
React
Redux, Redux Toolkit
Tailwind CSS
Express
Node.js
MongoDB (mongoose)
ApexCharts
node-cron
Vite

React

Data fetching from the backend in React is facilitated using custom hooks, making it explicit when the API is called.

Redux

The selected asset pair and period are stored in the Redux store. Upon accessing the home screen, configuration and constant data are fetched from the server side and stored in Redux.

MongoDB

MongoDB is employed to store OHLCV data obtained from the Cryptowatch API and provide it upon server request.

ApexCharts

ApexCharts is utilized for rendering candlestick and volume charts.

node-cron

node-cron is employed to regularly retrieve OHLCV data from the Cryptowatch API and store it in MongoDB.

Vite

Vite is the tool used for building the frontend.

Architecture

How to run

1. Clone this repository

2. Install dependencies

npm install

3. Set environment variables

cp .env.example .env

MONGODB_URI is the URI of the MongoDB database to be used.

4. Set config

If you want to change the exchange and the asset pairs, change the settings in config/default.json.

{
  "cryptowatch": {
    ...
    "exchange": "bitfinex",
    "baseAsset": "usd",
    "quoteAssets": ["btc", "eth"],
    ...
  }
}

/config/default.json

5. Run batch processing to register initial ohlcv data

npm run dev-batch-init

Thank you!

6. Run frontend and backend

npm run dev

How to build

1. The same as 1-5 of 'How to run'

2. Build frontend and backend

npm run build

3. Run the built app

npm run start

About this app, if you have any opinions or feedback, please contact the following:

fmsknn@gmail.com

Understanding Tree: Features, Time Complexity, Difference between BFS and DFS

Masaki Fukunishi — Thu, 17 Aug 2023 19:03:29 +0000

This article is based on a course in the following repository.
https://github.com/cookie777/altgorithm-data-structure-crash-course/blob/main/tree.md

What is Tree?

A tree is Graph with no cycles

- Nodes :V

- edges : V - 1

Why Tree?

Tree usages

- Hierarchical relationships

- Manage sorted data

- Enable fast searching operations

Terms

Root

The topmost node that has no parent.

Parent

A node that is connected directly above another node in the hierarchy.

Children

A node that is connected directly below another node in the hierarchy.

Ancestor

A node that is connected above another node in the hierarchy.

Descendent

A node that is connected below another node in the hierarchy.

Siblings

A node that has the same parent as another node.

Leaf

A node that has no children.

Depth

The number of edges from the root to the node.

Height (max Depth)

The number of edges from the node to the deepest leaf.

Type of trees

Binary Tree
- Variations Different Types of Binary Tree with colourful illustrations
- Binary Search Tree (BST)
Ternary Tree
N-ary Tree

How do we represent trees?

Using Nodes

A tree is composed of nodes, and each node has pointers to its child nodes. Each node can have multiple children, and the tree structure is defined by the connections between nodes.

Using an Array

A tree can also be represented by an array. The root node is the first element in the array. The next two elements of the array represent the children of the root node. The next four elements of the array represent the four children of the two nodes directly above them. This pattern continues throughout the array.

Traversal Algorithm

Depth-First Search (DFS) Algorithm

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

Breadth-First Search (BFS) Algorithm

BFS is a traversal algorithm that visits all the nodes at the current depth level before moving to nodes at the next depth level.

Tree Traversal

Achieved by DFS

Pre-Order
- 1st time you visit
- "Root", Left, Right
In-Order
- 2nd time you visit
- Left, "Root", Right
Post-Order
- 3rd time you visit
- Left, Right, "Root"

https://www.youtube.com/watch?v=WLvU5EQVZqY

Achieved by BFS

Level-Order

Analytics

Say if we have a simple request to traverse all Nodes of the tree. The order doesn't matter. What would be the complexity in terms of time and space?

Let's assume the number of all nodes are n first.
You can use h as a height of the tree for DFS too.

DFS

Time O(n)
- Since all nodes are visited only once
Space (h)
- In the worst case, the DFS call stack can grow to the height of the tree as you traverse from the root to a leaf.

BFS

Time O(n)
- Since all nodes are visited only once
Space (N/2) -> O(n)
- In the worst case, the queue can grow to store all the nodes in one level of the tree.
- For a balanced tree, the last node in the hierarchy is the total number of nodes in the previous hierarchy + 1

4 Types of Tree Traversal Algorithms

Exercise1

dfs

https://leetcode.com/problems/path-sum/

const hasPathSum = (root: TreeNode | null, targetSum: number): boolean => {
  const dfs = (root: TreeNode | null, currentSum: number): boolean => {
    if (root === null) return false;
    if (root.left === null && root.right === null) {
      return currentSum + root.val === targetSum;
    }
    return dfs(root.left, currentSum + root.val) || dfs(root.right, currentSum + root.val)
  };
  return dfs(root, 0);
};

https://leetcode.com/problems/binary-tree-inorder-traversal/

const inorderTraversal = (root: TreeNode | null): number[] =>{
  const result: number[] = [];
  const traverse = (node: TreeNode | null) => {
    if (node === null) return;
    traverse(node.left);
    result.push(node.val);
    traverse(node.right);
  }
  traverse(root)
  return result
};

https://leetcode.com/problems/maximum-depth-of-binary-tree/

const maxDepth = (root: TreeNode | null): number => {
  let max = 0;
  const dfs = (root: TreeNode | null, currentDepth: number): void => {
    if (!root) {
      max = Math.max(max, currentDepth);
      return;
    }
    dfs(root.left, currentDepth + 1);
    dfs(root.right, currentDepth + 1);
  };
  dfs(root, 0);
  return max;
};

bfs

Queue for BFS

class LinkedListNode {
  val: TreeNode | null;
  next: LinkedListNode | null;

  constructor(val: TreeNode | null = null, next: LinkedListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

class MyQueue {
  private head: LinkedListNode | null;
  private tail: LinkedListNode | null;
  private length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(value: TreeNode) {
    const newNode = new LinkedListNode(value);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      if (!this.tail) throw new Error("Unexpected: The tail is null.");
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  dequeue(): TreeNode | null {
    if (!this.head) return null;
    if (this.head === this.tail) {
      this.tail = null;
    }
    const holdingPointer = this.head;
    this.head = this.head.next;
    this.length--;
    return holdingPointer.val;
  }

  peek(): TreeNode | null {
    if (!this.head) return null;
    return this.head.val;
  }

  size(): number {
    return this.length;
  }
}

https://leetcode.com/problems/minimum-depth-of-binary-tree/

const minDepth = (root: TreeNode | null): number => {
  if (!root) return 0;
  let queue = new MyQueue();
  queue.enqueue(root);
  let depth = 0;

  while (queue.size() > 0) {
    depth++;
    const levelSize = queue.size();
    for (let i = 0; i < levelSize; i++) {
      const currentNode = queue.dequeue();

      if (!currentNode) throw new Error("Unexpected: The node is null.");

      if (currentNode.left === null && currentNode.right === null) {
        return depth;
      }
      if (currentNode.left) {
        queue.enqueue(currentNode.left);
      }
      if (currentNode.right) {
        queue.enqueue(currentNode.right);
      }
    }
  }
  return depth;
};

https://leetcode.com/problems/maximum-depth-of-binary-tree/

const maxDepth = (root: TreeNode | null): number => {
  if (!root) return 0;
  let queue = new MyQueue();
  queue.enqueue(root);
  let depth = 0;

  while (queue.size() > 0) {
    depth++;
    const levelSize = queue.size();
    for (let i = 0; i < levelSize; i++) {
      const currentNode = queue.dequeue();
      if (currentNode.left) {
        queue.enqueue(currentNode.left);
      }
      if (currentNode.right) {
        queue.enqueue(currentNode.right);
      }
    }
  }
  return depth;
};

https://leetcode.com/problems/average-of-levels-in-binary-tree/

const averageOfLevels = (root: TreeNode | null): number[] => {
  if (!root) return [];
  let queue = new MyQueue();
  queue.enqueue(root);
  let results = [];

  while (queue.size() > 0) {
    const levelList = []
    const levelSize = queue.size();
    for (let i = 0; i < levelSize; i++) {
      const currentNode = queue.dequeue();
      levelList.push(currentNode.val)
      if (currentNode.left) {
        queue.enqueue(currentNode.left);
      }
      if (currentNode.right) {
        queue.enqueue(currentNode.right);
      }
    }
    const levelSum = levelList.reduce((acc, val) => acc + val, 0);
    const average = levelSum / levelList.length;
    results.push(average)
  }
  return results;
};

Exercise2

https://leetcode.com/problems/same-tree/

BFS

const isSameTree = (p: TreeNode | null, q: TreeNode | null): boolean => {
  let queueP = new MyQueue();
  let queueQ = new MyQueue();
  queueP.enqueue(p);
  queueQ.enqueue(q);

  while (queueP.size() && queueQ.size()) {
    const currentNodeP = queueP.dequeue();
    const currentNodeQ = queueQ.dequeue();

    if (currentNodeP === null && currentNodeQ === null) {
      continue;
    }

    if (currentNodeP === null || currentNodeQ === null || currentNodeP.val !== currentNodeQ.val) 
    {
      return false;
    }
    queueP.enqueue(currentNodeP.left);
    queueP.enqueue(currentNodeP.right);
    queueQ.enqueue(currentNodeQ.left);
    queueQ.enqueue(currentNodeQ.right);
  }
  return true
};

DFS

const isSameTree = (p: TreeNode | null, q: TreeNode | null): boolean => {
    let result = true;
    const dfs = (node1: TreeNode, node2: TreeNode) => {
        if (!node1 && !node2) return;

        if (node1.val !== node2.val) {
            result = false;
            return;
        }

        dfs(node1.left, node2.left);
        dfs(node1.right, node2.right);
    };
    dfs(p, q);
    return result;
}

https://leetcode.com/problems/balanced-binary-tree/

const isBalanced = (root: TreeNode | null): boolean => {
  if (root === null) return true;
  let res = true
  const getHeight = (node: TreeNode | null): number => {
    if (node === null) return 0;
    if(!res) return;

    const leftHeight = getHeight(node.left);
    const rightHeight = getHeight(node.right);

    if (Math.abs(leftHeight - rightHeight) > 1) {
      res = false
    }
    return Math.max(leftHeight, rightHeight) + 1;
  };
  getHeight(root)
  return res
};

https://leetcode.com/problems/invert-binary-tree/

const invertTree = (root: TreeNode | null): TreeNode | null => {
  if (root === null) {
    return null;
  }
  let queue = new MyQueue();
  queue.enqueue(root);
  while(queue.size()) {
    const currentNode = queue.dequeue()
    // swap
    const temp = currentNode.left;
    currentNode.left = currentNode.right;
    currentNode.right = temp;

    if (currentNode.left) {
      queue.enqueue(currentNode.left)
    }
    if (currentNode.right) {
      queue.enqueue(currentNode.right)
    }
  }
  return root
};

https://leetcode.com/problems/search-in-a-binary-search-tree/
- Try to solve it with O(h): h is the height of the tree

const searchBST = (root: TreeNode | null, val: number): TreeNode | null => {
  if (!root) {
    return null
  } else if (val < root.val) {
    return searchBST(root.left, val)
  } else if (val > root.val) {
    return searchBST(root.right, val)
  } else {
    return root
  }
};

Understanding Queue: Features, Time Complexity, and Implementation

Masaki Fukunishi — Tue, 01 Aug 2023 20:40:11 +0000

This article is based on a course in the following repository.
https://github.com/cookie777/altgorithm-data-structure-crash-course/blob/main/queue.md

What is Queue?

A queue is a data structure that follows the First-In-First-Out (FIFO) principle. It has two main operations.

Enqueue

This operation adds an element to the end of the queue.
Dequeue

This operation removes the first element from the queue.

What is difference between Queue and Array. Pros and Cons

Queue

Pros

Dynamic size
Efficient deletion

Unlike Array, Queue does not have to shift all the elements when deliting an element at the beginning of the queue.

Cons

Random access is not supported

Array

Pros

Random access is supported

Cons

Fixed size
Inefficient deletion

Unlike Queue, Array has to shift all the elements when deliting an element at the beginning of the array.

Can you come up with when to use Queue?

Printer

In a printing system, a queue is used to manage multiple print jobs, ensuring they are printed in the order they were requested.
Asynchronous processing

In applications where tasks can take varying amounts of time to complete, using a queue can decouple task submission from task execution.
Stackable Pencil

In a Stackable Pencil, the first piece inserted into the pencil is the first one to be removed.

Analysis

What is the time complexity of following operations for Queue? Why?
Since they are multiple types of queue, consider a type using linked list.

Basics

enqueue (add an element to the Queue)

O(1)

Adding an element to the last of the queue requires updating only the last pointer, which takes constant time.

dequeue (remove and return an element from the Queue)

O(1)

Removing an element from the first of the queue requires updating only the first pointer, which takes constant time.

peek (return an element from the Queue)

O(1)

Returning an element from the first of the queue is just accessing the first pointer, which takes constant time.

size (get the size of the Queue)

O(1)

Getting the size of the queue is just accessing the size property, which takes constant time.

merge two Queue

O(1)

Merging two queues is just updating the last pointer of the first queue to the first pointer of the second queue, which takes constant time.

Comparison

What if we try to implement Queue with Array instead of Linked List?
What would be the difference?

Memory Usage

Linked lists require additional memory to store pointers for linking elements, while arrays can store elements in a contiguous block of memory.

Dynamic vs. Static Size

Linked lists can grow dynamically without requiring resizing operations, while arrays have a fixed size and require resizing operations when the capacity is exceeded.

Dequeue

Linked lists are more efficient than arrays when deleting an element at the beginning of the queue, since they do not have to shift all the elements.

Exercise

Exercise 01

Let's try to implement your own Queue with using Linked-List!

class ListNode {
  val: number | null;
  next: ListNode | null;

  constructor(val: number | null = null, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

class MyQueue {
  private head: ListNode | null;
  private tail: ListNode | null;
  private length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(value: number) {
    const newNode = new ListNode(value);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      if (!this.tail) throw new Error("Unexpected: The tail is null.");
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  dequeue(): number | null {
    if (!this.head) return null;
    if (this.head === this.tail) {
      this.tail = null;
    }
    const holdingPointer = this.head;
    this.head = this.head.next;
    this.length--;
    return holdingPointer.val;
  }

  peek(): number | null {
    if (!this.head) return null;
    return this.head.val;
  }

  size(): number {
    return this.length;
  }
}

const myQueue = new MyQueue();
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.enqueue(3);
console.log(myQueue.dequeue()); // 1
console.log(myQueue.peek()); // 2
console.log(myQueue.size()); // 2
console.log(myQueue);

Exercise 02

Let's try to solve some leet code questions

https://leetcode.com/problems/number-of-recent-calls/

class LinkedListNode {
  val: number | null;
  next: LinkedListNode | null;

  constructor(val: number | null = null, next: LinkedListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

class MyQueue {
  private head: LinkedListNode | null;
  private tail: LinkedListNode | null;
  private length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(value: number) {
    const newNode = new LinkedListNode(value);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      if (!this.tail) throw new Error("Unexpected: The tail is null.");
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  dequeue(): number | null {
    if (!this.head) return null;
    if (this.head === this.tail) {
      this.tail = null;
    }
    const holdingPointer = this.head;
    this.head = this.head.next;
    this.length--;
    return holdingPointer.val;
  }

  peek(): number | null {
    if (!this.head) return null;
    return this.head.val;
  }

  size(): number {
    return this.length;
  }
}

class RecentCounter {
  private requests: MyQueue;

  constructor() {
    this.requests = new MyQueue();
  }

  ping(t: number): number {
    this.requests.enqueue(t);
    while (this.requests.peek()) {
      const head = this.requests.peek()
      if (!head || head >= t - 3000) {
        break
      }
      this.requests.dequeue();
    }
    return this.requests.size();
  }
}

Understanding Stack: Features, Time Complexity, and Implementation

Masaki Fukunishi — Tue, 25 Jul 2023 19:05:44 +0000

This article is based on a course in the following repository.
https://github.com/cookie777/altgorithm-data-structure-crash-course/blob/main/stack.md

What is Stack?

A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. It has two main operations.

Push

This operation adds an element to the top of the stack.
Pop

This operation removes the top element from the stack.

What is the difference between Stack and Queue?

Stack

Follows the Last-In-First-Out (LIFO) principle, where the last element inserted is the first one to be removed
Queue

Follows the First-In-First-Out (FIFO) principle, where the first element inserted is the first one to be removed.

Can you come up with when to use Stack?

Function call stack

Used in programming languages to manage function calls. When a function is called, its variables and context are pushed onto the stack. When the function finishes, it is popped off the stack, returning control to the previous function.
Browser History

Web browsers use a stack-like structure to store the history of visited web pages. When the user clicks the back button, the most recently visited page is popped from the history stack, enabling navigation to the previous page.
Stacking of dishes

When stacking dishes, the last dish placed on the stack is the first one to be removed.

Analysis

What is the time complexity of following operations for Stack? Why?

Since they are multiple types of stack, consider a type using linked list.

Basics

push (add an element to the Stack)

O(1)

Adding an element to the top of the stack requires updating the top pointer, which takes constant time.

pop (remove and return an element from the Stack)

O(1)

Removing an element from the top of the stack requires updating the top pointer, which takes constant time.

peek (return the element from the Stack)

O(1)

Returning the element from the top of the stack requires accessing the top pointer, which takes constant time.

size (get the size of the Stack)

O(1)

Getting the size of the stack requires just accessing the size property, which takes constant time.

merge two Stack

O(1)

Merging two stacks requires updatting the first stack's bottom pointer to point to the second stack's top pointer, which takes constant time.

Comparison

What if we try to implement Stack with Array instead of Linked List?
What would be the difference?

Dynamic resizing

Since an array has a fixed size, if you exceed the capacity of the array, you need to resize it to accommodate more elements. On the other hand, Linked lists can grow dynamically without requiring resizing operations.
Memory efficiency

Linked lists require extra memory for storing pointers to the next element. This overhead is not present in arrays.
Implementation simplicity

Implementing a stack using an array is often simpler than using a linked list since it doesn't involve managing pointers or dealing with dynamic memory allocation.

Exercise

Exercise 01

Let's try to implement your own Stack with using Linked-List!

class ListNode {
  val: number | null;
  next: ListNode | null;

  constructor(val: number | null = null, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

class MyStack {
  top: ListNode | null;
  bottom: ListNode | null;
  length: number;

  constructor() {
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }

  push(value: number) {
    const newNode = new ListNode(value);
    if (this.length === 0) {
      this.top = newNode;
      this.bottom = newNode;
    } else {
      const holdingPointer = this.top;
      this.top = newNode;
      this.top.next = holdingPointer;
    }
    this.length++;
  }

  pop(): number | null {
    if (!this.top) return null;
    if (this.top === this.bottom) {
      this.bottom = null;
    }
    const holdingPointer = this.top;
    this.top = this.top.next;
    this.length--;
    return holdingPointer.val;
  }

  peek(): number | null {
    if (!this.top) return null;
    return this.top.val;
  }

  size(): number {
    return this.length;
  }
}

const myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.push(3);
console.log(myStack.pop());
console.log(myStack.peek());
console.log(myStack.size());

Exercise 02

Let's try to solve some leet code questions

https://leetcode.com/problems/valid-parentheses/

const isValid = (s: string): boolean => {
  let stack = [];
  let parentheses = {
    "(": ")",
    "{": "}",
    "[": "]",
  };
  for (let i = 0; i < s.length; i++) {
    let char = s[i];
    if (char in parentheses) {
      stack.push(parentheses[char]);
    } else if (stack[stack.length - 1] === char) {
      stack.pop();
    } else {
      return false;
    }
  }
  return stack.length === 0;
};

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

const removeDuplicates = (s: string): string => {
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    if (stack.length > 0 && stack[stack.length - 1] === s[i]) {
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }
  return stack.join("");
};

https://leetcode.com/problems/crawler-log-folder/

const minOperations = (logs: string[]): number => {
  const stack: string[] = [];

  for (let i = 0; i < logs.length; i++) {
    const log = logs[i];

    if (log === "../") {
      if (stack.length > 0) {
        stack.pop();
      }
    } else if (log !== "./") {
      stack.push(log);
    }
  }

  return stack.length;
};

Understanding Linked List: Features, Time Complexity, and Implementation

Masaki Fukunishi — Tue, 18 Jul 2023 17:59:19 +0000

This article is based on a course in the following repository.
https://github.com/cookie777/altgorithm-data-structure-crash-course/blob/main/linked-list.md

What is linked list?

Linked list is a data structure that consists of a sequence of nodes¹, where each node contains a data element and a reference to the next node in the sequence.

What is liked list good at?

Sorted data

Linked lists can have sorted data unlike hash table, Because nodes points the next node.
Dynamic Size

Linked list can dynamically grow or shrink in size during program execution. Unlike arrays, which have a fixed size, linked lists can accommodate new elements or remove existing elements without requiring a reallocation of memory.
Insertion and Deletion

Linked list excel at efficient insertion and deletion operations, especially at the beginning or middle of the list. Unlike arrays, which may require shifting elements to accommodate changes, linked lists only need to update a few pointers.
Efficient Iteration

Singly-linked lists are efficient for forward iteration, allowing easy traversal from the beginning to the end. Doubly-linked lists can traverse in both directions, enabling forward and backward traversal.
Merging and Splitting

Linked lists can be merged or split easily by manipulating the pointers.

When is good to use liked list?

When you need to maintain sorted data

If you need to maintain data in a sorted order, linked lists can be a suitable option. As the nodes in a linked list contain pointers to the next node.
When you need dynamic size

If the size of your data is not known in advance or if it frequently changes, a linked list can accommodate these changes efficiently.
When you need efficient insertion and deletion

If your application requires frequent insertion or deletion operations, especially at the beginning or middle of the data structure, linked lists provide efficient performance.
When you need efficient iteration

If your application primarily involves sequential access to the data, linked lists provide an efficient way to iterate through the elements.
When merging or splitting data structures

Linked lists a good choice when you need to combine multiple lists into one or divide a list into smaller segments.

What is head and tail in linked list?

Head

Head is the first node in the list. It is the entry point from which you can access the entire linked list structure
Tail

Tail is the last node in the list. It is the node that has a reference to null or points to nothing, indicating the end of the list.

Analysis

What is the time complexity of following operations

access by index

O(n)

insert at index

O(n)

delete at index

O(n)

Accessing, inserting, or deleting an element by index requires traversing the list from the head to the desired index, which takes linear time.

joint two listed list

O(1)

Joining two linked lists requires updating the tail of the first list to point to the head of the second list, which takes constant time.

add(delete) head

O(1)

Addind or deliting elements at the top of the linked list, just update few nodes, which takes constant time.

add(delete) tail

Adding O(1)

Addind elements at the end of the linked list, just update few nodes using tail, which takes constant time.
Deleting O(n)

Deleting elements at the end of the linked list, requires traversing the list from the head to the tail, which takes linear time.

Exercise

Exercise 01

Let's try to print all values in linked list.

class LinkedListNode {
  val: number | null;
  next: LinkedListNode | null;

  constructor(val: number | null = null, next: LinkedListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

const zero = new LinkedListNode(0);
const one = new LinkedListNode(1);
const two = new LinkedListNode(2);
const three = new LinkedListNode(3);
const four = new LinkedListNode(4);
zero.next = one;
one.next = two;
two.next = three;
three.next = four;

// Write the code to iterate and print all values connected to zero
// zero is the starting point.
// Ideally, it should print like
// 0
// 1
// 2
// 3
// 4

let currentNode: LinkedListNode | null = zero;

while (currentNode !== null) {
  console.log(currentNode.val);
  currentNode = currentNode.next;
}

Exercise 02

https://leetcode.com/problems/design-linked-list/

class LinkedListNode {
  val: number | null;
  next: LinkedListNode | null;

  constructor(val: number | null = null, next: LinkedListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

class MyLinkedList {
  private head: LinkedListNode | null;
  private tail: LinkedListNode | null;
  private length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  get(index: number): number {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    const leader = this.traverseToIndex(index);

    return leader!.val!;
  }

  addAtHead(val: number): void {
    const node = new LinkedListNode(val);
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head = node;
    }

    this.length++;
  }

  addAtTail(val: number): void {
    const node = new LinkedListNode(val);
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail!.next = node;
      this.tail = node;
    }
    this.length++;
  }

  addAtIndex(index: number, val: number): void {
    if (index < 0 || index > this.length) {
      return;
    }
    if (index === 0) {
      this.addAtHead(val);
      return;
    }

    if (index === this.length) {
      this.addAtTail(val);
      return;
    }

    const newNode = new LinkedListNode(val);
    const leader = this.traverseToIndex(index - 1);

    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;
    return;
  }

  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.length) {
      return;
    }

    if (index === 0) {
      this.head = this.head!.next;
      if (this.head === null) {
        this.tail = null;
      }
    } else {
      const leader = this.traverseToIndex(index - 1);
      const unwantedNode = leader!.next;
      leader!.next = unwantedNode!.next;
      if (unwantedNode === this.tail) {
        this.tail = leader;
      }
    }

    this.length--;
  }

  private traverseToIndex(index: number): LinkedListNode | null {
    let currentNode: LinkedListNode | null = this.head;
    let counter = 0;
    while (currentNode !== null && counter !== index) {
      currentNode = currentNode.next!;
      counter++;
    }
    return currentNode;
  }
}

Exercise 03

https://leetcode.com/problems/swapping-nodes-in-a-linked-list/

const swapNodes = (head: ListNode | null, k: number): ListNode | null => {
  let length = 0;
  let countLength = head;
  while (countLength) {
    countLength = countLength.next;
    length++;
  }

  const indexFromStart = k - 1;
  const indexFromEnd = length - k;

  let count = 0;
  let nodeFromStart: ListNode | null = null;
  let nodeFromEnd: ListNode | null = null;
  let current = head;

  while (current) {
    if (count === indexFromStart) {
      nodeFromStart = current;
    }
    if (count === indexFromEnd) {
      nodeFromEnd = current;
    }
    current = current.next;
    count++;
  }

  [nodeFromStart!.val, nodeFromEnd!.val] = [nodeFromEnd!.val, nodeFromStart!.val];

  return head;
};

References

https://leetcode.com/explore/learn/card/linked-list/

Double Liked List

What is Doubly Linked List?

Doubly linked list is similar to a singly linked list, except that each node has a reference to both the next and previous nodes in the sequence.

What is pros and cons compare to Singly Linked List?

pros

Bidirectional traversal

Doubly linked lists allow for traversal in both forward and backward directions. Each node contains pointers to both the next and previous nodes, enabling efficient backward traversal.

cons

Extra memory

Doubly linked lists require extra memory space to store the previous node reference.

Can you come up with good example when to use Double Liked List?😁

Music Player Playlist

When adding a new song, a new element is inserted into the list. Also, when a user navigates to the previous or next song, the previous or next element in the list can be accessed.

Node is a fundamental building block of a linked list or a tree. It is a data structure that holds a piece of data and one or more references to other nodes. ↩

Understanding Hash table: Features, Pros, Cons, and Time Complexity

Masaki Fukunishi — Tue, 11 Jul 2023 16:17:30 +0000

This article is based on a course in the following repository.
https://github.com/cookie777/altgorithm-data-structure-crash-course/blob/main/hash-table.md

What is hash?

Hash is a function that takes an input and produces a fixed-size string of characters.

Characteristics of Hash

Deterministic

Hash function always produces the same output for the same input.
Non-Reversible

Hash functions are designed to be one-way functions, meaning it is impossible to get the original input from the hash output.
Fixed Output Size

Hash function always produces the same size of output regardless of the input size. For example, a common hash function called SHA-256 generates a 256-bit (32-byte) hash value.
Uniform Distribution

A good hash function evenly distributes hash values across its output space, reducing the likelihood of collisions.
Avalanche Effect

A small change in the input should result in a significant change in the output, making it difficult to predict the original input based on the hash value alone.

How do you make hash?

Hashes are created using algorithms such as MD5, SHA-1, SHA-256, etc.

SHA-256 currently has no known security issues. Since it is suitable for modern security requirements.

Here is the code to create a hash using SHA-256 in JavaScript

import crypto from "crypto";

const data = "Hello!";
const hash = crypto.createHash("sha256");
hash.update(data);
// Specify a hexadecimal string
const hashedData = hash.digest("hex");

console.log(hashedData);

What is Hash Table?

Hash table is a data structure that stores key value pairs.

The basic idea behind a hash table is to use a hash function to transform a key into a distinct string of character. This value serves as an index in a bucket¹, where the corresponding value associated with the key is stored.

What do you have to care when you create the Hash Table?

Hash Function Selection

Choose a suitable hash function that distributes the keys uniformly across the hash table. A good hash function minimizes collisions.
Collision Resolution

Determine an appropriate strategy for handling collisions that may occur when two keys map to the same hash value. Common collision resolution techniques are separate chaining (using linked lists or other data structures to store multiple elements at the same hash index) etc.

What is good(bad) about Hash Table compare to array?

Advantages of Hash Table over array

Dynamic Size

Hash tables can dynamically resize themselves as the number of elements changes.
Flexibility in Keys

Hash tables allow for flexible key types. Unlike arrays, where the keys are typically integers representing indices, hash tables can use a wide range of data types as keys, including strings.
Efficient Search, Insertion, and Deletion

Searching, Adding, and removing elements from a hash table is generally fast. The time complexity for searches, insertions, and deletions in a hash table is also typically O(1) on average.

Disadvantages of Hash Table over array

Unordered Data

Hash tables do not guarantee an order of elements. If you need to maintain a specific order, arrays may be more suitable since they store elements contiguously.
Additional Overhead

Hash tables have additional memory overhead due to the need for hash functions, hash buckets, and potential collisions.

When is better to use Hash Table over array

When the size of the data can change dynamically
When you need to associate values with flexible keys
When the order of elements doesn't matter
When the additional memory overhead is acceptable

Analysis

What are the time complexity of

add(insert)

O(1)

get value by key

O(1)

find value

O(n)

finding a value without knowing its corresponding key requires traversing the entire table to search for a match, resulting in a linear time complexity.

remove key, value

O(1)

update value

O(1)

In add, get, remove and update, In the case of collisions, the time complexity can increase to O(n) in the worst case.

Exercise

Exercise 1

Let's try to implement your own hash function. There is a good leedcode question here!

https://leetcode.com/problems/design-hashmap/
Rules
- Do not ever use pre existing hash table API
- If you use an array, try to fixed the size with 1000

class MyHashMap<K, V> {
  private data: [K, V][][];
  constructor() {
    this.data = new Array(1000);
  }

  private hash(key: K): number {
    let hash = 0;
    const keyString = JSON.stringify(key);
    for (let i = 0; i < keyString.length; i++) {
      hash += keyString.charCodeAt(i);
    }
    return hash;
  }

  private address(key: K): number {
    return this.hash(key) % this.data.length;
  }

  public put(key: K, value: V): void {
    const address = this.address(key);
    if (this.data[address] === undefined) {
      this.data[address] = [];
    }

    const currentBucket = this.data[address];
    for (let i = 0; i < currentBucket.length; i++) {
      if (currentBucket[i][0] === key) {
        currentBucket[i][1] = value;
        return;
      }
    }

    currentBucket.push([key, value]);
  }

  public get(key: K): V | number {
    const address = this.address(key);
    const currentBucket = this.data[address];

    if (currentBucket) {
      for (let i = 0; i < currentBucket.length; i++) {
        if (currentBucket[i][0] === key) {
          return currentBucket[i][1];
        }
      }
    }
    return -1;
  }

  public remove(key: K): void {
    const address = this.address(key);
    const currentBucket = this.data[address];
    if (!currentBucket) return;

    for (let i = 0; i < currentBucket.length; i++) {
      if (currentBucket[i][0] === key) {
        currentBucket.splice(i, 1);
      }
    }
  }
}

const person = new MyHashMap<string, string>();
person.put("name", "John");
person.put("height", "180cm");

console.log(person.get("name")); // John
console.log(person.get("height")); // 180cm

person.remove("height");
console.log(person.get("height")); // -1

Exercise 2

Let's try to sovle some leetcode quesiton.
These can be optimized by leveraging array and hash table data structure💪

https://leetcode.com/problems/two-sum/

const twoSum = (nums: number[], target: number): [number, number] | void => {
  let hashmap: { [key: number]: number } = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (hashmap[complement] !== undefined) {
      return [hashmap[complement], i];
    }
    hashmap[nums[i]] = i;
  }
};
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

https://leetcode.com/problems/first-unique-character-in-a-string/

const firstUniqChar = (s: string): number => {
  const charCount: { [key: string]: number } = {};
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    charCount[char] = (charCount[char] || 0) + 1;
  }
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (charCount[char] === 1) {
      return i;
    }
  }
  return -1;
};

console.log(firstUniqChar("leetcode")); // 0
console.log(firstUniqChar("aabb")); // -1

https://leetcode.com/problems/minimum-index-sum-of-two-lists/

function findRestaurant(list1: string[], list2: string[]): string[] {
  const hashmap: { [key: string]: number } = {};
  let minIndexSum = Infinity;
  const result: string[] = [];

  for (let i = 0; i < list1 .length; i++) {
    hashmap[list1[i]] = i;
  }

  for (let j = 0; j < list2.length; j++) {
    if (hashmap[list2[j]] === undefined) {
      continue;
    }
    const indexSum = j + hashmap[list2[j]];
    if (indexSum < minIndexSum) {
      result.length = 0;
      minIndexSum = indexSum;
    }
    if (indexSum === minIndexSum) {
      result.push(list2[j]);
    }
  }
  return result;
}

const list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"];
const list2 = ["KFC", "Shogun", "Burger King"];
console.log(findRestaurant(list1, list2)); // ["Shogun"]

References

https://leetcode.com/explore/learn/card/hash-table/

Set

Q: Concept

What is Set?

A set is a collection of unique elements, where each element appears only once. It does not maintain any particular order for its elements.

What is Set vs Hash Table?

Elements

Sets only store distinct elements, whereas hash tables store key-value pairs.
Operations

Sets provide operations specific to sets, such as set union, intersection, and difference. Hash tables, on the other hand, focus on key-value operations like insertion, deletion, and retrieval of values based on keys.

When is better to use Set over Hash Table

Use a set when you need to work with a collection of unique elements and don't require key-value mappings or fast key-based lookups. Sets are well-suited for scenarios where element uniqueness and set operations are the primary concerns.

Bucket is a container for storing key value pairs. ↩

Understanding Array: Features, Pros, Cons, and Time Complexity

Masaki Fukunishi — Thu, 22 Jun 2023 20:24:22 +0000

This article is based on a course in the following repository.
https://github.com/cookie777/altgorithm-data-structure-crash-course/blob/main/array.md

What is array?

Array is the simplest and most widely used data structure, allowing multiple elements to be stored in order.
Each element is uniquely accessible by index.

How do we allocate memory when constructing the array?

In JavaScript

JavaScript arrays are dynamically allocated memory.

When you add an element to an array, the JavaScript runtime environment automatically allocates memory internally to store the element. Memory management is handled by the JavaScript runtime engine, and the programmer does not need to write explicit memory allocation code.

const os: string[] = ["Mac", "Windows", "Linux"];

What is fixed size vs dynamic size array?

Fixed size array

Uses a fixed-size memory area to store elements. The size is specified at declaration and cannot be changed thereafter
Elements are stored in contiguous memory areas.
Access to the elements of a fixed size array is fast and can be accessed directly using indexes.
The size of the fixed size array is determined at compile time and cannot be changed at run time.

Dynamic size array

Uses a dynamically allocated memory area to store elements.
Elements are stored in contiguous memory areas, but memory may be reallocated as needed.
Access to the elements of a dynamic size array is also fast and can be accessed directly using indexes.
The size of the dynamic size array is determined at runtime and can be changed at runtime.

What is pros and cons about array?

Pros

Random Access¹

Arrays provide constant-time access to individual elements based on their index. This means you can access any element directly using its index without iterating through the entire array.
Efficient use of memory

Arrays store elements in contiguous memory locations, which allows for efficient memory management.
Easy Iteration

Arrays provide a straightforward way to iterate over their elements using loops or iterators. This makes it convenient to perform operations on each element or process the entire array.

Cons

Wasted Memory

If an array is not fully populated with elements, there may be wasted memory space. If the size of the array is much larger than the number of elements it contains, it can result in inefficient memory usage.
Insertion and Deletion Overhead²

Inserting or deleting elements in the middle of an array requires shifting subsequent elements, which can be computationally expensive.
Fixed Size (For fixed size array)

Arrays have a fixed size, meaning they cannot dynamically grow or shrink once they are created. This inflexibility can be problematic if you need to store a varying number of elements or if the required size is not known in advance.

When do we use array?

When the number of elements is known and fixed

If you have a collection of elements with a predetermined size that will not change throughout the program's execution, arrays are a suitable choice.
When random access is required

If you need to access elements in the collection directly by their indices or perform operations on specific elements without iterating through the entire collection, arrays provide constant-time random access, making them efficient for such use cases.
When you need to iterate over the elements

Arrays provide a straightforward way to iterate over their elements using loops or iterators. This makes it convenient to perform operations on each element or process the entire array.
When memory efficiency is a concern

Arrays have a compact memory representation, as elements are stored in contiguous memory locations.

What is the time complexity of following instruction.

insert (push)

Time Complexity: O(1)

Inserting an element at the end of an array does not require shifting other elements.

delete by index

Time Complexity: O(n)

Deleting an element from an array requires shifting all the elements after the deleted index to fill the gap.

access by index

Time Complexity: O(1)

Accessing an element in an array or a list by index can be done in constant time since the position of the element is known and does not require iterating through the entire data structure.

find a specific value

Time Complexity: O(n)

Finding a specific value in an array or a list requires iterating through the entire data structure until the value is found.

pop (delete last)

Time Complexity: O(1)

Deleting the last element of an array or a list does not require shifting other elements.

pop left (delte first, shift)

Time Complexity: O(n)

Deleting the first element of an array or a list requires shifting all the elements after the deleted index to fill the gap.

Exercise

Exercise 1:

Let's try to implement an dynamic size array with using only fixed size array.
Since there is no fixed size array in Ts, pseudo code is ok

class DynamicArray {
  private array: FixedArray<number>; // Suppose this is a TS Array with fixed size. You can use all the features of a TS Array, but with a fixed size.
  private length: number;

  public constructor(size: number) {
    this.array = new FixedArray(size);
    // Feel free to add any class properties if needed
    this.length = 0;
  }

  public isEmpty(): boolean {
    return this.length === 0;
  }

  public getLength(): number {
    return this.length;
  }

  public push(value: number): void {
    // Add an element to the dynamic array. Check if the dynamic array is already full, and if so, create a new FixedArray instance with a larger size and copy the elements from the old array to the new one.
    // When creating a new fixed size array, it is doubled in size.
    if (this.length === this.array.length) {
      const newArray = new FixedArray(this.array.length * 2);
      for (let i = 0; i < this.array.length; i++) {
        newArray[i] = this.array[i];
      }
      this.array = newArray;
    }
    this.array[this.length] = value;
    this.length++;
  }

  public removeAt(index: number): void {
    if (index < 0 || index >= this.length) {
      return;
    }
    // remove an element at that index and shift all subsequent elements to fill the gap
    for (let i = index; i < this.length; i++) {
      this.array[i] = this.array[i + 1];
    }
    // Clear the last element
    this.array[this.length - 1] = undefined;
    this.length--;
  }
}

Exercise 02: Remove Master

Q1

Congratulation! You'are hired by that Big tech company😎
Your first job is to implement

removeAt function which removes an element at the givien index
removeAll function which removes all the elements that matches to the given element.

function removeAt(arr: Array<number>, index: number): Array<number> {
  // implement your code
  // e.g.  removeAll([1,4,5,6], 2) -> [1,4,6]
  if (index < 0 || index >= arr.length) {
    throw new Error("Index out of bounds");
  }
  for (let i = index; i < arr.length; i++) {
    arr[i] = arr[i + 1];
  }
  arr.pop();

  // or
  // return arr.splice(index, 1);

  return arr;
}
console.log(removeAt([1, 4, 5, 6], 5));

function removeAll(arr: Array<number>, value: number): Array<number> {
  // implement your code
  // e.g.  removeAll([1,4,5,6,3,4,2,4], 4) -> [1,5,6,3,2]

  const newArray = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) continue;
    newArray.push(arr[i]);
  }
  return newArray;

  // or
  // return arr.filter((element) => element !== value);
}

console.log(removeAll([1, 4, 5, 6, 3, 4, 2, 4], 4));

Q2

Easy Peasy? What is your codes time complexity and space complexity.

removeAt
- Time Complexity: O(n)
- It iterates through the entire array to shift the elements after the deleted index.
- Space Complexity: O(1)
- It modifies the input array in place without creating any additional data structures that grow with the size of the input.
removeAll
- Time Complexity: O(n)
  - It iterates through the entire array to find the elements that match the given value.
- Space Complexity: O(n)
  - It creates a new array to store the elements that do not match the given value.

Q3

Since your company is big and needs to handle a large amount of data,
you are asked to make it as efficient as possible.

Can you make it O(n) time complexity and O(1) space complexity for removeAll function? 😁
Let's try and get the bonus!

Hint:
https://leetcode.com/problems/move-zeroes/

function removeAll(arr: Array<number>, value: number): Array<number> {
  let idx = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== value) {
      arr[idx] = arr[i];
      idx++;
    }
  }
  arr.length = idx;
  return arr;
}

Since the original array is used and no additional array is created, the spatial computational complexity is O(1).

Random access refers to the ability to access individual elements in a data structure directly, without the need to traverse or iterate through the entire structure. ↩
In computing, overhead refers to any additional resources or costs incurred in performing a particular operation or executing a program that are not directly related to the desired task or functionality. ↩

Algorithm Analysis

Masaki Fukunishi — Wed, 07 Jun 2023 19:04:03 +0000

Algorithm Analysis

This article is based on a course in the following repository.
https://github.com/cookie777/altgorithm-data-structure-crash-course/blob/main/algorithm-analysis.md

What is time complexity?

Time complexity is a measure of how much time an algorithm takes to execute relative to its input size. Specifically, it evaluates how the algorithm's execution time increases as the input size of the problem to be solved by the algorithm increases.
Time complexity is expressed using Big O notation.
Time complexity usually considering worst-case execution time.

const list: number[] = [1, 7, 2, 6, 5];
const target: number = 1;

const getOne = (list: number[], target: number): boolean => {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) {
      return true;
    }
  }
  return false;
};

// O(n)
// The loop is executed once. But the worst case is 1 is the last element. O(n) expresses the worst case (5 loops).

Remove constant

const test = (boxes: string[]) => {
  boxes.forEach((box: string[]) => console.log(box));

  boxes.forEach((box: string[]) => console.log(box));
};

// O(2n) => O(n)

Drop non-dominant terms

const test = (n: number) => {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
};

// O(n + n^2) => O(n^2)

Why use Big O notation?

Simplicity

Big O notation expresses efficiency in terms of O( ). This notation can be used to convey the efficiency of an algorithm in a simplified form.

Comparison

The Big O notation makes it easy to compare the efficiency of different algorithms.
O(log n) is better than O(n), etc.

Accuracy

The actual algorithm execution time depends on the CPU, but the Big O can be used to determine efficiency without having to execute the algorithm exactly.

What is space complexity?

Space complexity is a measure how much amount of memory and storage required to execute relative to its input size. In other words, it considers the size of additional memory or data structures required when an algorithm is executed.

Why and when do we use time (space) complexity?

Algorithm comparison
- Time and space complexity help in comparing different algorithms for the same problem. By analyzing their complexity, you can determine which algorithm is more efficient in terms of runtime or memory usage, enabling you to select the most suitable solution.
Optimization
- Complexity analysis identifies areas for optimization within algorithms or programs. It allows developers to focus on improving the performance of specific parts of the code that contribute significantly to the overall time or space usage.
Resource management
- By understanding the complexity, you can design algorithms or select solutions that fit within the available resources, avoiding performance issues and ensuring optimal usage.
Predictive power
- Complexity analysis enables you to predict and estimate the performance characteristics of an algorithm before running it on actual data. This helps in understanding how the algorithm will scale with larger input sizes, allowing you to anticipate and plan for potential performance challenges.

Is running time == time complexity?

No Running time refers to the actual time it takes for an algorithm or program to execute on a specific input. It is typically measured in seconds or millisecond but on the other hand, time complexity is a measure of how much time an algorithm takes to execute relative to its input size. It is typically expressed using Big O notation.

Is number of calculations == time complexity??

No The number of calculations is not necessarily equal to time complexity.
The number of calculations refers to the actual count of computations or operations performed during the execution of an algorithm or program.

const array1: number[] = [1, 7, 2, 6, 5];
const array2: number[] = [1, 7, 2, 6, 5, 1, 1, 2, 10, 1];

const fn1 = (array: number[]): void => {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i]);
  }
};

fn(array1); // O(n) number of calculation is 5
fn(array2); // O(n) number of calculation is 10

What are the complexity of these functions?

def q0(n):
    print(n)
# O(1)

def q1(n):
    i = 0
    while i < n:
        print(i)
        i += 1
# O(n)

def q2(n):
    i = 0
    while i < n:
        print(i)
        i += 2
# O(n/2) = O(n)

def q3(n):
    i = 1
    while i < n:
        print(i)
        i *= 2
# O(log n)

def q4(n):
    i = 0
    while i < n:
        j = 0
        while j < n:
            print(i, j)
            j += 1
        i += 1
# O(n^2)

def q5(n):
    i = 0
    while i < n:
        j = 0
        while j < n:
            k = 0
            while k < n:
                print(i, j, k)
                k += 1
            j += 1
        i += 1
# O(n^3)

def q6(n):
    i = 0
    while i < n:
        j = 0
        while j < i:
            print(i, j)
            j += 1
        i += 1

# O(n^2)

def q7(n):
    i = 0
    while i < 100000000:
        print(i)
        i += 1
# O(1)

def q8(n):
    i = 0
    while i < n:
        j = 0
        while j < 100000000:
            print(i, j)
            j += 1
        i += 1
# O(n)

def q9(n):
    i = 0
    while i < n:
        print(i)
        i += 1

    i = 0
    while i < n:
        j = 0
        while j < n:
            print(i, j)
            j += 1
        i += 1
# O(n + n^2) = O(n^2)

def q10(n):
    i = 0
    while i < n:
        print(i)
        i += 1

    i = 0
    while i < n:
        j = 0
        while j < n:
            print(i, j)
            j += 1
        i += 1

    i = 0
    while i < n:
        j = 0
        while j < 100000000:
            print(i, j)
            j += 1
        i += 1

    i = 1
    while i < n:
        print(i)
        i *= 2

# O(n + n^2 + n + log n) = O(n^2)

Optional: Try to Implement

function which time complexity is O(n!)

// O(n!)
// it means that we're adding a nested loop for every input

const test = (n) => {
  if (n === 0) {
    console.log("**************");
  }
  for (let i = 0; i < n; i++) {
    test(n - 1);
  }
};

https://www.youtube.com/watch?v=vbh8t-ok_4E

function which time complexity is O(log n)

// O(log n)
const searchInsert = (nums: number[], target: number): number => {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
};

LeetCode #283 Move Zeroes with JavaScript

Masaki Fukunishi — Fri, 17 Feb 2023 19:33:38 +0000

Solution to LeetCode's 283. Move Zeroes with JavaScript.

Solution

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const moveZeroes = (nums) => {
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] === 0) {
      nums.splice(i, 1);
      nums.push(0);
    }
  }
};

Time complexity: O(n)
Space complexity: O(1)

It is important to process from the back of the array, since 0 is added to the end of the array.

LeetCode #141 Linked List Cycle with JavaScript

Masaki Fukunishi — Sat, 04 Feb 2023 05:04:21 +0000

Solutions to LeetCode's 141. Linked List Cycle with JavaScript.

Solution 2 also addresses the following follow-up.
Follow up: Can you solve it using O(1) (i.e. constant) memory?

Solution 1

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle1 = (head) => {
  const list = [];
  while (head) {
    if (list.includes(head.val)) return true;
    list.push(head.val);
    head = head.next;
  }
  return false;
};

Time complexity: O(n)
Space complexity: O(n)

Space complexity is O(n), so change to address follow-up.

Solution 2

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = (head) => {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast == slow) return true;
  }
  return false;
};

Time complexity: O(n)
Space complexity: O(1)

fast is 2 steps at a time, slow is 1 step at a time, and the list is put in a while loop to execute the search.

LeetCode #136 Single Number with JavaScript

Masaki Fukunishi — Fri, 03 Feb 2023 05:41:11 +0000

Solution to LeetCode's 136. Single Number with JavaScript.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
const singleNumber = (nums) => {
  let result = nums[0];
  for (let i = 1; i < nums.length; i++) {
    result = result ^ nums[i];
  }
  return result;
};

Time complexity: O(n)
Space complexity: O(1)

Using the XOR operator is simple way to implement.

LeetCode #121. Best Time to Buy and Sell Stock with JavaScript

Masaki Fukunishi — Thu, 02 Feb 2023 18:48:19 +0000

Solutions to LeetCode's 121. Best Time to Buy and Sell Stock with JavaScript.

Solution 1

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = (prices) => {
  let maxProfit = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      let profit = prices[j] - prices[i];
      if (maxProfit < profit) {
        maxProfit = profit;
      }
    }
  }
  return maxProfit;
};

Time complexity: O(n^2)
Space complexity: O(1)

The Time complexity of this solution is O(n^2), so I'll find another solution.

Solution 2

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = (prices) => {
  let maxProfit = 0;
  let stockToBuy = prices[0];

  for (let i = 1; i < prices.length; i++) {
    if (stockToBuy > prices[i]) {
      stockToBuy = prices[i];
    }
    const profit = prices[i] - stockToBuy;

    if (maxProfit < profit) {
      maxProfit = profit;
    }
  }
  return maxProfit;
};

Time complexity: O(n)
Space complexity: O(1)

I was able to change the for loop to one and shorten the time complexity to O(n).