Cracking_the_Coding_Interview.js

//Is Unique: Implement an algorithm to determine if a string 
//has all unique characters. What if you cannot use additional
//data structures?

function isUnique(str) {
	//Assuming capital letter is unique from its lower case
	//Will there be spaces?/Do spaces count as characters?
	//would be easy to use a Map & iterate through: O(n)
	//No add'l data structures: Sort & loop through O(n + logn)
	if (str.length <= 1) return true;
	if (str.length > 128) return false; //greater than possible unique characters
	let sorted = mergeSort(str);
	for (let i = 0; i < str.length - 1; i++) {
		if (sorted[i] === sorted[i + 1]) return false;
	}
	
	return true;
}

function mergeSort(str) {
  if (str.length <= 1) return str;
  
  let mid = Math.floor(str.length/2);
  
  let left = mergeSort(str.substring(0, mid));
  let right = mergeSort(str.substring(mid));
  
  return merge(left, right);
}

function merge(a, b) {
  let sorted = "";
  
  while (a.length && b.length) {
		if (a[0] > b[0]) {
			sorted += b[0];
			b = b.substring(1);
		} else {
			sorted += a[0];
			a = a.substring(1);
		}
  }
  
  return sorted.concat(a.length ? a : b);
}


// console.log(isUnique("hoola"));
// console.log(isUnique("bop"));
// console.log(isUnique("b"));
// console.log(isUnique("-$onedla$-"));
// console.log(isUnique("birdhouse"));

//Check Permutation: Given two strings,write a method to decide 
//if one is a permutation of the other.

//Brute force: sort & loop through: O(n + logn)
//If lengths aren't the same, false
//Alt: create a map for each, ++ for first, -- for second, if any values !== 0, false: O(2n);
function checkPermutation(a, b) {
	if (a.length !== b.length) return false;
	let charMap = {};
	
	for (let i = 0; i< a.length; i++) {
		charMap[a[i]] = charMap[a[i]] ? charMap[a[i]] + 1 : 1;
		charMap[b[i]] = charMap[b[i]] ? charMap[b[i]] - 1 : -1;
	};
	
	for (let key in charMap) {
		if (charMap[key] !== 0) return false;
	};
	
	return true;
}

// console.log(checkPermutation("123", "231"));
// console.log(checkPermutation("bcgh", "ghbc"));
// console.log(checkPermutation("", "231"));
// console.log(checkPermutation("124", "231"));

//URLify: Write a method to replace all spaces in a string with 
//'%20'. 

//Split & join w/ "%20": O(2n)

function urlify(str) {
	if (str.length <= 2) return str;
	
	return str.split(" ").join("%20");
}

//console.log(urlify("Mr John Smith"));

//Palindrome Permutation: Given a string, write a function to 
//check if it is a permutation of a palindrome. A palindrome is 
//a word or phrase that is the same forwards and backwards. A 
//permutation is a rearrangement of letters. The palindrome does 
//not need to be limited to just dictionary words.

//Create a frequency map of characters, check if it's an even
//quantity: O(2n)

function canPalindrome(str) {
	if (str.length <= 1) return true;
	let charMap = {};
	
	for (let char of str.toLowerCase()) {
		if (char !== " ") charMap[char] = charMap[char] ? charMap[char] + 1 : 1;
	}
	
	let oddCount = 0;
	for (let key in charMap) {
		if (charMap[key] % 2 !== 0) oddCount++;
		if (oddCount > 1) return false;
	}
	
	return true;
}

// console.log(canPalindrome("Tact Coa"));
// console.log(canPalindrome("blueberry"));
// console.log(canPalindrome("ooboo"));

// Partition: Write code to partition a linked list around a value x, 
//such that all nodes less than x come before all nodes greater than or 
//equal to x. If x is contained within the list, the values of x only 
//need to be after the elements less than x (see below). The partition 
//element x can appear anywhere in the "right partition"; it does not 
//need to appear between the left and right partitions.

class Node {
	constructor(val) {
		this.val = val;
		this.next = null;
	}
};

function partition(head, x) {
	let leftHead = new Node(0), rightHead = new Node(0), curr = head;
	let left = leftHead, right = rightHead;
	
	while (curr !== null) {
		if (curr.val < x) {
			left.next = new Node(curr.val);
			left = left.next;
		} else {
			right.next = new Node(curr.val);
			right = right.next;
		}
		
		curr = curr.next;
	}
	
	if (left.next === null) return rightHead.next;
	left.next = rightHead.next;
		
	return leftHead.next;
}

let head = new Node(3);
head.next = new Node(5);
head.next.next = new Node (8);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(10);
head.next.next.next.next.next = new Node(2);
head.next.next.next.next.next.next = new Node(1);

let parted = partition(head, 5);
let curr = parted;
while (curr !== null) {
	console.log(curr.val);
	curr = curr.next;
}