benmeiri84
BAN USERMost of the solutions had a bug. In the case that two consecutive numbers with diff larger than k.
for example: 1 6 7 10 k: 3
i = 0, j = 1: a[j] - a[i] = 5 > 3 so i++.
now i == j and the loop stops.
This is my solution that handle that case:
function findDiff(arr, k) {
if (arr.length === 0) {
return [];
}
let res = [];
let start = 0, end = 1;
while (start < end) {
let first = arr[start], second = arr[end], sum = second - first;
if (sum === k) {
res.push([first, second]);
start++;
second++;
} else if (sum < k) {
end++;
}else{
start++;
if(start === end){
end++;
}
}
if (end === arr.length) {
break;
}
}
return res;
}
console.log(findDiff([1,2,3,5,6,8,9,11,12,13],3));
JavaScript implementation. Let's say the longest words is K and we got N words the worst case will be:
1. Sorting O(NlogN)
2. for each word we work on every sub word length k-1 so it's O(K^2) and we do it for all the words so it's O(N*K^2)
Together it's O(NlogN + N*K^2) I add them because we don't know if K^2 > logN.
But in an actual dictionary it will run much faster because I added some optimisation so I don't check substrings if it won't be longer than the current maximum. But there are cases that the running time will still be that of O(NlogN + N*K^2)
/*
Sort an array of strings from longest to shortest
*/
let reverseSort = (a, b) => {
return -( a.length - b.length);
};
/*
Build a dictionary: String to Object
{
visited: boolean - Did we already visit this word
length: number - the length of the maximum chain
nextWord: string - the index for the next word in the dictionary
}
*/
let buildDictionary = (arr) => {
let dictionary = {};
arr.forEach((item)=> {
dictionary[item] = {
visited: false,
length: 1,
nextWord: null
};
});
return dictionary;
};
let findChainForWord = (originContext, originWord, dictionary) => {
let originWordCharArray = originWord.split('');
for(let i = 0; i < originWordCharArray.length ; i++){
//remove char
let tmpCharArray = originWordCharArray.splice(i,1);
let currentWord = originWordCharArray.join('');
let currentContext = dictionary[currentWord];
// this is a valid word in the dictionary
if(currentContext){
//build subchain
if(!currentContext.visited){
findChainForWord(currentContext, currentWord, dictionary);
}
// Change the current maximum to the new one if it's longer
if(currentContext.length + 1 > originContext.length){
originContext.length = currentContext.length + 1;
originContext.nextWord = currentWord;
}
}
//put the char back
originWordCharArray.splice(i,0, tmpCharArray[0]);
}
originContext.visited = true;
};
/*
Build a string from a chain node
*/
let buildResultChain = (dictionary, word) => {
let current = dictionary[word];
let res = `Length: ${current.length}: ${word} `;
while(current.nextWord){
res += ` -> ${current.nextWord}`;
current = dictionary[current.nextWord];
}
return res;
};
/*
This is the main method. It will return a string representation of the longest chain
*/
function findLongestChain(words) {
// Sort the words from the longest word to the shortest
words.sort(reverseSort);
//
let dictionary = buildDictionary(words);
let current = null;
words.forEach((word) => {
let wordObj = dictionary[word];
// we need to check only unvisited words. If I visit it already it must be part of a chain,
// meaning it won't be longer than the current longest
// Also, if current found word is longer than the word length, no need to check. The chain will never be as long
if (!wordObj.visited && !(current && dictionary[current].length >= word.length)) {
findChainForWord(wordObj, word, dictionary);
if(!current || dictionary[current].length < wordObj.length){
current = word;
}
}
});
return buildResultChain(dictionary, current);
}
let words = ['a', 'b', 'bca', 'ba', 'bda', 'bdca'];
console.log(findLongestChain(words));
//print Length: 4: bdca -> bca -> ba -> a
words = ['a', 'b', 'bca', 'bcdef', 'ba', 'abcd', 'bda', 'bdca', 'abcdef', 'cdef','cde','de','d', 'qqqqq'];
console.log(findLongestChain(words));
//print Length: 6: abcdef -> bcdef -> cdef -> cde -> de -> d
words = ['a'];
console.log(findLongestChain(words));
// print Length: 1: a
words = ['ba', 'agd', 'liuf','lkjda'];
console.log(findLongestChain(words));
// print Length: 1: lkjda (because we sort the dictionary this is the first word)
javascript implementation O(N)
let matrix = [];
for(var i = 0 ; i < 10 ; i++){
let arr = [];
matrix.push(arr);
for(let j = 0; j < 10; j++){
arr.push(i*10 + j);
}
}
console.log(matrix);
function findKth(k, matrix){
if(k <= 0 || k >matrix.length * matrix.length){
return null;
}
let startEdge = matrix.length;
let index = 0;
while(k > ((startEdge * 4) - 4)){
k -= ((startEdge * 4) - 4);
index++;
startEdge -= 2;
}
return findOnBorder(matrix, k, index, startEdge);
}
function findOnBorder(matrix, k, startPoint, edgeLength){
console.log('border')
k--;
if(k < edgeLength - 1){
// top part
return matrix[ startPoint][startPoint + k ];
}
k -= edgeLength - 1;
if(k < edgeLength - 1){
// right part
return matrix[startPoint + k ][startPoint + edgeLength - 1 ];
}
k -= edgeLength - 1;
if(k < edgeLength - 1){
// bottom
return matrix[ startPoint + edgeLength - 1 ][startPoint + edgeLength - 1 - k ];
}
// left side
k -= edgeLength - 1;
return matrix[ startPoint + edgeLength - 1 - k ][startPoint ];
}
console.log(findKth(37, matrix));
// print 11
console.log(findKth(100, matrix));
// print 54
console.log(findKth(50, matrix));
// print 78
console.log(findKth(64, matrix));
// print 21
console.log(findKth(65, matrix));
// print 22
I forgot the class for the Tree Node :D
class Node {
constructor(data) {
this.data = data;
}
insert(node) {
if (node.data < this.data) {
if (!this.left) {
this.left = node;
} else {
this.left.insert(node);
}
} else {
if (!this.right) {
this.right = node;
} else {
this.right.insert(node);
}
}
}
}
I think that there's a trick question here that everyone missed here. Your solutions work if it's digits but fail if it's any think longer.
The trick question (and I think that is way they gave simple examples) is that you search for sub numbers, meaning if the tree is: 5->64->23->77 and the target is "2377" you don't only need to check 2->3->7->7 but also, 2->3->77, 2->377, 23->7->7, 23->77, 237->7, 2->37->7.
In most of the implementations I saw here this is not being taken under consideration.
this is my implementation using javascript. Notice I used BST only because I had already implemented the function to create the tree for another question :D, but my solution doesn't actually need it to be BST
function buildTree(arr) {
const root = new Node(arr[0]);
for (let i = 1; i < arr.length; i++) {
root.insert(new Node(arr[i]));
}
return root;
}
function printTree(node) {
let arr = [node];
while (arr.length) {
let tmp = [];
let level = '';
for (let n of arr) {
level += ` ${n.data} `;
if (n.left) tmp.push(n.left);
if (n.right) tmp.push(n.right);
}
console.log(level);
arr = tmp;
}
}
//I build a BST, even thou I don't have to in the question
let root = buildTree([5, 3, 7, 1, 4, 6, 8, 2, 9, 10,22,65,23,44,664]);
printTree(root);
function findPath(root, target){
return findRoot(root,createDigitsArray(target), 0);
}
function checkPath(root, arr, index){
if(index >= arr.length){
return true;
}
let number = 0;
while(index < arr.length){
number *= 10;
number += arr[index];
if(root.left && root.left.data === number){
let found = checkPath(root.left, arr, index + 1);
if (found){
return true;
}
}
if(root.right && root.right.data === number){
let found = checkPath(root.right, arr, index + 1);
if (found){
return true;
}
}
index++;
}
return false;
}
function findRoot(root, arr, index){
if(index >= arr.length){
return;
}
let number = 0;
while(index < arr.length){
number *= 10;
number += arr[index];
let startPoint = findStartPoint(root, number);
if(startPoint){
let found = checkPath(startPoint, arr, index + 1);
if(found){
return true;
}
}
index++;
}
return false;
}
function createDigitsArray(num){
const arr = [];
while(num > 0){
arr.unshift(num % 10);
num = Math.floor(num / 10);
}
return arr;
}
function findStartPoint(root, number){
if(!root){
return;
}
if(root.data === number){
return root;
}
let found = findStartPoint(root.left, number);
return found || findStartPoint(root.right, number);
}
console.log('found',findPath(root,652344)); //return true
console.log('found',findPath(root,662344)); //return false
console.log('found',findPath(root,312)); //return true
Most of the answers here are either N*M or NlogN in runtime. Even the C++ set solution, because creating it and searching for all elements is NlogN. There's a solution of N+M which is optimal. Build a dictionary from array B (run time M). Search in it the diffrence from n for every element from array A.
Implementation in JavaScript:
- benmeiri84 March 21, 2017