Написать пост

5 задач с собеседований Amazon для Python-разработчиков

Составили подборку из 5 задач с собеседований в Amazon, IBM и Apple для Python-разработчиков для джунов и миддлов.

Составили подборку из 5 задач с собеседований в Amazon для Python-разработчиков.

Они относительно несложные и подойдут для junior и middle программистов, а встретить задачки можно в том числе на собеседованиях в Apple, Samsung, Oracle и IBM.

В статье собраны решения, которые предложили программисты CodingNinjas. Весь код представлен на Python 3.5.

Изменить порядок слов

Вам дана строка ‘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)
		

Заключение

Какие задачи из представленных вы смогли решить, не подглядывая под спойлеры? Может быть, задачи оказались сложными для вас? Или, может, вы встречали задачки и посложнее на собеседованиях в компаниях, в которых вы работали? Напишите об этом в комментариях!

Если вы думаете, что нашли более лаконичные решения задач, опишите их ниже: с радостью их обсудим. ?

Следите за новыми постами
Следите за новыми постами по любимым темам
12К открытий19К показов