Could someone help me verify the time & space complexity for these?
j9Y282Dn
32

I simpliefied the questions and I was asked these in FAANG companies. Please let me know if I'm making wrong assumptions here.

#1
I told the interviewer that without considering the input space complexity, it would be O(1) and he said it was wrong.

static int findDuplicate(int[] nums) {  //assuming num is not larger than 30
	int duplicateBit = 0;
	for(int num : nums) {
		int numBit = 1 << num;
		if((duplicateBit | numBit) == duplicateBit) {
			return num;
		}
		duplicateBit |= numBit;
	}
	return -1;
}

#2
The interviewer told me that the time complexity is O(n^2) while I said this is O(n). N being the number of all nodes.

void doFoo(Node root) {
	Queue<Node> queue = new Queue<>();
	queue.add(root)
	while(!queue.isEmpty()) {
		Queue<Node> nextQueue = new Queue<>();
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			if(node == null) {
				continue;
			}
			nextQueue.add(current.left);
			nextQueue.add(current.right);
		}
		queue = nextQueue;
	}
	return -1;
}
Comments (1)