Google L4 complete experience for phone screen and onsite interviews April 2025

Background

Previous Experience - 4.5 YOE in Finance Tech US based bank
HR reached out to me via linkedin for Hyderabad/Pune location

Phone Screening Round

The interviewer was from Bangalore. She was helpful and nice to talk to.

Problem

Given multiple files, we want to find the maxmimum matching prefix between any 2 files.

Sample input

String[] file1 = {"hello", "world", "abc", "xyz"};
String[] file2 = {"hello", "world", "abc", "xyz1"};
String[] file3 = {"hello", "world", "abc2", "xyz"};
String[] file4 = {"hello", "world", "abc1", "xyz2"};

Answer for this is 3, since the "hello", "world", "abc" strings match in file1 and file2

Solution

I treated files as an array of Strings for ease of implementation.

Brute Force - Compare all pairs of files and find the maximum prefix
Time complexity - for N files O(N^2) to compare each file pair and O(L*S) where L is number of lines in the file and S is average length of string. The complexity goes in order of 4.

Optimized - Instead of going through all pairs we can create a Trie structure for each String line that we encounter for a file and store the frequency along with it.
Time complexity - O(N*L) N is number of files and L is number of lines in a file.

I was asked to code the brute force which I completed in 10-15 minutes. Then I was asked to code the optimized solution as a follow up. There were some bugs but I explained the code and the complexities nicely. Below is the code that I wrote after the interview.

Code

public class FilePrefixMatching {

    private static class TrieNode {
        String value;
        int freq;
        Map<String, TrieNode> nodesMap;

        TrieNode(String value) {
            this.value = value;
            freq = 1;
            nodesMap = new HashMap<>();
        }

        TrieNode insert(String word) {
            if(nodesMap.containsKey(word)) {
                nodesMap.get(word).freq++;
                return nodesMap.get(word);
            } else {
                TrieNode node = new TrieNode(word);
                nodesMap.put(word, node);
                return node;
            }
        }
    }

    private static void dfs(TrieNode node, int level, int[] res){
        if(node == null) return;
        res[0] = Math.max(res[0], node.freq >= 2 ? level : 0);
        for(TrieNode adjNode : node.nodesMap.values()) {
            dfs(adjNode,level+1,res);
        }
    }

    private static void getMaxMatchLines(List<String[]> files) {
        TrieNode root = new TrieNode(null);
        for(int i=0;i<files.size();i++) {
            TrieNode curr = root;
            String[] file = files.get(i);
            for(int j=0;j<file.length;j++) {
                curr = curr.insert(file[j]);
            }
        }
        int[] res = new int[1];
        dfs(root,0,res); // not needed, store levels in nodes
        System.out.println(res[0]);
    }

    public static void main(String[] args) {
        String[] file1 = {"hello", "world", "abc", "xyz"};
        String[] file2 = {"hello", "world", "abc", "xyz1"};
        String[] file3 = {"hello", "world", "abc2", "xyz"};
        String[] file4 = {"hello", "world", "abc1", "xyz2"};
        getMaxMatchLines(Arrays.asList(file1,file2,file3,file4));
    }
}

HR feedback - I am decent with data structures. I can work more on the testability and the debugging aspects of the code. This is a very generic feedback I think.

Self evaluation - Hire

Onsite Round 1

The interviewer was from Seattle. He was helpful and nice to talk to.

Problem

Same as Round 3 question mentioned in the post :- https://leetcode.com/discuss/post/6495560/l3-interview-experience-by-anonymous_use-3dfv/

Implementation

I was able to code the Heap with Hashmap solution. I could not come up with the Quickselect approach.

HR feedback - The interviewer conveyed to HR that I was a bit slow for the role that they were hiring for. I challenged this point with HR since the interviewer asked me to go in as much details as I can, but they did not change the evaluation.

Self evaluation - Lean Hire

Onsite Round 2

The interviewer was from Bangalore. She was helpful and nice to talk to

Problem

Given an unweighted and undirected graph, there are some friends on some nodes and there are some cafes on some nodes. We want to find such a cafe that the maximum distance travelled by any of the friend to that cafe is minimal.

Sample input

Friends - 1,7
Cafes - 5,6

Edges - 1 2, 2 3, 3 4, 4 5, 3 6, 7 5, 7 3

Distance friend 1 has to travel to reach cafe 5 and 6 is 4 and 3

Distance friend 7 has to travel to reach cafe 5 and 6 is 3 and 2

Cafe 6 is the answer since max distance travelled by both friends is less compared to cafe 5.

If its impossible to reach a cafe then return null.
There could be cycles in graph.

Implementation

I mentioned we can use Djikstra or Floyd Warshall to solve this. The interviewer was fine with this but she gave a hint by asking how would I solve it in real life. Then I suggested the multi source BFS approach. It would be optimal compared to the other 2 approaches.

Questions like https://leetcode.com/problems/rotting-oranges/ are similar to this.

HR feedback - The interviewer conveyed to HR that I did good in the interview and the got generic feedback of I can work more on the testability of the code.

Self evaluation - Hire

Onsite Round 3

The interviewer was from Bangalore. He was kind of robotic and breaking my rhythm sometimes.

Problem

I am the team manager of an F1 team. I have different tyres with each tyre having 2 attributes where t is the 1st lap time and f is the degradation factor.
For example, for completing 3 laps with a tyre with t=1s f=2, it would take following time
lap 1 - 1 sec
lap 2 - 1x2 = 2 secs
lap 3 - 1x2x2 = 4 secs
Total time = 7 secs
It follows the pattern - t + t*f + t*f^2.. + t*f^n-1

Question 1 - lets say we use a single tyre for the entire race find out the minimum time taken to complete the race.

Question 2 - if we can change the tyres, find out the minimum time it takes to complete the race. For changing a tyre it takes C secs.

I asked for the constraints but interviewer did not share them and for the question 2 also they did not share any sample input with me.

Implementation

For question 1, we can calculate the time for each tyre for each lap and minimum total time taken by a tyre would be the answer. O(N*T) would be the complexity for this approach, where N is the number of laps and T is the types of tyres.

I also mentioned that the time taken follows the GP pattern so for each tyre we can calculate the time using the GP formula which would take logarithmic time(using binary exponentiation) for each tire. O(T*log time for GP formula).

The interviewer was satisfied with this and asked me to code the O(N*T) approach.

For question 2, I came up with a MCM DP approach using memoization. I used current lap, current tyre type and number of laps old as parameters to my recursive function. Inside the recursive function I looped over all tyres to find the min time taken by each and stored it as an answer in my 3D dp memoization table. If the tyre was changed then was adding C secs to the answer. For the 1st lap we start with each tyre and the min time taken would be computed recursively by considering all choices.

The interviewer mentioned during the interview that I missed the case when we can change the tyre and use tyre of same type. Also there was also a small bug in calculating the min time. He said it looked okay.

The above solution might be opmitised by avoiding pruning some recursive calls. I am not sure whats the most optimal approach for question 2. A backtracking solution could also exist for this. Since no constraints where shared not sure if backtracking approach is acceptable.

HR feedback - The interviewer conveyed to HR that I was a bit slow and I missed few edge cases. He also mentioned that I need more practice with DSA. I challenged this by saying that I was able to come up with the approach and I was also able to code it but the evaluation remain unchanged.

Self evaluation - Lean Hire

Overall experience

My googliness was cancelled since the feedback for onsite 1 and 3 was not so good. I think 2 LH might have caused this.

I think the level of questions asked to me where pretty doable compared to other interview experiences for this role.
The 1st question was easy medium with some changes to Trie implementation.
The 1st onsite was also easy medium, the quick select approach was not intuitive for me since I haven't practiced it.
The 2nd onsite question was a proper medium question with small BFS tricks which come with some practice on Graphs.
The 3rd question was hard for me but I was able to come up with a solution for it, and despite the negative feedback I think I did okay if not good.

I did not ask for any hints in any of the rounds since the HR discourages this.

Learnings for me are to pay attention to details since they keep the questions vague and open to interpretations, asking the right questions to interviewers, use comments for easy to implement code snippets (like some classes, getters and setters rather than actually implementing them), trying to think through all the edges cases and improving my speed. With good practice we can definitely clear all interviews.

I would be able to apply again after 12 months of cooldown according to the HR. All the best for your interviews!