tima-s@ya.ru

Задачка на Swift

Life is life

Created with Sketch.

Задачка на Swift

Хожу по собеседованиям в поиске работы. На одной из бесед дали вот такую интересную задачку. Я решал ее на языке Swift, поскольку собеседуюсь на iOS-программиста, но на самом деле язык неважен для решения.

На само решение давалось 20 минут. Скажу честно, я не успел решить за столь короткое отведенное время. Может быть волнение дало о себе знать. Однако дома, в спокойной обстановке я все-таки попытался написать решение. На это у меня ушло гораздо больше 20-ти минут, конечно, но я решил.

Задача.

Дан неупорядоченный массив целых чисел  arr и целое число k

Реализуйте функцию, которая возвращает число — количество уникальных пар, разность значений которых равна k

Пример:

  • arr = [1, 5, 3, 4, 2, 2]; k=3
  • Уникальные пары с разностью 3: [1, 4], [5, 2]
  • Итого, количество пар: 2

Решение.

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

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

Это было не оптимально. К циклам по массиву добавлялся еще один цикл по добавленным парам. И я стал думать, как улучшить решение. И тогда я сочинил более красивое и быстрое решение.

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

Что мы делаем сначала. Сначала пишем нечто, что бы нам вернуло массив без дубликатов. Я написал в виде расширения (extension), но это могла быть и простая функция, желательно конечно Generic.

Потом сортируем и разворачиваем массив стандартными средствами библиотеки языка Swift.

И, собственно, все, половина задачи решена. Осталось только пройти по массиву и посчитать нужные пары.

Другое дело, что у меня на обдумывание этого решения ушло вовсе не 20 минут. А вы бы уложились? Как бы решили задачу вы?

let arr = [1,5,3,4,2,2]
let k = 3

extension Array where Element: Hashable {
    var uniques: Array {
        var buffer = Array()
        var added = Set<Element>()
        for elem in self {
            if !added.contains(elem) {
                buffer.append(elem)
                added.insert(elem)
            }
        }
        return buffer
    }
}

struct Pair {
    let one: Int
    let two: Int
}

func countDiff(arr: [Int], k: Int) -> Int {
    
    let sorted = arr.sorted().reversed().uniques
    
    var pairs = [Pair]()

    for n in 0..<sorted.count - 1 {
        for i in n + 1..<sorted.count {
            
            let one = sorted[n]
            let two = sorted[i]
            
            if one - two == k {
                pairs.append(Pair(one: one, two: two))
            }
        }
    }
    
    return pairs.count
}

let result = countDiff(arr: arr, k: k)
print(result)

Tags: , ,

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *