Data Structures & Algorithms: Practice #1
In technical interviews, it’s common to be given various problems that test your data structures and algorithmic skills. While the Flatiron School occasionally gave problems that tested these skills, the majority of the curriculum was focused on understanding a language’s syntax, use, and quirks for the purpose of applying it towards app development. Thus, upon the suggestion of fellow Flatiron alum Alison Quaglia I decided to invest in some classes at Udemy to practice solving common interview problems. Currently, I’m progressing through Stephen Grider’s ‘The Coding Interview Bootcamp: Algorithms + Data Structures’ which I highly recommend due to his clear, concise instruction and the progression of problems you are presented to solve, as well as the well-explained alternate solutions that expand your current abilities and approach.
One problem that initially stumped me was the popular Chunked problem. The directions are given below:
// Given an array and chunk size, divide the array into many subarrays// where each subarray is of length size// --- Examples// chunk([1, 2, 3, 4], 2) --> [[ 1, 2], [3, 4]]// chunk([1, 2, 3, 4, 5], 2) --> [[ 1, 2], [3, 4], [5]]
There are a couple of things to keep in mind here. One, the length size indicates the maximum amount of elements in a ‘chunk’ array. Even if the original array length does not neatly divide into ‘chunks’ of ’n’ size, the remaining elements must be pushed into a ‘chunk’ to return the right ‘chunked’ array.
Additionally, knowledge of array methods will be helpful here, like the ‘.push()’ method.
Possible Solution #1
So first let’s pseudo-code one possible solution.
function chunk(array, size) {// lets created an empty array to hold our 'chunks'// for each element of original array
// get the last element of the 'chunks' array
// if it doesn't exist or if it's length is equal to the given size
// push in element in an array into 'chunks' array
// else push in current element into the current chunk// return 'chunks'}
Originally, I was trying to code a solution that went through the original array, tried to ‘chunk’ it, and push it into another overall ‘chunked’ array. The above approach is different, however, in that it’s first testing to see if a ‘chunk’ is completed, and then pushing it into a created array.
So how could this look like in code?
function chunk(array, size) {
let arr = []; //creates an array
for (element of array){ //loops over given array
let last = arr[arr.length - 1] //creates variable to compare
if (!last || last.length === size){ //if it doesn't exist or equal in length
arr.push([element]); //push in [element]
} else last.push(element) // else push in element into arr
}
return arr; //return the desired answer
}Possible Solution #2
Now of course there are many ways to solve this. Another possible answer uses the method .slice() instead. The slice method is very handy, as it allows you to go into an array, and modify elements at a desired index. Other methods (.pop(), .push(), .shift(), .unshift()) have a predetermined location, but slice gives much more freedom to the user. The only tricky thing about slice is that while the first number provided refers to the desired start index, the second optional number or ‘end’ . Thus, it can be a bit tricky to work with, but a very helpful tool once mastered. Here’s a possible pseudocode solution using .slice().
function chunk(array, size) {
//Create an empty array
//create an index starting at 0
//while index is less than given array's length
//push a slice of it according to given size into created array
//add size to index
// return array}
So what could this look like?
function chunk(array, size) {
let arr = []; //create empty array
let i = 0; //create index starting at 0
while (i < array.length){ //while i is less than given array length
arr.push(array.slice(i, i+size)) //push chunk into created arr
i+= size //increment by size variable
}
return arr //return arr
}This solution is more in line with my original approach but uses .slice() to create the ‘chunks’ from the beginning to add to a created array. It’s neater but definitely harder to come up with on the spot in an interview. That’s why we practice!
