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

skif

skif

Житель центра
#41
#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. При желании, можно найти и на русском.
 
A

Aliens

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

skif

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

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

skif

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

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

Dima

Житель окраин
#45
#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

skif

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

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

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

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

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

skif

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

 
D

Dima

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

Dima

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

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

GeneraL

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

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

GeneraL

Житель окраин
#60
#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 технологий и клиент-серверных приложений, но для разминки обложился книгами и решил. для развития кругозора. было свободное время, развеял однообразие. когда в своих, досконально изученных темах, тарабанишь тонны кода каждый день, утомляет. по коду и архитектуре естественно ко мне замечаний ноль, за то сложился очень интересный разговор с работодателем. получил от ребят инфу основанную на их собственном опыте. рассказали как сами набивали шишки с нуля поднимая бизнес, какие случались ситуации, какие инструменты как себя показали в боевом режиме. думаю, если мне приспичит, смогу собрать устойчивый биллинговый центр рассчитанный на интенсивную нагрузку и избегу многих подводных камней о которых в книгах не пишут.

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