Recently Posted Interviews

Was asked to solve the following binary tree question

Problem Statement:

Given a binary tree where each node contains either an operator (+, -, *, /) or an integer. The tree represents a mathematical expression where each leaf node is an integer and each internal node is an operator that combines the values of its left and right subtrees. Evaluate the expression represented by the binary tree to return an integer value.

Example:

Input:
        *
       / \
      +   5
     / \
    3   2

Output: 25

Input:
        -
       / \
      *   4
     / \
    6   3

Output: 14

I was asked a problem which was a variation of the LC combination-sum problem https://leetcode.com/problems/combination-sum/description/

Problem:

A customer at a restaurant wants to order appetizers that total a specific amount. Given a menu with item prices, find and return all possible combinations of items that sum to the target amount. If no combination is found, return an empty list.

Example Menu:

• Nachos — $3.50

• Spring Rolls — $2.80

• Chicken Wings — $4.10

• Fries — $3.20

Example #1:

Input: possible_order(6.70)
Output: [["Nachos", "Fries"], ["Spring Rolls", "Chicken Wings"]]

Example #2:

Input: possible_order(9.50)
Output: [["Nachos", "Chicken Wings", "Fries"], ["Nachos", "Spring Rolls", "Chicken Wings"], ["Spring Rolls", "Fries", "Chicken Wings"]]

Solution:

def possible_orders(target: float):
    menu = [
        ("Nachos", 3.50),
        ("Spring Rolls", 2.80),
        ("Chicken Wings", 4.10),
        ("Fries", 3.20)
    ]
    
    result = []

    # backtrack through combinations
    def backtrack(current_combination, start, current_sum):
        if current_sum == target:
            result.append(list(current_combination)) # found a valid combination
            return
        if current_sum > target:
            return

        for i in range(start, len(menu)):
            item, price = menu[i]
            current_combination.append(item)
            backtrack(current_combination, i, current_sum + price)
            current_combination.pop()  # backtrack
    
    backtrack([], 0, 0)

    return result

print(possible_orders(9.50))  # two combinations
print(possible_orders(5.30))  # one combination
print(possible_orders(10.50)) # no combination

Only had the first coding round of 45 mins where the interviewer asked to implement the "Connect Four" game, where two players alternately drop colored discs into a 7-column, 6-row grid. The goal is to be the first player to arrange four of their discs consecutively in a row, either horizontally, vertically, or diagonally.

I didn't do great and the interviewer wasn't much help when I got stuck.

The first 5 mins were introductions then we spent another 10-15 minutes talking about my past experiences and project. Then we jumped into a leetcode type coding problem.

Behavioral Question:

Tell me about a project you lead in the past.

Technical Problem:

Given an array of unsorted integers, determine the length of the longest sequence of consecutive integers that can be formed. The solution must run in linear time complexity.

Input: [100, 4, 200, 1, 3, 2]
Output: 4 # longest consecutive sequence is [1, 2, 3, 4]

Input: [-1, -2, 0, 1, 2, 3]
Output: 5 # sequence [-2, -1, 0, 1, 2, 3].

Input: [0, 0, 1, 2, 2, 3, 4, 5]
Output: 6 # sequence [0, 1, 2, 3, 4, 5]

Solution:

public class Solution
{
    public int LongestConsecutive(int[] nums)
    {
        var numSet = new HashSet<int>(nums);
        int longestStreak = 0;

        foreach (int num in numSet)
        {
            if (!numSet.Contains(num - 1))
            {
                int currentStreak = 1;
                while (numSet.Contains(num + currentStreak))
                {
                    currentStreak++;
                }
                longestStreak = Math.Max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }

    public static void Main()
    {
        var solution = new Solution();
        int[] nums = { 100, 4, 200, 1, 3, 2 };
        Console.WriteLine(solution.LongestConsecutive(nums));  // Outputs 4
    }
}

Both time and space complexity is O(n)

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)"