SDE - Intern

Approach: The idea is to use two pointers, one from start and one from the end. Assume the start person is A, and the end person is B. If A knows B, then A must not be the celebrity. Else, B must not be the celebrity. At the end of the loop, only one index will be left as a celebrity. Go through each person again and check whether this is the celebrity.
The Two Pointer approach can be used where two pointers can be assigned, one at the start and other at the end and the elements can be compared and the search space can be reduced.


Algorithm :

Create two indices a and b, where a = 0 and b = n-1
Run a loop until a is less than b.
Check if a knows b, then a can’t be celebrity. so increment a, i.e. a++
Else b cannot be celebrity, so decrement b, i.e. b–
Assign a as the celebrity
Run a loop from 0 to n-1 and find the count of persons who knows the celebrity and the number of people whom the celebrity knows. if the count of persons who knows the celebrity is n-1 and the count of people whom the celebrity knows is 0 then return the id of celebrity else return -1.

complexity analysis for this implementation:
Complexity Analysis:

Time Complexity: O(n).
Total number of comparisons 2(N-1), so the time complexity is O(n).
Space Complexity : O(1).
No extra space is required.

Suppose we start our summation series from 1 i.e. 1+2+3+…..
Max no. of numbers whose summation will be less than or equal to N: floor(X)
where X*(X+1)/2=N
So N as a sum of positive consecutive integers will at max consist of X numbers.
Here we can check each possibility k(assume) between 2 and X (both inclusive) and to check we can use the concept of A.P. as the summation series is an A.P whose sum is N.
We know the no. of term in A.P, n: k
Sum of A.P, S: N
Common difference, d: 1
We can easily calculate the first term a, using formula:

S=n/2*(2a + (n-1)d)
If a is an integer then N can be represented as a sum of k continuous integers, otherwise, it is not possible. Count the number of occurrences when a is an integer and that is our answer.
Time Complexity: Loop run X time which is O(sqrt(N)) and in each iteration, we take O(1) time. So overall time complexity is O(sqrt(N)).

intially a solution that finds whether given nodes are cousins or not by performing three traversals of binary tree has been discussed. next after asking for any different or optimal way to solve the same question by interviewer,
the approach to solve the problem by performing level order traversal is discussed . The idea was to use a queue to perform level order traversal, in which each queue element is a pair of node and parent of that node. For each node visited in level order traversal, check if that node is either first given node or second given node. If any node is found store parent of that node. While performing level order traversal, one level is traversed at a time. If both nodes are found in given level, then their parent values are compared to check if they are siblings or not. If one node is found in given level and another is not found, then given nodes are not cousins.

Traverse linked list using two pointers. Move one pointer by one and the other pointers by two. When the fast pointer reaches the end slow pointer will reach the middle of the linked list.