Comments 44
А вот менее эффективное, но довольно очевидное решение задачи про первый неповторяющийся символ:
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к за участие.
Очень многое зависит от того на какого рекрута вы попадете, это как в американском посольстве.
8к в Нью-Йорке — это ж вообще копейки, там обычно свежим бакалаврам столько (если не больше) дают =)
Это я осознал когда прошла эйфория и первые месяца полтора моих собеседований :)
Но я решил что те мои пару проектов которые могут быть осуществлены в штатах мне принесут добавку к моей зарплате, ну и на хлеб с маслом хватит на год.
> Найти первый не повторяющийся символ в строке
В 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 царил в мире скриптовых языков.
Да, полностью согласен. Просто когда-то прочитав о том как работает мусоросборщик в питоне, вспомнил о нём в контексте данных задач. Вот и написал о потенциальной проблеме, которую давно решили, но я пропустил мимо ушей. Поэтому это замечательно, что можно вот так вот обсуждать интересующие тебя темы и постоянно учиться на своих ошибках. Спасибо.
Простите, а вы на какую должность-то собеседуетесь? Судя по задачкам, на junior-a, а то и на стажёра.
Напишите задачки для senior'а — вместе с удовольствием порешаем.
if delElement == self.head:
            self.head = self.head.next
            # gc в питоне удалит объект, если на него никто не ссылается
            # (reference count)
            # или же: del delElement - что скажут знатоки?
            return True

Del удаляет переменную из области видимости, что так или иначе произойдет при завершении функции.

И кстати Python умеет справляться с циклическими ссылками.
Маленький совет. Если уж называть переменные по-английски целиком, то грамотно. На собеседовании коробит. Например, цикл — cycle, а никак не cicle.
Прошу прощения. Смесь какая-то получилось, думал про cycle и circle…
А сейчас подумал, что вообще надо было её loop'ом обозвать и не мучаться.
По поводу первого не повторяющегося символа. Не уверен, что самое быстрое решение, но зато короткое и элегантное.

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
Еще короче:
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К символов оно, конечно, медленнее. Ну вот тогда оптимизация:

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 в худшем случае.
Как алгоритм O(n^2) может быть быстрее O(n)? Для малых значений n — может быть, но для больших же… Можете оценить сложность алгоритма через n и k — число символов в строке и размер алфавита? Может в этом кроется ответ?
После оптимизации оно уже не квадратичное. Я сравнивал для случайных строк длинной 1М и 10М. Вот так генерировал тестовую строку:

test_line = ''.join(random.choice(string.ascii_letters + string.digits) for x in range(N))
ээ, а разве 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 нет практической ценности?
Абсолютно, если мы говорим о питоне. Мне кажется, что лучше использовать стандартные питоновские list и tuples вместо такой-вот дурацкой конструкции. Как минимум потому, что это не Си-шное число и пойнтер, а целый объект класса, который сжерает в сотни раз больше места. Памяти как-то жалко. Поэтому ДА, практической ценности от LinkedList в такой реализации в питоне нету.
Есть такие операции, как вставка и перемещение диапазона объектов. Боюсь что на list'ах эти операции могут съесть больше памяти, чем оверхед объектов в LinkedList, и уж точно сожрут больше процессорного времени.
Если вы чем-то не пользуетесь, то это еще не значит, что в этом нет ценности.
Тогда уж проще реализовать LinkedLists в чистом Си и вызывать функции из питона — прирост производительности и экономия памяти.
Не могли бы вы в начале или в конце текста сделать ссылки на предыдущие части статьи?
Прошло почти два месяца, чем все закончилось и будет ли четвертая часть повествования?
Only those users with full accounts are able to leave comments. Log in, please.