Комментарии 44
А я бы записал последнее так:
rev_order = lambda s: ' '.join(s.split()[::-1])А вот менее эффективное, но довольно очевидное решение задачи про первый неповторяющийся символ:
Регулярка хорошо решает обратную задачу, и совсем никак не решает прямую, потому что в питоне lookbehind работает только с выражениями фиксированного размера.
Файл полностью положил на гитхаб, там тесты и сравнение производительности, если кому-то интересно.
def first_uniq(text):
reject = set(re.findall(r'(.)(?=.*?\1)', text))
iterator = (c for c in text if c not in reject)
return next(iterator, '')
Регулярка хорошо решает обратную задачу, и совсем никак не решает прямую, потому что в питоне lookbehind работает только с выражениями фиксированного размера.
Файл полностью положил на гитхаб, там тесты и сравнение производительности, если кому-то интересно.
после этой серии статей мне расхотелось работать в гугл :) интересно какая должна быть ЗП за специалиста такого уровня
На самом деле уровень такой уж и высокий, как вам показалось. Достаточно года хорошей практики, чтобы свободно шпарить «по фене».
Ну, это же только вступительные задачи. Наверняка в реальной жизни у них все гораздо интереснее.
Это один из вариантов интервью. У меня была например совсем другая история на вакансию site administrator (системный администратор) relocation в New York. Агентом выступал EPAM который мне месяца два организовывал интервью с гуглом и с собой (в общем счёте 6) и в результате еще недели две после финального интервью тянул и сказал мы получили ответ что вы не подходите. Без объяснений. Знакомый на программиста 3 раза проходил подобные интервью с гуглом три раза получал отказ, но последний раз ему сказали «You are good but not such good for us». Теперь рекрутов из гугла отправляет лесом, занимается своим проектом.
По деньгам. Мне предлагали 80к в год в Нью Йорке, учитывая что на сайте у гугла эта вакансия 105к соответственно epam забирает 25к за участие.
Очень многое зависит от того на какого рекрута вы попадете, это как в американском посольстве.
По деньгам. Мне предлагали 80к в год в Нью Йорке, учитывая что на сайте у гугла эта вакансия 105к соответственно epam забирает 25к за участие.
Очень многое зависит от того на какого рекрута вы попадете, это как в американском посольстве.
> Найти первый не повторяющийся символ в строке
В repeated[l] = 1 можно присвоить текущую позицию цикла или len(repeated), тогда второй цикл достаточно ограничить словарём, а не всей строкой.
В repeated[l] = 1 можно присвоить текущую позицию цикла или len(repeated), тогда второй цикл достаточно ограничить словарём, а не всей строкой.
Про Untouchable — заблуждение. В питоне полноценный сборщик мусора и это он уберёт (в чём не трудно убедиться). Его можно отключить:
и только тогда память потечёт.
Сборщика мусора не делали только в доисторических языках типа перла. Вот это течёт:
import gc
gc.disable()и только тогда память потечёт.
Сборщика мусора не делали только в доисторических языках типа перла. Вот это течёт:
perl -e 'while (1) {my $x; $x=\$x;}'
Вопрос очень интересный. Вот тут растолковали хорошо. Удаление по числу ссылок было единственным способом контроля памяти до 2.0 версии питона. С этой версии ввели штатную проверку на зацикленность.
По моим ощущениям, версии ниже 2.4 были не пригодны для использования в «продакшене». Там и в библиотеках было много косяков, хардкода и неряшливости. И стам питон был сыроват. Поэтому 2.3 и раньше я даже не рассматриваю; да и когда это было? почти 10 лет назад; тогда ещё perl царил в мире скриптовых языков.
Да, полностью согласен. Просто когда-то прочитав о том как работает мусоросборщик в питоне, вспомнил о нём в контексте данных задач. Вот и написал о потенциальной проблеме, которую давно решили, но я пропустил мимо ушей. Поэтому это замечательно, что можно вот так вот обсуждать интересующие тебя темы и постоянно учиться на своих ошибках. Спасибо.
НЛО прилетело и опубликовало эту надпись здесь
if delElement == self.head:
self.head = self.head.next
# gc в питоне удалит объект, если на него никто не ссылается
# (reference count)
# или же: del delElement - что скажут знатоки?
return TrueDel удаляет переменную из области видимости, что так или иначе произойдет при завершении функции.
И кстати Python умеет справляться с циклическими ссылками.
Да, так и есть. Сам нашёл эту ссылку, когда копать начал ответ на прошлый коментарий. Но всё равно спасибо.
Маленький совет. Если уж называть переменные по-английски целиком, то грамотно. На собеседовании коробит. Например, цикл — cycle, а никак не cicle.
По поводу первого не повторяющегося символа. Не уверен, что самое быстрое решение, но зато короткое и элегантное.
from itertools import groupby
def non_repeating(line):
for k, g in groupby(line):
g_list = list(g)
if len(g_list) == 1:
return g_list[0]
return None
Еще короче:
PS. Не знал про itertools.groupby, спасибо.
def non_repeating(line):
return next((k for k, g in groupby(line) if next(g,False) and not next(g,False)), None)PS. Не знал про itertools.groupby, спасибо.
И так:
import collections
def first_non_repeated_character(str):
cntr = collections.Counter(str)
return next((x for x in str if cntr[x] == 1), None)
>>> import collections
>>> def t(str):
... cntr = collections.Counter(str)
... return next((x for x in str if cntr[x] == 1), None)
...
>>> t('test')
'e'
>>> from timeit import Timer
>>> Timer("t('1 2 3 45')", "from __main__ import t").timeit()
12.961874008178711
Т.е. в 13.6 раз медленнее второго способа из текста.
Может я что-то путаю, но разве это то, что надо сделать в задании?
>>> non_repeating('test')
't'
def first_uniq2(line):
i = 0
for c in line:
i += 1
if c not in line[i:] and c not in line[:i-1]:
return c
Очень очевидное решение и при этом быстрее решения топик-стартера. На моей машине в 3 раза быстрее если нужный символ где-то в начале строки и на несколько процентов если в конце.
Оно же квадратное… Проверьте на больших строках, разница быстро станет заметна.
Да, на строках больше 10К символов оно, конечно, медленнее. Ну вот тогда оптимизация:
Если словарь символов небольшой (латинские буквы в разных регистрах + цифры), то это быстрее на любых строках. Процентов на 20 в худшем случае.
def first_uniq3(line):
i = 0
checked = set()
for c in line:
i += 1
if c in checked:
continue
if c not in line[i:]:
return c
checked.add( c )
Если словарь символов небольшой (латинские буквы в разных регистрах + цифры), то это быстрее на любых строках. Процентов на 20 в худшем случае.
ээ, а разве groupby не последовательные символы группирует? нужно ещё sorted добавить…
Вот более эффективное решение, не требующее двух проходов по строке, как у автора:
def first_unique(s):
d = {}
v = len(s)
for i, c in enumerate(s):
if c in d:
d[c] = v
else:
d[c] = i
ind = min(d.values())
return None if ind == v else s[ind]многое зависит от условий задачи. Если у нас было много не повторяющихся символов, то второй проход по строке закончится почки в самом начале. Тогда как поиск минимального элемента словаря — O(k), где k — размер словаря.
Мое второе решение отрабатывает почти также на очень длинных строках (10М) и в несколько раз быстрее на куче мелких, по 10 символов. Но это скорее всего из-за накладных расходов enumerate.
Вот если и строка и алфавит будут огромными, тогда ваше решение будет быстрее, да.
Вот если и строка и алфавит будут огромными, тогда ваше решение будет быстрее, да.
И да, я не совсем верно понял задание. :-) Мое решение вернет первый символ, сразу перед которым нет такого же символа, и сразу после которого нет такого же символа, например для 'aabbccaf' вернет 'a'. Но задание сформулировано не очень четко.
«Практической ценности в такой конструкции особенно нет»
Вы серьезно считаете, что в LinkedList нет практической ценности?
Вы серьезно считаете, что в LinkedList нет практической ценности?
Абсолютно, если мы говорим о питоне. Мне кажется, что лучше использовать стандартные питоновские list и tuples вместо такой-вот дурацкой конструкции. Как минимум потому, что это не Си-шное число и пойнтер, а целый объект класса, который сжерает в сотни раз больше места. Памяти как-то жалко. Поэтому ДА, практической ценности от LinkedList в такой реализации в питоне нету.
Не могли бы вы в начале или в конце текста сделать ссылки на предыдущие части статьи?
Прошло почти два месяца, чем все закончилось и будет ли четвертая часть повествования?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Я хочу работать в Google! Телефонное интервью (часть 3, питоноводческая)