Skip to content

Instantly share code, notes, and snippets.

View AlexandraBeautyman's full-sized avatar

Alexandra Beautyman AlexandraBeautyman

View GitHub Profile

Curry


Prompt

Write a function called curry that takes a function as an argument and returns a "curried" version of that function.

But what is a "curried" version of a function?

Prompt

Given a target sum and an array of positive integers, return true if any combination of numbers in the array can add up to the target value. Each number in the array may only be used once. Return false if the numbers cannot be combined to sum to the target value.

Examples

subsetSum(2, [1, 10, 5, 3]); // false
subsetSum(10, [1, 10, 5, 3]); // true
subsetSum(9, [1, 10, 5, 3]); // true

Prompt

First, given the (quite inefficient) algorithm for calculating the nth Fibonacci number below, determine its time complexity.

function fib(n) {
  if (n === 0) {
    return 0
  }
  else if (n === 1) {
    return 1
 }

Prompt

Write an algorithm that checks if a number is prime. Then identify its time complexity.

Approach

We know that a prime number is one that is divisible only by itself and 1, so we know that there is a set of numbers we could iterate through, dividing our input number n by each, to determine whether n is divisible by any of them and therefore not prime. What exactly are the constraints on that set, though?

Assuming that n is a positive whole number, right away it's obvious that we don't need to check any numbers less than 2 or greater than n - 1.

But we can do better. Is there a number less than n that acts as a transition point dividing the set of whole numbers between 2 and n - 1, allowing us to set aside part of the set as redundant? Indeed there is! That transition point is the square root of n. Why? Because any number that is greater than the square root of n and by which n is also divisible has to be multiplied by a number less than the square root of n to equal n. If that doesn't seem obvi

@AlexandraBeautyman
AlexandraBeautyman / sortingArrayOfString.md
Last active October 17, 2022 08:12
Sorting each string in an array of strings, then sorting the whole array

Prompt

First, write an algorithm that takes in an array of strings, sorts each string, and then sorts the full array. Second, calculate the time complexity (Big O) of this algorithm.

Approach

To sort each individual string in the array, we would start by looping through the whole array, sorting each string element, and either replacing the strings in the original array with their sorted versions, or building a new array with the sorted strings.

Then, to sort the whole array, we would perform some sorting function on it.