Forem: Artem Maksimov

A Deep Dive into Advanced Linked List Implementations in JavaScript

Artem Maksimov — Tue, 21 Feb 2023 23:53:37 +0000

Introduction

LinkedLists are a common data structure used in computer science. They are made up of one or more nodes, which consist of a data element and an address that references the next node in the list. The last node in the list contains a null reference to indicate the end of the list.

In this article, we implement a LinkedList in JavaScript using two classes, Node and LinkedList. The Node class is used to create a new node in the list, while the LinkedList class manages the list as a whole.

Let's implement it based on this template:

function Node(data) {
    // Implementation
}

function LinkedList() {
  // Implementation
}

Implementation

The Node constructor takes a single argument, data, which is the value to be stored in the node. The constructor also initializes the next property to null, which will be set to the next node in the list if one exists.

function Node(data) {
  this.data = data;
  this.next = null;
}

The LinkedList constructor initializes three properties: head, tail, and length. head and tail are both initialized to null, indicating an empty list.

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

The add method adds a new node to the end of the list by creating a new Node object and updating the tail property to point to the new node.

LinkedList.prototype.add = function(item) {
  const node = new Node(item);

  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    this.tail = node;
  }
  this.length++;
}

The toString method creates a string representation of the list by iterating through each node and concatenating its value to the result string.

LinkedList.prototype.toString = function() {
  let current = this.head;
  let result = "";

  while(current) {
    result += current.data.toString() + ' ';
    current = current.next;
  }

  return result.trim();
}

The getByIndex method retrieves the value of the node at a given index by iterating through the list and stopping at the node with the corresponding index.

LinkedList.prototype.getByIndex = function(index) {
  if(index > this.length - 1) {
    throw Error('List index out of bounds');
  }

  let result = this.head;
  for(let i = 0; i < index; i++) {
    result = result.next;
  }
  return result.data;
}

The remove method removes a node from the list by iterating through the list and updating the next property of the previous node to point to the next node in the list.

LinkedList.prototype.remove = function(data) {
  let current = this.head;
  if(!current) {
    return false;
  }

  if(current.data === data) {
    this.head = current.next;
    this.length--;
    return true;
  }

  while(current.next) {
    if(current.next.data === data) {
      current.next = current.next.next;
      this.length--;
      return true;
    }
    current = current.next;
  }
  return false;
}

Finally, we implement the insertAfter method, which inserts a new node into the list after a given node. This method finds the node with the given value and updates its next property to point to the new node, while the next property of the new node is set to the next property of the original node.

LinkedList.prototype.insertAfter = function(afterData, data) {
  const node = new Node(data);
  let current = this.head;

  while(current) {
    if(current.data === afterData) {
      node.next = current.next;
      current.next = node;
      this.length++;
      return true;
    }
    current = current.next;
  }

  return false;
}

Summary

In conclusion, linked lists are a fundamental data structure in computer science, and this implementation in JavaScript can serve as a useful tool for managing data in web applications. By understanding the principles behind linked lists and implementing them in code, developers can gain a deeper understanding of data structures and algorithms.

Top 5 resources to prepare for a FAANG interview as a Frontend Engineer

Artem Maksimov — Tue, 24 Jan 2023 21:37:52 +0000

I want to share the most useful tips for a frontend interview at FAANG that helped me to get the job. I will focus specifically on my experience at Meta, but these tips can be applied to other FAANG companies as well. My goal is not to create a comprehensive guide on how to crack the interview, rather I want to provide actionable information that was most helpful for me in the process.

Top 5 Resources

There are a lot of materials available online to help you prepare for the frontend interview. I found the following resources to be the most useful:

BFE (leetcode alternative for JavaScript)
Glassdoor (feedback about an interview process in different companies)
Pramp (interview mocks)
Behavioral: Dan Croitor youtube (best behavioral interview videos)
Cracking the coding interview (book about interviews)

Random tips

Tip #1: forget about leetcode, use BFE
Tip #2: deep dive into JavaScript stack
Tip #3: solve as many tasks as you can
Tip #4: follow HR guidance and ask questions

Understand the structure of FAANG interview

It's really important to understand the structure of the interview. The frontend interview process typically follows the same structure as a usual software engineering interview:

HR Call

The HR call is usually a simple phone conversation without video. During this call, the HR representative may ask you simple questions like,

What is the difference between == and ===?

This call is an opportunity for HR to get to know you a bit better and to determine if you are a good fit for the company.

Screening (1 session, 45 min)

The screening session is usually a 45-minute session where you will be given 1-2 easy or medium JS coding tasks to complete. This is an opportunity for the interviewer to assess your coding skills and to see how you approach a problem.

Prep call

If you successfully complete the screening session, you will have a prep call with HR where you can ask any questions you have before the next interviews.

Coding (2+ sessions, 45 min each)

The coding sessions are similar in format to the initial screening session, but the questions may be more challenging (medium or hard). During these sessions, the interviewer will assess your ability to write efficient and clean code. It's worth mentioning that in general software engineering interviews, you can choose your preferred language, but in frontend interviews, the tasks are usually JavaScript specific and require knowledge of JS APIs.

System Design Interview (1-2 sessions, 45 min each)

The system design interview is an opportunity for the interviewer to assess your ability to design and implement scalable and performant frontend systems. You may be asked to design an application, component, or widget. However, you should focus on the frontend side of the implementation. For example, if you are asked to implement a search widget, you should explain how you will implement autocomplete for the search bar rather than focusing on choosing the right database and server.

Behavioral Interview (1 session, 45 min)

The behavioral interview is not different from a usual software engineering interview. This is an opportunity for the interviewer to assess your communication skills and to see how you handle different situations.

Conclusion

In conclusion, a frontend interview at a FAANG company follows a similar structure as a typical software engineering interview, but with a focus on JavaScript specific tasks. It's important to have a deep understanding of the JS stack and to be familiar with different frontend implementation techniques. In addition, it's also important to take the time to prepare and practice as many tasks as possible and follow the guidance of HR and ask questions during the interview process.

Advanced JavaScript Development: Building Promises from Scratch

Artem Maksimov — Mon, 16 Jan 2023 22:16:35 +0000

Introduction

Promise is a powerful tool in JavaScript that allows for asynchronous processing and handling of data. It can be a tricky concept to implement, especially during a FAANG interview. However, with the right understanding and approach, you can successfully implement your own Promise.

In this article, we will go over how to implement a basic version of a promise during a FAANG interview. The standard for promise implementation is called A+, but it includes a huge amount of details, making it almost impossible to implement all of them during a one-hour coding interview. Therefore, we will focus on implementing a basic variation that should be enough to show the interviewer your solving skills.

Implementation

TL;DR see the final code at the end

First, let's define the template for our promise. Promise is a JS class that contains two main functions then() and catch(), as well as two additional static functions resolve() and reject().

class MyPromise {
  constructor(executor) {
    // your code here
  }

  then(onFulfilled, onRejected) {
    // your code here
  }

  catch(onRejected) {
    // your code here
  }

  static resolve(value) {
    // your code here
  }

  static reject(value) {
    // your code here
  }
}

Now, let's take a look at how promises work and write a basic example of usage:

const promise = new MyPromise((resolve, reject) => {
  resolve('Test value');
  console.log('resolved');
});

console.log(promise.status); // should be 'resolved'
console.log(promise.value); // should be 'Test value'

We'll start by implementing the constructor. Promise can have three different states: pending, fullfiled, rejected. During its creation, we should set the status to pending and then call the function passed to the constructor with parameters onFullfil and onReject.

constructor(executor) {
  this. Status = 'pending';

  try {
    executor. Call(this, this.onFullfil.bind(this), this.onReject.bind(this));
  } catch(e) {
    this.onReject.call(this, e);
  }
}

onFullfil(value) {
  // your code here
}

onReject (value) {
  // your code here
}

Now, the executor is being called. However, after resolve is called, the status of the promise remains unchanged. Let's fix it:

onFullfil(value) {
  if (this.status !== 'pending') return;
  this.status = 'fullfiled';
  this.value = value;
}

onReject (value) {
  if (this.status !== 'pending') return;
  this.status = 'rejected';
  this. Value = value;
}

Now that the promise has the right value and status, let's revise how chaining of .then() works:

promise.then((val) => {
  console.log('Then ', val);
  return 'New value';
}).then((val) => {
  console.log('Second then ', val);
});

In order to enable chaining, the then() method should return a new instance of the promise. To accomplish this, we can utilize the new MyPromise constructor.

Additionally, we should run the appropriate callback, either onFulfilled or onRejected, based on the current state of the initial promise. The returned value from this callback should then be set as the value of the newly created promise instance. This allows for a chain of promises to be created, with each promise's value being determined by the return value of its corresponding callback.

  then(onFulfilled, onRejected) {
  return new MyPromise((resolve, reject) => {
    const newPromiseResolve = () => {
      try {
        const res = onFulfilled(this.value);
        resolve(res);
      } catch(e) {
        reject(e);
      }
    };

    const newPromiseReject = () => {
      try {
        if (onRejected) {
          const res = onRejected(this.value);
          resolve(res);
        } else {
          reject(this.value);
        }
      } catch(e) {
        reject(e);
      }
    };

    if (this.status === 'fullfiled') {
      newPromiseResolve();
    }

    if (this.status === 'rejected') {
      newPromiseReject();
    }
  });
}

While the implementation of the then() method appears to be functioning as intended, it's important to consider the scenario where the resolve function is called async. In order to properly handle this case, we can write a test case to evaluate the behavior of the promise in this case.

const asyncedPromise = new MyPromise((resolve, reject) => {
  setTimeout(() => {
    console.log('Async resolve');
    resolve('I am async value');
  }, 1000);
});

asyncedPromise.then((val) => {
  console.log('Asynced then', val);
});

When the then() method is called on a promise that is still in the pending state, our current implementation may not handle this scenario properly. To address this, we should save any callbacks passed to the then() method in separate arrays for resolve and reject callbacks. This way, when the promise's state changes from pending to either fulfilled or rejected, we can run the appropriate callbacks that were previously stored. To implement this, we can initialize two arrays, resolveCallbacks and rejectCallbacks.

this.resolveCallbacks = [];
this.rejectCallbacks = [];

this.tasks = [];

Then add one more condition for a pending status in .then() function. We need to save passed callbacks to our inner state.

if (this.status === 'pending') {
  this.resolveCallbacks.push(newPromiseResolve);
  this.rejectCallbacks.push(newPromiseReject);
}

Now we need to write function runTasks() to run all saved callbacks and clean arrays after.

doTask () {
  const task = this.tasks.shift();
  if (task) {
    task.call(this, this.value);
  }
}

runTasks () {
  while(this.tasks.length) {
    this.doTask();
  }
}

Let's call runTasks function inside onFulfill and onReject:

onFullfil(value) {
  if (this.status !== 'pending') return;
  this.status = 'fullfiled';
  this.value = value;

  this.tasks.push(...this.resolveCallbacks);
  this.resolveCallbacks = [];
  this.runTasks();
}

onReject (value) {
  if (this.status !== 'pending') return;
  this.status = 'rejected';
  this.value = value;

  this.tasks.push(...this.rejectCallbacks);
  this.rejectCallbacks = [];
  this.runTasks();
}

Congratulations, the implementation of the then() method now works asynchronously. However, we must not forget an important consideration when chaining multiple then() calls together. If a promise instance is returned within the onFulfilled or onRejected callback passed to the then() method, it should be handled correctly by the next then() in the chain. According to the Promise specification, the next then() in the chain should wait for the returned promise to resolve before proceeding, and the final resolved value should be passed as the input to the next then() rather than the promise instance.

Example:

promise.then(
  (val) => new MyPromise((res) => res('Value from promise'))
).then(
  (val) => console.log(val) // should print 'Value from promise' string, not promise instance
)

Let's check if res is a promise instance or just a value.

if (res instanceof MyPromise) {
  res.then(resolve, reject); // if it's a promise instance wait for value and resolve/reject
} else {
  resolve(res); // otherwise just resolve value
}

Now comes the easiest part. Let's implement the static methods. We simply need to create a promise and instantly resolve or reject its value.

static resolve(value) {
  return new MyPromise((resolve) => resolve(value));
}

static reject(value) {
  return new MyPromise((_resolve, reject) => reject(value));
}

And the method catch():

catch(onRejected) {
  return this.then((value) => value, onRejected);
}

The bonus part

Let's verify that all callbacks are called in the correct order by providing an example:

// Test: constructor should be sync, then handlers should be async
// order should be: 0, 1, 3, 2

console.log(0);
new MyPromise((resolve, reject) => {
  console.log(1);
  resolve(1);
}).then(() => {
  console.log(2)
});
console.log(3);

If we run this test we will see 0, 1, 2, 3 order. But it's expected to be 0, 1, 3, 2.

It happens because callbacks inside .then() must be called async. Let's wrap it with setTimeout to make it async.

setTimeout(() => {
  newPromiseResolve();
}, 0);

setTimeout(() => {
  newPromiseReject();
}, 0);

Summary

In summary, implementing a basic variation of a Promise class involves creating a class with a constructor, methods to resolve and reject the promise, and methods to handle the callbacks passed to the then() and catch() methods. Additionally, you need to make sure that callbacks passed to the then() method are called asynchronously and in the correct order.

Final version of the code:

class MyPromise {
  constructor(executor) {
    this.status = 'pending';

    this.resolveCallbacks = [];
    this.rejectCallbacks = [];

    this.tasks = [];

    try {
      executor.call(this, this.onFullfil.bind(this), this.onReject.bind(this));
    } catch(e) {
      this.onReject.call(this, e);
    }
  }

  doTask () {
    const task = this.tasks.shift();
    if (task) {
      task.call(this, this.value);
    }
  }

  runTasks () {
    while(this.tasks.length) {
      this.doTask();
    }
  }

  onFullfil(value) {
    if (this.status !== 'pending') return;
    this.status = 'fullfiled';
    this.value = value;

    this.tasks.push(...this.resolveCallbacks);
    this.resolveCallbacks = [];
    this.runTasks();
  }

  onReject (value) {
    if (this.status !== 'pending') return;
    this.status = 'rejected';
    this.value = value;

    this.tasks.push(...this.rejectCallbacks);
    this.rejectCallbacks = [];
    this.runTasks();
  }

  then(onFulfilled, onRejected) {
    return new MyPromise((resolve, reject) => {
      const newPromiseResolve = () => {
        try {
          const res = onFulfilled(this.value);

          if (res instanceof MyPromise) {
            res.then(resolve, reject);
          } else {
            resolve(res);
          }
        } catch(e) {
          reject(e);
        }
      };

      const newPromiseReject = () => {
        try {
          if (onRejected) {
            const res = onRejected(this.value);

            if (res instanceof MyPromise) {
              res.then(resolve, reject);
            } else {
              resolve(res);
            }
          } else {
            reject(this.value);
          }
        } catch(e) {
          reject(e);
        }
      };

      if (this.status === 'pending') {
        this.resolveCallbacks.push(newPromiseResolve);
        this.rejectCallbacks.push(newPromiseReject);
      }

      if (this.status === 'fullfiled') {
        setTimeout(() => {
          newPromiseResolve();
        }, 0);
      }

      if (this.status === 'rejected') {
        setTimeout(() => {
          newPromiseReject();
        }, 0);
      }
    });
  }

  catch(onRejected) {
    return this.then((value) => value, onRejected);
  }

  static resolve(value) {
    return new MyPromise((resolve) => resolve(value));
  }

  static reject(value) {
    return new MyPromise((_resolve, reject) => reject(value));
  }
}