Разворот односвязного списка за O(n) (память — O(1)) на Гугл Гоу

Вчера друг подвозил меня до дома, я решил, пока в пробке, попрограмировать на «Гоу». Практики давненько не было, язык уже начинает забываться, не модули, это ерунда, а сами конструкции, вот что неприятно.

Взял задачу — развернуть односвязный список за O(n) с константным ограничением на память. Задачу частенько дают на собеседованиях, как я слышал, говорят мало кто решает, решил посмотреть действительно ли это сложно. В уме прикинул, подумалось что нет, практика показала, что я не ошибся. В общем, выкладываю что получилось.

package main

import (
    "os"
    "bufio"
)

// тип для односвязного списка
type links struct {
    Next *links
    Value string
}

// вывод на печать односвязаного списка
func (chain *links) Print() {
    for chain != nil {
        os.Stdout.WriteString(chain.Value)

        chain = chain.Next
    }
}

// разворачиваем односвязный список за O(n)
func (chain *links) Reverse() *links {
    if chain == nil || chain.Next == nil {
        return chain
    }

    left, next := chain, chain.Next.Next
    chain = chain.Next
    left.Next = nil

    for {
        chain.Next = left

        if next == nil {
            break
        }

        left, chain, next = chain, next, next.Next
    }

    return chain
}

// Создаём список из чего-нибудь, умеющего выдавать по одной строке за раз
func CreateFromReader(readline func() *string) *links {
    var chain, start *links = nil, nil

    for {
        if line := readline(); line != nil {
            link := &links{ nil, *line }

            if chain == nil {
                chain, start = link, link
            } else {
                chain.Next, chain = link, link
            }

        } else {
            return start
        }
    }

    return nil
}

// Точка входа
func main() {
    if len(os.Args) < 2 {
        os.Exit(1)
    }

    f, err := os.OpenFile(os.Args[1], os.O_RDONLY, 0666)

    if err != nil {
        os.Exit(2)
    }

    defer f.Close()

    r := bufio.NewReader(f)

    CreateFromReader(
        func() (*string) {
            if line, e := r.ReadString('\n'); e == nil {
                return &line
            }

            return nil
        },
    ).Reverse().Print()
}

Список создаётся из файла, который нужно передать программе первым параметром. Вообще, вся реализация разворота — в методе Reverse класса links, остальное — заполнение структуры и вывод на печать. Оцените как мало надо кода, чтобы решить это задание.

Поделиться
Отправить
2012   googlego
5 комментариев
Fulcrum (fulc.ru)

говорят мало кто решает

Им, конечно же, сразу отказывают? Как можно не решить задачу, которая даже проще, чем сортировка пузырьком?

{"openid":null,"nick":"Baka (\u0432 \u0442\u043e, \u0447\u0442\u043e OpenID \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u043d\u0435 \u0432\u0435\u0440\u044e\u2026","userpic":"http:\/\/img-fotki.yandex.ru\/get\/4122\/136290390.40\/0_b82b9_ec872562_

Комментарий для fulc.ru:

Как можно не решить задачу, которая даже проще, чем сортировка пузырьком?

Легко.
Достаточно не [осо]знать (не догадаться (не прочитать где-то раньше)), что для «разворачивания» списка (а не массива) не надо копировать значения, а достаточно перевесить указатели.

{"openid":null,"nick":"Baka (\u0432 \u0442\u043e, \u0447\u0442\u043e OpenID \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u043d\u0435 \u0432\u0435\u0440\u044e\u2026","userpic":"http:\/\/img-fotki.yandex.ru\/get\/4122\/136290390.40\/0_b82b9_ec872562_

Комментарий для Baka (в то, что OpenID работает, не верю…:

(Ещё в первый момент можно понять «развернуть» как «unfold», а не как «reverse» и задуматься, о чём это вообще. O_o)

Евгений Степанищев (bolknote.ru)

Комментарий для fulc.ru:

Им, конечно же, сразу отказывают? Как можно не решить задачу, которая даже проще, чем сортировка пузырьком?

Увы, нет. В Яндексе средний уровень гораздо выше, чем средний уровень программистов в Казани. Нужно выбирать из тех, что есть.

Евгений Степанищев (bolknote.ru)

Комментарий для Baka (в то, что OpenID работает, не верю…:

Достаточно не [осо]знать (не догадаться (не прочитать где-то раньше)), что для «разворачивания» списка (а не массива) не надо копировать значения, а достаточно перевесить указатели.

Тяжело поверить, что хороший программист может до этого не догадаться.

Ещё в первый момент можно понять «развернуть» как «unfold», а не как «reverse» и задуматься, о чём это вообще.

Или воспользоваться своими навыками коммуникации и уточнить этот момент на собеседовании у меня.

Популярное