02.06.2017 10:06
SpiceIT 5 1600 Источник
Эту неделю завершаем подборкой задач и вопросов, которые часто дают на собеседованиях в Facebook. Задачи выбрали разных уровней сложности от «Easy» до «Hard». Условие снова оставили на английском языке. Варианты решений прикрепим в комментарии через неделю. Good luck!

Вопросы:

1. Вы хотите запустить анимацию через полсекунды после нажатия пользователем кнопки. Какой способ сделать это будет лучшим?

2. Приложение для обмена фотографиями отображает системное уведомление, когда пользователь получает фотографию. Ваше приложение должно отображать фотографию, когда пользователь удаляет уведомление. Какое из следующих действий вам необходимо связать с объектом Notification, который вы передаете в Notification Manager?

Задачи:

1.
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.


2.
Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?


3.
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
Поделиться с друзьями
-->

Комментарии (5)


  1. nickolaym
    02.06.2017 15:52
    #10247400

    Первая задача — это ровно то, что делают алгоритмы std::fill + std::remove.
    Не буду спойлерить, и так уже достаточно сказал.


  1. nickolaym
    02.06.2017 16:53
    #10247538

    Вторая задача.


    Пусть функция S(i,j) = sum(nums[i:j]) — сумма элементов на полуинтервале.
    Мы решаем уравнение S(i,j)=k, i<j, max(j-i).


    Мысленно построим функцию s(i) = sum(nums[0:i]) — сумму первых i элементов.
    Тогда S(i,j) = s(j)-s(i).


    Уравнение приобретает такой вид:
    s(i) + k = s(j), i<j, max(j-i).


    Построим хеш-таблицу h[sj] = max(j | s(j) == sj)
    Это делается так:


    • создаём пустую таблицу
    • для каждого j подряд
      • находим sj = s(j)
      • перезаписываем h[sj] = j.

    Теперь поехали решать уравнение.
    Для каждого i подряд находим


    • si = s(i)
    • sj = si + k
    • j = h[sj], если оно, конечно, есть
    • ij = j-i
    • запоминаем (i,j) для максимума ij.

    Время работы — от линейного (если нам повезло с хеш-таблицей) до логлинейного (если вместо хешей будем использовать двоичный поиск) или квадратного (если совсем не повезло с хешами).


    1. nickolaym
      02.06.2017 17:24
      #10247616

      На питончике


      def sums(ns, right):
  # sums(ns, False) = [ sum(ns[0:i]) for i in range(0,len(ns)+0) ]
  # sums(ns, True ) = [ sum(ns[0:j]) for j in range(1,len(ns)+1) ]
  s = 0
  for n in ns:
    if not right: yield s
    s += n
    if right: yield s

def findij(ns, k):
  hs = { sj:j for j,sj in enumerate(sums(ns,True),1) }
  return max((hs.get(si+k, 0)-i) for i,si in enumerate(sums(ns,False),0))

print findij([1, -1, 5, -2, 3], 3)
print findij([-2, -1, 2, 1], 1)


  1. KYKYH
    02.06.2017 17:30
    #10247630
    +1

    Ваше приложение должно отображать фотографию, когда пользователь удаляет уведомление.


    Когда пользователь удаляет уведомление — уведомление должно удалиться. Любые другие действия просто морально недопустимы. Я как пользователь немедленно удалю приложение, которое делает такие фокусы. Как лид, потребую изменения ТЗ. Как руководитель отдела разработки, подниму вопрос о некомпетентности UX дизайнера. С собеседования я просто уйду.


  1. nickolaym
    06.06.2017 16:33
    #10251732

    В третьей задаче неочевидно, что делать в случае комбинаторного взрыва.
    Требование "вывести все результаты" может означать два варианта:


    • или тестовые данные предполагают, что результатов немного; и тогда, например, можно пожертвовать O(L*R) дополнительной памятью, где L — длина строки, R — количество результатов
    • или же ограничений нет, но нам придётся писать генератор, выводящий результаты один за другим.

    Например, мы можем выводить все перестановки длинной строки (с помощью алгоритма Кнута std::next_permutation), но вывести их все нам не хватит времени вселенной.