Cracking Google’s Software Engineer Interview: Tips on Dynamic Programming & Hidden Test Cases

Software Engineering
, ,
1

google | Software Engineer | Interview Experience

Interview Date: Not specified
Result: Not specified
Difficulty: Not specified

Interview Process

The interview consisted of two questions, both of which included hidden test cases. Candidates were advised to pay attention to edge cases.

Technical Questions

  1. Array, String

    • Given an integer array points of length N and a string tokens of length N, where each character in tokens is either ‘T’ (indicating the presence of a token) or ‘E’ (indicating an empty cell), calculate the total score where each token on the K-th cell adds points equal to points[K]. Additionally, add 1 point for every pair of adjacent tokens.
      • Input:
        • Integer array points of length N.
        • String tokens of length N containing characters ‘T’ and ‘E’.
      • Output: An integer representing the total score.
      • Examples:
        • Input: points = [3, 4, 5, 2, 3], tokens = "TEETT" → Output: 9
        • Input: points = [3, 2, 1, 2, 2], tokens = "ETTTE" → Output: 7
        • Input: points = [2, 2, 2, 2], tokens = "TTTT" → Output: 11

  2. Dynamic Programming, Combinatorics

    • Consider all codes made of four digits (0-9). How many of them have a sum of digits equal to S?
      • Input: An integer S, in the range [0, 36].
      • Output: An integer representing the number of four-digit codes whose sum of digits is equal to S.
      • Examples:
        • Input: S = 35 → Output: 4
        • Input: S = 4 → Output: 35
        • Input: S = 2 → Output: 10

Tips & Insights

Candidates should focus on edge cases and hidden test cases during problem-solving.