5 задач с собеседований Amazon для Python-разработчиков
https://t.me/pythonl
Составили подборку из 5 задач с собеседований в Amazon, IBM и Apple для Python-разработчиков для джунов и миддлов.
Они относительно несложные и подойдут для junior и middle программистов, а встретить задачки можно в том числе на собеседованиях в Apple, Samsung, Oracle и IBM.
Изменить порядок слов
Вам дана строка 's' с некоторым количеством слов N. Нужно сделать так, чтобы исходный порядок слов в строке изменился на обратный.
При этом в исходной строке между словами может быть множество пробелов, но в результате работы скрипта мы должны получить предложение с одним пробелом между словами, без пробелов в начале предложения и после его конца.
Время выполнения скрипта не должно превышать 1 секунду.
Решение:
Если строка равна нулю или пуста, в выводе должна появиться пустая строка. То же самое стоит сделать, если в исходной строке находится один пробел.
Инициализируйте String ans для хранения перевернутой строки.
Инициализируйте указатель на конец исходной строки и запускайте цикл while, пока указатель не достигнет начала строки.
Если в строке встречается несколько пробелов, уменьшите указатель.
Добавьте пробелы в строку ans. После этого запустите вложенный цикл while, чтобы извлечь текущее слово из ans в вывод.
После прохождения всей строки верните ответ.
'''
Time Complexity = O(N)
Space Complexity = O(N)
Where N is the length of the string.
'''
def reverseString(str: str) -> str:
# if the string is " " then return "".
if(str == "" or str == " "):
return ""
ans = ''
start = len(str) - 1
while(start >= 0):
# Skip multiple spaces.
if(str[start] == ' '):
start-=1
else:
# Add space between words.
if(len(ans) > 0):
ans += (' ')
j = start
while(j >= 0 and str[j] != ' '):
j-=1
# add current word to ans.
ans += (str[j+1: j+1+start-j])
start = j
return ans
Сумма всех чисел до N
Вам дано число N. Напишите скрипт, который считал бы сумму всех четных чисел в промежутке от 1 до N, включая N. К примеру, если N равняется 6, то вывод должен быть равен 2+4+6, то есть 12.
Решение:
Нам нужно вывести формулу для вычисления суммы четных чисел до числа 'N'.
Пусть задано число N. Тогда общее количество четных чисел от 1 до N будет равно N/2. Например, для 4 список четных чисел будет равен 2 и 4, а их количество равно 2.
Последовательность четных чисел до N образует арифметическую прогрессию с общей разницей D между числами в 2, первым элементом A = 2, и количеством элементов N, равным N/2, как доказано выше.
Сумма арифметической прогрессии равна (N/2)*(A+L), где N — количество элементов, а L — последнее число, которое также можно записать как A + (N - 1)D.
Таким образом, сумма равна (N/2*2) * (2 + 2 + (N/2 - 1)*2) = (N/2) * (1 + 1 + N/2 - 1) = (N/2) * (N/2 + 1).
'''
Time Complexity : O(1)
Space Complexity : O(1)
'''
def evenSumTillN(n):
# Calculate the sum.
sum = (n // 2) * (n // 2 + 1)
return sum
Палиндромы из чисел
У вас есть список из целых чисел. Вам нужно написать скрипт, который определит, является ли последовательность чисел палиндромом. Если это палиндром, нужно вернуть true, а если нет — вернуть false.
Решение:
Мы можем написать скрипт, который пройдет по списку из чисел от начала до конца и сохранит данные. После этого скрипт должен пройти от конца и до начала. Если данные совпадают, последовательность чисел является палиндромом.
from sys import stdin
class Node:
def __init__(self,data):
self.data = data
self.next = None
def isPalindrome(head):
# It stores the Linked List node value.
st = []
# Creating temporary Node.
temp = head
while temp is not None:
# Add the current node value to stack.
st.append(temp.data)
# Move current pointer to next node.
temp = temp.next
while head is not None:
# Get the top most element of stack.
top = st.pop()
if top != head.data:
return False
head = head.next
return True
def takeinput():
inputlist=[int(ele) for ele in input().split()]
head=None
tail=None
for currentData in inputlist:
if currentData == -1:
break
Newnode=Node(currentData)
if head is None:
head=Newnode
tail=Newnode
else:
tail.next=Newnode
tail=Newnode
return head
#Main
t = int(stdin.readline().rstrip())
while t > 0:
head = takeinput()
if isPalindrome(head):
print('true')
else:
print('false')
t -= 1
Заменить пробелы
У вас есть строка STR, в которой есть слова с пробелами. Вам нужно заменить пробелы между словами на "@40".
Решение:
Вам стоит создать отдельную строку для хранения вывода. Поочередно копируйте символы из исходной строки в строку вывода, и всякий раз, когда в ней появляется пробел, просто добавляйте в новую строку вместо пробела "@40".
def replaceSpaces(str): # String to store result. res = "" # Variable to store length of string. leng = len(str) # Iterate the length of the string. for i in range(leng): # Add "@40" in place of space. if(str[i] == ' '): res += "@40" # Add character to result. else: res += str[i] # Return result. return res
Уровни двоичного дерева
Вам дано двоичное дерево, в котором находятся целые числа. Ваш скрипт должен вывести последовательность чисел, которая бы показывала, как он проходил по двоичному дереву.
При этом количество попыток не должно превышать 100, количество ветвей дерева не должно быть меньше нуля и не должно превышать 1000, а числа дерева не должны быть отрицательными.
Решение:
При обходе "уровней" дерева мы будем использовать структуру данных queue, которая обладает свойством "FIRST IN FIRST OUT". Скрипт обойдет все первые ветви дерева, потом перейдет к следующим в иерархии.
from sys import stdin, setrecursionlimit
from queue import Queue
setrecursionlimit(10**7)
# Binary tree node class for reference
class BinaryTreeNode:
def __init__(self, data):
self.val = data
self.left = None
self.right = None
def getLevelOrder(root):
output = []
# If given tree is empty
if (root == None):
return output
# To traverse level by level
level = Queue()
# Append root to the queue
level.put(root)
# Iterater until queue does not become empty
while (not level.empty()):
# Get the size of current level
levelSize = level.qsize()
# Visit all node which are at current level and append their children if they exist
while (levelSize != 0):
# Get the front node from queue
curr = level.get()
# Store in output
output.append(curr.val)
# Append left child into queue if it exist
if (curr.left != None):
level.put(curr.left)
# Append right child into queue if it exist
if (curr.right != None):
level.put(curr.right)
levelSize = levelSize - 1
# Return the output
return output
# Take input
def takeInput():
arr = list(map(int, stdin.readline().strip().split(" ")))
rootData = arr[0]
n = len(arr)
if(rootData == -1):
return None
root = BinaryTreeNode(rootData)
q = Queue()
q.put(root)
index = 1
while(q.qsize() > 0):
currentNode = q.get()
leftChild = arr[index]
if(leftChild != -1):
leftNode = BinaryTreeNode(leftChild)
currentNode.left = leftNode
q.put(leftNode)
index += 1
rightChild = arr[index]
if(rightChild != -1):
rightNode = BinaryTreeNode(rightChild)
currentNode .right = rightNode
q.put(rightNode)
index += 1
return root
def printAns(ans):
for x in ans:
print(x, end=" ")
print()
# main
T = int(stdin.readline().strip())
for i in range(T):
root = takeInput()
ans = getLevelOrder(root)
printAns(ans)