Sep 14

Зашел сегодня на блог одного знакомого. И тогда и сейчас у него было обьявление о наборе программистов в его фирму, писать на PHP. В качестве “пробы” предлагалось, да и предлагается, решить такую задачу:

Есть текстовый файл, в котором находится описание дерева в следующем виде:

node_id|parent_id|node_name

parent_id - id родителя, если оно равно 0 - это корневой узел.

Задача: отобразить этот файл в виде дерева, с отступами для каждого уровня табуляциями (первый уровень - ноль табуляций, второй уровень - одна, и т.д.).

Файл-пример содержит:

1|0|Electronics
2|0|Video
3|0|Photo
4|1|MP3 player
5|1|TV
6|4|iPod
7|6|Shuffle
8|3|SLR
9|8|DSLR
10|9|Nikon
11|9|Canon
12|11|20D

Ответом должно быть:

Electronics
	MP3 player
		iPod
			Shuffle
	TV
Video
Photo
	SLR
		DSLR
			Nikon
			Canon
				20D

Тут еще заметки относительно решения есть.

Где-то полгода назад я пробовал ее решить. Решил. Очень по идиотскому, даже вспоминать не хочется. Сейчас вот зашел на блог и захотелось опять попробовать решить задачу… И вот сейчас хочется услышать/увидеть ваши решения. Интересует именно алгоритм, писать можете на любом языке (для C++-ников предлагаю вставить вместо разделителя “|” пробел, чтобы не парится с считыванием из файла).

PS. Моим новым решением я тоже поделюсь… Потом. ;)

PPS. JQuery 1.2 - объявлен новый пользовательский интерфейс для платформы Java - Да… Не перевелись еще идиоты на Руси…

written by fxposter \\ tags:


11 Responses to “Небольшая задачка”

  1. 1. Kamashev Max Says:

    Использовать DOM функции, там с деревом работать просто :)

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

    Или нужен алгоритм с минимумом строк кода?

  2. 2. FX Poster Says:

    Нет. Нужен максимально оптимальный алгоритм. Хоть на псевдокоде. Сложность алгоритма, который получился у меня – O(n), n – кол-во узлов.

  3. 3. Andrew Kornilov Says:

    вот на питоне. только разъехалось форматирование :)
    работает с нелинейной нумерацией parent_id (то бишь, они могут быть 1,3,10 и всё)

    #!/usr/bin/python
    in_f = open('./inf','r+')
    goods = {}
    in_arr = in_f.readlines()
    max_ppid = 0
    for in_str in in_arr:
        (pid,ppid,name) = in_str.split('|')
        if (goods.has_key(ppid)):
            goods[ppid].append([pid,name])
        else:
            goods[ppid] = [[pid,name]]
        if (int(ppid) > max_ppid):
            max_ppid = int(ppid)
    for index in range(int(max_ppid+1)):
        if (not goods.has_key(str(index))):
            continue
        for index2 in range(len(goods[str(index)])):
            print '\\t' * int(index),'%s %s' % (goods[str(index)][index2][0],goods[str(index)][index2][1])
  4. 4. Kallisto Says:

    net sets только в текстовике походу..

  5. 5. Andrew Kornilov Says:

    Ясень пень, что не оптимально, нет проверок на все ошибки и т.п. Но общий смысле же понятен :)

  6. 6. FX Poster Says:

    Ахуенный код просто. Только неправильно работающий немного ;)

  7. 7. Andrew Kornilov Says:

    По диагонали прочитал задание. Там еще надо учитывать кое-что. Ладно, допишем :)

  8. 8. Артём Курапов Says:

    Делал нечто подобное для генерации дерева, правда все данные хранились в базе. В основе там была функция рекурсивная, работала по принципу “начать сверху, найти детей и сделать то же самое для детей”.

    Есть задача поинтересней – отрисовка дерева только до тех веток, где название/содержание ветки (частично) совпадает с поисковым словом

  9. 9. FX Poster Says:

    Тут суть в том – как быстро построить это самое дерево. Конкретных реализаций я пока что так и не увидел. :(

  10. 10. lyu Says:

    Честно говоря малость удивлёт отсутствием решений. Вой мой вариант.

    class FileTree
    {
           protected $tree = array();
    
    
           public function __construct($filename)
           {
           $f = file($filename);
           foreach ($f as $s) $this->AddNode(explode('|', trim($s)));
           }
    
    
           public function ShowTree($parent_id = 0, $level = 0)
           {
           foreach ($this->tree[$parent_id] as $node)
           {
                   echo str_repeat("\t", $level), $node['name'], "\n";
                   if (!empty($this->tree[$node['id']])) $this->ShowTree($node['id'], $level+1);
           }
           }
    
    
           protected function AddNode($nodeStruct)
           {
                   list($node_id, $parent_id, $node_name) = $nodeStruct;
                   $this->tree[$parent_id][] = array('id' => $node_id, 'name' => $node_name);
           }
    }
    
    
    $tree = new FileTree('file.txt');
    $tree->ShowTree();
  11. 11. FX Poster Says:

    Просто вот мое решение. :)

Leave a Reply