lienista’s gists

lienista / ctci-1.5-does-differ-by-one.js

Last active August 28, 2018 07:38

Algorithms in Javascript: CTCI 1.5 One Away: Given 2 strings, determine if they differ from each other by a single character, either via insertion, deletion or replacement of a character.

	const isDifferByOne = (s1, s2) => {
	if(s1.length > s2.length + 1 \|\|
	s2.length > s1.length + 1) {
	return false;
	}

	let count = 0;
	let charMap = new Map();
	let a1 = s1.split('');
	let a2 = s2.split('');

lienista / ctci-1.6-compress-string.js

Last active August 28, 2018 07:35

Algorithms in Javascript: String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, aabcccccaaa would become a2b1c5a3. If the compressed string would not become smaller than the original string, your method should return the original string.

	const compressString = (s1) => {
	let charMap = new Map();

	for(let i=0; i<s1.length; i++){
	charMap.set(s1[i], charMap.get(s1[i]) + 1 \|\| 1);
	}

	let s = '',
	mapKeys = charMap.keys(),
	mapValues = charMap.values();

lienista / ctci-1.7-rotate-matrix.js

Last active August 28, 2018 07:31

Algorithms in Javascript: CTCI 1.7 Rotate matrix: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

	const rotateMatrix = (m) => {
	let dimensions = [m.length, m[0].length];
	let target = new Array(dimensions[1]);
	for (let i = 0; i < dimensions[1]; i++) {
	target[i] = new Array(dimensions[0]);
	}
	for(let r=0; r<dimensions[0]; ++r) { //rows
	for(let c=0; c<dimensions[1]; ++c) { //cols
	target[c][dimensions[0] - r - 1] = m[r][c];
	}

lienista / ctci-1.7-rotate-matrix-1.js

Last active August 28, 2018 07:31

Algorithms in Javascript: CTCI 1.7 Rotate matrix in place: Rotate matrix: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

	const rotate = (m) => {
	const n = m.length,
	ny = m[0].length;
	if(n != ny) return; //undefined if not square matrix, cannot rotate in place
	let temp;
	m = m.reverse(); //reverse rows: bottom row placed on top

	//perform swap
	for (let r = 0; r < n; r++) {
	for (let c = 0; c < r; c++) {

lienista / ctci-1.8-zero-matrix.js

Last active August 28, 2018 07:32

Algorithms in Javascript: CTCI 1.8 Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

	const zeroMatrix = (m) => {
	const sizeY = m.length,
	sizeX = m[0].length;
	let charMap = new Map();

	for(let r=0; r<sizeY; r++){
	for(let c=0; c<sizeX; c++){
	if(m[r][c] === 0) {
	charMap.set(r, c);
	}

lienista / ctci-1.9-is-rotated-string.js

Last active December 12, 2018 05:50

Algorithms in Javascript: CTCI 1.9 - String rotation: Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, write the code to check if one string is a rotation of the other using only one call to isSubstring (e.g., waterbottle is a rotation of erbottlewat)

	const isSubstring = (s1, s2) => {
	if (!s1 \|\| !s2) {
	return false;
	}
	if (s1.length !== s2.length) {
	return false;
	}

	return (s1 + s1).includes(s2);
	}

lienista / leetcode-4-median-of-two-arrays.js

Last active August 31, 2021 07:49

Algorithms in Javascript: Leetcode 4. Median of Two Sorted Arrays - There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.

	const median = (a1, a2) => {
	let x = a1.concat(a2);
	x.sort(function (a,b) {
	return a - b;
	});
	let len = x.length;

	return len%2 === 0 ? (x[Math.floor(len/2)-1] + x[Math.ceil(len/2)])/2 : x[Math.floor(len/2)];

	}

lienista / leetcode-1-sum-of-two-indices.js

Last active October 11, 2018 22:59

Algorithms in Javascript: Leetcode 1. Two Sum - Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

	const twoSum = (a, target) => {
	let len = a.length;
	if(a.length === 2) return [0, 1];
	for(let i=0; i<len; i++) {
	for (let j = i + 1; j < len; j++) {
	if(a[j] === target - a[i]) {
	return [i,j];
	}
	}
	}

lienista / leetcode-3-longest-substring-without-repeating-characters.js

Last active October 11, 2018 22:59

Algorithms in Javascript: Leetcode 3. Longest Substring Without Repeating Characters - Given a string, find the length of the longest substring without repeating characters.

	const lengthOfLongestSubstring = (s) => {
	if(s === '') return 0;
	let a = s.split('');
	let newS = '';
	let len = 1;
	let words =a[0];
	let sLength = a.length;
	for(let i=0; i<sLength; i++){
	newS = a[i];
	let wordLen = sLength;

lienista / leetcode-5-longest-palindrome-substring.js

Last active October 28, 2019 16:10

Algorithms in Javascript: Leetcode 5. Longest Palindromic Substring - Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

	const longestPalindrome = (s) => {
	const reverseS = s.split('').reverse().join('');
	let len = s.length;
	let currentWord = '';
	let maxWord = s[0];

	//compare original string s with reverse string
	for(let i=0; i<len; i++){
	currentWord = '';
	for(let j=i; j<len; j++){ //note index j starts at i, not 0

macmini lienista