Algorithm Challenge - FCC Hack-A-Thon

Algorithm Challenge - FCC Hack-A-Thon
0

#1

You and a group of campers are participating in an upcoming Hack-A-Thon. You’ve brainstormed ideas for projects and you want to complete and present exactly two projects in the allotted time.

The group has compiled a list of projects represented by an array A, where the number of total projects is N. Each value in the array is the number of minutes M it will take to complete that project. Your calculations for M fall within a range of 1 <= M <= 43800.

You’re a creative bunch and the number of project ideas you came up with is massive. The number of projects N in A is in the range of 100,000 <= L <= 1,000,000. For this reason, you’ll need an efficient algorithm with a better runtime than O(n^2). A nested loop won’t get the results in time for the competition!

Given an array of projects A and the total time of the Hack-A-Thon in minutes T, write a function to find the two projects that can be completed in exactly T minutes. Return the answer in the form of an array where the two projects are given as their index in the project list A. Your team agrees you want to knock out the shortest project first, so the array result should be ordered with a project requiring less time coming before a project requiring more time.

Additional note: For every input, will always be exactly one pair of projects that together equal the time of the Hack-A-Thon. Both T and A[i] (every value in the array) are integers (n % 1 === 0)

Sample Input:
A (array) = [143, 805, 218, 483, 738, 372, 102, 635, 821];
T (min) = 1440

Returns:
[7, 1]

function findHackProjects(array, min) {
// Your code goes here!
}

If you post your solution on this topic, please surround your answer in “spoiler tags” like this
details=Your title]Your code[/details]


#3

My solution

Spoiler
function findHackProjects(array1, min) {
	var arr2 = array1.slice();
	arr2.sort(function(a, b){return a-b});
	var arr3 = [];
	
	for (var i=0; i < arr2.length; i++){
		
		var compliment = min- arr2[i];
		
		if (compliment > arr2[arr2.length - 1]){continue;}
		else if(search(compliment,i,arr2) === true){
			//console.log(compliment);
			arr3.push(array1.indexOf(arr2[i]));
			arr3.push(array1.indexOf(compliment));
			//console.log(arr2[i]);
			break;
		}
		
	}
	
	function search(value,index,array){

    	var startIndex  = index,
        	stopIndex   = array.length - 1,
    		middle      = Math.floor((stopIndex + startIndex)/2);

    	while(array[middle] != value && startIndex < stopIndex){
    		
    		if (value < array[middle]){
            	stopIndex = middle - 1;
        	} else if (value > array[middle]){
            	startIndex = middle + 1;
        	}

        	middle = Math.floor((stopIndex + startIndex)/2);
    	}

    	return (array[middle] != value) ? false : true;
	}
	return arr3;
}

#4

This one theoretically is better ( O(n) ) but test results show the same efficiency as my previous solution ( O(nlogn) )

Spoiler
function findHackProjects1(array, min) {
	var obj = {};
        var compliment;
	//var start = Date.now();
	for(var i=0; i < array.length; i++){
		
		compliment = min-array[i];
		
		if (compliment > 43800){continue;}
		else if(obj.hasOwnProperty(array[i])){break;}
		else{obj[compliment] = i;}
		
	}
	return (array[i] > compliment ) ? [obj[array[i]],i] : [i,obj[array[i]]];
}

#5

If this is not efficient enough, please tell me (I did not study Big O notation)

My Solution

function findHackProjects (array, min) {
    let result = [];
    let combos = array.map(project => min - project);
    
    [...array, ...combos].sort().reduce((a, b) => {
        if(result.length < 2) {
            if( a === b) result.push(a);
        }
        return b;
    });

    let [short, long] = result;
    
    return [array.indexOf(short), array.indexOf(long)];
}


#6

Thanks for your answers! It’s great to see some interesting and creative approaches to the problem! If you were asked this question like this in an interview, it would probably be a good idea to ask what an ideal solution should optimize for. The following is one approach. There are always many ways to solve the algorithm and this is just one!

Ok so we know there is a pair of times that equals the hack-a-thon time and the pair can be found anywhere in the array. Since we may have to look at every element in the array, the best runtime we can expect is O(n). O(n) time complexity is linear, which means the amount of time to complete the algorithm increases in linear proportion with the array size. If you were to graph the time it takes to get an answer against the array size, you would get a straight line.

We try to find an O(n) solution if we can because of the size of the input. The number of projects can be as high as a million. How long would it take to calculate the answer with O(n^2) time complexity? Well a million squared is a trillion. Say we have a 2 GHz processor that can handle 2 billion cycles per second. Even if we could process an element in the array once per cycle, in the best case scenario it would still take several minutes to get through the array. You can see how runtime is negligible for small problems, but massively important if you’re building say a system with a lot of users or accessing a lot of data.

We know we’ll need to iterate over our array. How can we walk through the array input while keeping track of what we’ve seen so far? When we store what we’ve seen, we can immediately return the answer when we find a complimentary time. What data structure in Javascript will allow us to store values and retrieve them in constant time O(1) (so we don’t add to our O(n) time)? A Javascript object!

So we keep track of the time’s we’ve seen so far as the key in our object and store the index as the value. If we come across a time where the current time plus a time we’ve seen equals the total time, then we know we’ve found our pair and we return an array of that pair. Finally we figure out which time is least and most and order them in the array.

Solution
function findHackProjects(array, min) {

  var mapOfTimesSeenSoFar = {};
  var currTime;

  for (var i = 0; i < array.length; i++) {

    currTime = array[i];

    if (mapOfTimesSeenSoFar.hasOwnProperty(min - currTime)) {

      var shortestProject = Math.min(mapOfTimesSeenSoFar[min - currTime], i);
      var longestProject = Math.max(mapOfTimesSeenSoFar[min - currTime], i);

      return new Array(shortestProject, longestProject);
    }

        if (!mapOfTimesSeenSoFar.hasOwnProperty(currTime)) {

      mapOfTimesSeenSoFar[currTime] = i;
    }
  }
  throw new Error("If we get here then there isn't a valid solution!");
}

So why is this a good problem to practice on? Because the pattern of using a hash map (An object in Javascript) to keep track of what we’ve seen is so common in interview questions (from my experience) that it should be top of mind! (Can I solve this with a hash map?)


#8

A little late to the party but just saw this.
(disclaimer - only tested this on the given sample input, but think it’s right)
My solution…

Spoiler
function findHackProjects(arr, min){

  var remainingTime, indexB;

  for (var i = 0; i<arr.length; i++){
    remainingTime = min-arr[i];
    indexB = arr.indexOf(remainingTime, i+1);
    if(indexB!=-1){
      if(indexB>arr[i]){
        return [i, indexB];
      }else{
        return [indexB, i];
      }
    }
  }
};

#9

Thanks a lot.I think I’m beginning to understand the usefulness of hash maps.So you are creating a dictionary of entries referencing each object(it may be primitive values or complex objects) of an array.In this dictionary i.e. hash map i.e. javascript object, each key is a distinct identifier of the object, and its value is not the object itself, but its index in the array.As in :

let persons = [

    {name: "John", age: 25, country: "UK"},
    {name: "Sophia", age: 30, country: "Greece"},
    {name: "Cristina", age:12, country: "Spain"}
    // add billions of people here
];

// 1st method: loop through the array one time
let hashMap = {};
persons.forEach( (obj, index) => {
    // make the key a unique and meaningful identifier of the person
    hashMap[obj.name] = index; 
});
// at this point, hashMap is {"John": 0, "Sophia": 1, "Cristina" : 2}

// 2nd method: loop through the array each time the function is called
function getAge(personName) {
    persons.forEach((person) => {
        if(person.name === "John") {
            console.log(person.country);
        }
    });
}

console.log(persons[hashMap["John"]].country); // fast
getAge("John"); // slow


#10

@P1xt

That’s interesting! It’s definitely possible that certain functions in Javascript are more efficient with smaller inputs (although they should follow the typical curve as inputs increase in size). I remember reading that Array.sort() in Firefox is coded with a merge sort algorithm, while in Chrome it’s coded with a quick sort algorithm. It’s cool to look under the hood and see how these functions are implemented in the browser. Sometimes one is more performant than the other.

@jer244

Nice! Very succinct solution. One thing to keep in mind (if you’re not already aware!) is that searching with Array.indexOf will add O(n) time to your algorithm. So if you nest it inside another loop, you will be at O(n^2). Javascript has some functions with “hidden” runtime cost. Another example is Array.slice() which also carries O(n) runtime. Sneaky! A good rule of thumb is that any function where you may have to “look at” each entry in the array to perform an action will have O(n)

@Omegga

Yeah I think a dictionary is a good way to look at it! When you have the dictionary with words (keys) and definitions (values), you’re able to access them quickly. It’s like having a directory at the front so you can flip right to the page with the word on it. Searching an array is like starting at the beginning of the dictionary and flipping through each page in turn while looking for the word - You may need to look through the whole dictionary if you start at the beginning and your word starts with Z!

Now if your dictionary is small, no big deal… But imagine you have Webster’s dictionary with nearly half a million words. You’ll probably be searching for awhile if you had to flip the pages one by one :slight_smile: Thankfully computers are better at these types of tasks than us humans!

Cool example with the array of persons. Each of those entries could be users of your app. When a user logs in, you search the array looking to find their name or ID so you can return their saved data. No big deal if you have a handful of users. So imagine you’re working at a big tech company on a popular app used by millions, many of them logging in during peak hours. You wouldn’t want to have to search an array with millions of entries millions of times, O(n^2). Definitely highlights how “Big O” is a good one to learn. FCC has a great series on YouTube all about it!


#11

@jmcilhargey thanks for the lesson.

No, I didn’t realize arr.indexOf added O(n) to a function, but in hindsite, probably should have. I haven’t spent much time thinking about optimizing code for speed, rather have spent most of my time just trying to get things to work! :sweat:

These little hack-a-thon challenges can be extremely helpful for that. I have zero experience with hashmaps but spent some time yesterday reading up on them. Still not completely clear, but my understanding now is much better than before. I wasn’t thinking along the lines that searching an object by a key is faster than searching for an element in an array.

Live and learn, thanks for putting the challenge together.


#12
Solution
function findHackProjects(array, min) {
  let ind2, reverse;
  
  // O(n) for findIndex(i) + O(n--) or O(n(n-1)/2) for diminishing on each step indexOf(el, i++) = O(n(n+1)/2)
  const ind1 = array.findIndex((el, i, a) => {
    ind2 = a.indexOf(min - el, i+1);
    if(ind2 !== -1) {
      // same as array[ind1] > array[ind2] sans the extra step of dereferencing,
      // however miniscule time it takes
      reverse = el > min - el;
      return true;
    }
    return false;
  });
  
  return reverse ? [ind2, ind1] : [ind1, ind2];
}

It’s been a while since I had to calculate Big O notation, am I right that my solution amounts to O(Sum(1…n))) = O(n(n+1)/2), which is twice as fast as O(n^2)?

UPDATE: After reading suggestions to use map (why didn’t I immediately think of it?!) I’ve decided to run some tests on the original and a much bigger array for implementatios with findIndex/IndexOf, ES6 Map and Object.

As expected, hashing gets lightning fast on big arrays:

Original array
findHackProjects: 0.111ms
findHackProjectsES6Map: 0.040ms
findHackProjectsObject: 0.038ms

Padded with 10000 zeros
findHackProjects: 147.688ms
findHackProjectsES6Map: 2.188ms
findHackProjectsObject: 0.832ms

Padded with 10000 random negative(so as not to trigger result) values
findHackProjects: 148.512ms
findHackProjectsES6Map: 1.126ms
findHackProjectsObject: 2.237ms

Also interesting to note is the fact that repeatedly accessing object[“0”] is faster than Map.get(0) thanks to V8 optimisations (I’m sure inline caching plays a major part). But when indices become random whatever optimisations are available to Map help it to pull ahead.