remi-bruguier’s gists

remi-bruguier / validParentheses.js

Last active May 12, 2020 19:46

validParentheses

	/**
	* Valid Parentheses
	* @param {string} s
	* @return {boolean}
	*/
	const validParentheses = (s) => {
	if (s === null \|\| !s.length) return true;

	const chars = s.split('');
	const stack = [];

remi-bruguier / twoSum.ts

Created May 16, 2020 12:37

Return whether or not there are two numbers in the list that add up to k.

	const twoSum = (numbers:number[], k: number): Boolean => {

	const rec:Record<number,number>= {};

	for(const n of numbers){
	rec[n] = n;
	if(rec.hasOwnProperty(k-n)) return true;
	}

	return false;

remi-bruguier / uniqueNumber.ts

Created May 17, 2020 15:46

Given a list of numbers, where every number shows up twice except for one number, find that one number.

const uniqueNumber = (arr:number[]):number => arr.reduce((x,y) => x^y);

remi-bruguier / couldBeMadeNonDecreasing.ts

Last active May 18, 2020 06:47

You are given an array of integers in an arbitrary order. Return whether or not it is possible to make the array non-decreasing by modifying at most 1 element to any value.

	const couldBeMadeNonDecreasing = (arr:number[]):Boolean => {
	let decreasingPairs = 0
	for(let i in arr){
	if(arr[i] > arr[+i+1]){
	decreasingPairs++
	}
	}
	return decreasingPairs <= 1
	}

remi-bruguier / MaxStack.ts

Created May 21, 2020 15:06

Implement a class for a stack that supports all the regular functions (push, pop) and an additional function of max() which returns the maximum element in the stack (return None if the stack is empty). Each method should run in constant time.

	class MaxStack {

	private stack: number[] = new Array<number>();
	private maxStack: number[] = new Array<number>();
	private length: number = 0;

	public push(item: number): void {
	let previousMax = this.maxStack[this.length-1] \|\| 0;
	this.maxStack[this.length] = item > previousMax ? item : previousMax;
	this.stack[this.length++] = item;

remi-bruguier / waysToClimbStairs.ts

Created May 22, 2020 20:15

	// no recursion
	const waysToClimbStairs = (n:number):number => {
	const a:number[] = [1,1];
	if(n>1){
	for(let i = 2; i <= n ; i++){
	a[i] = a[i-1] + a[i-2];
	}
	};
	return a[a.length - 1];
	}

remi-bruguier / waysToClimbStairs.ts

Last active May 22, 2020 22:33

	// without recursion 💪
	const waysToClimbStairs = (n:number):number => {
	const a:number[] = [1,1];
	if(n>1){
	for(let i = 2; i <= n ; i++){
	a[i] = a[i-1] + a[i-2];
	}
	};
	return a[a.length - 1];
	}

remi-bruguier / findPythagoreanTriplets.ts

Created May 25, 2020 20:32

Given a list of numbers, find if there exists a pythagorean triplet in that list. A pythagorean triplet is 3 variables a, b, c where a² + b² = c²

	const findPythagoreanTriplets = (arr:number[]):boolean => {

	if(arr.length<3) return false;

	const sorted = arr
	.map(v => v*v)
	.sort((a,b) => a-b);

	let [l,r,i] = [0, sorted.length -2, sorted.length -1];

remi-bruguier / getEditDistance.ts

Created May 29, 2020 20:09

Given two strings, determine the edit distance between them. The edit distance is defined as the minimum number of edits (insertion, deletion, or substitution) needed to change one string to the other.

	const getEditDistance = function(a: string, b: string):number{

	if(!a.length) return b.length;
	if(!b.length) return a.length;

	const matrix:number[][] = [];

	// fill first row and column
	for(let i = 0; i <= b.length; i++){
	matrix[i] = [i];

remi-bruguier / word_search.ts

Created June 7, 2020 18:08

You are given a 2D array of characters, and a target string. Return whether or not the target word exists in the matrix. Unlike a standard word search, the word must be either going left-to-right, or top-to-bottom in the matrix.

	const word_search = (arr:string[][], word: string) : boolean => {

	if(word.length > arr.length) return false;

	let horizontal = '';
	let vertical:{ [key: string]: string } = {};

	for(let i=0; i<arr.length;i++){
	for(let j=0; j<arr[i].length;j++){
	horizontal+= arr[i][j];

Rémi BRUGUIER remi-bruguier