Coding Interview | Easy Difficulty

Question 1

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.

Answer 1

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

Question 2

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.

Answer 2

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

Question 3

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

Answer 3

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

Question 4

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.

Answer 4

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

Question 5

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.

Answer 5

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)**

Question 6

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

Answer 6

True
Always return an empty enumerable/collection!

return []

Question 7

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).

Answer 7

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 []

Question 8

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.

Answer 8

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

Question 9

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.

Answer 9

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 []

Question 10

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.

Answer 10

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

Question 11

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).

Answer 11

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

Question 12

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)

Answer 12

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

Question 13

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.

Answer 13

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

Question 14

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

Answer 14

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]

Question 15

insertionSort

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

Answer 15

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

Question 16

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

Answer 16

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

Question 17

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

Answer 17

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

Question 18

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.

Answer 18

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

Question 19

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.

Answer 19

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

Question 20

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

Answer 20

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

Question 21

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.

Answer 21

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

Question 22

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.

Answer 22

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)

Question 23

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.

Answer 23

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)

Question 24

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

Answer 24

for loop

while loop limited be the len of each array/list

both manipulating the Idx values

Question 25

In O(n) time what does n represent?

Answer 25

the length of the input

Question 26

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

Answer 26

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]

Question 27

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

Answer 27

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]

Question 28

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

Answer 28

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)

Question 29

What is % in Python

x % y

Answer 29

modulus operator

returns the remainder 5 % 2 = 1

Question 30

What is chr in Python?

Answer 30

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’

Question 31

What is ord() in Python return?

Answer 31

The ord() function returns an integer representing the Unicode character. Opposite of chr()

ord(z) returns 122

ord(‘+’) returns 43

Question 32

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

Answer 32

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]

Question 33

What are the two ways to traverse a graph?

Answer 33

depth-first, breadth-first searches

Question 34

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

Answer 34

depth-first, breadth-first search

Question 35

Code a depth-first Search

Answer 35

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

Question 36

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

Answer 36

1

Question 37

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

Answer 37

3

initialize, addChild, depthFirstSearch

Question 38

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

Answer 38

a list in the initialize function

def __init__(self, name):

• *self.children = []**
  self. name = name

Question 39

True or False

A depth-first Search searches for left to right.

Answer 39

True

Question 40

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

Answer 40

visited, graph, node

Question 41

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

Answer 41

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)

Question 42

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.

Answer 42

def nonConstructibleChange(coins):
 coins.sort()
 change = 0

for coin in coins:
if coin > change + 1:
return change + 1
change += coin
return change + 1