Share interview questions you were asked this year [List]

This is going to be a bit long.

1/ Seems to be a fairly common problem: Find all words that can be formed on a Boggle board. (https://en.wikipedia.org/wiki/Boggle). You're given the board as a 4x4 matrix and a list of words to serve as a dictionary of legal words. 2/ A certain company in San Francisco that's fairly well known put me through 3 interviews and all were very similar problems i/ Given a list of words with no duplicates, generate the unique prefix for each word in the list. For example, given ['single', 'simple'], the unique prefixes would be ['sin', 'sim'] because the only word in the list to have the prefix 'sin' is 'single' and the only word in the list to have the prefix 'sim' is 'simple'. ii/Similar to i/, you're given a list of words. The problem is as follows, there is an autocompleter function that hleps you type words in the list. Based on the words typed so far, the autocompleter tries to finish the word for you. The autocompleter only knows of words in the list. Given the list of words, determine the number of letters you would have to input with the autocompleter's help to type out the word. E.g., for the list ['single', 'simple'], typing out 'single' requires 2 keypresses. The first is to type 's', after whcih the autocompleter will type 'i' for you since all the words in the list starting with 's' have an 'i' following the 's'. Next, you type 'n', and the autocompleter types 'gle' for you as that's the only possibility out of the words in the list. 1/ and 2/ are basically trie problems.

3/ Given an nxm matrix of integers. Traverse and print out the integers in a spiral pattern. 4/ Convex Hull problem. 5/ Two-sum, to three-sum, and then k-sum problem. Simple idea: given a list of integers and a target number. Find the number of pairs/triples/k-tuples in the list that sum up to the target. 6/ Given a list of words in sorted order, determine the alphabet ordering for those words. E.g. if the sorted list was ['cd', 'ca', 'dd'], you would return ['c', 'd', 'a'] as the ordering. 7/ Using the numbers 1..n to form binary search trees, determine the number of different binary search tree structures that can be obtained. 8/ Determine the sub-array with the largest sum in an array of integers. 9/ Distributed JOIN of two tables spread out over k machines. 10/ Dstributed median over k machines. 11/ Solve a tilt maze. What that is, you have a data structure given representing the maze, and you can always make 1 of 4 moves: tile up, right, left, or down. Your position changes to be the closeest wall in the direction tilted. Given an start and end node, determine the optimal set of moves (minimum number) to get from start to goal. 12/ Given a sorted list of integers, write a function that will find the number of occurences for a given integer in the list. 13/ Given a string, determine the number of permutations of that string which is a palindrome. 14/ Given a 1D array representing the heights of buildings, determine the volume of water that will remain after it rains. 15/ Given a string and a dictionary, return the number of words in the dictionary that can be formed by using letters in the string. You don't have to use all the ltters. E.g., using 'cater', you can form 'cat' and 'car'. Assume you can preprocess for free.

A lot more that I can't remember. Not sure how useful this is since most problems are already on sites like leetcode or hackerrank.

/r/cscareerquestions Thread