American Express Interview Preparation and Recruitment Process

def find_duplicates(nums):
    seen = set()
    duplicates = []
    for num in nums:
        if num in seen:
            duplicates.append(num)
        else:
            seen.add(num)
    return duplicates

Relevance to Amex: Detecting duplicates is critical for fraud detection in transaction logs. For large datasets (e.g., credit card transactions), optimize with O(n) time and space. Alternative: Use sorting (O(n log n) time, O(1) space) for memory constraints.

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

Why Amex Asks: Linked lists are foundational for systems like transaction ledgers or caching mechanisms. This tests pointer manipulation and memory efficiency.

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return is_valid_bst(root.left, min_val, root.val) and is_valid_bst(root.right, root.val, max_val)

Amex Context: BSTs are used in fraud detection trees or transaction categorization. Validating structure ensures data integrity.

Key components:

1. API Gateway: Handle RESTful requests (e.g., /process-payment).

2. Authentication Service: Validate API keys/tokens (OAuth 2.0).

3. Transaction Service: Process payments, handle idempotency (to prevent duplicate charges).

4. Database: Use ACID-compliant SQL (e.g., PostgreSQL) for consistency.

5. Fraud Check: Integrate ML models to flag suspicious transactions in real-time.

Polymorphism allows objects of different classes to be treated as objects of a common superclass. Two types:

1. Compile-time (Overloading): Multiple methods with the same name but different parameters.

2. Runtime (Overriding): Subclass redefines a method from its superclass.
   Example (Python):
   

   class Payment:
       def process(self):
           pass
   
   class CreditCardPayment(Payment):
       def process(self):
           print("Processing credit card payment")
   
   class PayPalPayment(Payment):
       def process(self):
           print("Processing PayPal payment")

SELECT MAX(amount) FROM transactions 
WHERE amount < (SELECT MAX(amount) FROM transactions);

Alternative (Window Functions):

SELECT amount FROM (
    SELECT amount, DENSE_RANK() OVER (ORDER BY amount DESC) as rank
    FROM transactions
) WHERE rank = 2;

Amex Relevance: Analyzing transaction data for trends (e.g., high-value fraud patterns) is critical. Optimize for large datasets with indexes on amount.

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Amex Context: Cycle detection prevents infinite loops in transaction processing pipelines or ledger validations.

Use a Least Recently Used (LRU) cache with thread safety via locks (e.g., threading.Lock in Python).
Components:

• Hash Map: For O(1) lookups.

• Doubly Linked List: Track usage order.

• Concurrency Control: Lock during get/put operations.

def merge_sorted_arrays(arr1, arr2):
    merged = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged

Amex Relevance: Merging sorted datasets (e.g., transaction logs from multiple regions) is common in analytics.

CAP theorem states that a distributed system can only guarantee two of three properties:

• Consistency: All nodes see the same data.

• Availability: Every request receives a response.

• Partition Tolerance: System works despite network failures.

from collections import deque

class Stack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x):
        self.q1.append(x)

    def pop(self):
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        popped = self.q1.popleft()
        self.q1, self.q2 = self.q2, self.q1
        return popped

Amex Use Case: Stacks are used in parsing financial data (e.g., XML/JSON transaction files).

def longest_palindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l+1:r]
    res = ""
    for i in range(len(s)):
        odd = expand(i, i)
        even = expand(i, i+1)
        res = max(res, odd, even, key=len)
    return res

Amex Relevance: String algorithms are used in data validation (e.g., detecting anomalies in cardholder names).

Endpoints:

• GET /transactions?user_id=123&limit=10

• Authentication: JWT tokens in headers.

• Pagination: Use limit and offset.

• Response Format: JSON with fields like amount, date, merchant.

def two_sum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

Amex Use Case: Detecting pairs of transactions that sum to a suspicious amount (e.g., money laundering).

HTTPS encrypts data using TLS/SSL:

1. Handshake: Client-server agree on encryption algorithms.

2. Certificate Validation: Server sends a certificate (signed by a CA) to prove identity.

3. Key Exchange: Symmetric session keys are generated for encryption.

Steps:

1. EXPLAIN ANALYZE: Identify bottlenecks (e.g., full table scans).

2. Add Indexes: On columns in WHERE, JOIN, or ORDER BY.

3. Normalize/Denormalize: Balance read vs. write performance.

4. Cache Results: Use Redis for frequent queries.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Amex Use Case: Searching transaction logs by timestamp or amount.

Java’s GC automatically reclaims memory from unused objects. Key components:

• Heap: Divided into Young (Eden, Survivor) and Old generations.

• Algorithms: Mark-and-sweep, G1GC, ZGC.

from collections import deque
import time

class RateLimiter:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.tokens = capacity
        self.last_refill = time.time()
        self.refill_rate = refill_rate  # tokens per second

    def allow_request(self):
        now = time.time()
        time_elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + time_elapsed * self.refill_rate)
        self.last_refill = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Amex Context: Prevent abuse of customer-facing APIs (e.g., transaction history endpoints).

def reverse_string(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    return s

Amex Use Case: Data sanitization (e.g., masking card numbers by reversing before truncating).

Prevention strategies:

1. Lock Ordering: Acquire locks in a predefined order.

2. Timeout: Release locks after a threshold.

3. Deadlock Detection: Use graph algorithms to identify cycles.

def max_subarray(nums):
    max_current = max_global = nums[0]
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
    return max_global

Amex Relevance: Analyzing profit/loss trends in merchant transactions.

Components:

1. Real-Time Processing: Kafka streams for transaction events.

2. ML Models: Anomaly detection (e.g., isolation forests) for unusual amounts/locations.

3. Rules Engine: Flag transactions exceeding velocity limits (e.g., 5 purchases/minute).

4. Data Storage: Cassandra for time-series data.