ANSI C: Walking tree

tengiz · Post by **tengiz** » 28 Apr 2004 20:56

A. Fig Lee - а как обходить дерево в условии задачи не задано? Приведённый нерекурсивный алгоритм обходит эту структуру вполне определённым образом. Любой другой обход потребует дополнительной памяти либо в виде стека для рекурсии, либо в виде программного стека/очереди.

Если нужно делать программный стек, но не хочется хипа, то в таких задачах часто удобно использовать alloca. Дополнительной памяти обычно нужно под столько указателей, какова высота дерева. Т.е. заметно меньше, чем под дополнительный parent указатель в каждом узле.

Так что если это не специальный частный случай, то задача на самом слегка надумана. Специальный случай, это, скажем, когда нужно иметь возможность readonly обходить дерево одновременно и параллельно несколькими потоками, поэтому вместо дополнительного стека для каждого потокам может оказаться выгоднее иметь parent указатель в каждом узле.

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

P.S. A. Fig Lee - пожалуйста перестаньте хулиганить

и исправьте название дискуссии, а то из-за пропущенного неопределённого артикля получается "Дерево на прогулке" вместо "Обхода дерева". В результате сбивает с толку и не привлекает должного внимания. Или наоборот, потенциально может привлечь любознательных ботаников, а не софтверных инженеров

.

vc · Post by vc » 28 Apr 2004 21:03

SVK wrote:

olg2002 wrote:Не пожалейте времени, напишите программу.

Трассировка:

Code: Select all

cur---statement
. . . . . . . . . . . начало пропущено до момента cur=4 
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----}
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----}
5-----cur = cur->parent;
4-----}
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----}
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----}
5-----cur = cur->parent;
4-----}
. . . . . . и т.д., пока хватит сил....

Ну, не надо еще с анекдотами путаться...

Here's the correct trace:

Code: Select all

...............................
cur=4 
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----} 
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----} 
5-----cur = cur->parent; 
4-----} 
4-----while ( cur ) { 
4-----if ( cur->next ) {
8-----cur = cur->next;
8-----break;
8-----while ( cur ) 
8-----process(cur) 
...........  etc  ........

With an attitude like that, you'd better be 100% sure you are right ...

VC

SVK · Post by **SVK** » 29 Apr 2004 00:03

vc wrote:With an attitude like that, you'd better be 100% sure you are right ...

Да. Заслуживаю общественное порицание, и оценку -2. Рассматривал код со сдвинутым концом цикла - сам виноват, каюсь.

SVK · Post by **SVK** » 29 Apr 2004 00:24

tengiz wrote:Так что если это не специальный частный случай, то задача на самом слегка надумана. Специальный случай, это, скажем, когда нужно иметь возможность readonly обходить дерево одновременно и параллельно несколькими потоками, поэтому вместо дополнительного стека для каждого потокам может оказаться выгоднее иметь parent указатель в каждом узле.

Не только для такого случая. Некоторые виды обработки могут требовать просто "подъема" начиная с нижних уровней дерева к верхним. Для такого типа проходов указатели parent все равно нужны. А коли они уже есть в структуре (а по условию дано, что они все-таки есть), то грех не использовать их, а строить стек даже и при стандартном обходе дерева.

Не так разве?

8K · Post by 8K » 29 Apr 2004 00:44

SVK wrote:Самый красивый алгоритм вычисления факториала

А слабо написать compile-time факториал, чтобы его компилятор в момент компиляции считал, если N - константа? Правда, под нашим VC++ все равно не работает, т.к. реализация шаблонов кривая.

tengiz · Post by **tengiz** » 29 Apr 2004 01:08

SVK wrote:Не только для такого случая. Некоторые виды обработки могут требовать просто "подъема" начиная с нижних уровней дерева к верхним. Для такого типа проходов указатели parent все равно нужны. А коли они уже есть в структуре (а по условию дано, что они все-таки есть), то грех не использовать их, а строить стек даже и при стандартном обходе дерева.

Не так разве?

Не уверен, что я точно понимаю, что Вы имеете в виду под подъёмом начиная с нижних уровней (с чего в этом случае начинается обход - со списка внешних узлов, т.е. самого нижнего уровня?). Но я, конечно, не буду спорить, что в жизни могут попасться самые причудливые задачи - здесь Вы абсолютно правы. Но то что я имел в виду всё-так сводится к стандартным базовым вариантам обхода дерева: pre-/in-/post-order начиная с корня дерева и различные их модификации, включая обход statefull итераторами.

SVK · Post by **SVK** » 29 Apr 2004 01:20

tengiz wrote:что Вы имеете в виду под подъёмом начиная с нижних уровней (с чего в этом случае начинается обход - со списка внешних узлов, т.е. самого нижнего уровня?).

Тупой, но наглядный пример - печать "предков" до седьмого колена от заданного произвольного узла - нужны parents. Если сюда же добавить печать "потомков", то появляется примерно тот стандартный обход дерева, который был задан вначале, но ссылки parents уже туда засажены все равно.

olg2002 · Post by **olg2002** » 29 Apr 2004 01:36

Ну, с простым случаем, вижу, разобрались. Как насчет того же самого, но без parent ссылки? Приглашаю всех в "Головоломки".

theukrainian · Post by **theukrainian** » 29 Apr 2004 01:42

olg2002 wrote:Ну, с простым случаем, вижу, разобрались. Как насчет того же самого, но без parent ссылки? Приглашаю всех в "Головоломки".

теперь - стэк

vc · Post by vc » 29 Apr 2004 02:36

Tengiz,

tengiz wrote:A. Fig Lee - а как обходить дерево в условии задачи не задано? Приведённый нерекурсивный алгоритм обходит эту структуру вполне определённым образом. Любой другой обход потребует дополнительной памяти либо в виде стека для рекурсии, либо в виде программного стека/очереди.

.

The task is ambiguous as to what the Parent link really means:

1. The structure Node( Next, Child, Parent, Key) clearly represents an _ordered_ tree node but it's not clear what's considered to be the parent;

2. The usual interpretation would be :
(null,2,null, 1), (6,3,1,2), (7,4,2,3), (8,5,3,4), (null,null,4,5), (9,null, 2, 6),
(null,null,3,7),(10,null,4,8 ), ... etc.

Assuming the above interpretation is correct and remembering than any ordered tree is equivalent to a binary tree, all the DFS traversals (pre/post/in-order) can be expressed iteratively.

3. An alternative interpretation assumed by SVK was:
(null,2,null, 1), (6,3,1,2), (7,4,2,3), (8,5,3,4), (null,null,4,5), (9,null, 1, 6),
(null,null,2,7),(10,null,3,8 ), ... etc.

In this case, only the pre-order traversal can be iterative and the other traversals can be implemented trivially over the equivalent binary tree using the standard recursive approach or a manual stack (which is the same as recursion).

As to the interview ... I would not want to work for someone asking this kind of a silly question at an interview unless the pay was really good.

Regards.

VC

SVK · Post by **SVK** » 29 Apr 2004 15:44

vc wrote:1. The structure Node( Next, Child, Parent, Key) clearly represents an _ordered_ tree node but it's not clear what's considered to be the parent;

Насколько я помню из разных давних примеров подобных структур, смысл parent совершенно ясен, и никаких сомнений вызывать не должен бы: это именно общий "предок" всех "братьев", связанных между собой в цепочку next. Разные прадлагавшиеся здесь альтернативы никогда раньше не рассматривались в значении parent. Если бы parent указывал на "предыдущего брата", то он назывался бы previous. Также делать parent=NULL для "промежуточных братьев", кроме последнего в списке next, тоже неправильно - это лишает ссылку parent ее первоначального смысла. И т.д. В общем - parent есть parent, и он самообъясняющий.

Также непонятен смысл поворота дискуссии от основного вопроса. Были даны начальные условия задачи, - как они есть. И предложено найти оптимальный способ обхода дерева - именно при тех условиях, как они заданы. В качестве скорее подсказки также дано требование не использовать рекурсию, хотя в такой ситуации этого можно было не требовать, а ожидать что в качестве предпочтительного решения будет предложен именно обход без рекурсии, поскольку все промежуточные данные, для сохранения которых обычно и требуется либо рекурсия, либо стек данных, в данной конкретной ситуации уже заложены в исходную структуру (хорошо это, или плохо - другой вопрос, но главное - они там уже есть).

Этот вопрос я так и понимал, как желание увидеть, кто из решающих заметит достаточность исходных данных для решения задачи без создания (явно либо неявно) промежуточных структур, которые получаются при заученных способах решения этой в общем стандартной задачи. Это - полная копия той шутки: Как вскипятить чайник наполненный водой, который находится рядом со включенной газовой плитой? Программист предлагал (1) вылить воду, (2) погасить плиту, (3) сделать кипячение так, как делал вчера.

Разве не похожие способы были предложены для обхода дерева, в котором уже заданы parents: (1) игнорировать parents, (2) рекомендовать руководству никогда не вносить лишних ссылок в их данные, (3) создать свой стек из тех же самых значений parents, и обходить дерево так, как на днях делали в другой конторе.

Разве не похожая ситуация?

* * *

И совсем непонятное замечание было про отказ от работы там, где задали бы "такой глупый вопрос". Конечно, в качестве реального вопроса для интервью, этот вопрос - не лучший кандидат. Но в похожей ситуации лично я бы взял на работу кандидата, который для простой задачи предложит именно простое решение, а не более сложное, но: (1) стандартное, или (2) модное, или (3) использующее новейшие технологии, или (4) названное именем известного изобретателя, или же вообще вместо конкретного решения конкретной задачи начнет предлагать выбросить все что есть, и переделать с самого начала.

A. Fig Lee · Post by **A. Fig Lee** » 29 Apr 2004 15:57

tengiz wrote:A. Fig Lee - а как обходить дерево в условии задачи не задано? Приведённый нерекурсивный алгоритм обходит эту структуру вполне определённым образом. Любой другой обход потребует дополнительной памяти либо в виде стека для рекурсии, либо в виде программного стека/очереди.

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

Если нужно делать программный стек, но не хочется хипа, то в таких задачах часто удобно использовать alloca. Дополнительной памяти обычно нужно под столько указателей, какова высота дерева. Т.е. заметно меньше, чем под дополнительный parent указатель в каждом узле.

Когда давно я пытался использовать alloca на UNIX. И не нашел ее. Глянул стандард - тоже не нашел. Кстати, в МСДН указано что ето личная Виндовс функция.
По поводу дерева - ничего не указано, дано дерево абстрактное. Являются ли парент нулями или нет - тоже не сказано. Ограничений на использование хипа не было. Но слишком сложно - не думаю, что ето хотели. Вопросов аналогичных сложнее/слабее было порядка 20.

Так что если это не специальный частный случай, то задача на самом слегка надумана.

Так отож. Моя мысль - неумение задавать точные вопросы - ето очень характерно для проводящих тесты/интервью.

P.S. A. Fig Lee - пожалуйста перестаньте хулиганить и исправьте название дискуссии, а то из-за пропущенного неопределённого артикля получается "Дерево на прогулке" вместо "Обхода дерева". В результате сбивает с толку и не привлекает должного внимания. Или наоборот, потенциально может привлечь любознательных ботаников, а не софтверных инженеров .

Так я ж бисхрамотный... :pain1:

Еще вопрос интерсный - не помню точно как звучит.
Примерно:
С и С++ языки со стронг тайп чекинг. Почему в С++ ето более важно чем в С, особенно в енвайронмент где типикалли используется MFS. I gde v MFS ето обычно дисейблед?
Надеюсь, не переврал. Какой-то из наиболее очевидных ответов отвергался сразу - по моему, оверлоадинг - ето не то, что они имеют ввиду.
Мне в голову пришло только разница в том, кто будет освобождать стек, хотя кто конкретно освобождает стек в тот момент не вспомнил. Или ордер в стеке? Тогда где ето дисейблед?

интерсно, что народу было только в 1 день человек 6, возможно что в день больше сессий проводят. Зарплата, наверное, тыщ 40. В общем, когда я увидел куда попал, решил что больше на тесты не хожу, пока не узнаю зарплату.

Ну и последний вопрос - чтото типа (упрощенный вариант):

void f (StructX *x, StructY *y)
{
int v1 = g(y);
int v2 = (v1 & x->a);
if (v2....???
{
while ()
{
int v3 = ((v1>>16) & x->a) + 1;
if ((v2 -= v3) < 0)
{
v2 += x->c
}
if (x->v[v2].y == y)
break;
.......
}

}

}

Ну еще там столько же внутри. что делает функция и каково должно быть x->c?

A. Fig Lee · Post by **A. Fig Lee** » 29 Apr 2004 16:05

SVK wrote:Насколько я помню из разных давних примеров подобных структур, смысл parent совершенно ясен, и никаких сомнений вызывать не должен бы: это именно общий "предок" всех "братьев", связанных между собой в цепочку next. Разные прадлагавшиеся здесь альтернативы никогда раньше не рассматривались в значении parent. Если бы parent указывал на "предыдущего брата", то он назывался бы previous. Также делать parent=NULL для "промежуточных братьев", кроме последнего в списке next, тоже неправильно - это лишает ссылку parent ее первоначального смысла. И т.д. В общем - parent есть parent, и он самообъясняющий.

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

Короче - верить нельзя никому, ожидать всего чего угодно - дефенсив стайл оф программинг.

SVK · Post by **SVK** » 29 Apr 2004 16:41

A. Fig Lee wrote:Странно, для меня он не само обьясняющий. Например, родитель, дети - школьники, следующий школьник, следующий, паренты могут быть другими.

Не могу представить ситуации, которая заставляет думать, что у "школьников-братьев" может быть разный "родитель"? (Приемных детей мы в такой ситуации не рассматриваем :mrgreen:

)

A. Fig Lee · Post by **A. Fig Lee** » 29 Apr 2004 16:45

SVK wrote:
A. Fig Lee wrote:Странно, для меня он не само обьясняющий. Например, родитель, дети - школьники, следующий школьник, следующий, паренты могут быть другими.

Не могу представить ситуации, которая заставляет думать, что у "школьников-братьев" может быть разный "родитель"? (Приемных детей мы в такой ситуации не рассматриваем )

1. почему братьев? просто одноклассники. Например, множество учившихся в школе и их релейшиншип.
2. А и не надо представлять - есть факты. Мыслим абстрактно: дано а, надо получить б. про с никто ничего не говорил.

vc · Post by vc » 29 Apr 2004 17:10

SVK wrote:
vc wrote:1. The structure Node( Next, Child, Parent, Key) clearly represents an _ordered_ tree node but it's not clear what's considered to be the parent;

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

I apologize beforehand for being blunt.

I described in my previous response two possible interpretations of the parent link. Its only raison d'etre is to enable iterative tree traversal. In my interpretation, the link makes possible all the three iterative binary tree traversals (pre/in/post) whilst in yours, only the first is possible. It's sort of stupid to waste memory and achieve only one third of what might have been done if one used the proper interpretation, would not you agree ?. If you care so much about efficiency, why choose an inferior approach ? .

In any case, the question was ambiguous and it would have been quite legitimate to ask for clarification.

SVK wrote:Также непонятен смысл поворота дискуссии от основного вопроса. Были даны начальные условия задачи, - как они есть. И предложено найти оптимальный способ обхода дерева - именно при тех условиях, как они заданы. В качестве скорее подсказки также дано требование не использовать рекурсию, хотя в такой ситуации этого можно было не требовать, а ожидать что в качестве предпочтительного решения будет предложен именно обход без рекурсии, поскольку все промежуточные данные, для сохранения которых обычно и требуется либо рекурсия, либо стек данных, в данной конкретной ситуации уже заложены в исходную структуру (хорошо это, или плохо - другой вопрос, но главное - они там уже есть).

Этот вопрос я так и понимал, как желание увидеть, кто из решающих заметит достаточность исходных данных для решения задачи без создания (явно либо неявно) промежуточных структур, которые получаются при заученных способах решения этой в общем стандартной задачи. Это - полная копия той шутки: Как вскипятить чайник наполненный водой, который находится рядом со включенной газовой плитой? Программист предлагал (1) вылить воду, (2) погасить плиту, (3) сделать кипячение так, как делал вчера.

Разве не похожие способы были предложены для обхода дерева, в котором уже заданы parents: (1) игнорировать parents, (2) рекомендовать руководству никогда не вносить лишних ссылок в их данные, (3) создать свой стек из тех же самых значений parents, и обходить дерево так, как на днях делали в другой конторе.

Разве не похожая ситуация?

I am not sure what you are trying to say here so I won't comment.

SVK wrote:И совсем непонятное замечание было про отказ от работы там, где задали бы "такой глупый вопрос". Конечно, в качестве реального вопроса для интервью, этот вопрос - не лучший кандидат. Но в похожей ситуации лично я бы взял на работу кандидата, который для простой задачи предложит именно простое решение, а не более сложное, но: (1) стандартное, или (2) модное, или (3) использующее новейшие технологии, или (4) названное именем известного изобретателя, или же вообще вместо конкретного решения конкретной задачи начнет предлагать выбросить все что есть, и переделать с самого начала.

The problem with the question is that it belongs to the same category as, for example, the following:

1. Name all the parameters and their types in the OCIFetch2 call;
2. Is the Warshall algorithm applicable for directed acyclic graphs;
3. Please implement the bubble sort algorithm on the whiteboard;

The interviewee's ability to do his job is entirely independend on whether he knows/does not know a correct answer to the above. I'll leave it you to figure out why.

VC

SVK · Post by **SVK** » 29 Apr 2004 17:22

A. Fig Lee wrote:1. почему братьев? просто одноклассники. Например, множество учившихся в школе и их релейшиншип.
2. А и не надо представлять - есть факты. Мыслим абстрактно: дано а, надо получить б. про с никто ничего не говорил.

Вот нашел наглядную картинку (из http://www.mae.cornell.edu/lipson/409/elementary.doc) - в точности отражающую стандартное понимание смысла ссылок типа parent, которое было общепринятым. Раньше было много примеров, теперь их труднее найти.

SVK · Post by **SVK** » 29 Apr 2004 17:28

vc wrote:I am not sure what you are trying to say here so I won't comment.

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

Дискуссия начала отходить в сторону: условие дано некрасивое/неэффективное/непривычное/непонятное/неприятное/незнакомое/не<что угодно>. Поэтому давайте изменим/выбросим это условие, и будем решать другую задачу - она привычнее/изящнее/эффективнее(?)/еще какая-нибудь.

SVK · Post by **SVK** » 29 Apr 2004 17:34

vc wrote:The problem with the question is that it belongs to the same category as, for example, the following:

1. Name all the parameters and their types in the OCIFetch2 call;
2. Is the Warshall algorithm applicable for directed acyclic graphs;
3. Please implement the bubble sort algorithm on the whiteboard;

По-моему - с точностью до наоборот: как раз эти вопросы из совершенно другой категории - скорее на знание/запоминание некоторых конкретных вещей, на проверку эрудиции, в каком-то смысле. А не на способность придумать что-то, хотя бы и простое. Хотя в некоторых случаях такие вопросы тоже бывают нужны.

Mongush · Post by **Mongush** » 29 Apr 2004 18:00

8K wrote:
SVK wrote:Самый красивый алгоритм вычисления факториала

А слабо написать compile-time факториал, чтобы его компилятор в момент компиляции считал, если N - константа? Правда, под нашим VC++ все равно не работает, т.к. реализация шаблонов кривая.

Code: Select all

#include<iostream>
template <int N>
struct fact{
   enum{res=N*fact<N-1>::res};
};
template <>
struct fact<1>{
   enum{res = 1};
};
int main()
{
   fact<6> aa;
   std::cout<<aa.res;
}

Это просто и неинтерсно

А вот корень квадратный слабо? (округленый из целого)

tengiz · Post by **tengiz** » 30 Apr 2004 01:47

A. Fig Lee wrote:Когда давно я пытался использовать alloca на UNIX. И не нашел ее. Глянул стандард - тоже не нашел. Кстати, в МСДН указано что ето личная Виндовс функция.

Я погуглил на эту тему, и первая же ссылка говорит, что conformance для alloca - 4.4BSD, кроме того, ссылки дальше говорят, что такой compiler intrinsic имеется также в GNU C. И вообще много где, в смысле в юниксах. В MSDN же написано, видимо, про _alloca. А вот этот pdf вообще внаглую утверждает, что alloca - это теперь ANSI C.

theukrainian · Post by **theukrainian** » 30 Apr 2004 02:52

alloca is definitely not part of c99. i am pretty sure its not part of c89 either....

tengiz · Post by **tengiz** » 30 Apr 2004 05:07

theukrainian wrote:alloca is definitely not part of c99. i am pretty sure its not part of c89 either....

Я только что заглянул в C99 - да, там нет alloca, причина, по которой alloca не включена в стандарт - сложность или невозможность качественной реализации на платформах без аппаратного стека. Однако там есть одна крайне забавная конструкция, которая во многих случаях заменяет alloca - VLA (variable length arrays). Я, правда, не совсем понимаю, почему VLA проще в реализации, чем alloca.

theukrainian · Post by **theukrainian** » 30 Apr 2004 06:38

out of curiousity... are there compilers out there with solid support for c99 already? ... is it pretty mainstream now?

A. Fig Lee · Post by **A. Fig Lee** » 30 Apr 2004 12:27

tengiz wrote:
theukrainian wrote:alloca is definitely not part of c99. i am pretty sure its not part of c89 either....

Я только что заглянул в C99 - да, там нет alloca, причина, по которой alloca не включена в стандарт - сложность или невозможность качественной реализации на платформах без аппаратного стека. Однако там есть одна крайне забавная конструкция, которая во многих случаях заменяет alloca - VLA (variable length arrays). Я, правда, не совсем понимаю, почему VLA проще в реализации, чем alloca.

varg-и? Ето и было мое первое предположение в етом топике. Ну управление ними не тривиально, да и врядли ето требовалось от задачи.