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

Aliens

Меня знают многие ;-)
#22
Готов забрать вискарь!
Код:
public class Node {
private int element;
private Node next;
private Node prev;
public int getElement()
{return element;}
public void setElement(int e)
{ element = e;}
public Node getNext()
{return next;}
public void setNext(Node n)
{ next = n;}
public Node getPrev()
{returnprev;}
publicvoid setPrev(Node n)
{prev= n;}
}
 

absent

Известный деятель города
#23
Я даю всем небольшой тест из 90 вопросов, его нужно сделать за сутки. Можно пользоваться любыми средствами. В тесте 9 разделов из разных областей. На несколько вопросов нет ответа в интернете :) Пока все устраивает. Сразу видно и возможность решать незнакомые задачи, и характер. И потом, человек может не знать ничего о двусвязных списках, но отлично разбираться в сетях. И наоборот.
 

skif

Житель центра
#25
Готов забрать вискарь!
Код:
public class Node {
private int element;
private Node next;
private Node prev;
public int getElement()
{return element;}
public void setElement(int e)
{ element = e;}
public Node getNext()
{return next;}
public void setNext(Node n)
{ next = n;}
public Node getPrev()
{returnprev;}
publicvoid setPrev(Node n)
{prev= n;}
}
Неее, так не пойдет.
Подразумевается, что это связный список. Методы setNext и setPrev не удовлетворяют этому условию.

И да, привет копипастерам :)
Взять пример из википедии и влепить туда Node prev; – это не то, что достойно бутылки отличного виски.
Пожалуй, мне стоит уточнить задание.
 

Aliens

Меня знают многие ;-)
#26
хорошо уточни :)
тем более я сразу написал, что задача данная в подобном виде имеет простое решение
 

Aliens

Меня знают многие ;-)
#27
Ну что там с заданием? Зажал вискарек то?

И почему это мой ответ не соответствует условию? Переписать методы setNext и setPrev что бы указатели возвращали, а ?
 

skif

Житель центра
#28
За такое решение, конечно, зажал:)
Но неволнуйся, вискарь будет. Давно ведь уже писали о необходимости проведения программерской пьянки)

Так вот. ЗАДАЧА.

Есть двусвязный список следующего вида:
Код:
struct Element
{
  Element * m_prev;
  Element * m_next;
  ...
  ...
};

class List
{
   Element * m_first;
   Element * m_last;
   void swap(Element * e1,  Element * e2);
};
m_prev первого элемента и m_next последнего равны NULL.
Необходимо реализовать метод swap, меняющий местами два элемента.

ЯП значения не имеет.
 

Aliens

Меня знают многие ;-)
#30
Код:
void swap(Element * e1,  Element * e2)
{
  Element * tmp;
  tmp=e1.m_first;
  e1.m_first=e2.m_first;
  e2.m_first=tmp;
 
  tmp=e1.m_last;
  e1.m_last=e2.m_last;
  e2.m_last=tmp;
}
 

skif

Житель центра
#33
Не правильно.
Это попытка охватить вершину айсберга, но попытка с большим количеством ошибок:)
 

Aliens

Меня знают многие ;-)
#34
Первое что в голову пришло :)
Недоделки вижу. Завтра покажу рабочий вариант.
 

Aliens

Меня знают многие ;-)
#35
Вот, выкроил 20 минут :)

Код:
namespace List
{
    class Element
    {
        public Element(int value)
        {
            this.Value = value;
            this.Previous = null;
            this.Next = null;
        }
        public Element(int value, Element node)
        {
            this.Value = value;
            node.Next = this;
            this.Previous = node;
        }
 
        public Element Previous { get; set; }
        public Element Next { get; set; }
        public int Value { get; set; }
    }
 
    class LList
    {
        public Element foot;
 
        public void Add(int value)
        {
            this.foot = this.foot == null ? new Element(value) : new Element(value, this.foot);
        }
 
        public void swap(Element node1, Element node2)
        {
            Element tmp = new Element(0);
            tmp.Next = node2.Next;
            tmp.Previous = node2.Previous;
            node2.Next = node1.Next;
            node2.Previous = node1.Previous;
            if (node1.Next != null)
            {
                node1.Next.Previous = node2;
            }
            if (node1.Previous != null)
            {
                node1.Previous.Next = node2;
            }
 
            node1.Next = tmp.Next;
            node1.Previous = tmp.Previous;
            if (tmp.Next != null)
            {
                tmp.Next.Previous = node1;
            }
            if (tmp.Previous != null)
            {
                tmp.Previous.Next = node1;
            }
 
            if (node1.Next == null)
            {
                foot = node1;
            }
        }
   
    }
}
 

skif

Житель центра
#36
Вот, выкроил 20 минут :)

Код:
namespace List
{
    class Element
    {
        public Element(int value)
        {
            this.Value = value;
            this.Previous = null;
            this.Next = null;
        }
        public Element(int value, Element node)
        {
            this.Value = value;
            node.Next = this;
            this.Previous = node;
        }
 
        public Element Previous { get; set; }
        public Element Next { get; set; }
        public int Value { get; set; }
    }
 
    class LList
    {
        public Element foot;
 
        public void Add(int value)
        {
            this.foot = this.foot == null ? new Element(value) : new Element(value, this.foot);
        }
 
        public void swap(Element node1, Element node2)
        {
            Element tmp = new Element(0);
            tmp.Next = node2.Next;
            tmp.Previous = node2.Previous;
            node2.Next = node1.Next;
            node2.Previous = node1.Previous;
            if (node1.Next != null)
            {
                node1.Next.Previous = node2;
            }
            if (node1.Previous != null)
            {
                node1.Previous.Next = node2;
            }
 
            node1.Next = tmp.Next;
            node1.Previous = tmp.Previous;
            if (tmp.Next != null)
            {
                tmp.Next.Previous = node1;
            }
            if (tmp.Previous != null)
            {
                tmp.Previous.Next = node1;
            }
 
            if (node1.Next == null)
            {
                foot = node1;
            }
        }
   
    }
}

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

Что не верно:
- Список не является связным.
- Почему последний элемент списка указывает на this?
- Зачем создавать промежуточный элемент, если мы оперируем ссылками?
- Функция swap вызывает и другие вопросы.

Без обид.
 

Aliens

Меня знают многие ;-)
#37
Хм, так мы ничего не добьемся. Ты имеешь ввиду какое-то свое представление о двусвязных списках, а я пытаюсь отгадать что ты имеешь под этим ввиду.
В моем ответе я использовал именно такую структуру данных, как ты дал в задаче. Элемент public Element foot;
Я добавил просто для удобства обращения к списку, можно было добавить что то типа индексов или или ссылку на голову, к функции свап это отношения не имеет.

Какие вопросы к функции свап? Дай тогда исходные данные на которых она заткнется (может что-то не учел)

Все остальные вопросы относятся к конкретному ЯП, а в задаче выбор ЯП не определен, поэтому мы их опустим.
 

skif

Житель центра
#38
К ЯП у меня ни одного вопроса нет:)

Код:
  class Element
    {
        public Element(int value)
        {
            this.Value = value;
            this.Previous = null;
            this.Next = null;
        }
        public Element(int value, Element node)
        {
            this.Value = value;
            node.Next = this;
            this.Previous = node;
        }
 
        public Element Previous { get; set; }
        public Element Next { get; set; }
        public int Value { get; set; }
    }
Код:
    class LList
    {
        public Element foot;
 
        public void Add(int value)
        {
            this.foot = this.foot == null ? new Element(value) : new Element(value, this.foot);
        }
....
1. Этот код не обеспечит вставку нового элемента в связанный список.

Код:
        public Element(int value, Element node)
        {
            this.Value = value;
            node.Next = this;
            this.Previous = node;
        }
2. Это не соответсвует определению связного списка.
 

Aliens

Меня знают многие ;-)
#39
1 Этот код добавляет новый элемент в хвост, а не вставляет, для проверки всего этого кода я написал маленькую прогу, поверь элементы прекрасно вставляются, свапаются, перебираются по ссылкам взад и вперед.
2. Это элемент связанного списка содержащий ссылку Next на след элемент и ссылку Previuos на предыдущий, и поле Value хранящая некую полезную информацию. Аналог кода из постановки задачи, твоего.
Просто в c# по умолчанию указатели относятся к небезопасному коду, или что-то такое, поэтому напрямую их нельзя использовать если не включить галочку... В общем я сильно не разбирался, не обращай на это внимание. Все равно все IL код компилится потом...