10 популярных вопросов на собеседовании по кодированию о рекурсии

10 популярных вопросов на собеседовании по кодированию о рекурсии

Работает умно

Подготовка к собеседованию по кодированию занимает много времени. Есть так много разных тем, структур данных и алгоритмов, которые нужно рассмотреть. Рекурсия - один из важнейших типов алгоритмов. Потому что это основа для многих важных алгоритмов, таких как «разделяй и властвуй», графовые алгоритмы, динамическое программирование, некоторые древовидные алгоритмы поиска и сортировки и многие другие. Это неизбежно. Поэтому перед собеседованием по кодированию важно иметь некоторую практику.

В этой статье мы сосредоточимся на основных вопросах рекурсии, которые очень распространены и популярны в собеседованиях по базовому кодированию. Если вы будете искать в Google, вы все равно найдете большинство этих вопросов здесь и там. Я просто собираю для вас некоторые из распространенных шаблонов вопросов на собеседовании. Здесь вы увидите несколько различных моделей рекурсивных алгоритмов.

Эта статья не гарантирует, что вы увидите только эти вопросы. Это несколько распространенных типов, и это должно дать вам хорошую практику!

Я буду переходить от простого к сложному. Это не учебник по рекурсии. Я предоставляю здесь лишь некоторые практические материалы. Решения будут предоставляться на Python, поскольку я использую Python большую часть времени.

Предлагаю вам сначала попробовать решить все вопросы самостоятельно, а потом уже искать решение.

Вопрос 1

Напишите рекурсивную функцию, которая принимает число и возвращает сумму всех чисел от нуля до этого числа.

Я назову эту функцию «накопительной». Если я введу 10 в качестве входных данных, он должен вернуть сумму всех чисел от нуля до 10. То есть 55.

Вот решение для Python:

def cumulative(num):
    if num in [0, 1]:
        return num
    else:
        return num + cumulative(num-1)

Вопрос 2

Напишите рекурсивную функцию, которая принимает число в качестве входных данных и возвращает факториал этого числа.

Я уверен, что мы все узнали, что такое факториал. Я назову функцию «факториал».

Вот решение для Python:

def factorial(n):
    assert n >=0 and int(n) == n, 'The number must be a positive integer only!'
    if n in [0,1]:
        return 1
    else:
        return n * factorial(n-1)

Вопрос 3

Напишите рекурсивную функцию, которая принимает число «n» и возвращает n-е число числа Фибоначчи.

Напоминаем, что ряд Фибоначчи - это последовательность положительных целых чисел, которые начинаются с 0 и 1, а остальные числа - это просто сумма двух предыдущих чисел: 0, 1, 1, 2, 3, 5, 8, 11…

Вот решение для Python:

def fibonacci(n):
    if n in [0, 1]:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Вопрос 4

Напишите рекурсивную функцию, которая принимает на вход список чисел и возвращает произведение всех чисел в списке.

Если вы не являетесь пользователем Python, список в Python похож на массив в Java, JavaScript или PHP.

Вот решение для Python:

def productOfArray(arr):
    if len(arr) == 0:
        return 0
    if len(arr) == 1:
        return arr[0]
    else:
        return arr[len(arr)-1] * productOfArray(arr[:len(arr)-1])

Вопрос 5

Напишите функцию, которая принимает строку и возвращает, если строка является палиндромом.

Напоминаем, что если строка равна своей обратной стороне, это называется палиндромом. Такие как мадам, цивик, байдарка. Если вы перевернете любое из этих слов, они останутся такими же.

Вот рекурсивное решение на Python:

def isPalindrom(strng):
    if len(strng) == 0:
        return True
    if strng[0] != strng[len(strng)-1]:
        return False
    return isPalindrome(strng[1:-1])

Эта функция возвращает True, если строка является палиндромом, и false в противном случае.

Вопрос 6

Напишите рекурсивную функцию, которая принимает строку и меняет ее местами.

Если ввод "потрясающий", он должен вернуть "гнизама".

Вот решение Python:

def reverse(st):
    if len(st) in [0, 1]:
        return st
    else:
        return st[len(st)-1] + reverse(st[:len(st)-1])

Вопрос 7

Напишите рекурсивную функцию, которая принимает массив, который может содержать больше массивов, и возвращает массив со всеми сглаженными значениями.

Предположим, это входной массив:

[[1], [2, 3], [4], [3, [2, 4]]]

Результат должен быть:

[1, 2, 3, 4, 3, 2, 4]

Вот решение для Python:

def flatten(arr):
    res = []
    for i in arr:
        if type(i) is list:
            res.extend(flatten(i))
        else:
            res.append(i)
    return res

Вопрос 8

Напишите рекурсивную функцию, которая принимает массив слов и возвращает массив, содержащий все слова с заглавной буквы.

Если это входной массив:

['foo', 'bar', 'world', 'hello']

Выходной массив должен быть:

['FOO', 'BAR', 'WORLD', 'HELLO']

Вот решение для Python:

def capitalizeWords(arr):
    if len(arr) == 0:
        return []
    else:
        return [arr[0].upper()]+capitalizeWords(arr[1:])

Вопрос 9

Напишите рекурсивную функцию, которая принимает массив и функцию обратного вызова и возвращает True, если какое-либо значение этого массива возвращает True из этой функции обратного вызова, в противном случае возвращает False.

В этом решении я использовал функцию isEven в качестве функции обратного вызова, которая возвращает True, если число является четным, и возвращает False в противном случае.

Вот функция обратного вызова:

def isEven(num):
    if num%2==0:
        return True
    else:
        return False

Наша основная рекурсивная функция должна возвращать True, если хотя бы один элемент входного массива возвращает True из функции isEven и False в противном случае. Вот массив:

[1, 2, 3, 5]

Рекурсивная функция должна здесь вернуть True, потому что в этом массиве есть один элемент, который является четным числом.

Вот решение для Python:

def anyEven(arr, cb):
    if len(arr) == 0:
        return False
    if cb(arr[0]):
        return True
    return anyEven(arr[1:], cb)

Вопрос 10

Напишите рекурсивную функцию, которая будет возвращать сумму всех положительных чисел в словаре, который может содержать больше словарей, вложенных в него.

Вот пример:

obj = {
  "a": 2,
  "b": {"x": 2, "y": {"foo": 3, "z": {"bar": 2}}},
  "c": {"p": {"h": 2, "r": 5}, "q": 'ball', "r": 5},
  "d": 1,
  "e": {"nn": {"lil": 2}, "mm": 'car'}

Это должно вернуть 10. Потому что этот словарь содержит пять двоек и никаких других четных чисел.

Вот решение для Python:

def evenSum(obj, sum=0):
    for k in obj.values():
        if type(k) == int and k%2 ==0:
            sum += k
        elif isinstance(k, dict):
            sum += evenSum(k, sum=0)
    return sum

Вывод

Чтобы овладеть рекурсией, потребуется много практики. Но это хорошая идея, чтобы взглянуть на эти проблемы перед тем, как идти на собеседование. Никто не может гарантировать ответы на вопросы собеседования, но ключевым моментом является подготовка различных шаблонов вопросов по кодированию. Но с какими бы собеседованиями я не сталкивался до сих пор, они никогда не создавали мне серьезных проблем. Обычно они задают вопросы, чтобы проверить знания и общий подход к проблеме.

Не стесняйтесь подписываться на меня в Twitter и ставить лайки на моей странице Facebook.

Больше Чтения