Answer two coding questions (SQL and DP)
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Solve the following two coding tasks.
## Problem A (SQL)
You are given a table:
**Employee(id INT, salary INT)**
Write a query that returns the **second highest distinct salary** in the company.
- If there is no second distinct salary, return `NULL`.
## Problem B (Dynamic Programming on strings)
Given a string `s` (lowercase English letters), compute the **number of distinct non-empty palindromic subsequences** of `s`.
Requirements:
- Return the count modulo `1_000_000_007`.
- Subsequences are formed by deleting zero or more characters without reordering.
- Two subsequences are considered different if their resulting strings differ.
Constraints (typical):
- `1 <= len(s) <= 1000`
Quick Answer: This multi-part question evaluates SQL query skills (handling distinct values, aggregation and edge-case NULL results) and algorithmic proficiency in dynamic programming on strings, specifically counting distinct palindromic subsequences under modular arithmetic.
Second Highest Distinct Salary
Given salary values, return the second highest distinct salary, or None if it does not exist.
Constraints
- Distinct salaries matter
Examples
Input: ([100, 200, 300],)
Expected Output: 200
Input: ([100, 100],)
Expected Output: None
Input: ([],)
Expected Output: None
Input: ([5, 5, 3, 4],)
Expected Output: 4
Hints
- Sort unique salaries descending.
Count Distinct Palindromic Subsequences
Return the number of distinct non-empty palindromic subsequences modulo 1,000,000,007.
Constraints
- s contains lowercase English letters
Examples
Input: ('bccb',)
Expected Output: 6
Input: ('aaa',)
Expected Output: 3
Input: ('abcd',)
Expected Output: 4
Input: ('aba',)
Expected Output: 4
Hints
- Use interval DP and handle duplicate boundary characters carefully.