Meta Interviews · 5

Had to solve two leetcode questions in 45 minutes, one easy and the other hard difficulty. Didn't make it to the next round.

Question #1:

Largest common substring: Given two strings, s1 and s2, find the length of the largest substring that is common between the two strings.

Input:
s1 = "hello"
s2 = "yellow"

Output: 2 # common substring is "llo"

Questions #2:

Minimum remove to make valid parentheses: given a string s consisting of lowercase english characters and parentheses ( and ), remove the minimum number of parentheses to make the string valid.

Input:
s = "(a(b(c)d)"

Output:
"a(b(c)d)"

Jumped straight into questions, was given the valid palindrome leetcode problems.

Question: Valid Palindrome II

Given a string s, determine if it can form a palindrome by removing at most one character. Return true if it can, and false otherwise.

Input: "abca"
Output: true  removing 'b' results in the palindrome "aca"

Input: "abcdef"
Output: false

Follow-up question was the valid palindrome III problem:

Given a string s and an integer k, determine if the string is a K-Palindrome. A string is considered a K-Palindrome if it can be transformed into a palindrome by removing no more than k characters

Input: s = "aebcbda", k = 1
Output: true

Input: s = "abcdef", k = 1
Ouput: false

Given a string, remove the minimum number of parentheses to make the string valid.

Examples:

Input: "a)b(c)d"

Output: ab(c)d

Python solution:

def min_remove_to_make_valid(s: str) -> str:
    stack = []
    to_remove = set()
    
    # identify parentheses to remove
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                to_remove.add(i)
    
    # add remaining unmatched '(' indices to to_remove
    to_remove.update(stack)
    
    # build the result string without the indices in to_remove
    result = []
    for i, char in enumerate(s):
        if i not in to_remove:
            result.append(char)
    
    return ''.join(result)


s = "(a(b(c)d)"
print(min_remove_to_make_valid(s))  # outputs => "a(b(c)d)"

Online multiple-choice assessment covering CS fundamentals.

This round was a coding challenge over Zoom. Was asked to find the longest increasing sequence in an array.

Problem:

Find the longest increasing subsequence (LIS) from an array of integers.

Example:

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: [2, 3, 7, 101]

Input: [0, 1, 0, 3, 2, 3]
Output: [0, 1, 2, 3]

Was asked to implement a class that reads 4k characters at a time from stdin and stores it in a buffer.

Was given the leetcode meeting room problem in this round. The interviewer didn’t interact much during the interview so the experience wasn't great.

Problem Statement:

Given a list of intervals where each interval represents the start and end time of a meeting, determine the minimum number of meeting rooms required to accommodate all meetings without overlap.

Examples:

Input: meetings = [[0, 30], [5, 10], [15, 20]]

Output: 2

Input: meetings = [[1, 4], [2, 3], [3, 6], [5, 8], [7, 9]]

Output: 3

Can be solved using two pointer or min-heap

Solution:

def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    # Separate and sort the start and end times
    start_times = sorted([interval[0] for interval in intervals])
    end_times = sorted([interval[1] for interval in intervals])

    # Pointers for start and end times
    start_pointer = end_pointer = 0
    used_rooms = 0
    max_rooms = 0

    # Iterate over all the meetings by start time
    while start_pointer < len(intervals):
        # If a meeting starts before the earliest ending one finishes
        if start_times[start_pointer] < end_times[end_pointer]:
            used_rooms += 1
            start_pointer += 1
        else:
            # Meeting room freed up
            used_rooms -= 1
            end_pointer += 1

        # Track maximum rooms in use
        max_rooms = max(max_rooms, used_rooms)

    return max_rooms

Time Complexity: O(nlog⁡n), because we still need to sort the start and end times.

Space Complexity: O(n), for storing start and end times separately.