Meta E5 Phone Screen - (Unexpected questions)

Round 1

Questions:

Question 1

Find and return a pair of integers in a sorted array (all integers are positive) that, when summed up, bring you the closest to the value of k.
Example Input: [5, 8, 14, 17, 25, 40, 43] k: 35
Expected Output: (8, 25) since 8 + 25 = 33 which is closest to 35 (sum could be equals to, smaller or larger than k).

Question 2

Given a binary tree, implement an iterator which can return the tree node value in post-traverse order (cannot modify the tree):

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}

Provide an implementation of the following interface:

public interface PostOrderBinaryTreeIterator extends Iterator<Integer> { 
  Returns the next integer in the post-order traversal of the given binary tree.
  For example, given a binary tree below,
         4
       /    \
     2      6
    / \       / \ 
  1  3    5  7
the outputs will be 1, 3, 2, 5, 7, 6, 4.

  public int next(); 
  
  /** Return true if traversal has not finished; otherwise, return false. */ 
  public boolean hasNext();
}

This one was hard for me. I gave one solution to traverse tree and keep items in queue and pop from left on the next() method call but the interviewer was looking for optimal space complexity.