Вопросы на собеседовании на вакансию C#

[assazello]

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

Форумулировочка, конечно... Ничего не понял. Что имеется ввиду под "база данных"? что за корневая персона? она дана или ее надо найти? а если корневых несколько? всеми детьми - именно детьми или потомками?

Как кто-то шутил выше, мне - no hire.

Есть связанный список

class person
{
string name;
person mother;
person father;
}

Нужно вывести на экран дерево наследников (в узле может быть и мама и папа) со сложностью O(N)

И что тут понимается под "кореневой персоной"? Наследники - это все потомки или только дети?

[8K]

Не, ну очевидно же не список. Или там в структуре еще одно поле есть. Мозг кипит, разве что задача специально нечетко поставлена в расчете на диалог.

[OtherSide]

Я даже не знаю как еще объяснить. По моему все очевидно. Есть список, в котором у каждой персоны известна папа и мама. Нужно на экран вывести дерево, во главе которого самый старый дедушка, ниже его дети, дети его детей и т.д.

Петров
=Иванов
==Сидоров
==Терехова
===Петрушкин
=Кукушкин
==Попов

Сложность алгоритма должна быть O(N)

[assazello]

Я даже не знаю как еще объяснить. По моему все очевидно. Есть список, в котором у каждой персоны известна папа и мама. Нужно на экран вывести дерево, во главе которого самый старый дедушка, ниже его дети, дети его детей и т.д.

Петров
=Иванов
==Сидоров
==Терехова
===Петрушкин
=Кукушкин
==Попов

Сложность алгоритма должна быть O(N)

Петя мама:Валя папа:Коля
Валя мама: nil папа: nil
Коля мама: nil папа: nil

Кто у нас тут "самый старый дедушка" - Валя или Коля?

[OtherSide]

Я даже не знаю как еще объяснить. По моему все очевидно. Есть список, в котором у каждой персоны известна папа и мама. Нужно на экран вывести дерево, во главе которого самый старый дедушка, ниже его дети, дети его детей и т.д.

Петров
=Иванов
==Сидоров
==Терехова
===Петрушкин
=Кукушкин
==Попов

Сложность алгоритма должна быть O(N)

Петя мама:Валя папа:Коля
Валя мама: nil папа: nil
Коля мама: nil папа: nil

Кто у нас тут "самый старый дедушка" - Валя или Коля?

Предполагается что такого в базе нет

[8K]

Есть список, в котором у каждой персоны известна папа и мама.

Так не бывает.

[OtherSide]

Есть список, в котором у каждой персоны известна папа и мама.

Так не бывает.

кроме одной

[OtherSide]

У меня нет задания под рукой, пишу по памяти, я надеялся общий смысл понятен. Просто не понимаю, какой мне смысл препираться с вами?
И решение выше дал уже. Там предполагалось выводить не сразу, а заполнить Dictionary. Вроде ничего сложного, но ответ надо было дать в течении минуты. К тому же я для себя в голове держал скорость поиска по Словарю как логарифм, а не линейный.


Это n^2

class person
{
string name;
person mother;
person father;
}

List<person> storage;

List<person> GetChildren(person)
{
var list = new List<person>();
foreach (var v in storage)
if (v.mother == person || v.father = person)
list.add(v);

return list;
}

void Out(person p, string s)
{
Console.Write(s+ p.name);
foreach (v in GetChildren(p))
Out(v, s + "=");
}

void Out()
{
foreach (var v in storage)
if (v.mother == null || v.father = null)
Out(v, "");
}

[8K]

Ну, поиск в словаре, может, и линейный (по длине строки, хотя и не факт), а вставка, похоже, n-squared (тоже не факт):

If the Count property value already equals the capacity, the capacity of the Dictionary<TKey, TValue> is increased by automatically reallocating the internal array, and the existing elements are copied to the new array before the new element is added.

[Alexandr]

Просто придрались к первой же маленькой ошибке.
ИМХО, но вас не хотели брать по какой-то другой причине, возможно к вам лично не имеющей никакого отношения.

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

[Alexandr]

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

Форумулировочка, конечно... Ничего не понял. Что имеется ввиду под "база данных"? что за корневая персона? она дана или ее надо найти? а если корневых несколько? всеми детьми - именно детьми или потомками?

Как кто-то шутил выше, мне - no hire.

тоже нифига не врубился в задание
но Dictionary в C# - это хеш таблица

[OtherSide]

Просто придрались к первой же маленькой ошибке.
ИМХО, но вас не хотели брать по какой-то другой причине, возможно к вам лично не имеющей никакого отношения.

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

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

[OtherSide]

тоже нифига не врубился в задание
но Dictionary в C# - это хеш таблица

Короче, задача звучала так: "Внесите небольшое изменение в код, что бы он заработал со сложностью O(N)"

class person
{
string name;
person mother;
person father;
}

List<person> storage;

List<person> GetChildren(person)
{
var list = new List<person>();
foreach (var v in storage)
if (v.mother == person || v.father = person)
list.add(v);

return list;
}

void Out(person p, string s)
{
Console.Write(s+ p.name);
foreach (v in GetChildren(p))
Out(v, s + "=");
}

void Out()
{
foreach (var v in storage)
if (v.mother == null || v.father = null)
Out(v, "");
}

[Alexandr]

Есть связанный список

class person
{
string name;
person mother;
person father;
}

Нужно вывести на экран дерево наследников (в узле может быть и мама и папа) со сложностью O(N)

ну так банальная рекурсия и будет O(n)

[Alexandr]

Просто придрались к первой же маленькой ошибке.
ИМХО, но вас не хотели брать по какой-то другой причине, возможно к вам лично не имеющей никакого отношения.

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

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

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

[OtherSide]

Есть связанный список

class person
{
string name;
person mother;
person father;
}

Нужно вывести на экран дерево наследников (в узле может быть и мама и папа) со сложностью O(N)

ну так банальная рекурсия и будет O(n)

См. GetChildren()

[OtherSide]

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

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

[Alexandr]

Есть связанный список

class person
{
string name;
person mother;
person father;
}

Нужно вывести на экран дерево наследников (в узле может быть и мама и папа) со сложностью O(N)

ну так банальная рекурсия и будет O(n)

См. GetChildren()

так у тебя в GetChildren() цикл и в Out цикл, что суммарно даст n^2, а я говорю о рекурсивном DepthSearch, который каждый node по разу посетит, дав тем самым n

[Alexandr]

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

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

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

[SaintDog666]

тоже нифига не врубился в задание
но Dictionary в C# - это хеш таблица

Короче, задача звучала так: "Внесите небольшое изменение в код, что бы он заработал со сложностью O(N)"

Так вроде изначально вообще задача звучала как
"Задача. Создайте базу данных, в которой существует персона и 2 ее родителя..."
потом
"Есть связанный список. Нужно вывести на экран дерево наследников (в узле может быть и мама и папа) со сложностью O(N)"
потом
"Есть список, в котором у каждой персоны известна папа и мама. Нужно на экран вывести дерево, во главе которого самый старый дедушка, ниже его дети, дети его детей и т.д.
"
а сейчас уже оказывается надо было внести изменение в код ???

[assazello]

тоже нифига не врубился в задание
но Dictionary в C# - это хеш таблица

Короче, задача звучала так: "Внесите небольшое изменение в код, что бы он заработал со сложностью O(N)"

class person
{
string name;
person mother;
person father;
}

List<person> storage;

List<person> GetChildren(person)
{
var list = new List<person>();
foreach (var v in storage)
if (v.mother == person || v.father = person)
list.add(v);

return list;
}

void Out(person p, string s)
{
Console.Write(s+ p.name);
foreach (v in GetChildren(p))
Out(v, s + "=");
}

void Out()
{
foreach (var v in storage)
if (v.mother == null || v.father = null)
Out(v, "");
}

Кто-нибудь решил в такой формулировке? Я пока не смог.

Мне кажется я вижу решение, но на "небольшое изменение" оно не тянет. Только на большое.

[8K]

Вроде бы топологическая сортировка O(|V| + |E|).

За десять минут не напишу. И за полчаса тоже.

[OtherSide]

Кто-нибудь решил в такой формулировке? Я пока не смог.

Мне кажется я вижу решение, но на "небольшое изменение" оно не тянет. Только на большое.

Ну в какой задали в такой и передал. На самом деле предполагалось сохранять значение в структуре Dictionary<parent, list<parent>>

var dic = new Dictionary<parent, list<parent>>();
foreach( var l in list)
{
if (!dic.keyexistst(l.mother))
dic[l.mother] = new List<parent>();

if (!dic.keyexistst(l.father))
dic[l.mother] = new List<parent>();

dic[l.mother].Add(l);
dic[l.father].Add(l);
}

[SaintDog666]

Кто-нибудь решил в такой формулировке? Я пока не смог.
Мне кажется я вижу решение, но на "небольшое изменение" оно не тянет. Только на большое.

Да чушь это. Данная формулировка задачи подразумевает однополые браки и кровосмешение.

[Prosche]

No offence, но после strlen, я бы тоже начал прощаться с кандидатом. Самые мерзкие ошибки, это когда где-то тихонько перетирается память, причем байтик-другой. Соперничать с ними могут разве что дедлоки в мультитрединге.