ANSI C: Walking tree

[SVK]

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]

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

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

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

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

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

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

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

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


Еще вопрос интерсный - не помню точно как звучит.
Примерно:
С и С++ языки со стронг тайп чекинг. Почему в С++ ето более важно чем в С, особенно в енвайронмент где типикалли используется 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]

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

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

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

[SVK]

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

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

[A. Fig Lee]

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

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

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

[vc]

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.

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

Этот вопрос я так и понимал, как желание увидеть, кто из решающих заметит достаточность исходных данных для решения задачи без создания (явно либо неявно) промежуточных структур, которые получаются при заученных способах решения этой в общем стандартной задачи. Это - полная копия той шутки: Как вскипятить чайник наполненный водой, который находится рядом со включенной газовой плитой? Программист предлагал (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.

И совсем непонятное замечание было про отказ от работы там, где задали бы "такой глупый вопрос". Конечно, в качестве реального вопроса для интервью, этот вопрос - не лучший кандидат. Но в похожей ситуации лично я бы взял на работу кандидата, который для простой задачи предложит именно простое решение, а не более сложное, но: (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]

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

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

[SVK]

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

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

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

[SVK]

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]

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

А слабо написать 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]

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

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

[theukrainian]

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

[tengiz]

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]

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

[A. Fig Lee]

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-и? Ето и было мое первое предположение в етом топике. Ну управление ними не тривиально, да и врядли ето требовалось от задачи.