2 вопроса: 1 легкий; 1 Трудно.

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

Опять же, это обычное дело, и не бойтесь этого, это случается с лучшими из нас.

Они сказали, что у них есть одна неплохая проблема, которую я считаю «легкой» в этом мире технических собеседований по алгоритму / структуре данных. И с одним было довольно сложно. Я удивлен, увидев, что Amazon даже задала этот вопрос младшему разработчику, который окончил учебный курс и не имел опыта программирования.

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

Легкий

Учитывая строку, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, действительна ли входная строка.

Строка ввода действительна, если:

  1. Открытые скобки должны закрываться скобками того же типа.
  2. Открытые скобки должны быть закрыты в правильном порядке.

Обратите внимание, что пустая строка также считается допустимой.

Пример 1:

Input: "()"
Output: true

Пример 2:

Input: "()[]{}"
Output: true

Пример 3:

Input: "(]"
Output: false

Пример 4:

Input: "([)]"
Output: false

Пример 5:

Input: "{[]}"
Output: true

Жесткий

Учитывая n неотрицательных целых чисел, представляющих карту высот, где ширина каждой полосы равна 1, вычислите, сколько воды она может уловить после дождя.

Пример:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Я нарисую массив, чтобы лучше его визуализировать.

Попробуйте эти два вопроса и поделитесь со мной своими мыслями о том, что мне задают такой сложный вопрос для младшей роли!