Katkat
Back

Answer two coding questions (SQL and DP)

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests SQL data aggregation skills with NULL handling and algorithmic proficiency in dynamic programming to count palindromic subsequences in a string.

Part 1: SQL

Given a table user_logins with columns user_id (INT) and login_date (DATE), write a query to return the count of distinct users who have logged in on each date. If a date has no logins, ensure it does not appear in the results. If a user has multiple logins on the same day, they should be counted only once per day.

Part 2: Dynamic Programming

Given a string s, return the number of non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 10^9 + 7.

A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements. A palindromic subsequence is a subsequence that reads the same forward and backward.

Example 1:

Input: s = "bccb" Output: 6 Explanation: The palindromic subsequences are "b", "c", "b", "c", "bb", "cc", "bcb", "bccb". (Note: return count based on index positions).

Constraints:

  • 1 int:

Hints

Hint 1

For the SQL part, consider the `GROUP BY` clause combined with `COUNT(DISTINCT user_id)` to ensure unique users are counted per day.

Hint 2

For the DP part, define `dp[i][j]` as the number of palindromic subsequences in the substring `s[i:j+1]`. Consider the relationship between `dp[i+1][j]`, `dp[i][j-1]`, and `dp[i+1][j-1]` based on whether `s[i]` equals `s[j]`.

Hint 3

When `s[i] == s[j]`, the number of new subsequences formed is related to the internal palindromic subsequences plus those that can be wrapped by the new characters.

Follow-up questions

  • How would you optimize the SQL query if the `user_logins` table contained billions of rows spanning several years?
  • Can you reduce the space complexity of the DP solution from O(n^2) to O(n)?
  • How would the DP logic change if you were asked to count only distinct palindromic strings rather than subsequences by index?