## January 13th, back to the grind!

Today I will be getting back into the coding routine with a new schedule. After a lovely holiday break, and spending some time looking over goals, and setting new ones with my wife for the year, I am ready to get back into the daily routine with my learning and job search.

My current plan is to finish up an advanced React course, an Algorithms and Data structures course / refresher, and continue to apply for work. It’s been challenging to find and connect with the right people in my job search thus far, but it has also been extremely rewarding. I cannot stress enough how welcoming and kind the coding community here in Louisiana has been.

My ‘coding’ days will look like this until I complete my current goals. 3 hours of algorithms etc, 3 hours of Advanced React, and 1 hour of job search & research activities. Today I started off with a quick refresher on recursion before getting back into the algorithms course.

#### Helper Method Recursion

With helper method Recursion, we have two functions. We have the outer function, and inside, we use a helper method to call recursively. A design pattern example the instructor gives is:

```
function outer(input){
var outerScopedVariable = []
function helper(helperInput){
// modify the outerScopedVariable
helper(helperInput--)
}
helper(input)
return outerScopedVariable;
}
```

This recursive pattern is useful when we need to compile an array, or a list of data. The following example given by the instructor recursively collects all of the odd values in an array.

```
function collectOddValues(arr){
let result = [];
function helper(helperInput){
if (helperInput.length === 0) return;
if (helperInput[0] % 2 !== 0) result.push(helperInput[0])
helper(helperInput.slice(1))
}
helper(arr)
return result;
}
```

This is a great alternative design pattern because it solves the problem of your ‘result’ being reset with each recursive call. With helper method recursion, it has scoped access to the result and can use and edit its information and data without ever erasing it due to a recursive call to itself.

#### Pure Recursion

The function itself is purely self contained. It does not have a helper function built in. It is a little more complicated to look at but here is a ‘pure’ version of the previous code.

```
function collectOddValues(arr){
let newArr = [];
if (arr.length === 0) {
return newArr;
}
if(arr[0] % 2 !== 0){
newArr.push(arr[0]);
}
newArr = newArr.concat(collectOddValues(arr.slice(1)))
return newArr;
}
```

This does reset newArr with each recursive call, but we want it to work that way. We use concatenation to build up an array of odd values at the very end. Essentially, we are concatenating arrays together, with each array containing either nothing, or one odd number.

```
collectOddValues([1,2,3,4])
[1].concat(collectOddValues([2,3,4]))
[].concat(collectAddValues([3,4]))
[3].concat(collectOddValues([4]))
[]
// essentially [1].concat([].concat([3].concat([])))
// [1,3]
```

#### Pure Recursion Tips

- For arrays use methods like
`slice`

, the spread operator, and`concat`

that make copies of arrays in order to not mutate them. - Strings are immutable, so you will need to use methods like
`slice`

,`substr`

, or`substring`

tp make copies of strings. - To make copies of objects, use
`Object.assign`

or the spread operator.

### Exercises

#### Power

Write a function called power which accepts a base and an exponent. The function should return the power of the base to the exponent. This function should mimic the functionality of Math.pow() - do not worry about negative bases and exponents.

```
function power(base, exp){
if (exp === 0) return 1;
return base * power(base, exp-1)
}
```

#### Factorial

Write a function which accepts a number and returns the factorial of that number. (factorial 0 is always 1)

```
function factorial(num){
if (num === 0) return 1;
return num * factorial(num-1)
}
```

#### Product of Array

Write a function which takes in an array of numbers and returns the product of them all.

```
function productOfArray(arr){
if (arr.length === 0) return 1;
return arr[0] * productOfArray(arr.slice(1))
}
```

#### Recursive Range

Write a function which accepts a number and adds up all the numbers from 0 to the number passed to the function.

```
function recursiveRange(num){
if (num === 1) return 1;
return num + recursiveRange(num - 1)
}
```

#### Fib

Write a recursive function which accepts a number and returns the `nth`

number ion the Fibonacci sequence.

```
// My solution
function fib(idx){
let fib = [1];
function helper(count) {
if (count === idx) return;
let prevFib = fib[count-2] || 0;
fib.push(fib[count-1] + prevFib)
helper(count+1)
}
helper(1)
return fib[idx-1]
}
// Instructor Solution
function fib(n) {
if (n <= 2) return 1;
return fib(n-1) + fib(n-2)
}
```

### HARDER Exercises Part 1

These exercises came with a warning that they are difficult, and for people who enjoy pain and misery lol. I will try my shot at some of them.

#### Reverse

Write a function that accepts a string and returns a new string in reverse.

```
// Got this one in less than 5 mintues. Not to brag but I feel good about that!
function reverse(str) {
if (str.length === 1) return str
let lastLetter = str.substr(str.length-1,1)
let newString = str.substr(0,str.length-1)
return lastLetter.concat(reverse(newString))
}
```

#### isPalindrome

Write function which returns true if the string passed to it is a palindrome, otherwise it returns false.

```
function isPalindrome(str){
// if str is shortened down to either 1 or 0 char's it is true
if (str.length === 1 || str.length === 0) {
return true;
}
if (str[0] == str[str.length-1]) {
return isPalindrome(str.substr(1,str.length-2))
}
return false;
}
```

#### someRecursive

Write a function which accepts an array and a callback. The function returns true if a single value in the array returns true when passed to the callback, otherwise it returns false.

```
function someRecursive(arr, callback) {
if (arr.length === 0) return false;
if (callback(arr[0])) return true;
return someRecursive(arr.splice(1), callback)
}
```

#### Flatten

Write a function that accepts an array and returns a new array with all of the values flattened.

```
// flatten([1, 2, 3, [4, 5] ]) // [1, 2, 3, 4, 5]
// flatten([1, [2, [3, 4], [[5]]]]) // [1, 2, 3, 4, 5]
// flatten([[1],[2],[3]]) // [1,2,3]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1,2,3]
function flatten(arr) {
let newArr = [];
for (let i = 0; i < arr.length; i++) {
if (Array.isArray(arr[i])) {
newArr = newArr.concat(flatten(arr[i]))
}
else {
newArr.push(arr[i])
}
}
return newArr;
}
```

### HARDER Exercises Part 2

More of the difficult problems!

#### capitalizeFirst

Write a function that when given an array of strings, capitalize the first letter of each string in the array.

```
function capitalizeFirst(arr){
function capitalizeFirst(arr){
if (arr.length === 1) {
return arr[0][0].toUpperCase().concat(arr[0].substr(1))
}
return [arr[0][0].toUpperCase().concat(arr[0].substr(1))]
.concat(capitalizeFirst(arr.splice(1)))
}
}
```

#### nestedEvenSum

Write a function that returns the sum of all even numbers in an object which may contain many nested objects.

```
// this one was a little similar to the flattened array exercise
function nestedEvenSum(obj){
let sum = 0;
for (let key in obj) {
if (typeof obj[key] === 'object') {
sum += nestedEvenSum(obj[key])
} else {
if (typeof obj[key] === 'number' && obj[key] % 2 === 0) sum += obj[key]
}
}
return sum;
}
```

#### capitalizeWords

Write a function that takes an array of words, and returns a new array with all of the words in uppercase.

```
// not sure why this one was considered to be HARD
function capitalizeWords(arr){
if (arr.length === 1) return arr[0].toUpperCase()
return [arr[0].toUpperCase()].concat(capitalizeWords(arr.splice(1)))
}
```

#### stringifyNumbers

Write a function which takes in an object and finds all of the values which are numbers and converts them to strings. This one was a little difficult. I couldnt figure out how to go about copying inner objects while also converting their numbers to strings. I looked at the solution and understood it better once I went through it in the debugger.

```
function stringifyNumbers(obj) {
let objCopy = {}
for (let key in obj) {
if (typeof obj[key] === 'number') {
objCopy[key] = obj[key].toString();
} else if (typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
objCopy[key] = stringifyNumbers(obj[key])
} else {
objCopy[key] = obj[key]
}
}
return objCopy;
}
```

#### collectStrings

Write a function that accepts an object and returns an array of all the values in the object that have a `typeof === 'string'`

.

```
// I solved this one pretty quickly. It is similar to other 'flatten' type recursive problems.
function collectStrings(obj) {
let collection = [];
for (let key in obj) {
if (typeof obj[key] === 'string') collection.push(obj[key])
if (typeof obj[key] === 'object') {
return collection.concat(collectStrings(obj[key]))
}
}
return collection;
}
const obj = {
stuff: "foo",
data: {
val: {
thing: {
info: "bar",
moreInfo: {
evenMoreInfo: {
weMadeIt: "baz"
}
}
}
}
}
}
collectStrings(obj) // ["foo", "bar", "baz"])
```

### Searching Algorithms

At its most basic, a searching algorithm finds a peice of data like a string or anything really, in an assortment of data. `Array.indexOf()`

is an example of a searching algorithm.

Our objects are:

- to describe what a searching algorithm is
- Implement linear search on arrays
- Implement binary search on sorted arrays
- Implement a naive string searching algorithm
- implement the KMP string searching algorithm

#### Linear Search

The simplest way to search for something in an array is to check against each peice of data in the array. This is called `Linear Search.`

`indexOf, includes, find, findIndex`

all use linear searching to find data. `O(n) - Linear big O notation`

Write a function that accepts an array and a value. Loop through the array and check if the current element is equal to the value. If so, return the index, if not return -1.

```
function linearSearch(arr,val){
for (let i = 0; i < arr.length; i++) {
if (arr[i] === val) return i;
}
return -1;
}
```

#### Binary Search

Much faster form of searching. Rather than eliminating one element at a time, you can eliminate *half* of the remaining elements at a time. The caveat is that it only works on **SORTED** arrays.

The idea is **divide and conquer**. We will split up the array into two peices. We do this by picking the middle point, then checking to see if our value is going to be in the first or second half. We continue to do this until we find our item.

```
// lets search for 15
[1,3,4,6,8,9,11,12,15,16,17,18,19]
// is 15 > 11 ? yes, so now we close the window to the second half of the array
[12,15,16,17,18,19]
// is 15 > 17 ? no, so now we close the window to the first half of this new section
[12,15,16]
// is 15 === 15 ? yes, we have discovered 15 exists in this array in only 3 'guesses' as opposed to searching the whole thing
```

##### Binary search Exercise

Write a function that accepts a sorted array and a value to look for. Create a left pointer at the start of the array, and a right pointer at the end. While the left pointer is before the right pointer, take the middle, and check to see if the value being searched for is equal. If the value is too small, move the left pointer up, if too large, the right pointer comes down. If nothing is found, return -1.

```
function binarySearch(arr,val) {
debugger;
let left = 0;
let right = arr.length-1
while (left < right) {
let idx = Math.floor((right+left) / 2)
if (arr[idx] === val) {
return idx;
} else if (arr[idx] < val) {
left = idx+1;
} else {
right = idx-1;
}
}
return -1;
}
```

I was able to solve this relatively quickly. I love the divide and conquer algorithm as it is super clever. The Big O of this algorithm is average case `O(log n)`

which is VERY good.

#### Naive String Search

Suppose you want to count the number of times a smaller string appears in a longer string. A straightforward approach involves checking pairs of characters individually.

This is an exercise to implement a naive version of string search. Loop over the longer string, loop over the shorter string, if the characters dont match, break out of the inner loop. If you complete the inner loop and find a match, increment the count of matches and return the count.

```
function naiveStringSearch(str,toMatch) {
let matchCount = 0;
for (let i = 0; i < str.length; i++) {
for (let j = 0; j < toMatch.length; j++) {
if (str[i+j] !== toMatch[j]) break;
if (j === toMatch.length-1) matchCount++
}
}
return matchCount;
}
```

There are a handful of more videos on a couple other algorithms, but I will move on for now to look into data structures because, I have an interview tomorrow with a local company! A part of the interview will cover data structures and I’d like to familiarize myself with them.

### Data Structures

Data structures are collections of values, the relationships among them, and the functions or operations that can be applied to the data.

Different data structures excel at different things. Some are highly specialized, while others (like arrays) are more generally used.

The more time you spend as a developer, the more likely you’ll need to use one. We’ve already worked with many of them unknowingly. ALSO! They are used in interviews!!

#### Use Cases ?

**Working with map/location data?** - Use a graph!!

**Inserts/Removals at beginning and end of an ordered list?** - Use a Linked List!!

**Web Scraping HTML?** - Use a tree!!