1

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

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

Вот само задание:

Разработать алгоритм который:

Сортирует переданный список записей (каждая запись - набор колонок) таблицы по указанной колонке по следующим правилам:

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

2) строка бьется на подстроки следующим образом:

Выделяем непрерывные максимальные фрагменты строки, состоящие только из цифр, и считаем набором подстрок эти фрагменты и все оставшиеся от такого разбиения фрагменты строки.

3) при сравнении строк осуществляется последовательное сравнение их подстрок до первого несовпадения,

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

По 2) пункту: Я не совсем понимаю, как могут быть максимальными фрагментЫ строки. Максимальным (по длине) может быть только один фрагмент?!

Что в понимании постановщика задачи есть "строка"? Это совокупность столбцов одной записи или же это значение столбца по которому нужно сортировать список?

5
  • Было бы не плохо увидеть пример данных с которыми будет работать этот алгоритм. 23 авг 2016 в 5:01
  • 3
    Кажется лучше спросить у того кто давал задание, а то неясно, какой ответ будет правильным. Понять задание каждый может по своему. 23 авг 2016 в 5:23
  • Я так и сделал, но "в ответ тишина.."(с)
    – Vard32
    23 авг 2016 в 5:45
  • Я тоже хочу увидеть пример данных, но по условию задачи, этим набором данных может быть результат Select-а (к примеру) Т.е. это список одномерных массивов, где записи - это элементы списка(массивы), а столбцы - это элементы одномерного массива.
    – Vard32
    23 авг 2016 в 5:49
  • По описанию выглядит как хранение csv в базе и соответственно сортировка по этому полю. Правильное решение в данном случае - приведение бд хотя бы к первой нормальной форме, а "алгоритм-костыль" таки реализовать и высечь на могиле автора задания. 23 авг 2016 в 8:09

1 ответ 1

8

Речь о таком разбиении:

11х1111хххх1ххх1
["11", "х", "1111", "хххх", "1", "ххх", "1"]

Под "максимальные" понимается "жадное совпадение" при котором совпадение старается захватить как можно больше символов. Совпадений по каждой строке может быть больше одного, и каждое из них должно захватывать как можно больше. Максимальное относится к каждому фрагменту, а не ко всему набору.

Это разбиение однозначно, т. е. для каждой строки существует ровно одно такое.

Если это условие убрать из задачи, появятся дополнительные разбиения, в которых непрерывные последовательности из цифр раскиданы по отдельным фрагментам, типа:

11ххх11111хх
["1", "1", "xxx", "11", "111", "xx"]

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

16
  • 1
    Ну вот к примеру такое выражение: 111ххх222223334455хх - это первая строка и xxx2222xxxx11 - это вторая. Теперь смотрим: в первой строке максимальное совпадение это "222223334455". Во второй строке - это "2222". Переводим их в числа. Получим 2222 и 222223334455 соответственно. Следуя условию задачи, строка с 2222 должна быть первой, а строка с 222223334455 - второй. Но это же не правильно! Первой должна быть строка "111ххх222223334455хх" где первые символы единицы - т.е. 111 Иначе это уже не сортировка а что-то другое.
    – Vard32
    23 авг 2016 в 6:44
  • @Vard32 вы вообще не поняли ответ. Сейчас подумаю, как его прояснить...
    – user181100
    23 авг 2016 в 6:48
  • Да, я чувствую что не понял. Если Вам не сложно - поясните пож-ста.
    – Vard32
    23 авг 2016 в 6:50
  • @Vard32 во, посмотрите сейчас.
    – user181100
    23 авг 2016 в 6:51
  • Смотрю + Думаю.
    – Vard32
    23 авг 2016 в 6:51

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.