Skip to content

Instantly share code, notes, and snippets.

@umar-ibn-shafee
Last active November 29, 2018 23:32
Show Gist options
  • Save umar-ibn-shafee/0eaa6cb55b73f72328d5f3c7ea12bb51 to your computer and use it in GitHub Desktop.
Save umar-ibn-shafee/0eaa6cb55b73f72328d5f3c7ea12bb51 to your computer and use it in GitHub Desktop.
Oursky Pre-test
/**
* This @function checkSubset will check if arr2 is subset of arr1.
* @param {Array} arr1 this is the array to be checked over.
* @param {Array} arr2 this is the array to check if it is subset of arr1.
*/
function checkSubset(arr1, arr2) {
/**
* Validating the parameters passed.
*/
if ((Array.isArray(arr1) && arr1.length > 0) && (Array.isArray(arr2) && arr2.length > 0)) {
/**
* Diclaring an empty object
*/
const hashMap = {};
let k = 1;
/**
* Creating a hashMap of the array arr1 by iterating over the array and
* assigning its values as the keys of hashMap
*/
arr1.forEach(elm => {
hashMap[elm] = k;
k++;
});
/**
* Checking if arr2 array is a subset of arr1 array by using
* every() method to itarate over the arr2 array and we're using
* hasOwnProperty() method to check whether the every element is present
* in the hashMap or not.
*/
const isSubsetOfFirst = arr2.every(elm => hashMap.hasOwnProperty(elm));
console.log('Is Second array subset of First array:', isSubsetOfFirst);
return isSubsetOfFirst;
}
console.error('Provided parameters are not of type Array or the provided Arrays are Empty');
}
const a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k'];
const b = ['b', 'c', 'd'];
checkSubset(a, b);

Solution of the first question

function checkSubset(arr1, arr2) {
    
    if ((Array.isArray(arr1) && arr1.length > 0) && (Array.isArray(arr2) && arr2.length > 0)) {
        const hashMap = {};
        let k = 1;
        arr1.forEach(elm => {
            hashMap[elm] = k;
            k++;
        });
        const isSubsetOfFirst = arr2.every(elm => hashMap.hasOwnProperty(elm));
        console.log('Is Second array subset of First array:', isSubsetOfFirst);
        return isSubsetOfFirst;
    }
    
    console.error('Provided parameters are not of type Array or the provided Arrays are Empty');   
}

The Time Complexity of the above solution is

O(n)

Explanation

If we calculate the time complexity of each statement of the above solution we'll get higher time complexity of

n + 1

for statements arr1.forEach() and arr2.every()

If we ignore the constant then it'll be n.

If we add both n and n it'll be 2n.

Again if we ignore the constant the Time Complexity of the function will be

O(n)

/**
* Declaring an array with predefind first two elements of fibonacci sequence.
* This array will store all fibonacci numbers.
*/
const fibonacciList = [0, 1];
/**
* This is the Main @function nextFibonacci which will take an input array.
* @param {Array} arr: this is the given array to find the fibonacci numbers.
*/
function nextFibonacci(arr) {
/**
* Validating the given param if it's an array or not & checking if Empty.
*/
if (Array.isArray(arr) && arr.length > 0) {
/**
* Finding the maximum integer among the given array.
*/
const maxInteger = Math.max(...arr);
constructFibonacci(maxInteger);
/**
* Iterating over the given array to find fibonacci numbers.
*/
return arr.map(elm => {
const nextFib = searchNextFibonacci(fibonacciList, elm, 0, fibonacciList.length - 1);
console.log(nextFib);
return nextFib;
});
}
}
/**
* This @function constructFibonacci is used to create fibonacci sequence.
* @param {Integer} maxV is the maximum value in the given array.
*/
function constructFibonacci(maxV) {
let i = 1;
/**
* Finding all the fibonacci numbers until next greter fibonacci number than maxV is found.
*/
while (fibonacciList[i] < maxV) {
i++;
fibonacciList[i] = fibonacciList[i - 1] + fibonacciList[i - 2];
}
}
/**
* This @function searchNextFibonacci is used to search for a next greater
* fibonacci value than given value.
* @param {Array} fibArr is an Array if fibonacci numbers.
* @param {Integer} num an element of given array.
* @param {Number} start starting index of the fibonacci array.
* @param {Number} end last index of the fibonacci array.
*/
function searchNextFibonacci(fibArr, num, start, end) {
/**
* Validation condition
*/
if (start > end) return 'Provided an empty array';
/**
* Finding the middle index
*/
const mid = Math.floor((start + end) / 2);
/**
* Compare middle index value with the given num
* if both equal next number of the array.
*/
if (fibArr[mid] === num && fibArr[mid + 1] !== num) return fibArr[mid + 1];
/**
* Comparing if num is greater than arr[mid] and
* if num is less than arr[mid + 1] then return arr[mid + 1].
*/
if (num > fibArr[mid] && num < fibArr[mid + 1]) return fibArr[mid + 1];
/**
* Comparing if num is greater than arr[mid - 1] and
* if num is less than arr[mid] then return arr[mid].
*/
if (num < fibArr[mid] && num > fibArr[mid - 1]) return fibArr[mid];
/**
* If element at middle is greater than num then search in the left half
* or else search in the right half of mid
*/
return fibArr[mid] > num ?
searchNextFibonacci(fibArr, num, start, mid - 1) :
searchNextFibonacci(fibArr, num, mid + 1, end);
}
nextFibonacci([1, 22, 9]);

Given function

function createArrayOfFunctions(y) {
    var arr = [];
    for (var i = 0; i < y; i++) {
        arr[i] = function (x) { return x + i; };
    }
    return arr;
}

In the above function i has global scope, In this case i is always y.

Correct Solution

If we change the scope of i and make it specific to block of for loop by using let.

function createArrayOfFunctions(y) {
    var arr = [];
    for (let i = 0; i < y; i++) {
        arr[i] = function (x) { return x + i; };
    }
    return arr;
}

This code will work fine. although we can make it even better by making arr immutable by changing var arr = [] to const arr = []

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment