Categorize Google Interview Questions

Categorize Google Interview Questions

Data Representation

Bit

• 1. 818. Race Car
• 1. 2103. Rings and Rods
• 1. 1483. Kth Ancestor of a Tree Node

RLE

• 1. 809. Expressive Words

Rolling Hash

• 1. 1554. Strings Differ by One Character

Height Array

• 1. 1240. Tiling a Rectangle with the Fewest Squares
• 1. 1504. Count Submatrices With All Ones
• 1. 807. Max Increase to Keep City Skyline

Data Structure Implementation

Tree

• 1. 428. Serialize and Deserialize N-ary Tree
• 1. 894. All Possible Full Binary Trees
• 1. 951. Flip Equivalent Binary Trees
• 1. 889. Construct Binary Tree from Preorder and Postorder Traversal

Data Structures Design

Container

• 1. 1146. Snapshot Array
• 1. 2034. Stock Price Fluctuation
• 1. 359. Logger Rate Limiter
• 1. 981. Time Based Key-Value Store
• 1. 1244. Design A Leaderboard
• 1. 729. My Calendar I
• 1. 380. Insert Delete GetRandom O(1)
• 1. 731. My Calendar II
• 1. 460. LFU Cache
• 1. 1472. Design Browser History
• 1. 155. Min Stack
• 1. 146. LRU Cache

Iterator

• 1. 900. RLE Iterator
• 1. 158. Read N Characters Given read4 II - Call Multiple Times
• 1. 284. Peeking Iterator
• 1. 173. Binary Search Tree Iterator

Intervals

• 1. 715. Range Module
• 1. 307. Range Sum Query - Mutable

File System

• 1. 588. Design In-Memory File System
• 1. 1166. Design File System

OOD?

• 1. 631. Design Excel Sum Formula

Data Structures Usage Pattern

Stack

• 1. 150. Evaluate Reverse Polish Notation
• 1. 394. Decode String
• 1. 772. Basic Calculator III
• 1. 726. Number of Atoms
• 1. 388. Longest Absolute File Path
• 1. 1096. Brace Expansion II
• 1. 1807. Evaluate the Bracket Pairs of a String
• 1. 71. Simplify Path
• 1. 856. Score of Parentheses

Monotonic Deque

some property of the problem is telling us, we can ignore smaller / larger stuff from the past.

• 1. 1776. Car Fleet II
• 1. 1499. Max Value of Equation
• 1. 975. Odd Even Jump
• 1. 1673. Find the Most Competitive Subsequence

Priority Queue

Priority ~= greedy, some property of the problem is telling us, some partial result is better than others.

• 1. 1293. Shortest Path in a Grid with Obstacles Elimination
• 1. 1834. Single-Threaded CPU
• 1. 1882. Process Tasks Using Servers
• 1. 253. Meeting Rooms II
• 1. 1514. Path with Maximum Probability
• 1. 1642. Furthest Building You Can Reach
• 1. 759. Employee Free Time
• 1. 857. Minimum Cost to Hire K Workers
• 1. 632. Smallest Range Covering Elements from K Lists

Tree Traversal

• 1. 2096. Step-By-Step Directions From a Binary Tree Node to Another
• 1. 690. Employee Importance
• 1. 1110. Delete Nodes And Return Forest
• 1. 968. Binary Tree Cameras
• 1. 236. Lowest Common Ancestor of a Binary Tree
• 1. 965. Univalued Binary Tree

Path / Subtree / Nodes in Tree

• 1. 652. Find Duplicate Subtrees
• 1. 549. Binary Tree Longest Consecutive Sequence II
• 1. 222. Count Complete Tree Nodes
• 1. 298. Binary Tree Longest Consecutive Sequence

Depth / Height / width / Size in Tree

• 1. 366. Find Leaves of Binary Tree
• 1. 662. Maximum Width of Binary Tree

Geometry

• 1. 2013. Detect Squares
• 1. 1610. Maximum Number of Visible Points
• 1. 939. Minimum Area Rectangle
• 1. 593. Valid Square

Bit Manipulation

• 1. 389. Find the Difference

Numbers

Tabluation

• 1. 233. Number of Digit One
• 1. 400. Nth Digit
• 1. 313. Super Ugly Number

Cycle

• 1. 202. Happy Number

Numerical Pattern

• 1. 660. Remove 9
• 1. 1088. Confusing Number II
• 1. 788. Rotated Digits
• 1. 621. Task Scheduler
• 1. 7. Reverse Integer
• 1. 246. Strobogrammatic Number

Sequence Pattern

• 1. 2007. Find Original Array From Doubled Array
• 1. 843. Guess the Word
• 1. 954. Array of Doubled Pairs
• 1. 1877. Minimize Maximum Pair Sum in Array
• 1. 1296. Divide Array in Sets of K Consecutive Numbers
• 1. 564. Find the Closest Palindrome
• 1. 846. Hand of Straights samething as above
• 1. 1864. Minimum Number of Swaps to Make the Binary String Alternating
• 1. 360. Sort Transformed Array
• 1. 41. First Missing Positive

Prefix Sum

• 1. 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
• 1. 525. Contiguous Array

2D Matrix Pattern

• 1. 2128. Remove All Ones With Row and Column Flips
• 1. 794. Valid Tic-Tac-Toe State
• 1. 1275. Find Winner on a Tic Tac Toe Game
• 1. 835. Image Overlap
• 1. 1138. Alphabet Board Path

Search

BFS

• 1. 1345. Jump Game IV
• 1. 1263. Minimum Moves to Move a Box to Their Target Location
• 1. 417. Pacific Atlantic Water Flow
• 1. 505. The Maze II
• 1. 1197. Minimum Knight Moves
• 1. 1368. Minimum Cost to Make at Least One Valid Path in a Grid
• 1. 752. Open the Lock
• 1. 743. Network Delay Time
• 1. 1730. Shortest Path to Get Food

DFS

• 1. 489. Robot Room Cleaner
• 1. 1254. Number of Closed Islands
• 1. 1728. Cat and Mouse II
• 1. 200. Number of Islands
• 1. 465. Optimal Account Balancing
• 1. 753. Cracking the Safe
• 1. 399. Evaluate Division
• 1. 695. Max Area of Island
• 1. 721. Accounts Merge
• 1. 733. Flood Fill

Binary Search

• 1. 302. Smallest Rectangle Enclosing Black Pixels
• 1. 410. Split Array Largest Sum
• 1. 34. Find First and Last Position of Element in Sorted Array
• 1. 852. Peak Index in a Mountain Array
• 1. 702. Search in a Sorted Array of Unknown Size

Cycle Detection

• 1. 261. Graph Valid Tree
• 1. 207. Course Schedule

Greedy

• 1. 1153. String Transforms Into Another String
• 1. 1042. Flower Planting With No Adjacent

String

KMP

• 1. 1397. Find All Good Strings
• 1. 686. Repeated String Match
• 1. 459. Repeated Substring Pattern

HashMap

• 1. 205. Isomorphic Strings
• 1. 616. Add Bold Tag in String

Sliding Window

• 1. 551. Student Attendance Record I
• 1. 3. Longest Substring Without Repeating Characters

Two Pointers

On Array

• 1. 539. Minimum Time Difference
• 1. 727. Minimum Window Subsequence
• 1. 1855. Maximum Distance Between a Pair of Values
• 1. 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
• 1. 43. Multiply Strings
• 1. 334. Increasing Triplet Subsequence
• 1. 18. 4Sum
• 1. 21. Merge Two Sorted Lists

On Linked List

• 1. 92. Reverse Linked List II
• 1. 141. Linked List Cycle

On String

• 1. 833. Find And Replace in String
• 1. 68. Text Justification
• 1. 418. Sentence Screen Fitting
• 1. 299. Bulls and Cows
• 1. 1592. Rearrange Spaces Between Words
• 1. 925. Long Pressed Name

Circular Array / Linked List

• 1. 1423. Maximum Points You Can Obtain from Cards
• 1. 708. Insert into a Sorted Circular Linked List

Backtrack

• 1. 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
• 1. 267. Palindrome Permutation II
• 1. 37. Sudoku Solver
• 1. 93. Restore IP Addresses
• 1. 77. Combinations
• 1. 46. Permutations

DP

From previous result through a simple relationship

• 1. 1218. Longest Arithmetic Subsequence of Given Difference
• 1. 1987. Number of Unique Good Subsequences
• 1. 91. Decode Ways
• 1. 338. Counting Bits

From previous result through a branching choice and / or bit mask as state or table rows / cols / or condition

• 1. 1691. Maximum Height by Stacking Cuboids
• 1. 920. Number of Music Playlists similar to distrbute candy
• 1. 1531. String Compression II
• 1. 1494. Parallel Courses II

Expansion to k between i and j

• 1. 241. Different Ways to Add Parentheses
• 1. 787. Cheapest Flights Within K Stops

Game

• 1. 1406. Stone Game III

2D

range(n) -> reversed(range(n)) or range(n) -> range(i, n) etc

• 1. 664. Strange Printer
• 1. 312. Burst Balloons
• 1. 1770. Maximum Score from Performing Multiplication Operations

Depends on preivous row / column

• 1. 1937. Maximum Number of Points with Cost
• 1. 1277. Count Square Submatrices with All Ones
• 1. 562. Longest Line of Consecutive One in Matrix
• 1. 568. Maximum Vacation Days
• 1. 62. Unique Paths
• 1. 72. Edit Distance

Set

• 1. 1048. Longest String Chain

State Machine

• 1. 552. Student Attendance Record II

Sorting

Quickselect

• 1. 973. K Closest Points to Origin

Merge Sort

• 1. 23. Merge k Sorted Lists

Use of a SortedList

• 1. 315. Count of Smaller Numbers After Self

Sweep Line

• 1. 792. Number of Matching Subsequences
• 1. 2158. Amount of New Area Painted Each Day
• 1. 2018. Check if Word Can Be Placed In Crossword
• 1. 1272. Remove Interval
• 1. 853. Car Fleet
• 1. 850. Rectangle Area II
• 1. 56. Merge Intervals
• 1. 1094. Car Pooling

Topological Sort

• 1. 2115. Find All Possible Recipes from Given Supplies
• 1. 329. Longest Increasing Path in a Matrix
• 1. 210. Course Schedule II

Math

RNG

• 1. 384. Shuffle an Array
• 1. 528. Random Pick with Weight
• 1. 710. Random Pick with Blacklist

Counting

On Frequencies

• 1. 2083. Substrings That Begin and End With the Same Letter
• 1. 2131. Longest Palindrome by Concatenating Two Letter Words

Combinations

• 1. 679. 24 Game

Pairwise

• 1. 447. Number of Boomerangs

2D grid

• 1. 419. Battleships in a Board
• 1. 463. Island Perimeter

Union Find

• 1. 803. Bricks Falling When Hit
• 1. 407. Trapping Rain Water II
• 1. 990. Satisfiability of Equality Equations
• 1. 2092. Find All People With Secret
• 1. 1632. Rank Transform of a Matrix
• 1. 305. Number of Islands II
• 1. 778. Swim in Rising Water
• 1. 1101. The Earliest Moment When Everyone Become Friends
• 1. 827. Making A Large Island

Trie

• 1. 745. Prefix and Suffix Search
• 1. 1032. Stream of Characters
• 1. 642. Design Search Autocomplete System
• 1. 1948. Delete Duplicate Folders in System
• 1. 720. Longest Word in Dictionary

Concurrency

• 1. 1226. The Dining Philosophers

Heuristic

• 1. 722. Remove Comments
• 1. 1055. Shortest Way to Form String

Simple?

• 1. 1436. Destination City
• 1. 8. String to Integer (atoi)
• 1. 2. Add Two Numbers