Tripadvisor Interview: Specify Number in Array in C++

Giving an array, let you find the numbers which is larger than its previous numbers and smaller or equal than the numbers behind it. Then you can return a random number in the specified number array.

Requirements:1, Implement this question.2, Using O(n) time complexity.3, Using O(n) space complexity.

int specificNum(vector<int> arr)
{
vector<int> result;
vector<int> m_vec;
int max = INT_MIN;
for(int i=0;i<arr.size();i++)
{
if(arr[i]>max)
{
max = arr[i];
}
m_vec.push_back(max);
}
int min = INT_MAX;
for(int i=arr.size()-1;i>=1;i--)
{
if(arr[i]<min)
{
min = arr[i];
}
if(arr[i]>m_vec[i-1]&&arr[i]<=min)
result.push_back(arr[i]);
}
if(arr[0]<=min)
result.push_back(arr[0]);
 assert(result.size()==0);
int n = result.size();
srand (time(NULL));
int r_num = rand()%n;
return result[n];
}

Leetcode/Google onsite: Binary Tree Zigzag Level Order Traversal in C++

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree {3,9,20,#,#,15,7},
  3
  / \
 9 20
 / \
15 7
Return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

Solution:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int> > result;
        if(!root)
        return result;
        stack<TreeNode*> s1,s2,s3;
        s1.push(root);
        TreeNode *tmp;
        int level =0;
        while(!s1.empty())
        {
            tmp = s1.top();
            if(result.size()==level)
            {
              vector<int> tmpvec;
              tmpvec.push_back(tmp->val);
              result.push_back(tmpvec);
            }
            else
              result[level].push_back(tmp->val);
            s1.pop();
            if(level%2==0) //odd level
            {
              if(tmp->left)
                s2.push(tmp->left);
              if(tmp->right)
                s2.push(tmp->right);
            }
            else   //even level
            {
              if(tmp->right)
                s2.push(tmp->right);
              if(tmp->left)
                s2.push(tmp->left);
            }
            if(s1.empty())  //after one level
            {
                s1 = s2;
                s2 = s3;
                level++;
            }
        }
        return result;
}

Microsoft SDET phone interview: Two Sum for Sorted Array in C++

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are zero-based.
Suppose the array is already sorted.
vector<int> twoSum(vector<int> &numbers, int target) {
        int start =0;
        int end = numbers.size()-1;
        vector<int> result(2,0);
        while(start<end)
        {
            if(numbers[start]+numbers[end]>target)
            {
                end--;
            }
            else if(numbers[start]+numbers[end]<target)
                start++;
            else
                break;
        }
        if(start!=end)
        {
            result[0] = start;
            result[1] = end;
        }
        return result;
    }