Coding Interview | Easy Difficulty Flashcards by Kelvin Waters

isPalindrome

Write a function that takes in a non-empty string and returns a boolean representing whether the string is a palindrome, via slice that steps backwards.

def isPalindrome(string):
if string == string[::-1]:
return True
else:
return False

How well did you know this?

Not at all

Perfectly

isPalindrome

Write a function that takes in a non-empty string and returns a boolean representing whether the string is a palindrome, use the join built-in function.

def isPalindrome(string):
if string == “”.join(reversed(string)):
return True
else:
return False

How well did you know this?

Not at all

Perfectly

isPalindrome

Write a function that takes in a non-empty string and returns a boolean representing whether the string is a palindrome, use a while loop

def isPalindrome(string):
leftIdx = 0
rightIdx = len(string) - 1
while leftIdx < rightIdx:
if string[leftIdx] != string[rightIdx]:
return False
leftIdx += 1
rightIdx -= 1
return True

How well did you know this?

Not at all

Perfectly

isPalindrome

Write a function that takes in a non-empty string and returns a boolean representing whether the string is a palindrome, via a new array.

def isPalindrome(string):
reversedChars = []
for i in reversed(range(len(string))):
reversedChars.append(string[i])
return string == ““.join(reversedChars)

How well did you know this?

Not at all

Perfectly

isPalindrome

Write a function that takes in a non-empty string and returns a boolean representing whether the string is a palindrome, use recursion to solve the problem.

this is not pep8
def isPalindrome(string, i = 0):
 j = len(string) - 1 - i 
 return True if i \>= j else string[i] == string[j] and **isPalindrome(string, i + 1)**

How well did you know this?

Not at all

Perfectly

True or False
It is considered a best practice to NEVER return null when returning a collection or enumerable. (ie twoNumbersSum)

True
Always return an empty enumerable/collection!

return []

How well did you know this?

Not at all

Perfectly

twoNumberSum

Write a func that takes in a non-empty arr of distinct integers and an integer representing a target sum. If any two number in the input sum up to the target sum, the func returns them in an arr. If no two equates to the target sum return an empty arr, use brute-force (nested for loop).

def twoNumberSum(array, targetSum):
**for** i in range(len(array)):
 **for** j in range(i + 1, len(array)):
 if array[i] + array[j] == targetSum:
 return array[i], array[j]
 return []

How well did you know this?

Not at all

Perfectly

twoNumberSum

Write a func that takes in a non-empty arr of distinct integers and an integer representing a target sum. If any two number in the input sum up to the target sum, the func returns them in an arr. If no two equates to the traget sum return an empty arr, use a hash table.

def twoNumbersSum(arr, targetSum):
nums = {}
for num in arr:
potentialMatch = targetSum - num
if potentialMatch in nums:
return [potentialMatch, num]
else:
nums[num] = True
return []

How well did you know this?

Not at all

Perfectly

twoNumberSum

def twoNumbersSum(arr, targetSum):
arr.sort()
left = 0
right = len(arr) -1
while left < right:
currentSum = arr[left] + arr[right]
if currentSum == targetSum:
return arr[left], arr[right]
elif currentSum < targetSum:
left += 1
elif currentSum > targetSum:
right -= 1
return []

How well did you know this?

Not at all

Perfectly

firstNonRepeatingCharacter

Write a func that takes in a str of lowercase English-alpha letters and returns the index of the strs first non-repeating char, if the input str doesn’t have any non-repeating chars return -1, use the python built-in Counter method.

from collections import Counter

def firstNonRepeatingCharacter(string):
 freq = **Counter**(string)

for idx in range(len(string)):
char = string[idx]
if(freq[char] == 1):
return idx
return -1

How well did you know this?

Not at all

Perfectly

firstNonRepeatingCharacter

def firstNonRepeatingCharacter(string):
**characterFreq = {}**

for char in string:
characterFreq[char] = characterFreq.get(char, 0) + 1

for idx in range(len(string)):
char = string[idx]
if characterFreq[char] == 1:
return idx
return -1

How well did you know this?

Not at all

Perfectly

firstNonRepeatingCharacter

def firstNonRepeatingCharacter(string):
 **for** i in range(len(string)):
 duplicate = False
 **for** j in range(len(string)):
 if string[i] == string[j] and i != j:
 duplicate = True
 if not duplicate:
 return i 
 return -1

How well did you know this?

Not at all

Perfectly

bubbleSort

Write a func that takes in an array of integers and returns a sorted version of that array. Use the bubble sort algorithm, nested for loop.

def bubbleSort(array):
 n = len(array)
 **for** i in range(n-1):
 **for** j in range(0, n-i-1):
 if array[j] \> array[j+1]:
 array[j], array[j+1] = array[j+1], array[j]
 return array

How well did you know this?

Not at all

Perfectly

bubbleSort

Write a func that takes in an array of integers and returns a sorted version of that array. Use the bubble sort algorithm, do a while loop amd use a separate func to complete the swap

def bubbleSort(array):
isSorted = False
counter = 0
while not isSorted:
isSorted = True
for i in range(len(array) -1 - counter):
if array[i] > array[i + 1]:
swap(i, i + 1, array)
isSorted = False
counter += 1
return array

def swap(i, j, array):
 array[i], array[j] = array[j], array[i]

How well did you know this?

Not at all

Perfectly

insertionSort

Write a func that takes in an arr of int and returns a sorted version of that arr, use a while loop.

def insertionSort(array):
 for i in range(len(array)):
 key = array[i]
 j= i - 1
 **while** j \>= 0 and key \< array[j]:
 array[j + 1] = array[j]
 j -= 1
 array[j + 1] = key

return array

How well did you know this?

Not at all

Perfectly

selectionSort

Write a func that takes in an arr of int and returns a sorted version of that arr, use the selection sort algo with a nested for loop

def selectionSort(array):
**for** i in range(0, len(array)):
 iMin = i
**for** j in range(i + 1, len(array)):
 if array[iMin] \> array[j]:
 iMin = j
 if i != iMin:
 array[i], array[iMin] = array[iMin], array[i]

return array

How well did you know this?

Not at all

Perfectly

sortedSquareArray

Write a func that takes in a non-empty arr of integers that are sorted in ascending order and returns a new arr of the same length with the squares of the original integers in asc order, return via list comprehension

def sortedSquaredArray(array):
 return sorted(**[i \* i for i in array]**)

sortedSquareArray

def sortedSquaredArray(array):
 sortedSquares = [0 for _ in array]

for idx in range(len(array)):
value = array[idx]
sortedSquares[idx] = value * value

sortedSquares.sort()
return sortedSquares

sortedSquareArray

def sortedSquaredArray(array):
 sortedSquares = [0 for _ in array]
**smallerValueIdx = 0
 largerValueIdx = len(array) - 1**

for idx in reversed(range(len(array))):
smallerValue = array[smallerValueIdx]
largerValue = array[largerValueIdx]

if abs(smallerValue) > abs(largerValue):
sortedSquares[idx] = smallerValue * smallerValue
else:
sortedSquares[idx] = largerValuee * largerValue
largerValueIdx -= 1
return sortedSquares

binarySearch

Write a func that takes in a sorted arr of int and a target int. The func should use a binary search algo to determine if the target int is contained in the arr and return its idx if it is otherwise return -1

def binarySearch(array, target):
 array.sort()
 lo = 0
 hi = len(array) - 1

while hi >= lo:
mid = lo + (hi - lo) // 2
if array[mid] < target:
lo = mid + 1
elif array[mid] > target:
hi = mid - 1
else:
return mid
return -1

binarySearch

def binarySearch(array, target):
 return binarySearchHelper(array, target, 0, len(array) - 1)

def binarySearchHelper(array, target, left, right):
while left <= right:
middle = (left + right) // 2
potentialMatch = array[middle]
if target == potentialMatch:
return middle
elif target < potentialMatch:
right = middle -1 # right pointer move left
else:
left = middle + 1 # left pointer move right
return -1

isValidSubsequence

Given two non-empty int arrays, write a func that determines whether the seond array is a subset of the first one, use a while loop to traverse both arrays simultaniously.

def isValidSubsequence(array, sequence):
arrIdx = 0
seqIdx = 0
while arrIdx < len(array) and seqIdx < len(sequence):
if array[arrIdx] == sequence[seqIdx]:
seqIdx += 1
arrIdx += 1
return seqIdx == len(sequence)

isValidSubsequence

Given two non-empty int arrays, write a func that determines whether the seond array is a subset of the first one, use a for loop.

def isValidSubsequence(array, sequence):
seqIdx = 0
for i in array:
if seqIdx == len(sequence):
break
if sequence[seqIdx] == i:
seqIdx += 1
return seqIdx == len(sequence)

How would one might traverse two sequences like an array/list for comparison operations?

for loop

while loop limited be the len of each array/list

both manipulating the Idx values

In *O(n)* time what does *n* represent?

the length of the input

**selectionSort** Write a func that takes in an array of int and returns a sorted version, use the selection sort algo to sort the array. Use a **while** loop

def selectionSort(array): for i in range(0, len(array)): currentIdx = 0 **while** currentIdx smallestIdx = currentIdx for i in range(currentIdx + 1, len(array)): if array[smallestIdx] \> array[i]: smallestIdx = i swap(currentIdx, smallestIdx, array) currentIdx += 1 return array def swap(i, j, array): array[i], array[j] = array[j], array[i]

**Caesar Cipher Encryptor** Given a non-empty str of lowercase and a non-negative int key, write a func that returns a new str by shifting every letter in the input by k letters should wrap *z to a*

def caesarCipherEncryptor(string, key): newLetters = [] newKey = key % 26 alpha = list('abcdefghijklmnopqrstuvwxyz') for letter in string: newLetters.append(getNewLetter(letter, newKey, alpha)) return "".join(newLetters) ``` def getNewLetter(letter, key, alpha): newLetterCode = alpha.index(letter) + key return alpha[newLetterCode % 26] ```

**Caesar Cipher Encryptor** Given a non-empty str of lowercase and a non-negative int key, write a func that returns a new str by shifting every letter in the input by k letters should wrap z to a, use **ord** and **chr**

def caesarCipherEncryptor(string, key): newletters = [] newKey = key % 26 for letter in string: newletters.append(getNewLetter(letter, newKey)) return "".join(newletters) ``` def getNewLetter(letter, key): newLetterCode = **ord**(letter) + key return chr(newLetterCode) if newLetterCode \<= 122 else **chr**(96 + newLetterCode % 122) ```

What is % in Python x % y

**modulus** operator returns the remainder 5 % 2 = 1

What is **chr** in Python?

The **chr**() method returns a character (a string) from an integer (represents unicode code point of the character, opposite of ord() **chr**(122) returns z **chr**(54) returns '6'

What is **ord**() in Python return?

The **ord**() function returns an integer representing the Unicode character. Opposite of chr() **ord**(z) returns 122 **ord**('+') returns 43

**findThreeLargestNumbers** Wrtie a func that takes in an array of at least three int and without sorting returns a sorted array of the three largetst values

def findThreeLargestNumbers(array): threeLargest = [None, None, None] for num in array: updateLargest(threeLargest, num) return threeLargest def updateLargest(threeLargest, num): if threeLargest[2] is None or num \> threeLargest[2]: shiftAndUpdate(threeLargest, num, 2) elif threeLargest[1] is None or num \> threeLargest[1]: shiftAndUpdate(threeLargest, num, 1) elif threeLargest[0] is None or num \> threeLargest[0]: shiftAndUpdate(threeLargest, num, 0) def shiftAndUpdate(array, num, idx): for i in range(idx + 1): if i == idx: array[i] = num else: array[i] = array[i + 1]

What are the two ways to traverse a graph?

depth-first, breadth-first searches

What is this common code for? ## Footnote ``` class Node: def \_\_init\_\_(self, name): self.children = [] self.name = name ``` ``` def addChild(self, name): self.children.append(Node(name)) return self ``` ``` def xxxxXxxSearch(self, array): # Write your code here. pass ```

depth-first, breadth-first search

Code a depth-first Search

``` class Node: def \_\_init\_\_(self, name): self.children = [] self.name = name ``` ``` def addChild(self, name): self.children.append(Node(name)) return self ``` def depthFirstSearch(self, array): array.append(self.name) for child in self.children: child.depthFirstSearch(array) return array

How many nodes are there in a depth-first search?

How many defined functions are in a depth-first search?

3 initialize, addChild, depthFirstSearch

What type of data structure does the depth-first algorithm utilize?

a list in the initialize function ## Footnote def \_\_init\_\_(self, name): * *self.children = []** self. name = name

True or False A depth-first Search searches for left to right.

True

A depth-first algo using a set takes in what 3 parameters?

visited, graph, node

Write a depth-first algo that utilizes a set data structure and recursion

visited = **set()** def dfs(visited, graph, node): if node not in visited: print(node) visited.add(node) for neighbour in graph[node]: **dfs(visited, graph, neighbour)**

non-constructable Change Given an array of positive int representing the values of coins in your possession, write a func that returns the minimum amount of change that you cannot create.

``` def nonConstructibleChange(coins): coins.sort() change = 0 ``` for coin in coins: if coin \> change + 1: return change + 1 change += coin return change + 1