[Google Interview] No. 31 - Binary Search Tree Verification

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

For example, the tree in Figure 1 is a binary search tree.

Figure 1: A binary search tree

A node in binary tree is defined as:

struct BinaryTreeNode

{

    int                    nValue;

    BinaryTreeNode*        pLeft; 

    BinaryTreeNode*        pRight;

};

[Google Interview] No. 30 - Median in Stream

Question: 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.

[Google Interview] No. 28 - A Pair with the Maximal Difference

Problem: 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).

[Google Interview] No. 13 - First Character Appearing Only Once

Problem: 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”.

[Google Interview] No. 03 - Maximum Sum of All Sub-arrays

Question: 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).

[Google Interview] No. 02 - Stack with Function min()

Problem: 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).

[C++] Virtual function in inheritance

This is a small inspection of virtual function in inheritance in C++.