How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Pinterest during technical interviews.

Solve prefix, array, and string problems | Pinterest Coding Question

Quick Overview

This set of problems evaluates proficiency in string and array algorithm design—covering prefix search, subsequence matching, and maximal-area computation from bar heights—measuring competence in algorithmic thinking, data structure usage, and time/space efficiency.

Solve prefix, array, and string problems

Company: Pinterest

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

The interview included several coding problems: 1. **First index matching a prefix**: Given a sorted array of lowercase strings such as `["a", "apple", "appz", "b"]` and a prefix such as `"ap"`, return the index of the first word that starts with the prefix. If no word matches, return `-1`. 2. **Maximum rectangle from bar heights**: Given an array of non-negative integers representing adjacent bar heights, where each bar has width `1`, return the maximum rectangular area that can be formed using one or more consecutive bars. 3. **Check ordered deletion match**: Given two strings `s` and `t`, determine whether `s` can be formed by deleting some characters from `t` without changing the order of the remaining characters.

Quick Answer: This set of problems evaluates proficiency in string and array algorithm design—covering prefix search, subsequence matching, and maximal-area computation from bar heights—measuring competence in algorithmic thinking, data structure usage, and time/space efficiency.

Part 1: First index matching a prefix

You are given a list of strings sorted in lexicographic order and a prefix string. Return the index of the first word that starts with the prefix. If no word starts with the prefix, return -1. If multiple words match, you must return the smallest index.

Constraints

0 <= len(words) <= 200000
words is sorted in non-decreasing lexicographic order
0 <= len(prefix) <= 100000
Each word contains lowercase English letters

Examples

Input: (["a", "apple", "appz", "b"], "ap")

Expected Output: 1

Explanation: "apple" is the first word that starts with "ap".

Input: (["banana"], "ban")

Expected Output: 0

Explanation: The only word matches the prefix.

Input: (["ant", "bat", "cat"], "car")

Expected Output: -1

Explanation: No word starts with "car".

Input: ([], "a")

Expected Output: -1

Explanation: An empty list has no matching index.

Input: (["a", "ab", "b"], "")

Expected Output: 0

Explanation: Every string starts with the empty prefix, so the first index is 0.

Hints

Because the array is sorted, you can search for the first position where a word is not less than the prefix.
After binary search, verify that the candidate actually starts with the prefix.

Part 2: Maximum rectangle from bar heights

You are given an array of non-negative integers where each value represents the height of a bar in a histogram. Every bar has width 1. Return the largest rectangular area that can be formed using one or more consecutive bars.

Constraints

0 <= len(heights) <= 200000
0 <= heights[i] <= 1000000000
Bars are adjacent and each bar has width 1

Examples

Input: [2, 1, 5, 6, 2, 3]

Expected Output: 10

Explanation: The best rectangle uses heights 5 and 6 with width 2, giving area 10.

Input: [2, 4]

Expected Output: 4

Explanation: The best area is max(2*2, 4*1) = 4.

Input: []

Expected Output: 0

Explanation: No bars means no rectangle.

Input: [6]

Expected Output: 6

Explanation: A single bar forms a rectangle of area 6.

Input: [0, 2, 0]

Expected Output: 2

Explanation: Only the middle bar contributes a positive area.

Hints

For each bar, imagine extending left and right until you hit a shorter bar.
A monotonic increasing stack can help compute the best area in one pass.

Part 3: Check ordered deletion match

Given two strings s and t, determine whether s can be formed by deleting some characters from t without changing the order of the remaining characters. In other words, decide whether s is a subsequence of t.

Constraints

0 <= len(s), len(t) <= 200000
Strings may contain any characters
Character comparison is case-sensitive

Examples

Input: ("ace", "abcde")

Expected Output: True

Explanation: Delete 'b' and 'd' from t to get "ace".

Input: ("aec", "abcde")

Expected Output: False

Explanation: The needed order does not appear in t.

Input: ("", "anything")

Expected Output: True

Explanation: The empty string can always be formed by deleting all characters.

Input: ("a", "")

Expected Output: False

Explanation: A non-empty string cannot be formed from an empty string.

Input: ("abc", "abc")

Expected Output: True

Explanation: No deletions are needed when the strings already match.

Hints

Walk through t from left to right while tracking how many characters of s you have matched.
If you match all of s in order, the answer is True even if t still has characters left.

Quick Overview