Received some time ago Google Internet company The time limit for the OA invitation is 90 minutes and three questions. To be honest, OA is not considered to be the ceiling-hard kind, but the questions cover quite a wide range, and you have to consider both algorithms and implementation details. If you haven't done similar questions in advance, the time pressure will be great.
This post to restore a more realistic experience, and also share some of my personal solving strategies and pitfalls I encountered.
OA Overview
- firms: Google
- duration:90 minutes
- quantity of questions: 3 Coding questions
- difficulty feeling: Moderate to high, with data structure and string processing questions predominating
- Platform: HackerRank
- programming language: Python (multilingual support)
- bonus point: Write clean, readable code and don't forget about boundary tests!
Coding Real Questions
1. Word Pattern Matcher
Given a pattern string consisting of lowercase letters and a sentence of words, determine if the sentence follows the same pattern. Each letter in the pattern corresponds to a unique word, and each word maps to exactly one letter. Each letter in the pattern corresponds to a unique word, and each word maps to exactly one letter.
Example.
Input: pattern = "abba", s = "dog cat cat dog"
Output: True
Input: pattern = "abba", s = "dog cat cat fish"
Output: False
Constraints.
1 <= pattern.length <= 3001 <= s.length <= 3000
2. Top K Frequent Listings
Given an array of Google Search query IDs, return the top k If two IDs have the same frequency, return the smaller ID first.
Example.
Input: ids = [1,1,2,2,2,2,3], k = 2
Output: [2, 1]
Constraints.
1 <= ids.length <= 10^51 <= id <= 10^9
3. Merge Booking Intervals
Given a list of meeting time intervals where intervals[i] = [start, end], merge all overlapping intervals and return the result in sorted order.
Example.
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Constraints.
1 <= intervals.length <= 10^40 <= start < end <= 10^9
My problem solving strategy
- Do the most stable questions first: I did the first question first because hash map pattern matching is a common routine and can be written quickly.
- Save time with library functions for the second question: Python's
collections.+heapqIt was done quickly and the time complexity was steady at O(n log k). - Sorting and merging of the third question: Sort by start, then merge by linear scan, paying attention to boundary conditions.
Common Potholes
- Forget about handling empty input (especially when string splitting).
- The tie-break in the second question (in ascending order of ID when same frequency) is easy to miss.
- Merge interval questions, intervals without sorting first will be wrong.
- HackerRank's Python defaults to Python3, note that the
input().split()Read.
FAQ
Q: What if I get stuck in the middle of the program?
A: Skip to the next question, don't run out of time, and leave the last 5 minutes to come back and try to make it up.
Q: Do I need to write very complex optimizations?
A: Google OA puts more emphasis on correctness and readability, and unless the question explicitly asks for it, an O(n log n) solution is sufficient.
Q: Do boundary conditions matter?
A: Very important, when I last checked, I realized that the second question didn't return all IDs when k > distinct_ids, luckily I fixed it in time.
Take it easy and win the next OA.
For this Google OA, not only did I finish all the questions 10 minutes early, but I also spent the rest of the time doing more tests to make sure the boundary cases were covered.Programhelp The assistance is not simply writing on your behalf, but helping you lock in high scores in the fastest way possible so that you can maintain confidence and a steady pace in the exam. Instead of toughing it out alone, let an experienced partner have your back.
