10+ Google Sdet Interview Questions and Answers

To design a search engine with keyword-based document indexing and numeric attributes, we need to build appropriate indices.

• Create an inverted index for each keyword, mapping it to the documents that contain it

• For numeric attributes, use a B-tree or other appropriate data structure to store the values and their associated documents

• Combine the indices to allow for complex queries, such as keyword and attribute filters

• Consider using stemming or other text processing techniques ...read more

Implement spelling and word suggestions for full keyboard phones

• Create a dictionary of commonly used words

• Use algorithms like Trie or Levenshtein distance to suggest words

• Implement auto-correct feature

To find a given integer in a circularly sorted array of integers, use binary search with slight modifications.

• Find the middle element of the array.

• If the middle element is the target, return its index.

• If the left half of the array is sorted and the target is within that range, search the left half.

• If the right half of the array is sorted and the target is within that range, search the right half.

• If the left half is not sorted, search the right half.

• If the right half is not so...read more

To determine if someone has won a game of tic-tac-toe on a board of any size, we need to check all possible winning combinations.

• Create a function to check all rows, columns, and diagonals for a winning combination

• Loop through the board and call the function for each row, column, and diagonal

• If a winning combination is found, return the player who won

• If no winning combination is found and the board is full, return 'Tie'

• If no winning combination is found and the board is not f...read more

Program to find intersection of words in two files

• Read both files and store words in two arrays

• Loop through one array and check if word exists in other array

• Print the common words

Replace each number in an array with the product of all other numbers without using division.

• Iterate through the array and calculate the product of all numbers to the left of the current index.

• Then, iterate through the array again and calculate the product of all numbers to the right of the current index.

• Multiply the left and right products to get the final product and replace the current index with it.

Program to find depth of binary search tree without recursion

• Use a stack to keep track of nodes and their depths

• Iteratively traverse the tree and update the maximum depth

• Return the maximum depth once traversal is complete

Find the maximum rectangle (in terms of area) under a histogram in linear time

• Use a stack to keep track of the bars in the histogram

• For each bar, calculate the area of the rectangle it can form

• Pop the bars from the stack until a smaller bar is encountered

• Keep track of the maximum area seen so far

• Return the maximum area

Recursive mergesort divides array into halves, sorts them and merges them back. O(nlogn) runtime.

• Divide array into halves recursively

• Sort each half recursively using mergesort

• Merge the sorted halves back together

• Runtime is O(nlogn)

• Iterative version can be written using a stack or queue

Create a cache with fast look up that only stores the N most recently accessed items

• Implement a hash table with doubly linked list to store the items

• Use a counter to keep track of the most recently accessed items

• When the cache is full, remove the least recently accessed item