Search a Sorted Array of Words
Updated
Problem statement
You are given an array of strings words sorted in dictionary order, with no word repeated, and a string target. Return the index of target in words (indexes start at 0), or -1 if it is not there.
Only an exact match counts: a word that merely starts with target, or that target starts with, is not a match.
Dictionary order compares two words letter by letter. At the first position where they differ, the word with the earlier letter comes first. If one word runs out first (it is the start of the other), the shorter word comes first. For example, "in" < "inlet" < "inn".
Follow-up: can you find the answer with O(log n) string comparisons, where n is the length of words?
Function
findWord(words: String[], target: String) → intExamples
Example 1
words = ["anchor","bay","cabin","dune","ferry","grove"]target = "dune"return = 3"dune" is at index 3. A binary search looks at index 2 ("cabin", which comes before "dune"), then at index 4 ("ferry", which comes after it), then finds it at index 3.
Example 2
words = ["inlet","inn","island"]target = "in"return = -1Every word starts with "in", but none of them is exactly "in". Only an exact match counts, so the answer is -1.
Example 3
words = ["coast","cove","creek","crest"]target = "coast"return = 0"coast" is the first word, at index 0.
Constraints
1 <= words.length <= 10^41 <= words[i].length, target.length <= 20words[i]andtargetcontain only lowercase English letters.wordsis sorted in dictionary order and has no repeated word.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Closest Version DateAmazon · ONSITE INTERVIEW
- Find Unmet Users With Shared InterestsPalantir · ONSITE INTERVIEWPalantir interview questions
- Lexicographic Search SuggestionsGoogle · ONSITE INTERVIEWGoogle interview questions
- Find the First Matching Ordered EntryFigma · OAFigma interview questions
- Product Record SearchWells Fargo · OAWells Fargo interview questions
- Find the Words for Each PrefixDocuSign · PHONE SCREENDocuSign interview questions
- Longest Common PrefixKotak Mahindra Bank · PHONE SCREEN · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Roll a Weighted DieLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Bounded Word Guess SolverAtlassian · ONSITE INTERVIEWAtlassian interview questions
- Filter Pins by Excluded IDsPinterest · ONSITE INTERVIEWPinterest interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)