Задачи на собеседовании программистов

skif

Житель центра
#41
Дело не в реализации указателей в с# или еще в каком-то языке.

Двусвязный список, это по определению вот такая структура:

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

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

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

Для тех, кто заинтересовался в возможных подводных камнях, то эта тема хорошо описана тут
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein – Introduction to Algorithms, Second Edition или тут http://staff.science.uva.nl/~heck/JAVAcourse/ch4/sss1_2_3.html. При желании, можно найти и на русском.
 

Aliens

Меня знают многие ;-)
#42
Я не понимаю, к чему эти теоретические заносы, если код приведенный мной работает.
Добавить в список указатель на 1й элемент? - Пара устяков.
Написать функции вставки и удаления? - Но так этого не было в задании! Было задание написать функцию свап, она есть. Или тебе надо реализовать полностью все функции работы со списком? Так это надо указывать.
Может быть в следующем ответе, для хорошего понимания работы списка, ты попросишь реализовать сортировку? Бинарный поиск? Сразу все требование к составу методов библиотеки уже озвуч )
 

skif

Житель центра
#43
Ок. Это была лирика и, наверное, подсказка.

Что такое связный список нужно знать. LinkedList есть всюду.
Функция swap не реализована. В текущем виде этот код не будет работать как связный список.
Не знаю, что еще добавить.
 

skif

Житель центра
#44
Я не понимаю, к чему эти теоретические заносы, если код приведенный мной работает.
Как это проверить?

Задание не изменилось. Нужно реализовать перстановку двух элементов списка. Как ты себе это представляешь без удаления и вставки элементов?
 

Dima

Житель окраин
#45
C#:

Описание элемента:
Код:
  class Element
    {
        public Element PrevElement = null;
        public Element NextElement = null;
        public string Data = "";
 
        public Element(string data)
        {
            Data = data;
        }
 
        public override string ToString()
        {
            return Data;
        }
    }
Класс списка:
Код:
  class List
    {
        public Element FirstElement;
        public Element LastElement;
 
        public List(Element firstElement, Element lastElement)
        {
            FirstElement = firstElement;
            LastElement = lastElement;
        }
 
        public void Swap(Element _e1, Element _e2)
        {
            if (_e1 == _e2)
                return;
 
            Element e1 = _e1;
            Element e2 = _e2;
 
            if (e2.NextElement == e1)
            {
                Element tmp = e1;
                e1 = e2;
                e2 = tmp;
            }
 
            Element e1_prev = e1.PrevElement;
            Element e1_prev_old = e1.PrevElement;
         
            Element e1_next = e1.NextElement;
            Element e1_next_old = e1.NextElement;
 
            Element e2_prev = e2.PrevElement;
            Element e2_prev_old = e2.PrevElement;
 
            Element e2_next = e2.NextElement;
            Element e2_next_old = e2.NextElement;
 
            if (e1.NextElement == e2)
            {
                if (e1_prev != null)
                {
                    e1_prev.NextElement = null;
                }
 
                if (e2_next != null)
                {
                    e2_next.PrevElement = null;
                }
 
                e2.NextElement = e1;
                e1.NextElement = e2_next_old;
 
                e1.PrevElement = e2;
                e2.PrevElement = e1_prev_old;
 
                if (e1_prev != null)
                {
                    e1_prev.NextElement = e2;
                }
 
                if (e2_next != null)
                {
                    e2_next.PrevElement = e1;
                }
 
            }
            else
            {
                if (e2_prev != null)
                {
                    e2_prev.NextElement = null;
                }
 
                if (e1_next != null)
                {
                    e1_next.PrevElement = null;
                }
 
                if (e1_prev != null)
                {
                    e1_prev.NextElement = e2;
                }
     
                if (e2_next != null)
                {
                    e2_next.PrevElement = e1;
                }
     
                if (e2_prev != null)
                {
                    e2_prev.NextElement = e1;
                }
 
                if (e1_next != null)
                {
                    e1_next.PrevElement = e2;
                }
 
                e1.NextElement = null;
                e2.NextElement = e1_next_old;
                e1.NextElement = e2_next_old;
 
                e2.PrevElement = null;
                e1.PrevElement = e2_prev_old;
                e2.PrevElement = e1_prev_old;
            }
        }
    }
Тест:
Код:
            Element e1 = new Element("e1");
            Element e2 = new Element("e2");
            Element e3 = new Element("e3");
            Element e4 = new Element("e4");
            e1.NextElement = e2;
            e2.PrevElement = e1;
            e2.NextElement = e3;
            e3.PrevElement = e2;
            e3.NextElement = e4;
            e4.PrevElement = e3;
 
            List list = new List(e1, e3);
 
            Console.WriteLine("Before (expect: e1, e2, e3, e4)");
            Element el;
            el = list.FirstElement;
            while (el != null)
            {
                Console.WriteLine(el.ToString());
                el = el.NextElement;
            }
         
            list.Swap(e2, e3);
            Console.WriteLine("After #1 (expect: e1, e3, e2, e4)");
            el = list.FirstElement;
            while (el != null)
            {
                Console.WriteLine(el.ToString());
                el = el.NextElement;
            }
         
            list.Swap(e3, e4);
            Console.WriteLine("After #2 (expect: e1, e4, e2, e3)");
            el = list.FirstElement;
            while (el != null)
            {
                Console.WriteLine(el.ToString());
                el = el.NextElement;
            }
Комментарии:
1. В классе списка намеренно не реализовал методы навигации, инициализации, а только лишь сконцентрировался на методе обмена местами элементов списка.
2. Метод Swap() работает для двух случаев отдельно:
- элементы списка для обмена смежные - второй следует за первым, или первый следует за вторым (в последнем случае я их временно меняю, чтобы рассматривать общий случай смежных элементов)
- элементы не смежные.
3. Вообще, для списка еще было бы не плохо хранить количество элементов, которое бы позволяло исключить зацикливание в случае возможных ошибок пользования списком клиентом.
4. Задачка для собеседования крутая! Возьму на вооружение. Но в случае с "онлайн" собеседованием я бы наверное не стал за 10-15 минут ждать готового решения от соискателя, но на ход мыслей соискателя посмотреть можно.
 

skif

Житель центра
#50
Всем привет.

Автор темы пропал в вымышленном мире, но был недавно возвращен к реальности, в которой существует армавирский форум небезызвестным Александром Рутовым, за что ему и спасибо:)

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

Победителем, предоставившим единственный выдерживающий критику вариант провозглашается Dima. С чем его и поздравляем, ура-ура!
В Армавире буду на выходных 15-16 июня. В эти же дни будет награжден победитель. Предлагаю предать событие награждения публичной огласке, снабдить фотосессией, пьянкой и прочими социальным излишествами.

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

skif

Житель центра
#51
И всем кто еще только планирует связать свою жизнь с разработкой ПО рекомендую посмотреть вот это видео (есть русские субтитры).
Учитесь и будете волшебниками завтрашнего дня :-)

 

Dima

Житель окраин
#55
О! Я тут.
Ожидая не менее честно заработанный в другом конкурсе планшет уже месяц, думал, что это долго. Ан нет! :-)
На этих выходных физически никак не выйдет.
 

Dima

Житель окраин
#57
... Победителем, предоставившим единственный выдерживающий критику вариант ...
Давайте подискутируем, интересно же.
Я вот, помню, почти голову сломал при работе над решением. Есть ли какое-то более элегантное решение?

Значит заберешь у меня, если скифик доедет :)
Да ну что вы, не в призе же дело!
А в будний день можно подъехать куда-нибудь? :)
 

GeneraL

Житель окраин
#59
в тему 1го поста:

вот забавный вариант:
http://wp7rocks.com/posts/details/8...paign=Feed:+wp7rocks+(Windows+Phone+7+Rocks!)
согласен по поводу практической ценности, но возможно и в правду может, в качестве первого вопроса собеседования, являться фильтром от нежелательного спама.
 

GeneraL

Житель окраин
#60
друзьям, русским товарищам, в Дубае нужен был специалист.
задание рассчитано, в последствии, на удаленную работу.

Test task.
Coding question:
Develop Web Application to both search and view data from Customers table of North Wind database.
The search should be realized by specified conditions:
1. Country;
2. City;
3. Company name.
Notice, the search parameters can be set up partially.
Functional requirements:
The search parameters should be presented as following:
1. The company name parameter as a Textbox control;
2. The city as a Dropdown list control;
3. The country as a Dropdown list control.
Results should be presented as a single table with both sorting by individual columns and paging opportunities.
Development requirements:
1. The application must be developed using C# as a programming language (.net 3.5 or .net 4.0);
2. The type of the application must be a Web Application. To develop the project candidate have to use ASP.NET MVC framework (the latest version would be appreciated);
3. The project architecture should be scalable with opportunity for future modifications;
4. All application preferences such as connection strings shouldn’t be hardcoded. The project relocation from one application server to another shouldn’t invoke additional modifications in the source code;
5. To work with the data warehouse use existing OR/M. For instance, NHibernate;
6. The main attention should be concentrated on how you will catch and process errors. Incorrect user’s input should be processed as well;
7. Using both caching and paging mechanisms absolutely necessary;
8. The application architecture should be developed with keep in mind that the application will work in an environment where 10 000 simultaneous requests per second is a daily work;
9. All application functionality should be under the tests;
10. The S.O.L.I.D development principles should be the main development principles while you develop the application.
Note: To develop the project Visual Studio 2010 and Nunit tests must be used.

на решение давали несколько дней.

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

в последствии устроил туда своего товарища и получил рекрутерский бонус.