Google Sdet Interview Questions and Answers

Implement 3 stacks in a single array efficiently

• Divide the array into 3 equal parts

• Use pointers to keep track of top of each stack

• Implement push and pop operations for each stack

• Handle stack overflow and underflow cases

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

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

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

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...read more

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.

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

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

Use a hash map to index anagrams by sorting characters as keys.

• Create a hash map where the key is the sorted string of characters.

• For example, 'top' and 'pot' both map to 'opt'.

• Store all anagrams in a list associated with the sorted key.

• When querying, sort the input word and retrieve the list from the map.