Зачем просят перевернуть строку на интервью? - О работе

Здравствуйте, koodeer, Вы писали:
K>Бегло просмотрел ответы в теме. Большинство провалили тест. Сказано же:

не выделяя новой памяти

Не сказано. Если посмотришь историю изменений сообщения Тёмки, то увидишь, что про "не выделение новой памяти" было дописано уже после.

Тё>без выделения новой строки

В начальной версии твоего сообщения такого требования не было.

Здравствуйте, Nuzhny, Вы писали:

Тё>>


Тё>>class Node {
Тё>>public:
Тё>>char *value;
Тё>>Node *next;
Тё>>}

Тё>>Node* reverse(Node *head) {
Тё>>...
Тё>>}

Тё>>

Вот, что у меня получилось за 15 минут в 4 часа утра:

Node* reverse(Node *head) 
{
  if ( nullptr == head )
    return head;

  Node* pPrev = nullptr;
  Node* pNext = head->next;

  while(nullptr != pNext)
  {
    head->next = pPrev;
    pPrev      = head;
    head       = pNext;
    pNext      = head->next;
  } 
  return head;
}

или

Node* reverse2(Node *head) 
{
  if ( nullptr != head->next )
    return head;

  Node* pNewHead = reverse2(head->next);
  head->next = head;

  return pNewHead;
}  

Node* reverse(Node *head) 
{
  if ( nullptr == head )
    return head;

  Node* pNewHead = reverse2(head->next);
  head->next = nullptr;

  return pNewHead;
}

Здравствуйте, De-Bill, Вы писали:

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

Чисто спортивный интерес. В каком языке вычисление длины строки требует выделения памяти?

Здравствуйте, VVV, Вы писали:

VVV>А как рекурсивно?

Я не знаю, что там в жемчужинах, но элементарно же:

void reverse(char* first, char* last)
{
  if ( first < last )
  {
    reverse(first + 1, last - 1);
    std::swap(*first, *last);
  }
}

Здравствуйте, De-Bill, Вы писали:

CAF>>А вообще не надо выдумавать проблем, там где их нет. Никто на собесе никого не хочет завалить, нет смысла придираться.

DB>При собеседовании у Тёмки, возможно. Но я знаю вполне конкретные конторы (так как там мои знакомые собеседуют), где за решение задачи без уточнения условий (вопросов со стороны соискателя) будет серьёзный минус.

Именно этой задачи или вообще?

Я имел ввиду, что в задаче обычно не ожидается ничего более сложнее индексации. И что чаще всего это простой тест для отсева полных нулей,
без всяких подвохов. В этом был КМК вопрос Темы. Конечно в данном случае можно уточнить какой язык/что используешь, но без фанатизма.

Я кстати давным давно проверял десятки кандидатов решающих и переворот строки и списка. К сожалению не все способны перевернуть и строку. А список вообще швах

Если человек использует функции — можно спросить что внутри должно быть по его мнению. Если рекурсию — пусть про стек расскажет, чем плохо в днном случае. Кодировки меня признаюсь не волновали. Если вопрос а как же на джаве, то предлагался голый массив или буфер. Да пусть хоть в нотации пишет.
Я кстати еще и на тестирование смотрел, когда проверял. (Конечно его почти никогда не было)

CAF>Именно этой задачи или вообще?

В том числе и именно этой.

CAF>Я имел ввиду, что в задаче обычно не ожидается ничего более сложнее индексации. И что чаще всего это простой тест для отсева полных нулей,
CAF>без всяких подвохов. В этом был КМК вопрос Темы. Конечно в данном случае можно уточнить какой язык/что используешь, но без фанатизма.

Даже если взять эту конкретную задачу на этом конкретном форуме. Изначально у Тёмы не было условия in-place (можно посмотреть историю правок его начального сообщения). Потом in-place появилось. И это полностью изменило задачу, а для некоторых языков программирования делало решение невозможным нормальным способом. А маленькое дополнительное требование (но вполне реальное в бизнесе) переворачивать строки типа "приве́т" (с ударением на e), может вообще поменять всё.
А так да, у многих собеседующих в голове прошито решение задачи. В их голове — это задача на индексацию. Но в реальности задачей на индексацию она является только при куче дополнительных условий и ограничений.

Здравствуйте, De-Bill, Вы писали:

CC>>По условиям задачи на собеседованиях надо как раз in-place.
DB>Начнём с того, что условие in-place Артёмка приписал уже после моего ответа.

Начнём с того что это настолько бородатая задача что условия эти давно известны.

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

CC>Начнём с того что это настолько бородатая задача что условия эти давно известны.

А с чего ты взял, что это именно та бородатая задача? Без условия на in-place это может быть вполне задачей на отсев любителей заморочится на пустом месте.

Здравствуйте, De-Bill, Вы писали:

CAF>>Именно этой задачи или вообще?

DB>В том числе и именно этой.

CAF>>Я имел ввиду, что в задаче обычно не ожидается ничего более сложнее индексации. И что чаще всего это простой тест для отсева полных нулей,
CAF>>без всяких подвохов. В этом был КМК вопрос Темы. Конечно в данном случае можно уточнить какой язык/что используешь, но без фанатизма.

DB>Даже если взять эту конкретную задачу на этом конкретном форуме. Изначально у Тёмы не было условия in-place (можно посмотреть историю правок его начального сообщения). Потом in-place появилось. И это полностью изменило задачу, а для некоторых языков программирования делало решение невозможным нормальным способом. А маленькое дополнительное требование (но вполне реальное в бизнесе) переворачивать строки типа "приве́т" (с ударением на e), может вообще поменять всё.

Про память — да существенное условие. А всяких ударений не предусмотреть. Можно всего понапридумать, и ударение, и строки длиной больше предела в языке. И кстати в бизнесе тоже, но задумывать о трубованиях бизнеса это перебор.

DB>А так да, у многих собеседующих в голове прошито решение задачи. В их голове — это задача на индексацию. Но в реальности задачей на индексацию она является только при куче дополнительных условий и ограничений.

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

CAF>Про память — да существенное условие.
Это то, что делает из одной задачи другую.
CAF>А всяких ударений не предусмотреть.
Не предусмотреть. Поэтому и важно примерно отметить ограничения, при которых решение будет работать.
CAF>В реальности это зависит только от собеседующего. Я написал, то что мне кажется наиболее типичным.
Согласен. Некоторые собеседующие могут считать: "Это же бородатая задача, значит in-place по умолчанию, зачем обговаривать дополнительно?". Другие будут считать, что задача намного глубже, чем кажется. И если соискатель начинает накидывать решение даже без малейших уточнений, то это минус.

Здравствуйте, B0FEE664, Вы писали:

Тё>>>


Тё>>>class Node {
Тё>>>public:
Тё>>>char *value;
Тё>>>Node *next;
Тё>>>}

Тё>>>Node* reverse(Node *head) {
Тё>>>...
Тё>>>}

Тё>>>

BFE>Вот, что у меня получилось за 15 минут в 4 часа утра:

BFE>

BFE>Node* reverse(Node *head) 
BFE>{
BFE>  if ( nullptr == head )
BFE>    return head;

BFE>  Node* pPrev = nullptr;
BFE>  Node* pNext = head->next;

BFE>  while(nullptr != pNext)
BFE>  {
    head->>next = pPrev;
BFE>    pPrev      = head;
BFE>    head       = pNext;
BFE>    pNext      = head->next;
BFE>  } 
BFE>  return head;
BFE>}
BFE>

Есть лишние буквы. Так короче:

reverse(head *Node){

Node *prev = 0;
while(head) {
  Node *next = head.next;
  head.next = prev;
  prev = head;
  head = next;
}
return prev;
}

BFE>или
BFE>

BFE>Node* reverse2(Node *head) 
BFE>{
BFE>  if ( nullptr != head->next )
BFE>    return head;

BFE>  Node* pNewHead = reverse2(head->next);
  head->>next = head;

BFE>  return pNewHead;
BFE>}  

BFE>Node* reverse(Node *head) 
BFE>{
BFE>  if ( nullptr == head )
BFE>    return head;

BFE>  Node* pNewHead = reverse2(head->next);
  head->>next = nullptr;

BFE>  return pNewHead;
BFE>}
BFE>

BFE>

Опять много буков и зачем-то две функции вместо одной.


reverse(head *Node, reversedHead *& Node) {

  if(head && head.next){
    Node *reversedTail = reverse(head.next, reversedHead);
    reversedTail.next = head;
    head.next = 0;
  } else {
    reversedHead = head;
  }
  return head;
}

Здравствуйте, De-Bill, Вы писали:

CAF>>Про память — да существенное условие.
DB>Это то, что делает из одной задачи другую.
CAF>>А всяких ударений не предусмотреть.
DB>Не предусмотреть. Поэтому и важно примерно отметить ограничения, при которых решение будет работать.
CAF>>В реальности это зависит только от собеседующего. Я написал, то что мне кажется наиболее типичным.
DB>Согласен. Некоторые собеседующие могут считать: "Это же бородатая задача, значит in-place по умолчанию, зачем обговаривать дополнительно?". Другие будут считать, что задача намного глубже, чем кажется. И если соискатель начинает накидывать решение даже без малейших уточнений, то это минус.

Я уже сказал, я написал о том чего ждет большинство с моей точки зрения. Особенно для вполне среднего уровня. Да — если ты идешь в супер R&D, то при виде такой задачи — должно в голове щелкнуть, что что-то не так. Что цель не продемонстрировать навыки итерации и индексации. (Может самому придется догадаться и делать строки оптимизированные для разворота). Да-да, меня такое про бинарный поиск спрашивали. Но в общем как мне кажется, мы друг друга поняли. По крайней мере я думаю, что тебя понял.

Кстати, вспомнил. Достаточно часто эта задача — начало длинной беседы. А что если так, а так, а так. (Но тут есть свой минус) Но простой переворот — маст хев.

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, Тёмчик, Вы писали:

Тё>>Ну зачем итераторы C++ пихать?
CC>А почему нет? Итератор это всего то абстракция. Если девелопер не способен её понять — у меня для него плохие новости.

Тё>>Но блин, в моей вселенной никому не нужен C++.
CC>Restrictions надо оговаривать отдельно а главное заранее.

Тё>> Так почему бы не выпендриваться и не сделать с массивом и индексами.
CC>Лично я увидев в этой задаче индексы даже на С засчитал бы как небольшой минус и попросил бы переписать решение так, чтобы от индексов избавиться.

Вот кстати:
А какое решение быстрее (я слабо знаком с оптимизациями компиляторов, поэтому любые комменты от опытных тов приветствуются)
индекс
— вычитать потом надо
+ loop unrolling
+ четкий икнремент по индексу может оптимизироваться
пара итераторов
+ параллельно икремент/декремент в конвейре

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

CC>Из моего опыта — любители индексов в массе пишут спагетти код.

Это мнение субъективное

Спорить с таким утверждением бессмысленно.

Здравствуйте, mgu,

mgu> Потому что в реальном проекте нужно будет переставлять кровати.

Бинго!

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

Здравствуйте, Vlad_SP, Вы писали:

V_S>Здравствуйте, mgu,

mgu>> Потому что в реальном проекте нужно будет переставлять кровати.

V_S>Бинго!

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

Да, и поэтому не надо уметь программировать

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

Здравствуйте, mgu, Вы писали:

mgu>А если серьёзно, то это первое, что нашлось в интернетах с готовым ответом. Как-то ни разу не сталкивался с вариациями, например, поменять левую часть строки с правой.

Это типичные задачи для студентов 1-го курса.

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, kaa.python, Вы писали:

KP>>Не надо её переворачивать, всегда можно взять rend().
CC>Нельзя. По условиям задачи надо именно изменить данные.

Считать данные из строки через:
https://en.cppreference.com/w/cpp/iterator/reverse_iterator

сохранить в новой (временной) строке,
затем заменить имеющуюся на новую.

Что НЕ так ?

Здравствуйте, AlexGin, Вы писали:

AG>Здравствуйте, CreatorCray, Вы писали:

CC>>Здравствуйте, kaa.python, Вы писали:

KP>>>Не надо её переворачивать, всегда можно взять rend().
CC>>Нельзя. По условиям задачи надо именно изменить данные.

AG>Считать данные из строки через:
AG>https://en.cppreference.com/w/cpp/iterator/reverse_iterator

AG>сохранить в новой (временной) строке,
AG>затем заменить имеющуюся на новую.

AG>Что НЕ так ?

Нельзя память выделять. (Кроме переменных)

	От:	De-Bill
	Дата:	11.10.18 01:42
	Оценка:

	От:	De-Bill
	Дата:	11.10.18 01:42
	Оценка:

	От:	B0FEE664
	Дата:	11.10.18 02:20
	Оценка:

	От:	Ziaw
	Дата:	11.10.18 02:26
	Оценка:

	От:	B0FEE664
	Дата:	11.10.18 02:48
	Оценка:

От:	Тёмчик	жж
Дата:	11.10.18 03:48
Оценка: