I was interviewed by Pubmatic(Pune) over BlueJeans.
In the last that lady interviewer asked about routines & channels in Go & I was wonderning why?
When I told the recruiter already that I don't know Go & over that recruiter agreed that knowledge of Go is not mandatory then why in interview knowledge of some advanced topics of Go was expected.
Below are the questions asked & the answers I gave -
Question 1 : Find Maximum Path Sum in a Binary Tree
Answer : Question was asked from this site as I interviewer screen was also sharing & during screen switching, so here she
was picking the questions from Geeksforgeeks to ask me during interview, that is the level of these interviewers
here. I saw this screen. https://www.geeksforgeeks.org/find-maximum-path-sum-in-a-binary-tree/
I still don't agree with the approach & the solution is expected on above page, if anyone can help please let me
know. Edit: Though I didn't get any help on this, rather got some senseless comment, so I checked this question again & I see it is correct
as per the definition but I was explained in wrong way by interviewer so I thought it in that way and wrote below for that, so solution given on
Geeksforgeeks is correct but explanation given by that interviewer was wrong & then she was expecting the above solution.
I was not clear with the question requirements & may be interviewer was also not, as per my understanding I wrote
below code -
int sum = 0;
int maxSum(Node start, sum) {
sum+=start.data; //5...15...35...43...46
int leftSum = 0;
int rightsum = 0;
if(start.left != null) {
leftSum = maxSum(start.left, sum); //46
}
if(start.right != null) {
rightSum = maxSum(start.right, sum); //44...16
}
if(leftSum == 0 && rightSum == 0)
return sum;
if(sum > leftSum && sum > rightSum)
return sum;
return leftsum > rightSum ? leftSum : rightSum;
}
Question 2 : You need to write 2 APIs such that one API will get continuous stream of numbers & other API will return top 10
numbers when called
Answer : Check - https://www.geeksforgeeks.org/kth-largest-element-in-a-stream/
I told I will use either MaxHeap of size 10 or can have tree structure sorted in reverse order of size 10. And I will create another API(A) which will maintain this global structure, one API(B) will pass the numbers to this API(A) & when top 10 are required then from other API(C) I will fetch those number from that common structure.
Question 3 : Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
Answer : This question was asked from
https://www.geeksforgeeks.org/in-a-linked-list-given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/
I didn't get the idea to copy the data of next node during the interview. But again I don't see such workaround as the right solution, as if consumers are having the address of that node but one consumer does change the data of that node in name of 'Delete' then other consumer will see different data, rather I feel that other consumer should get some error as the expected node is not there.
And I believe such interviewers just visit such sites & start asking questions from there without further analysing it. So I don't like such nonsense in these organisations.
Question 4 : input = A - B - C - D - E - F - G - H
k = 3
output = C - B - A - F - E - D - H - G
You are given a linked list as input & one k number, so that you need to reverse the nodes of that list in the blocks of k to get the above output.
Answer : Question is from -
https://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
Funny thing is that interviewer also sticked to similar example, I think it was easier to understand the code.
Any how I gave my solution, which is not as given above, so the interviewer was finding it difficult to understand it & she was expecting me to tell the same solution/approach as mentioned above, but I told the reasons for both approaches.
reverse(Node root, int k) {
int block = k;
Stack stack;
Node prevTail = null;
while(root != null) {
while(block > 0 && node != null) {
stack.add(node);
node = node.next();
block--;
}
if(!stack.isEmpty())
Node temp = stack.peek().next();
curr = stack.peek();
if(prevTail != null)
prevTail.next = curr;
while(!stack.isEmpty()) {
curr = stack.pop();
curr.next = stack.peek();
}
prevTail = curr;
root = temp;
block = k;
}
}
temp = C.next;
C.next = B
B.next = A;
A.next = F
F.next = E
E.next = F
D.next = H
H.next = G
G.next = null
C - B - A - F - E - D - H - G
In the last that lady interviewer asked about routines & channels in Go & I was wonderning why?
When I told the recruiter already that I don't know Go & over that recruiter agreed that knowledge of Go is not mandatory then why in interview knowledge of some advanced topics of Go was expected.
Below are the questions asked & the answers I gave -
Question 1 : Find Maximum Path Sum in a Binary Tree
Answer : Question was asked from this site as I interviewer screen was also sharing & during screen switching, so here she
was picking the questions from Geeksforgeeks to ask me during interview, that is the level of these interviewers
here. I saw this screen. https://www.geeksforgeeks.org/find-maximum-path-sum-in-a-binary-tree/
I still don't agree with the approach & the solution is expected on above page, if anyone can help please let me
know. Edit: Though I didn't get any help on this, rather got some senseless comment, so I checked this question again & I see it is correct
as per the definition but I was explained in wrong way by interviewer so I thought it in that way and wrote below for that, so solution given on
Geeksforgeeks is correct but explanation given by that interviewer was wrong & then she was expecting the above solution.
I was not clear with the question requirements & may be interviewer was also not, as per my understanding I wrote
below code -
int sum = 0;
int maxSum(Node start, sum) {
sum+=start.data; //5...15...35...43...46
int leftSum = 0;
int rightsum = 0;
if(start.left != null) {
leftSum = maxSum(start.left, sum); //46
}
if(start.right != null) {
rightSum = maxSum(start.right, sum); //44...16
}
if(leftSum == 0 && rightSum == 0)
return sum;
if(sum > leftSum && sum > rightSum)
return sum;
return leftsum > rightSum ? leftSum : rightSum;
}
Question 2 : You need to write 2 APIs such that one API will get continuous stream of numbers & other API will return top 10
numbers when called
Answer : Check - https://www.geeksforgeeks.org/kth-largest-element-in-a-stream/
I told I will use either MaxHeap of size 10 or can have tree structure sorted in reverse order of size 10. And I will create another API(A) which will maintain this global structure, one API(B) will pass the numbers to this API(A) & when top 10 are required then from other API(C) I will fetch those number from that common structure.
Question 3 : Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
Answer : This question was asked from
https://www.geeksforgeeks.org/in-a-linked-list-given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/
I didn't get the idea to copy the data of next node during the interview. But again I don't see such workaround as the right solution, as if consumers are having the address of that node but one consumer does change the data of that node in name of 'Delete' then other consumer will see different data, rather I feel that other consumer should get some error as the expected node is not there.
And I believe such interviewers just visit such sites & start asking questions from there without further analysing it. So I don't like such nonsense in these organisations.
Question 4 : input = A - B - C - D - E - F - G - H
k = 3
output = C - B - A - F - E - D - H - G
You are given a linked list as input & one k number, so that you need to reverse the nodes of that list in the blocks of k to get the above output.
Answer : Question is from -
https://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
Funny thing is that interviewer also sticked to similar example, I think it was easier to understand the code.
Any how I gave my solution, which is not as given above, so the interviewer was finding it difficult to understand it & she was expecting me to tell the same solution/approach as mentioned above, but I told the reasons for both approaches.
reverse(Node root, int k) {
int block = k;
Stack stack;
Node prevTail = null;
while(root != null) {
while(block > 0 && node != null) {
stack.add(node);
node = node.next();
block--;
}
if(!stack.isEmpty())
Node temp = stack.peek().next();
curr = stack.peek();
if(prevTail != null)
prevTail.next = curr;
while(!stack.isEmpty()) {
curr = stack.pop();
curr.next = stack.peek();
}
prevTail = curr;
root = temp;
block = k;
}
}
temp = C.next;
C.next = B
B.next = A;
A.next = F
F.next = E
E.next = F
D.next = H
H.next = G
G.next = null
C - B - A - F - E - D - H - G
