Выпуск#3: ITренировка — актуальные вопросы и задачи от ведущих компаний

    Эту неделю завершаем подборкой задач и вопросов, которые часто дают на собеседованиях в 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())()"]
    ")(" -> [""]
    Spice IT Recruitment
    69.51
    ИТ специализированное кадровое агентство
    Share post

    Comments 10

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

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


        Пусть функция 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.

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

          0

          На питончике


          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)
            0

            А разве это не NP полная задача с псевдополиномиальным временем решения?

              0

              Нет, конечно.
              Задача решается за полиномиальное время очевидным способом.
              Даже тупое наивное решение:


              • перебрать все пары 0<=i<j<n, где n — длина массива — это O(n^2)
              • для каждой пары найти сумму в полуинтервале: a[i]+a[i+1]+...+a[j-1] — это O(n) каждое
              • проверить подходящие и взять среди них лучшее.

              Кубического времени — за глаза и за уши.
              А если подумать и чуть улучшить — то квадратного времени.


              Либо разменять квадратное время на линейную память и линейное время.

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


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

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


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

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

                0
                Всем привет! Надеемся, что ваши выходные прошли максимально приятно.
                В первый рабочий день этой недели публикуем по одному варианту решения для каждой задачи.
                Комментарии, как и раньше, не переводим.

                1. Простое O(N) Java решение с использованием Insert Index
                // Shift non-zero values as far forward as possible
                // Fill remaining space with zeros
                 
                public void moveZeroes(int[] nums) {
                	if (nums == null || nums.length == 0) return;    	
                 
                	int insertPos = 0;
                	for (int num: nums) {
                    	if (num != 0) nums[insertPos++] = num;
                	}    	
                 
                	while (insertPos < nums.length) {
                    	nums[insertPos++] = 0;
                	}
                }
                

                2. O(n) C++ решение с использованием unordered_map
                class Solution {
                public:
                	int maxSubArrayLen(vector<int>& nums, int k) {
                    	unordered_map<int, int> sums;
                    	int cur_sum = 0;
                    	int max_len = 0;
                    	for (int i = 0; i < nums.size(); i++) {
                        	cur_sum += nums[i];
                        	if (cur_sum == k) {
                            	max_len = i + 1;
                        	} else if (sums.find(cur_sum - k) != sums.end()) {
                            	max_len = max(max_len, i - sums[cur_sum - k]);
                        	}
                        	if (sums.find(cur_sum) == sums.end()) {
                            	sums[cur_sum] = i;
                        	}        	
                    	}
                    	return max_len;
                	}
                };
                

                3. Java BFS решение
                The idea is straightforward, with the input string s, we generate all possible states by removing one ( or ), check if they are valid, if found valid ones on the current level, put them to the final result list and we are done, otherwise, add them to a queue and carry on to the next level.
                The good thing of using BFS is that we can guarantee the number of parentheses that need to be removed is minimal, also no recursion call is needed in BFS.
                Time complexity:
                In BFS we handle the states level by level, in the worst case, we need to handle all the levels, we can analyze the time complexity level by level and add them up to get the final complexity.
                On the first level, there's only one string which is the input string s, let's say the length of it is n, to check whether it's valid, we need O(n) time. On the second level, we remove one ( or ) from the first level, so there are C(n, n-1) new strings, each of them has n-1 characters, and for each string, we need to check whether it's valid or not, thus the total time complexity on this level is (n-1) x C(n, n-1). Come to the third level, total time complexity is (n-2) x C(n, n-2), so on and so forth…
                Finally we have this formula:
                T(n) = n x C(n, n) + (n-1) x C(n, n-1) +… + 1 x C(n, 1) = n x 2^(n-1).
                Following is the Java solution:

                public class Solution {
                	public List<String> removeInvalidParentheses(String s) {
                  	List<String> res = new ArrayList<>();
                  	
                  	// sanity check
                  	if (s == null) return res;
                  	
                  	Set<String> visited = new HashSet<>();
                  	Queue<String> queue = new LinkedList<>();
                  	
                  	// initialize
                  	queue.add(s);
                  	visited.add(s);
                  	
                  	boolean found = false;
                  	
                  	while (!queue.isEmpty()) {
                    	s = queue.poll();
                    	
                    	if (isValid(s)) {
                      	// found an answer, add to the result
                     	 res.add(s);
                      	found = true;
                    	}
                  	
                    	if (found) continue;
                  	
                    	// generate all possible states
                    	for (int i = 0; i < s.length(); i++) {
                      	// we only try to remove left or right paren
                      	if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
                    	
                      	String t = s.substring(0, i) + s.substring(i + 1);
                    	
                      	if (!visited.contains(t)) {
                        	// for each state, if it's not visited, add it to the queue
                        	queue.add(t);
                        	visited.add(t);
                      	}
                    	}
                  	}
                  	
                  	return res;
                	}
                	
                	// helper function checks if string s contains valid parantheses
                	boolean isValid(String s) {
                  	int count = 0;
                	
                  	for (int i = 0; i < s.length(); i++) {
                    	char c = s.charAt(i);
                    	if (c == '(') count++;
                    	if (c == ')' && count-- == 0) return false;
                  	}
                	
                  	return count == 0;
                	}
                }
                 
                



                  0

                  Слушайте, ну это же ад — предлагать экспоненциальное по времени и памяти решение.
                  Строка, содержащая жалкие 60 скобок, выжрет терабайт памяти, прежде чем даст первый ответ.

                  0
                  первая на питоне

                  nums = [1, 1, 0, 3, 12]

                  last_zero=-1
                  i=0
                  for item in nums:
                  print(«nums={}, item={}, last_zero={}».format(nums, item, last_zero))
                  if item > 0 and last_zero < 0:
                  i+=1
                  continue
                  if item > 0 and last_zero >= 0:
                  nums[last_zero]=item
                  nums[i]=0
                  last_zero+=1
                  if item == 0 and last_zero<0:
                  last_zero = i

                  i += 1
                  print(«nums={}».format(nums))

                  Only users with full accounts can post comments. Log in, please.