Meta E5 Phone Screen - Location: SF Bay Area

Interviewer was 5 mins late to the interview. Asked for a quick intro followed by 2 coding 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)

Solved this using 2 pointer and a optimal solution

Question2

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 {
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.
Some things they were looking for in Question 2

• Space Complexity less then O(N) - (hinted to use stack)
• next() retrieval to be O(1). No processing should happen here.

If anyone knows how to approach/solve the second question please comment below! I'd appreciate it :)

I already know the result is not going to be positive for me. I could see that on the interviewer's face. I worked so hard for this opportunity! :(
I hope these questions help someone who has interview coming soon...