Google Interview Questions

No. 02 - Stack with Function min()

 Define a stack, in which we can get its minimum number with a function min. In this stack, the time complexity of min(), push() and pop() are all O(1).

No. 03 - Maximum Sum of All Sub-arrays

A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n).

No. 13 - First Character Appearing Only Once

Implement a function to find the first character in a string which only appears once.

For example: It returns ‘b’ when the input is “abaccdeff”.

No. 28 - A Pair with the Maximal Difference

A pair contains two numbers, and its second number is on the right side of the first one in an array. The difference of a pair is the minus result while subtracting the second number from the first one. Please implement a function which gets the maximal difference of all pairs in an array. For example, the maximal difference in the array {2, 4, 1, 16, 7, 5, 11, 9} is 11, which is the minus result of pair (16, 5).

No. 30 - Median in Stream

How to get the median from a stream of numbers at any time? The median is middle value of numbers. If the count of numbers is even, the median is defined as the average value of the two numbers in middle.

No. 31 - Binary Search Tree Verification

How to verify whether a binary tree is a binary search tree?

No. 41 - Group of 1s in a Matrix

Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s. For example, there are four groups of 1s in Figure 1 which are drawn with different colors.

No. 42 - Three Increasing Elements in an Array

Given an array of integers A, please find three indexes i, j, k, such that i<j<k and A[i]<A[j]<A[k].

No. 43 - Minimal Number of Splits on a String

A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string “abbab” into palindrome substrings, such as: “abba”|”b”, “a”|”b”|”bab” and “a”|”bb”|”a”|”b”.

Given a string str, please get the minimal numbers of splits to partition it into palindromes. The minimal number of splits to partition the string “abbab” into a set of palindromes is 1.

No. 45 - Closest Node in a Binary Search Tree

Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

No. 46 - Nodes with Sum in a Binary Search Tree
Given a binary search tree, please check whether there are two nodes in it whose sum equals a given value.

No. 47 - Search in a Rotation of an Array
When some elements at the beginning of an array are moved to the end, it gets a rotation of the original array. Please implement a function to search a number in a rotation of an increasingly sorted array. Assume there are no duplicated numbers in the array.

No. 48 - Least Number after Deleting Digits

Please get the least number after deleting k digits from the input number. For example, if the input number is 24635, the least number is 23 after deleting 3 digits.