Autocoder

American Express coding round questions with solutions

Last updated 2026-11-19

American Express technology assessments are commonly described as coding problems of medium difficulty with some SQL, hosted on a platform such as HackerEarth or HackerRank. The company's own hackathon, CodeStreet, also runs on HackerEarth. The ten problems below are practice in that style: sequences, trees, backtracking, DP and one SQL problem, with two MCQs on probability and complexity.

They are not recalled questions. Each answer has the approach, the complexity, a common mistake and runnable Python and Java. For interview rounds, see American Express interview questions.

StyleMedium sequences, trees, backtracking, DP, SQL
Languages herePython, Java, SQL
Problems8 coding, 2 MCQ-style
LevelMedium to hard

How to approach this set

Medium problems reward spotting the pattern quickly: hashing for sequences, DFS with undo for backtracking, a table for DP. After reading a problem, spend two minutes naming the pattern and the complexity before you code.

Practise explaining the solution aloud as you write, since follow-up interviews often revisit the same problems. See dynamic programming interview questions and how to crack an online assessment.

American Express coding round questions with solutions: questions with worked answers

  1. 1

    Longest consecutive sequence: the length of the longest run of consecutive integers in an unsorted array, in O(n).

    medium

    Put all numbers in a set. Only start counting from a number x where x - 1 is not in the set, since that is the start of a run, then walk x + 1, x + 2 and so on while present. Each number is visited at most twice overall, so time is O(n), space O(n). Sorting is O(n log n). The mistake is starting a count from every element, which turns it into O(n^2) on a long run.

    python
    def longest_consecutive(a):
        s, best = set(a), 0
        for x in s:
            if x - 1 not in s:
                y = x
                while y + 1 in s:
                    y += 1
                best = max(best, y - x + 1)
        return best
    java
    import java.util.*;
    class Solution {
        static int longestConsecutive(int[] a) {
            Set<Integer> s = new HashSet<>();
            for (int x : a) s.add(x);
            int best = 0;
            for (int x : s) {
                if (!s.contains(x - 1)) {
                    int y = x;
                    while (s.contains(y + 1)) y++;
                    best = Math.max(best, y - x + 1);
                }
            }
            return best;
        }
    }
  2. 2

    K-th smallest element in a binary search tree.

    medium

    An in-order traversal of a BST visits values in ascending order, so stop at the k-th visited node. Do it iteratively with a stack to stop early. Time O(h + k), space O(h). If the tree is modified often and k-th queries are frequent, store subtree sizes in each node to answer in O(h). Mistake: collecting the whole traversal into a list when an early exit is possible.

    python
    def kth_smallest(root, k):
        st, cur = [], root
        while st or cur:
            while cur:
                st.append(cur)
                cur = cur.left
            cur = st.pop()
            k -= 1
            if k == 0:
                return cur.val
            cur = cur.right
    java
    import java.util.*;
    class Solution {
        static class TreeNode { int val; TreeNode left, right; }
        static int kthSmallest(TreeNode root, int k) {
            Deque<TreeNode> st = new ArrayDeque<>();
            TreeNode cur = root;
            while (cur != null || !st.isEmpty()) {
                while (cur != null) { st.push(cur); cur = cur.left; }
                cur = st.pop();
                if (--k == 0) return cur.val;
                cur = cur.right;
            }
            return -1;
        }
    }
  3. 3

    Word search: does a word exist in a grid by moving to adjacent cells, using each cell at most once?

    medium

    Backtracking DFS from each cell matching the first letter. Mark the current cell as used (overwrite it), try the four neighbours for the next letter, then restore the cell before returning. Time O(R x C x 3^L) for word length L, space O(L). The classic bugs are forgetting to restore the cell, which corrupts later searches, and not marking it, which lets one cell be used twice.

    python
    def exist(board, word):
        R, C = len(board), len(board[0])
        def dfs(i, j, k):
            if k == len(word):
                return True
            if not (0 <= i < R and 0 <= j < C) or board[i][j] != word[k]:
                return False
            ch, board[i][j] = board[i][j], '#'
            ok = any(dfs(i + a, j + b, k + 1) for a, b in ((1,0),(-1,0),(0,1),(0,-1)))
            board[i][j] = ch
            return ok
        return any(dfs(i, j, 0) for i in range(R) for j in range(C))
    java
    class Solution {
        static boolean exist(char[][] b, String w) {
            for (int i = 0; i < b.length; i++)
                for (int j = 0; j < b[0].length; j++)
                    if (dfs(b, w, i, j, 0)) return true;
            return false;
        }
        static boolean dfs(char[][] b, String w, int i, int j, int k) {
            if (k == w.length()) return true;
            if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] != w.charAt(k)) return false;
            char ch = b[i][j];
            b[i][j] = '#';
            boolean ok = dfs(b, w, i + 1, j, k + 1) || dfs(b, w, i - 1, j, k + 1)
                      || dfs(b, w, i, j + 1, k + 1) || dfs(b, w, i, j - 1, k + 1);
            b[i][j] = ch;
            return ok;
        }
    }
  4. 4

    Generate all subsets of a list of distinct integers.

    medium

    Each element is either included or not, giving 2^n subsets. Iteratively, start with [[]] and for each number append a copy of every existing subset with that number added. Time O(n x 2^n), space O(n x 2^n) for the output. The recursion version builds a path and records it at every node. A bitmask loop from 0 to 2^n - 1 also works for n up to about 20. Mistake: mutating the list you are iterating over.

    python
    def subsets(a):
        out = [[]]
        for x in a:
            out += [s + [x] for s in out]
        return out
    java
    import java.util.*;
    class Solution {
        static List<List<Integer>> subsets(int[] a) {
            List<List<Integer>> out = new ArrayList<>();
            out.add(new ArrayList<>());
            for (int x : a) {
                int n = out.size();
                for (int i = 0; i < n; i++) {
                    List<Integer> s = new ArrayList<>(out.get(i));
                    s.add(x);
                    out.add(s);
                }
            }
            return out;
        }
    }
  5. 5

    Decode ways: a string of digits maps A=1 to Z=26. Count the ways to decode it.

    medium

    dp[i] is the number of ways to decode the first i digits. A single digit 1 to 9 adds dp[i-1]; a two-digit number from 10 to 26 adds dp[i-2]. A leading zero contributes nothing alone, and a lone '0' that cannot pair with the previous digit makes the answer 0. Time O(n), space O(1) with rolling values. The common error is treating '0' as a valid single digit, or '06' as a valid two-digit code.

    python
    def num_decodings(s):
        if not s or s[0] == '0':
            return 0
        a, b = 1, 1
        for i in range(1, len(s)):
            c = 0
            if s[i] != '0':
                c += b
            if 10 <= int(s[i - 1:i + 1]) <= 26:
                c += a
            a, b = b, c
        return b
    java
    class Solution {
        static int numDecodings(String s) {
            if (s.isEmpty() || s.charAt(0) == '0') return 0;
            int a = 1, b = 1;
            for (int i = 1; i < s.length(); i++) {
                int c = 0;
                if (s.charAt(i) != '0') c += b;
                int two = Integer.parseInt(s.substring(i - 1, i + 1));
                if (two >= 10 && two <= 26) c += a;
                a = b; b = c;
            }
            return b;
        }
    }
  6. 6

    Edit distance between two strings with insert, delete and replace operations.

    hard

    dp[i][j] is the minimum edits to turn the first i characters of a into the first j of b. If the characters match, dp[i][j] = dp[i-1][j-1]; otherwise it is 1 plus the minimum of replace (dp[i-1][j-1]), delete (dp[i-1][j]) and insert (dp[i][j-1]). The base cases are dp[i][0] = i and dp[0][j] = j. Time O(mn), space O(mn), reducible to O(n). Forgetting the base cases is the typical failure.

    python
    def edit_distance(a, b):
        m, n = len(a), len(b)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1): dp[i][0] = i
        for j in range(n + 1): dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]
    java
    class Solution {
        static int editDistance(String a, String b) {
            int m = a.length(), n = b.length();
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 0; i <= m; i++) dp[i][0] = i;
            for (int j = 0; j <= n; j++) dp[0][j] = j;
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1) ? dp[i - 1][j - 1]
                        : 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
            return dp[m][n];
        }
    }
  7. 7

    Meeting rooms II: the minimum number of rooms needed for a set of meeting intervals.

    medium

    Sort the start times and end times separately and sweep with two pointers: if the next start is before the earliest unfinished end, a new room is needed; otherwise a room is freed. The maximum number of rooms in use is the answer. Alternatively, sort by start and keep a min-heap of end times. Time O(n log n), space O(n). Mistake: treating a meeting that starts exactly when another ends as overlapping; use start >= end to reuse the room.

    python
    def min_rooms(iv):
        s = sorted(x[0] for x in iv)
        e = sorted(x[1] for x in iv)
        rooms = best = j = 0
        for i in range(len(s)):
            while e[j] <= s[i]:
                j += 1
                rooms -= 1
            rooms += 1
            best = max(best, rooms)
        return best
    java
    import java.util.*;
    class Solution {
        static int minRooms(int[][] iv) {
            int n = iv.length;
            int[] s = new int[n], e = new int[n];
            for (int i = 0; i < n; i++) { s[i] = iv[i][0]; e[i] = iv[i][1]; }
            Arrays.sort(s); Arrays.sort(e);
            int rooms = 0, best = 0, j = 0;
            for (int i = 0; i < n; i++) {
                while (e[j] <= s[i]) { j++; rooms--; }
                rooms++;
                best = Math.max(best, rooms);
            }
            return best;
        }
    }
  8. 8

    SQL: find customers who made purchases on at least three consecutive days.

    hard

    Remove duplicate dates per customer, number each customer's dates in order, and subtract the row number (as days) from the date: consecutive dates give the same result. Group by customer and that value and keep groups with at least three rows. This is the 'gaps and islands' technique. Mistake: forgetting to de-duplicate, so two purchases on one day inflate the count.

    sql
    SELECT DISTINCT customer_id
    FROM (
      SELECT customer_id, d,
             d - (ROW_NUMBER() OVER (PARTITION BY customer_id ORDER BY d)) * INTERVAL '1 day' AS grp
      FROM (SELECT DISTINCT customer_id, txn_date::date AS d FROM Transactions) x
    ) y
    GROUP BY customer_id, grp
    HAVING COUNT(*) >= 3;
  9. 9

    Probability MCQ: 1% of transactions are fraudulent. A model flags 90% of fraud and also wrongly flags 5% of genuine transactions. If a transaction is flagged, what is the probability it is fraud?

    hard

    Use Bayes. Flagged and fraud: 0.01 x 0.90 = 0.009. Flagged and genuine: 0.99 x 0.05 = 0.0495. So P(fraud | flagged) = 0.009 / (0.009 + 0.0495) = 0.009 / 0.0585, about 15.4%. Despite a 90% detection rate, most flags are false alarms because genuine transactions vastly outnumber fraud. The trap answer is 90%.

  10. 10

    CS MCQ: what are the time and space complexity of generating all subsets of an n-element set and storing them?

    medium

    There are 2^n subsets and the average subset has n/2 elements, so both time and the output size are O(n x 2^n). Counting only the number of subsets is 2^n. If the question asks for auxiliary space beyond the output, a recursive generator needs only O(n) for the recursion path. Read whether the option counts the output.

Frequently asked questions

How hard is the American Express coding test?

It is commonly described as medium difficulty, with some SQL. This set is written at that level.

Is the hackathon related to hiring?

American Express runs CodeStreet on HackerEarth; see the hiring page for the sourced details and check the company site for how it connects to hiring.

Does the test have a probability section?

Some data-oriented roles are reported to include probability or statistics questions. Practise Bayes and expectation.

Are these the real questions?

No. They are original practice problems in the style of the topics the round commonly covers.

Related guides

More in Company Interview Questions

See all in this section