Coding Interview | Easy Difficulty Flashcards
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
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
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
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)
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)**
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 []
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 []
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 []
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 a while loop.
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 []
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
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 a hash table (python dict).
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
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 brute force (nested for loop)
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
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
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]
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
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
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
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 for loop via the idx.
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
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, use abs and pointers to address negative values.
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
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, two func example.
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?
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?
1
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
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
