FoxClub Forums > Игры Разума > Задачка с собеседования ::

• Войти

Задачка с собеседования
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005	Extortioner 11.07.11 14:34:02 Добрый день, недавно проходил собеседование в одной организации - прислали задание - есть строка, состоящая из строчных/прописных букв английского и русского алфавитов, а так же цифр. Необходимо отсортировать эту строку так: сначала заглавные буквы в алфавитном порядке, затем цифры по порядку ("0"-первый),потом строчные буквы в алфавитном порядке.Строка не содержит пробелов. При алфавитной сортировке русский стоит последним. Результат: англ.загл буквы, русские загл. буквы, цифры, англ.строчные буквы, русские строчные буквы. PS Задачу решил минут за 15. Через какое-то время опишу свой алгоритм.

Extortioner
Автор

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005

Extortioner

11.07.11 14:34:02

Добрый день, недавно проходил собеседование в одной организации - прислали задание - есть строка, состоящая из строчных/прописных букв английского и русского алфавитов, а так же цифр.
Необходимо отсортировать эту строку так: сначала заглавные буквы в алфавитном
порядке, затем цифры по порядку ("0"-первый),потом строчные буквы в алфавитном
порядке.Строка не содержит пробелов. При алфавитной сортировке русский
стоит последним.
Результат: англ.загл буквы, русские загл. буквы, цифры, англ.строчные буквы,
русские строчные буквы.

PS Задачу решил минут за 15. Через какое-то время опишу свой алгоритм.

Re: Задачка с собеседования
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005	Влад Колосов 11.07.11 14:46:42 Создаем четыре курсора , читаем из файла посимвольно. Пишем в каждый из курсоров, после окончания 4 вставки в результирующий набор с ордером по алфавиту. ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить.

Re: Задачка с собеседования

Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005

Влад Колосов

11.07.11 14:46:42

Создаем четыре курсора , читаем из файла посимвольно. Пишем в каждый из курсоров, после окончания 4 вставки в результирующий набор с ордером по алфавиту.

------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.

Re: Задачка с собеседования
Goodwin Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006	Goodwin 11.07.11 14:47:53 Свалить всё в курсор в полями "порядок группы", "символ" и проиндексировать. Ну или пузырьком, через свою функцию сравнения А если процессор бесплатный, то s='qwQWE123qweячсэ' out('A', 'Z') out('А', 'Я') out('0', '9') out('a', 'z') out('а', 'я') function out(a, b) for c=asc(a) to asc(b) ??chrt(s, chrt(s, chr(c), ''), '') endfor ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер

Re: Задачка с собеседования

Goodwin

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006

Goodwin

11.07.11 14:47:53

Свалить всё в курсор в полями "порядок группы", "символ" и проиндексировать.
Ну или пузырьком, через свою функцию сравнения

А если процессор бесплатный, то


s='qwQWE123qweячсэ'

out('A', 'Z')
out('А', 'Я')
out('0', '9')
out('a', 'z')
out('а', 'я')

function out(a, b)
for c=asc(a) to asc(b)
    ??chrt(s, chrt(s, chr(c), ''), '')
endfor

------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер

Re: Задачка с собеседования
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005	Влад Колосов 11.07.11 15:06:45 Функция-то много проходов будет делать по строке. Фокус в том, чтобы сделать это за один проход. Цитата: А если процессор бесплатный, то Это да. ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. Исправлено 1 раз(а). Последнее : Влад Колосов, 11.07.11 15:07

Re: Задачка с собеседования

Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005

Влад Колосов

11.07.11 15:06:45

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

Цитата:
А если процессор бесплатный, то

Это да.

------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.

Исправлено 1 раз(а). Последнее : Влад Колосов, 11.07.11 15:07

Re: Задачка с собеседования
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006	leonid 11.07.11 16:07:18 Свалить в один курсор побуквенно, а затем index on iif(between(chr(bukva),0x41,0x5A),"1",iif(between(chr(bukva),0xC0,0xDF),"2",iif(between(chr(bukva),0x30,0x39),"3",iif(between(chr(bukva),0x61,0x7A),"4","5")+bukva tag tmp

Re: Задачка с собеседования
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005	Extortioner 11.07.11 17:22:58 Можно проще и быстрее Как подсказка - процедура сортировки не используется. Исправлено 1 раз(а). Последнее : Extortioner, 11.07.11 17:23

Re: Задачка с собеседования
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005	Влад Колосов 11.07.11 18:10:50 Можно еще посимвольным перебором заполнить массив с вычислением смещения для каждой подгруппы. Но это подход не с точки зрения программирования баз данных ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. Исправлено 2 раз(а). Последнее : Влад Колосов, 11.07.11 18:12

Re: Задачка с собеседования

Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005

Влад Колосов

11.07.11 18:10:50

Можно еще посимвольным перебором заполнить массив с вычислением смещения для каждой подгруппы. Но это подход не с точки зрения программирования баз данных

------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.

Исправлено 2 раз(а). Последнее : Влад Колосов, 11.07.11 18:12

Re: Задачка с собеседования
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005	Extortioner 11.07.11 19:28:36 Создаём массив от asc('A') до asc('я'), пробегаемся по строке и для каждого встреченного символа увеличиваем значение в массиве с индексом равным asc('Встреченный символ') на единицу. В итоге получается, что мы собрали полную статистику, то есть если, к примеру буква A встречалась в строке 5 раз то в элементе массива с индексом asc('A') будет 5. Ну, а теперь просто последовательно пять раз пробегаемся циклом по массиву сначала с ASC('A')..ASC('Z'), потом с ASC('А')..ASC('Я') и т.д., при этом выводим каждый раз столько раз встреченный символ сколько раз он встречается в строке. То есть по сути обходимся без сортировки в привычном понимании этого слова

Re: Задачка с собеседования

Extortioner
Автор

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005

Extortioner

11.07.11 19:28:36

Создаём массив от asc('A') до asc('я'), пробегаемся по строке и для каждого встреченного символа увеличиваем значение в массиве с индексом равным asc('Встреченный символ') на единицу. В итоге получается, что мы собрали полную статистику, то есть если, к примеру буква A встречалась в строке 5 раз то в элементе массива с индексом asc('A') будет 5.
Ну, а теперь просто последовательно пять раз пробегаемся циклом по массиву сначала с ASC('A')..ASC('Z'), потом с ASC('А')..ASC('Я') и т.д., при этом выводим каждый раз столько раз встреченный символ сколько раз он встречается в строке.
То есть по сути обходимся без сортировки в привычном понимании этого слова

Re: Задачка с собеседования
Goodwin Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006	Goodwin 12.07.11 08:54:37 leonid Свалить в один курсор побуквенно, а затем index on iif(between(chr(bukva),0x41,0x5A),"1", iif(between(chr(bukva),0xC0,0xDF),"2", iif(between(chr(bukva),0x30,0x39),"3", iif(between(chr(bukva),0x61,0x7A),"4","5")+bukva tag tmp Тогда уж index on icase(IsUpper(bukva), '1', IsDigit(bukva), '2', '3')+bukva tag tmp ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер

Re: Задачка с собеседования

Goodwin

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006

Goodwin

12.07.11 08:54:37

leonid
Свалить в один курсор побуквенно, а затем


index on iif(between(chr(bukva),0x41,0x5A),"1",
iif(between(chr(bukva),0xC0,0xDF),"2",
iif(between(chr(bukva),0x30,0x39),"3",
iif(between(chr(bukva),0x61,0x7A),"4","5")+bukva tag tmp

Тогда уж


index on icase(IsUpper(bukva), '1', IsDigit(bukva), '2', '3')+bukva tag tmp

------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер

Re: Задачка с собеседования
Goodwin Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006	Goodwin 12.07.11 09:59:57 Или вот: in='qwQWE123qweÿ÷ñý' out='' for i=1 to len(in) l=substr(in, i, 1) n=1 do while n<=len(out) and ord(l)>ord(substr(out, n, 1)) n=n+1 enddo out=stuff(out, n, 0, l) endfor ?out function ord(l) return iCase(IsUp(l), 0, isdi(l), 10^3, 10^6)+asc(l) ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер

Re: Задачка с собеседования

Goodwin

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006

Goodwin

12.07.11 09:59:57

Или вот:


in='qwQWE123qwe&#255;&#247;&#241;&#253;'

out=''
for i=1 to len(in)
    l=substr(in, i, 1)
    n=1
    do while n<=len(out) and ord(l)>ord(substr(out, n, 1))
        n=n+1
    enddo
    out=stuff(out, n, 0, l)
endfor
?out

function ord(l)
return iCase(IsUp(l), 0, isdi(l), 10^3, 10^6)+asc(l)

------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер

Re: Задачка с собеседования
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006	leonid 12.07.11 10:09:16 Goodwin Тогда уж index on icase(IsUpper(bukva), '1', IsDigit(bukva), '2', '3')+bukva tag tmp Я на шестерке писал, там icase нету, а чтобы isupper на русских правильно работал, у меня нужно в config.fpw прописывать русскую codepage, де еще, насколько помню, collate установить в russian. Впрочем, насчет collate не уверен, давно такого не делал.

Re: Задачка с собеседования

leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006

leonid

12.07.11 10:09:16

Goodwin
Тогда уж


index on icase(IsUpper(bukva), '1', IsDigit(bukva), '2', '3')+bukva tag tmp

Я на шестерке писал, там icase нету, а чтобы isupper на русских правильно работал, у меня нужно в config.fpw прописывать русскую codepage, де еще, насколько помню, collate установить в russian. Впрочем, насчет collate не уверен, давно такого не делал.

Re: Задачка с собеседования
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002	Igor Korolyov 12.07.11 13:39:04 Да, Collate нужен в RUSSIAN, иначе пара буковок "вывалится" - в русском это Ё, а в других славянских ещё и их "специфические" буковки. CP=1251 это очевидно, иначе и варианты с chr не покатят (там другие диапазоны кодов у кириллицы). А Collate в 9-ке можно не "дёргая" прямо в INDEX ON прописать. Варианты с массивами и там паче с их ручными сортировками - они уж очень "нефоксовые" - хотя чисто как "универсальные алгоритмы" они гораздо больше подходят ------------------ WBR, Igor

Re: Задачка с собеседования

Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002

Igor Korolyov

12.07.11 13:39:04

Да, Collate нужен в RUSSIAN, иначе пара буковок "вывалится" - в русском это Ё, а в других славянских ещё и их "специфические" буковки. CP=1251 это очевидно, иначе и варианты с chr не покатят (там другие диапазоны кодов у кириллицы). А Collate в 9-ке можно не "дёргая" прямо в INDEX ON прописать.
Варианты с массивами и там паче с их ручными сортировками - они уж очень "нефоксовые" - хотя чисто как "универсальные алгоритмы" они гораздо больше подходят

------------------
WBR, Igor

:: Список Форумов•Список тем•Поиск•Войти

Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 5 (Гостей: 5)