Hi, I think the purpose of this followup is to test whether the interviewee could figure out the duplicates would lead to a O(N) worst case, rather than modify the previous implementation since it is not much worthy than a O(N) linear search in this case.
WTYJack
@WTYJack
Posts made by WTYJack

RE: Medium level question is follow up for a hard level question?

RE: AC Java Graph DFS solution with adjacency list
@jeantimex Hi, I think you just need do a normal dfs from any node, and do the visit check after that. The tree validation could be guaranteed by checking
 # of nodes == # of edges + 1
 No self loop

RE: Divide Conquer Java Solution
@dachuan.huang +1. But the worst case will be O(N^2) when the tree looks like a descending single chain.

RE: My Accepted Java Solution
Shorter...
public TreeNode sortedArrayToBST(int[] nums) { if (nums == null  nums.length == 0) return null; int len = nums.length; TreeNode root = new TreeNode(nums[len/2]); root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, len/2)); root.right = sortedArrayToBST(Arrays.copyOfRange(nums, len/2 + 1, len)); return root; }

RE: Preorder, Inorder, and Postorder Iteratively Summarization
@xinying3 Stack is an obsolete class inherited from Vector (so wired), but Deque is a flexible interface which is obviously better than Stack. If you need to deal with concurrency, BlockingDeque is also a better one.

RE: 9 line easy JAVA solution
Really nice and elegant recursion! However, there will be a lot of redundant recursive calls in this case. Using a cache for memorizing the list of abbreviations for sub cases could be faster.

RE: Using n&(n1) trick
@jeffrey_leo said in Using n&(n1) trick:
return n > 0 && (n & (~n + 1)) == n;
Hi,
This might be more concise,
return n > 0 && (n & n) == n; 
RE: O(n) time O(1) space fastest solution
@Leo_Wang It is because the problem assume majority element (# > n/2) exists.