Amazon Online Assessment (OA) - Slowest Key

Practice here: https://leetcode.com/problems/slowest-key/

Solution and Explanation

This question asks for the key with largest duration releaseTimes[i] - releaseTimes[i - 1]. We can simple loop through each release time and calculate its difference to the previous time. If multiple characters have the same duration, we want to use the lexicographically largest.

class Solution:
  def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
      slowest_key = 'a'
      longest_duration = 0
      n = len(keysPressed)

      for i in range(n):
          pressedTime = releaseTimes[i - 1] if i > 0 else 0
          duration = releaseTimes[i] - pressedTime
          if duration == longest_duration:
              slowest_key = max(slowest_key, keysPressed[i])
          elif duration > longest_duration:
              slowest_key = keysPressed[i]
              longest_duration = duration

      return slowest_key

class Solution {
  public char slowestKey(int[] releaseTimes, String keysPressed) {
      int n = releaseTimes.length;
      char[] keys = keysPressed.toCharArray();
      char ans = 'a';
      int longestDuration = 0;
      int pressedTime;
      int duration;
      for (int i = 0; i < n; i++) {
          if (i == 0) {
              pressedTime = 0;
          } else {
              pressedTime = releaseTimes[i - 1];
          }
          duration = releaseTimes[i] - pressedTime;
          if (duration == longestDuration) {
              if (ans < keys[i]) ans = keys[i];
          } else if (duration > longestDuration) {
              ans  = keys[i];
              longestDuration = duration;
          }
      }
      return ans;
  }
}

Overview

Basic Data Structures

Basic Algorithms

Warm Up

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Interval

Two Sequences

Game Theory

0-1 Knapsack

Bitmask

Tree

Introduction

Generalized

Binary Search

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Greedy

Monotonic Stack

Line Sweep

Interval

Tree Traversal without Recursion

Composite Patterns

Math

Matrix

Classics

OA2 2021/2020

Microsoft OA

Google OA

Twitter OA

Amazon Online Assessment (OA) - Slowest Key

Solution and Explanation