daily log 11.20.20

11/20/20

find the largest and smallest number in an unsorted integer array?

Largest_number = array[0] Smallest_number = array[0] For number in array: If number < smallest_number: Smallest_number = number If number > largest_number: Largest_number = number

Return (Largest_number, Smallest_number)

TIME: O(N)

SPACE: O(1)

test inputs: [1] // 1,1 [1,2,3,4,5] // 5, 1 [9,12,3] [1,1,1,1,1,1,1,1,1,1,1] [] [-1, -2] [1,………. 10000000000] [10^500, 10^999]

Given a string check if isPalindrome

I am going to COMPARE the first and last element Then I am going to COMPARE the second and second to last element Then I am going to COMPARE the third and third to last element If at any point, this comparison returns false, return false

Function isPalindrome(input){ Var input_length = input.length - 1 for ( var i=0; i<input.length; i++ {

If (input[i] !== input[input.length - i]) {
Return false } } }

Def isPalindrome(input): // fingers as pointers Start = 0 End = len(input) - 1

while(start <= end): If input[start]  != input[end]:
Return False
Start  += 1
End -= 1 
Return True

…

SPACE: O(1)

TIME: O(N/2) → O(N)

TESTS:

“T” // expecting True “Ta” // expecting False “Tat” // expecting True “Taat” // expecting True “Tacocat” // expecting TRUE “Tacodog” // expecting FALSE “Aaaaaaaaaaaaaaaaaaaaaaa” // expecting TRUE “Aaaaaaaab” // expecting FALSE “Aaabaaa” // expecting TRUE (same as tacocat)

QUESTIONS:

Do I care about case?

function palindromePermutation(string){

// make the dictionary let my_dict = {} for(let i=0;i<string.length;i++){ if(string[i] !== “ “) { if(my_dict[string[i]]){ my_dict[string[i]] = my_dict[string[i]] + 1 } else { my_dict[string[i]] = 1 } } }

let odd_number = 0
for (var key in my_dict) {
    console.log(key, my_dict[key])
    if (my_dict[key]%2 !== 0){
        odd_number += 1
    }
}

if (odd_number > 1){
    return false
} else {
    return true
} //     console.log(my_dict) }

palindromePermutation(‘tact coa’) palindromePermutation(‘aaaatc’)

How do you find the missing number in a given integer array of 0 to 100?

Def missingNumber(input): Start = 0 End = len(input) -1

While start <= end:
	Midpoint = Floor((start + end) /2)
	If input[midpoint] < midpoint:
		End = midpoint
	If input[midpoint] > midpoint:
		Start = midpoint

//comparison

TESTS:

HOMEWORK: Review work NEXT TIME Space and Time Complexity Test cases