Meta | E4 | Phone screen | US

Round 1

Questions:

Problem Statement 1: Shortest Path in a Social Network

Given a directed social network represented as a graph, where each person is a node and a directed edge indicates that one person follows another, you need to determine the minimum number of steps required to reach a target person from a starting person. If it is not possible to reach the target, return -1.

Graph Representation: The social network is represented by a directed graph, where each key in the graph corresponds to a person, and the associated values are the people they follow. For example:

• Person 1 follows: 2, 4
• Person 2 follows: 3, 5
• Person 3 follows: 4
• Person 4 follows: 1
• Person 5 follows: (none)
• Person 6 follows: 3

Input:

1. A directed graph represented as an adjacency list, where graph[start] = {followings}.
2. A starting person A.
3. An ending person B.

Output:

• The minimum number of steps required to go from person A to person B.
• If it is not possible to reach B from A, return -1.

Example:

1. Input:
   A: 1, B: 4
   Output: 1
   (Path: 1 → 4)

2. Input:
   A: 1, B: 5
   Output: 2
   (Path: 1 → 2 → 5)

3. Input:
   A: 1, B: 6
   Output: -1
   (There is no path from 1 to 6)

Constraints:

• The graph may contain cycles.
• You may assume that the input will always be a valid graph.

Notes:

• Use breadth-first search (BFS) to explore the shortest path in the directed graph.
• Keep track of visited nodes to avoid infinite loops.

Problem 2: Valid Word Abbreviation

Valid Word Abbreviation

Problem 2.5: Wildcard Matching

Wildcard Matching

def patternMatch(word, pattern):
    if len(word) == 0 and len(pattern) == 0:
        return True
    if len(pattern) == 0:
        return False
    if len(word) == 0:
        return all(char == '*' for char in pattern)
    
    if pattern[0].isdigit():
        num = 0
        i = 0
        while i < len(pattern) and pattern[i].isdigit():
            num = num * 10 + int(pattern[i])
            i += 1
        if len(word) < num:
            return False
        return patternMatch(word[num:], pattern[i:])
    
    if pattern[0] == '*':
        return patternMatch(word[1:], pattern) or patternMatch(word, pattern[1:])
    if word[0] == pattern[0]:
        return patternMatch(word[1:], pattern[1:])
    return False

Candidate's Approach

The interview went pretty well; I solved all the questions within 35 minutes (the interviewer was 5 minutes late, and we ended on time), even though I was asked a modified version of the Valid Word Abbreviation that included Wildcard Matching, effectively combining both problems into one question. I followed the steps in the Meta preparation guide, especially focusing on the verification step.

Interviewer's Feedback

I had to wait for over a week because the interviewer took PTO and didn’t submit my feedback. Then, I received a rejection email from the recruiter without any feedback. I really didn’t expect such a poor experience from a tech giant like Meta, especially since I received positive feedback from the interviewer during the interview.

---