CollegeStash – Page 3

Find mismatches in badging records

Given an ordered list of employees who used their badge to enter or exit the room, write a function that returns two collections:
1. All employees who didn’t use their badge while exiting the room – they recorded an enter without a matching exit. (All employees are required to leave the room before the log ends.)
2. All employees who didn’t use their badge while entering the room – they recorded an exit without a matching enter. (The room is empty when the log begins.)
Each collection should contain no duplicates, regardless of how many times a given employee matches the criteria for belonging to it.

records1 = [
	  ["Martha",   "exit"],
	  ["Paul",     "enter"],
	  ["Martha",   "enter"],
	  ["Steve",    "enter"],
	  ["Martha",   "exit"],
	  ["Jennifer", "enter"],
	  ["Paul",     "enter"],
	  ["Curtis",   "exit"],
	  ["Curtis",   "enter"],
	  ["Paul",     "exit"],
	  ["Martha",   "enter"],
	  ["Martha",   "exit"],
	  ["Jennifer", "exit"],
	  ["Paul",     "enter"],
	  ["Paul",     "enter"],
	  ["Martha",   "exit"],
	  ["Paul",     "enter"],
	  ["Paul",     "enter"],
	  ["Paul",     "exit"],
	  ["Paul",     "exit"] 
	]

Expected output: ["Paul", "Curtis", "Steve"], ["Martha", "Curtis", "Paul"]

Other test cases:

records2 = [
	  ["Paul", "enter"],
	  ["Paul", "exit"],
	]

Expected output: [], []

records3 = [
	  ["Paul", "enter"],
	  ["Paul", "enter"],
	  ["Paul", "exit"],
	  ["Paul", "exit"],
	]

Expected output: ["Paul"], ["Paul"]

records4 = [
	  ["Paul", "enter"],
	  ["Paul", "exit"],
	  ["Paul", "exit"],
	  ["Paul", "enter"],
	]

Expected output: ["Paul"], ["Paul"]

const mismatches = (records) => {
  const obj = {};
  const notExited = [];
  const notEntered = [];
  for (const [name, state] of records) {
    if (!(name in obj)) {
      obj[name] = 0;
    }

    if (state === 'enter') {
      obj[name]++;
    } else {
      obj[name]--;
    }

    if (obj[name] > 1) {
      if (!notExited.includes(name)) {
        notExited.push(name);
      }
      obj[name] = 0;
    }
    if (obj[name] < 0) {
      if (!notEntered.includes(name)) {
        notEntered.push(name);
      }
      obj[name] = 0;
    }
  }

  for (const [key, val] of Object.entries(obj)) {
    if (val === 1) {
      if (!notExited.includes(key)) {
        notExited.push(key);
      }
    }
  }
  return [notExited, notEntered];
};

console.log(mismatches([
    ["Martha", "exit"],
    ["Paul", "enter"],
    ["Martha", "enter"],
    ["Steve", "enter"],
    ["Martha", "exit"],
    ["Jennifer", "enter"],
    ["Paul", "enter"],
    ["Curtis", "exit"],
    ["Curtis", "enter"],
    ["Paul", "exit"],
    ["Martha", "enter"],
    ["Martha", "exit"],
    ["Jennifer", "exit"],
    ["Paul", "enter"],
    ["Paul", "enter"],
    ["Martha", "exit"],
    ["Paul", "enter"],
    ["Paul", "enter"],
    ["Paul", "exit"],
    ["Paul", "exit"]
  ]),
  mismatches([
    ["Paul", "enter"],
    ["Paul", "exit"]
  ]),
  mismatches([
    ["Paul", "enter"],
    ["Paul", "enter"],
    ["Paul", "exit"],
    ["Paul", "exit"],
  ]),
  mismatches([
    ["Paul", "enter"],
    ["Paul", "exit"],
    ["Paul", "exit"],
    ["Paul", "enter"],
  ]));

Demo

August 12, 2022

Implement getElementById() polyfill

Implement a method to search for an element in DOM by it’s Id. We use Breadth First Search (BFS) algorithm to traverse the DOM and store the elements in a queue in the following example.
Example: document.getElementById(‘demo’)

<div id="demo">
  <div>1</div>
  <div>2</div>
  <div>
    <div id="hello">Hello world!</div>
  </div>
  <div>3</div>
</div>
<script>
const getElementById = (element, id) => {
  const queue = [element];
  while (queue.length) {
    const curr = queue.shift();
    if (curr.id === id) {
      return curr;
    }
    if (curr.children.length) {
      queue.push(...curr.children);
    }
  }
};

console.log(getElementById(document.documentElement, 'hello').innerHTML); // Hello world!
</script>

Demo

August 9, 2022

Valid Parentheses

/**
 * @param {string} str
 * @return {boolean}
 */
const isValid = function(str) {
  /*  
    if (typeof str !== 'string') {
      return false;
    }
  */
  const stack = [];
  const map = {
    ')': '(',
    '}': '{',
    ']': '['
  };

  for (const char of str) {
    if (Object.values(map).includes(char)) {
      stack.push(char);
    } else if (Object.keys(map).includes(char)) {
      if (map[char] !== stack[stack.length - 1]) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0;
};

console.log(
  isValid('{{[test]})'), // false
  isValid('({[test]})'), // true
  isValid('({['), // false
  isValid(''), // true
);

/* You can verify the following cases as well, by uncommenting the if statement at the start of the method.
console.log(
  isValid(),            // false
  isValid(null),        // false
  isValid(0),           // false
  isValid(1),           // false
  isValid(1.12)         // false
);
*/

Demo

August 6, 2022

HTML element as a datastore

The dataset read-only property of the HTMLElement interface provides read/write access to custom data attributes (data-*) on elements. It exposes a map of strings (DOMStringMap) with an entry for each data- attribute.

HTMLElement.dataset

<div id="demo" data-user="john"></div>
<script>
const element = document.getElementById('demo');

// Set a data attribute.
element.dataset.dateOfBirth = '2000-10-10';
// HTML: <div id="demo" data-user="john" data-date-of-birth="2000-10-10"></div>

delete element.dataset.dateOfBirth;
// HTML: <div id="demo" data-user="john"></div>
</script>

Demo

July 26, 2022

React Component to render Directory Structure

import "./styles.css";

const Directory = (props) => {
  const { content } = props;

  return content.children.map((item) => {
    const isDirectory = "children" in item;
    return (
      <div class="container" key={item.name}>
        <span> {isDirectory ? "Dir - " : "File - "}</span>
        <span>{item.name}</span>
        {isDirectory && <Directory content={item} />}
      </div>
    );
  });
};

export default function App() {
  return (
    <Directory
      content={{
        name: "Root",
        children: [
          {
            name: "John"
          },
          {
            name: "Private",
            children: [
              {
                name: "Private1"
              },
              {
                name: "Private2"
              }
            ]
          }
        ]
      }}
    />
  );
}


/* Output

File - John
Dir - Private
  File - Private1
  File - Private2

*/

July 23, 2022

Shallow copy vs Deep copy

// Shallow Copy.
const obj = {
  a: 1,
  b: 2,
  c: 3,
  d: {
    f: 4,
  },
};

const testObj = {
  ...obj // Similar to Object.assign()
};
testObj.d.f = 5; // This modified the original object.

console.log(obj.d);
// {
//    f: 4,
//  }

const newTestObj = {
  ...obj,
  d: {
    ...obj.d
  },
};

// Deep Copy.
const deepCopy = (inpObj) => {
  const obj = {};
  for (const [key, val] of Object.entries(inpObj)) {
    obj[key] = typeof val === 'object' ? deepCopy(val) : val;
  }
  return obj;
};

console.log(deepCopy(obj));
// {
//  a: 1,
//  b: 2,
//  c: 3,
//  d: {
//    f: 5
//   }
//  }

Demo

July 23, 2022

Singleton pattern – Javascript

Often times we would want to limit number of instances of a class to 1. We can achieve this using the following pattern. You can use Object.freeze() to prevent further modifications of an object.

// Using ES6 Classes.
class Singleton {
  static getInstance() {
    if (!this.instance) {
      this.instance = new Object('Test');
    }
    return this.instance;
  }
}

console.log(Singleton.getInstance() === Singleton.getInstance());
  
// true

// Using functions.
function SingletonWrapper() {
  let instance;

  return {
    getInstance: function() {
      if (!instance) {
        instance = new Object('Test');
      }
      return instance;
    }
  }
}

const singletonWrapper = SingletonWrapper();

console.log(singletonWrapper.getInstance() === singletonWrapper.getInstance());
// true

Demo

July 23, 2022

Minimum Window Substring

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
  if (s.length < t.length) {
    return '';
  }

  const sMap = Array(256).fill(0);
  const tMap = Array(256).fill(0);
  for (const c of t) {
    tMap[c.charCodeAt(0)]++;
  }
  let count = 0;
  let start = 0;
  let minStart = -1;
  let min = s.length;
  for (let j = 0; j < s.length; j++) {
    const c = s[j].charCodeAt(0);
    sMap[c]++;
    if (sMap[c] <= tMap[c]) {
      count++;
    }

    if (count === t.length) {
      // Minimize the window by moving the start pointer.
      while (sMap[s[start].charCodeAt(0)] > tMap[s[start].charCodeAt(0)]) {
        sMap[s[start].charCodeAt(0)]--;
        start++;
      }
      const currLen = j - start + 1;
      if (currLen < min) {
        min = currLen;
        minStart = start;
      }
    }
  }
  if (minStart === -1 && count !== t.length) {
    return '';
  }
  return minStart !== -1 ? s.substring(minStart, minStart + min) : s;
};

console.log(minWindow('ABCDFEDFI', 'DF'));
// DF

Demo

April 24, 2022

Maximum Subarray of size K

// Uses sliding window technique. Runtime Complexity 0(n).
const maxSubarraySizeK = (arr, k) => {
  if (arr.length < k) {
    return [];
  }
  let sum = 0;
  let s = 0;
  let maxSum = Number.MIN_VALUE;
  for (let i = 0; i < arr.length; i++) {
    if (i < k) {
      sum += arr[i];
      maxSum = sum;
    } else {
      sum += arr[i] - arr[i - k];
      if (sum > maxSum) {
        maxSum = sum;
        s = i - k + 1;
      }
    }
  }
  return arr.slice(s, s + k);
};

console.log(maxSubarraySizeK([1, 4, 2, 10, 2, 3, 1, 0, 20], 4));
// [3, 1, 0, 20]  - 24

Demo

April 24, 2022