Microsoft

I was asked to find the length of the longest palindromic substring in a string, which I solved in linear time using Manacher's algorithm. The interviewer asked me to count the number of valid ways to tile a 3×n grid with 2×1 domino blocks using dynamic programming with bitmasking. I was asked to compute range minimum queries with dynamic point updates over an array of size 10^5 using a Segment Tree.