The problem statement​

Given an array of asynchronous functions functions, return a new promise promise. Each function in the array accepts no arguments and returns a promise. All the promises should be executed in parallel.

promise resolves:

When all the promises returned from functions were resolved successfully in parallel. The resolved value of promise should be an array of all the resolved values of promises in the same order as they were in the functions. The promise should resolve when all the asynchronous functions in the array have completed execution in parallel.

promise rejects:

When any of the promises returned from functions were rejected. promise should also reject with the reason of the first rejection.

Please solve it without using the built-in Promise.all function.

Understanding the problem​

They are essentially asking us to return a promise function that loops through the array of functions and call them with the .then .catch promise based accessors. Push the results into an ordered array and return them once the last fn has executed. However, if we run into an error with the function which will hit our catch block. We should reject our new promise with the error.

Examples​

Example 1:

Input: functions = [ () => new Promise(resolve => setTimeout(() => resolve(5), 200)) ]

Output: {"t": 200, "resolved": [5]}

Explanation:

promiseAll(functions).then(console.log); // [5]

The single function was resolved at 200ms with a value of 5.

Example 2:

Input: functions = [ () => new Promise(resolve => setTimeout(() => resolve(1), 200)), () => new Promise((resolve, reject) => setTimeout(() => reject("Error"), 100)) ]

Output: {"t": 100, "rejected": "Error"}

Explanation: Since one of the promises rejected, the returned promise also rejected with the same error at the same time.

Example 3:

Input: functions = [ () => new Promise(resolve => setTimeout(() => resolve(4), 50)), () => new Promise(resolve => setTimeout(() => resolve(10), 150)), () => new Promise(resolve => setTimeout(() => resolve(16), 100)) ]

Output: {"t": 150, "resolved": [4, 10, 16]}

Explanation: All the promises resolved with a value. The returned promise resolved when the last promise resolved.

Code​

type Fn<T> = () => Promise<T>;

function promiseAll<T>(functions: Fn<T>[]): Promise<T[]> {
  return new Promise<T[]>((res, rej) => {
    // Create an array with the length of our functions array.
    // So we can update the results at the correct index as they come in.
    const outputs: T[] = new Array<T>(functions.length);
    // countdown for remaining functions to execute. As they will run asynchronously we need a counter to maintain our 'state'.
    let remainingFns = functions.length;
    for (let i = 0; i < functions.length; i++) {
      // execute func
      functions[i]()
        .then((val) => {
          // set the index value for our ordered array to the result.
          outputs[i] = val;
          // decrement the amount of remaining funcs.
          remainingFns--;

          // as this is ran in an async manner we need to check if this is our last func.
          if (remainingFns === 0) return res(outputs);
        })
        // return a rejection upon failure
        .catch(rej);
    }
  });
}

Key Takeaways​

1. I focused way too much on the parallel element to this problem. If I had just focused on solving the problem first. I might have discovered how it comes with just running a promise in a for loop.
2. Write code thoughts -> write code -> try to make it better / right -> look at solutions. This code flow should always be followed when solving questions.

The problem statement​

Given a function fn and a time in milliseconds t, return a debounced version of that function.

A debounced function is a function whose execution is delayed by t milliseconds and whose execution is cancelled if it is called again within that window of time. The debounced function should also receive the passed parameters.

For example, let's say t = 50ms, and the function was called at 30ms, 60ms, and 100ms. The first 2 function calls would be cancelled, and the 3rd function call would be executed at 150ms. If instead t = 35ms, The 1st call would be cancelled, the 2nd would be executed at 95ms, and the 3rd would be executed at 135ms.

Understanding the problem​

The question is asking us to implement a function which checks for an existing timeout of the previous invocation of the function and if there is one remove it, if not then set a new timeout.

Quite a simple one really... especially for a medium!

Examples​

Example 1:

Input: t = 50

calls = [ {"t": 50, inputs: [1]}, {"t": 75, inputs: [2]} ]

Output: [{"t": 125, inputs: [2]}]

Explanation:

let start = Date.now();

function log(...inputs) { console.log([Date.now() - start, inputs ]) } const dlog = debounce(log, 50); setTimeout(() => dlog(1), 50); setTimeout(() => dlog(2), 75);

The 1st call is cancelled by the 2nd call because the 2nd call occurred before 100ms The 2nd call is delayed by 50ms and executed at 125ms. The inputs were (2).

Example 2:

Input:

t = 20

calls = [ {"t": 50, inputs: [1]}, {"t": 100, inputs: [2]} ]

Output: [{"t": 70, inputs: [1]}, {"t": 120, inputs: [2]}]

Explanation: The 1st call is delayed until 70ms. The inputs were (1). The 2nd call is delayed until 120ms. The inputs were (2).

Example 3:

Input:

t = 150

calls = [ {"t": 50, inputs: [1, 2]}, {"t": 300, inputs: [3, 4]}, {"t": 300, inputs: [5, 6]} ]

Output: [{"t": 200, inputs: [1,2]}, {"t": 450, inputs: [5, 6]}]

Explanation: The 1st call is delayed by 150ms and ran at 200ms. The inputs were (1, 2). The 2nd call is cancelled by the 3rd call The 3rd call is delayed by 150ms and ran at 450ms. The inputs were (5, 6).

Code​

type F = (...args: number[]) => void;

function debounce(fn: F, t: number): F {
  let timeoutId: ReturnType<typeof setTimeout> | null = null;
  return function (...args) {
    if (timeoutId) {
      clearTimeout(timeoutId);
    }
    timeoutId = setTimeout(() => fn(...args), t);
  };
}

Key Takeaways​

1. Creating a type of a return type from the typeof a return of a function is surprisingly simple!
2. A lot of these js challenges are very much cache based. A good concept to remember!

The problem statement​

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

Understanding the problem​

The question is asking us to return an array which takes the iterated item and sets the value to the index of the value i.e. nums[loopedItem].

There is nothing mentioned about ordering so we just do it inline sequentially as we trace down the array.

It asks for a bonus answer with O(1) space. But for now O(n) is good enough.

Examples​

Example 1:

Input: nums = [0,2,1,5,3,4]

Output: [0,1,2,4,5,3]

Explanation: The array ans is built as follows: ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]] = [0,1,2,4,5,3]

Example 2:

Input: nums = [5,0,1,2,3,4]

Output: [4,5,0,1,2,3]

Explanation: The array ans is built as follows: ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]] = [4,5,0,1,2,3]

Code​

function buildArray(nums: number[]): number[] {
  return nums.map((val) => nums[val]);
}

The problem statement​

Write a class that allows getting and setting key-value pairs, however a time until expiration is associated with each key.

The class has three public methods:

set(key, value, duration): accepts an integer key, an integer value, and a duration in milliseconds. Once the duration has elapsed, the key should be inaccessible. The method should return true if the same un-expired key already exists and false otherwise. Both the value and duration should be overwritten if the key already exists.

get(key): if an un-expired key exists, it should return the associated value. Otherwise it should return -1.

count(): returns the count of un-expired keys.

Understanding the problem​

What they are asking for is pretty simple.

Create a map which holds our key value pairs. Each value should consist of the numerical value and a timeoutid that is a reference to the setTimeout we create.

Examples​

Example 1:

Input:

actions = ["TimeLimitedCache", "set", "get", "count", "get"]

values = [[], [1, 42, 100], [1], [], [1]]

timeDelays = [0, 0, 50, 50, 150]

Output: [null, false, 42, 1, -1]

Explanation:

• At t=0, the cache is constructed.
• At t=0, a key-value pair (1: 42) is added with a time limit of 100ms. The value doesn't exist so false is returned.
• At t=50, key=1 is requested and the value of 42 is returned.
• At t=50, count() is called and there is one active key in the cache.
• At t=100, key=1 expires.
• At t=150, get(1) is called but -1 is returned because the cache is empty.

Example 2:

Input:

actions = ["TimeLimitedCache", "set", "set", "get", "get", "get", "count"]

values = [[], [1, 42, 50], [1, 50, 100], [1], [1], [1], []]

timeDelays = [0, 0, 40, 50, 120, 200, 250]

Output: [null, false, true, 50, 50, -1, 0]

Explanation:

• At t=0, the cache is constructed.
• At t=0, a key-value pair (1: 42) is added with a time limit of 50ms. The value doesn't exist so false is returned.
• At t=40, a key-value pair (1: 50) is added with a time limit of 100ms. A non-expired value already existed so true is returned and the old value was overwritten.
• At t=50, get(1) is called which returned 50.
• At t=120, get(1) is called which returned 50.
• At t=140, key=1 expires.
• At t=200, get(1) is called but the cache is empty so -1 is returned.
• At t=250, count() returns 0 because the cache is empty.

Code​

class TimeLimitedCache {
  private cache: Map<
    number,
    { value: number; timeoutId: ReturnType<typeof setTimeout> }
  >;
  constructor() {
    this.cache = new Map<
      number,
      { value: number; timeoutId: ReturnType<typeof setTimeout> }
    >();
  }

  set(key: number, value: number, duration: number): boolean {
    const hasEntry = this.cache.has(key);
    if (hasEntry) {
      clearTimeout(this.cache.get(key).timeoutId);
    }
    const timeoutId = setTimeout(() => this.cache.delete(key), duration);
    this.cache.set(key, { value, timeoutId });
    return hasEntry;
  }

  get(key: number): number {
    return this.cache.has(key) ? this.cache.get(key).value : -1;
  }

  count(): number {
    return this.cache.size;
  }
}

/**
 * const timeLimitedCache = new TimeLimitedCache()
 * timeLimitedCache.set(1, 42, 1000); // false
 * timeLimitedCache.get(1) // 42
 * timeLimitedCache.count() // 1
 */

Key Takeaways​

1. A Map has a property on it called .size which is like array.length.

The problem statement​

Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).

Specifically, ans is the concatenation of two nums arrays.

Return the array ans.

Understanding the problem​

Please return an array that is double the size of the original array and where you enter new indexs, populate them with the equivalent values in the before allocated array.

Disecting the parts of the problem:

1. nums = integer array
2. n = nums.length
3. ans = new Array(n * 2)
4. ans elements must equal the same as nums at relevant pointers
5. ans[i] must equal nums[i - n] where i > n

The problem tries to throw you off by giving you the index looped equation in reverse order. Also ans[i + n] in a loop would be out of bound since we would loop the ans array.

We could loop the original array, but guessing that elements will be there rather than truly looping through didn't feel like best practice.

Approaching the problem​

We will want to create a function that has the following:

1. A reference to nums.length
2. A new array based upon nums.length *= 2
3. A for loop that loops the new array
   1. An if statement to check if we are looping an index that is within the original array bounds. If it is then do a 1-1 map. newArray[i] = nums[i];
   2. Else we will do the following newArray[i] = nums[i - n] to get the duplicated positional value.
4. Return the array.

Examples:​

Example 1:

Input: nums = [1,2,1]

Output: [1,2,1,1,2,1]

Explanation: The array ans is formed as follows:

• ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
• ans = [1,2,1,1,2,1]

Example 2:

Input: nums = [1,3,2,1]

Output: [1,3,2,1,1,3,2,1]

Explanation: The array ans is formed as follows:

• ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
• ans = [1,3,2,1,1,3,2,1]

Constraints:

• n == nums.length
• 1 <= n <= 1000
• 1 <= nums[i] <= 1000

Code solution​

function getConcatenation(nums: number[]): number[] {
  const n = nums.length;
  // create a 2 times larger array with blank vals
  const newArray = new Array(n * 2).fill(0);
  // loop that new array
  for (let i = 0; i < newArray.length; i++) {
    // if the index matches that within the original array, do a 1-1 map.
    if (i <= n - 1) {
      newArray[i] = nums[i];
    } else {
      // else get the value from nums array at index position i - nums.length; i.e. 4 - 4 = position 0.
      newArray[i] = nums[i - n];
    }
  }
  return newArray;
}

Key Takeaways​

1. Making notes at the top of the function to understand and digest the problem before writing any code is a good practice to do. Follow the question and note down the key factors to influence your answer.
2. Creating an array with new Array(n * 2); would create the array with a capacity, but wouldnt populate any items. So .fill(0) must be called to populate it with a .length.

Overview​

In computer science we have two different types of arrays. We have static arrays and we have dynamic arrays.

Static arrays​

These are arrays which have an allocated amount of capacity and cannot increase without being re-created. They are commonly found in lower level languages in those such as c++.

Dynamic arrays​

These are arrays which will scale with the data being requested to be stored. They are found in all languages.

The challenge​

Re-create the behaviour of a js dynamic array inside of a custom typescript class.

Here are the rules:​

Design a Dynamic Array (aka a resizable array) class, such as an ArrayList in Java or a vector in C++.

Your DynamicArray class should support the following operations:

• DynamicArray(int capacity) will initialize an empty array with a capacity of capacity, where capacity > 0.
• int get(int i) will return the element at index i. Assume that index i is valid.
• void set(int i, int n) will set the element at index i to n. Assume that index i is valid.
• void pushback(int n) will push the element n to the end of the array.
• int popback() will pop and return the element at the end of the array. Assume that the array is non-empty.
• void resize() will double the capacity of the array.
• int getSize() will return the number of elements in the array.
• int getCapacity() will return the capacity of the array.

If we call void pushback(int n) but the array is full, we should resize the array first.

Example 1:

Input: ["Array", 1, "getSize", "getCapacity"]

Output: [null, 0, 1] Example 2:

Input: ["Array", 1, "pushback", 1, "getCapacity", "pushback", 2, "getCapacity"]

Output: [null, null, 1, null, 2] Example 3:

Input: ["Array", 1, "getSize", "getCapacity", "pushback", 1, "getSize", "getCapacity", "pushback", 2, "getSize", "getCapacity", "get", 1, "set", 1, 3, "get", 1, "popback", "getSize", "getCapacity"]

Output: [null, 0, 1, null, 1, 1, null, 2, 2, 2, null, 3, 3, 1, 2] Note:

The index i provided to get(int i) and set(int i) is guranteed to be greater than or equal to 0 and less than the number of elements in the array.

class DynamicArray {
  /**
   * @constructor
   * @param {number} capacity
   */
  constructor(capacity) {
    this.capacity = capacity;
    this.length = 0;
    this.arr = new Array(this.capacity).fill(0);
  }

  /**
   * @param {number} i
   * @returns {number}
   */
  get(i) {
    return this.arr[i];
  }

  /**
   * @param {number} i
   * @param {number} n
   * @returns {void}
   */
  set(i, n) {
    this.arr[i] = n;
  }

  /**
   * @param {number} n
   * @returns {void}
   */
  pushback(n) {
    if (this.length === this.capacity) {
      this.resize();
    }
    this.arr[this.length] = n;
    this.length++;
  }

  /**
   * @returns {number}
   */
  popback() {
    return this.arr[--this.length];
  }

  /**
   * @returns {void}
   */
  resize() {
    this.capacity *= 2;
    const newArr = new Array(this.capacity).fill(0);
    for (let i = 0; i < this.length; i++) {
      newArr[i] = this.arr[i];
    }
    this.arr = newArr;
  }

  /**
   * @returns {number}
   */
  getSize() {
    return this.length;
  }

  /**
   * @returns {number}
   */
  getCapacity() {
    return this.capacity;
  }
}

Learnings​

This problem forces you to really think about what js has to do under the hood to maintain arrays. It was tricky to understand and I initially resorted to using helper funcs provided by js out the box. But after reading and digesting the solution, I realised that most of this stuff can be done manually.

It's another case of re-reading the question and really understand what it's asking for.

The problem statement​

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Understanding the problem​

What they are asking for here is the following:

1. Return the count of items that do not equal val.
2. Place the items that do not equal val to the beginning of the array.
3. Don't be concerend about what the val items look like.

Do not:

1. Create a new array and do funky manipulation. This is a test to get you to solve the problem inline with a big O of O(1) in space. Which means no new variables that could hold x items.

Approaching the problem​

We will want to create a function that has the following:

1. A value to hold k which we need to return at the end, but will also act as our pointer to move items to.
2. A for loop to iterate the array.
3. An if statement to check if the item is not equal to val.
   1. A reassignment of the item to position k and increment k.
4. return k.

Remember, they are looking to inline array manipulation and the result of how many vals don't equal val.

Examples:​

Example 1:

Input: nums = [3,2,2,3], val = 3

Output: 2, nums = [2,2,,]

Explanation: Your function should return k = 2, with the first two elements of nums being 2.

It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2

Output: 5, nums = [0,1,4,0,3,,,_]

Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.

Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k (hence they are underscores).

Code solution​

/**
  This func will tell us the number of unique values in an array.
  We do this by looping the array, looking for nums that != val
  Then moving them to the beginning of the array.
 */
function removeElement(nums: number[], val: number): number {
  // Store k as a pointer.
  let k = 0;
  // Loop the array
  for (let i = 0; i < nums.length; i++) {
    // If the item looped is not equal to val
    if (nums[i] !== val) {
      // Set the value of num at k to the current num.
      // K is essentially the last known index to reassign a value to.
      // As we loop, k is confirmed to not be equal to val. so we are safe to replace.
      nums[k] = nums[i];
      // We increment K each time, we know that prev elements wont be overridden
      // Since we are doing in an inline replace when we do find matching elems.
      k++;
    }
  }
  return k;
}

Key Takeaways​

1. Pointers are a useful concept in array algorithm questions.
2. Re-read the question 3 times thoroughly, make notes in code. For example, the part about not caring what happens to the val values I missed the first time and spent 15 mins on an inefficient solution.
3. KISS (Keep It Simple Stupid).