Current status: Final year UG CS student
Tier-1 College (Darr ka Mahol hai)

About :Navi Technologies (erstwhile known as BACQ) is founded by Sachin Bansal & Ankit Agarwal to build consumer-centric and technology-driven businesses in the BFSI (Banking, Financial Services & Insurance) space.

Compensation is quite good.
Location is Bangalore.

Navi came to our campus for the role of SDE1. It was also open for placed students having offers with less than a particular CTC.

Round 1: Online Test 48 questions,
Time : 2 hours
Aptitude (20 questions ): profit Loss, mixtures, ratios and identities, series completion etc
Maths and Aptitude (25 questions): Aptitude question with similar difficulty.
Section A, B had a total of 45 questions, and 40 minutes were given to complete.
Coding Level A: 
Time: 50 minutes 2 question
2 Questions. Both of them were easy. Implementation was a bit tricky for one of them.

Coding Level B: 
Time: 30 Minutes
Given some numbers. Choose exactly k pairs and find the maximum abs of difference of the two numbers in every pair.N~ 10^3 afair.
I did it through DP.

Coding Questions were easy-medium. Time was very limited for aptitude/maths questions.

PIs, platfrom was google meet.
Round 2: Problem solving and Data structures
Around 20 student shortlisted, 45 mins round

Interviewer was very friendly person having total 5 YOE with 5 months in NAVI. First he introduce himself then took my introduction.
Then asked my favourite DS. I told, I was not specific but let’s go with arrays. He said if trees okay? I said yes. He asked me, what is complete tree. Donot know what I said but I was not confident. Then, I told him that there are complete,full and perfect binary trees coudlnot remember their details, this took a lot of time around 7-8 minutes. He said okay and said that I have total 35 mins mor(total 45) and will ask 2 ques if time permits then 3.

He, made a tree on google docs and,
Q1. Find all node at k distance from root node.
I took some time, did some clarification on output sequence and values of k. and told my dfs approach and its TC & SC. Then, he told me to write whole implementable code including making a tree in any IDE. Code gave wrong results initially. Figuring out and resolving 2 bugs, it satisfied him.

Q2. How can I sort a linked list.
I said, in naive way, I will store data in array sort it then assign it. Then I said marge sort is good. He said why not earlier one. Then I also introduce quick sort into the scene. Discussion became very confusing, he was asking about merge & quick sort on array & LL, then their TC and SC. I was taking time in giving answers, but I was clearly on the backfoot.

Q3. Add 2 LL representing numbers.
// 1 -> 9 -> 9
// 4 -> 5 -> 6 -> 7
// 5 -> 4 -> 6 -> 8

I told im my approach and started coding.
Code was good but made a very big blunder. Time was 12:43. He said me to take 3-4 more and modify. I removed a bug but he said that blinder was somewhere else.

Correct code is: ( Interview code had some bugs which I corrected here)

struct  Node{

  Node*next;
  int data;

  Node(int val)
  {
    next=NULL;;
    data=val;
  }

};
Node*addUtill(Node*head1,Node*head2,int carry)
{
  if(!head1 && !head2)
  {
    if(carry)
      return new Node(carry);
    else
      return NULL;
  }
  int sum=0;
  if(head1)
    sum+=head1->data;
  if(head2)
    sum+=head2->data;
  sum+=carry;

  Node* cur= new Node(sum%10);

  cur->next= addUtill(head1?head1->next:NULL,head2?head2->next:NULL,sum/10);

  return cur;
}
Node* add(Node*head1,Node*head2)
{
    int sum=0,carry=0;
    if(head1)
      sum+=head1->data;
    if(head2)
      sum+=head2->data;
    sum+=carry;

    Node* cur= new Node(sum%10);

    cur->next= addUtill(head1?head1->next:NULL,head2?head2->next:NULL,sum/10);
    return cur;
}


int main() {
  init_code();

  Node*head1= new Node(1);
  head1->next= new Node(9);
  head1->next->next= new Node(9);

  Node*head2= new Node(9);
  head2->next= new Node(9);
  head2->next->next= new Node(9);
  head2->next->next->next= new Node(9);

  Node* root= add(head1,head2);

  Node*t=root;

  while(t)
  {
    cout<<t->data<<" ";
    t=t->next;
  }

   return 0;
}

Then, he said that I had worked on mysql DB in intern, what DB I know. I said Oracle, SQL. He said, if I know about NoSQL DB. He asked me the difference. I told that data is stored in form of tables and relations in SQL DB while in form of key-value par(can store docs, objects, files) in NoSQL DB. He said what is difference bwn tables and relations ( I was behind weeket keeper now). Then said to write a SQL query.

Q4. Find name of employee getting highest salary from an EMP table.
Select Name from EMP
Where salary=(select max(salary)from EMP);
Then said, find 3r heighest. I gave him logic to find heighest then remove it from all salaries, do this one more time and then find heighest salary. He told what if 5th highest or even more. I was clean bowled but was not giving up and thinking.

He said that’s it and if I had any question.

I asked was round supposed to be only of DSA. He said yes, but he extended it in my case. He keep on insisting me to ask more questions. It made me remind of one of my earlier interviews where similar thing happed and last verdict was rejected. I think he had got my nerves at this point that what I was thinking. By still I asked very enthusiastically.

Round 3: Hiring manager Round, 45 mins. Around 12 students shortlisted
Some students had already give this round and quesions asked to them were: Multi-level caching, B,B+ Trees, Design Google forms, Twitter ER Diagram, sharding, How search happens in SQL, internships, projects… From previous interviews it was estimated that a Design question would be asked. Design part was difficult for everyone and one could pass it then, through prayers only, I guess xD.

Interviewer read my resume in front of me. Asked my comfortable language to code and why I had choosen it. I said C++ and honestly said because first langage was C and C++ syntax was similar to it. Said if I have read OOPs and asked overloading. I took my proper time to thing(5-8 secs) then explaned with an example. Then asked Overriding.
Asked about Normalization. I quickely told it and wrote

NF 1,2,3,BCNF,4,5

I was explaining NF1, he told okay. Then asked De-normaliztion. I said opposited of normaliztion. After normlization for query, sometimes we need to join tables and then perfom operations again and again. Thus to prevent that we do De-normalization to save that time.
This time I was giving quick answers and was wrapping them up so that there would be no time issues and out of range cross questions be there.

He moved on to DSA.
Q.Reverse a linked list.
I gave stack approach, its TC & SC and explained it. He asked to code it. I was like (ohh no, I knew a better and easy approach to code but coding this approach. No no). Then donot know how confidently within 10 secs of dry run I explained my approach very well and quickly coded it and then dry run it also. He said okay and told to reduce SC to O(1).

I told him I cannot reduct TC below O(N), but SC can be reduced to O(N^0.5) or O(1) so on. He said, do it in O(1).
I said I had studied a simlar algo earlier that can be used here then perfoming some avaerage peice of my oscar award wining acting I presented my approach. Then quickly coded it. He was satisfied and said, that;s it from his side and if I had any questions for him. I said, (wait, time is 4:58, only 28 minutes and he has said all done) yes. I took few seconds, then asked about the NAVI culture and qualities a fresher should have.

My code then(correct)

class shapes{
public:
  int area(int r)
  {
    return pi*r*r;
  }
  int area(int a,int b)
  {
    return a*b;
  }
};

NF 1,2,3,BCN,4,5

Node* reversLL(Node*head)
{
  if(!head || !head->next)
    return head;

  stack<Node*>stck;
  

  while(head)
  {
    stck.push(head);
    head=head->next;
    stck.top()->next=NULL;
  }

  Node*resh=NULL;
  Node*temp=NULL;

  reshh=stck.top();
  stck.pop();
  temp=resh;

  while(!stck.empty())
  {
    temp->next=stck.top();
    stck.pop();
    temp=temp->next;
  }

  return resh;
}

Node* reversLL(Node*head)
{
  if(!head || !head->next)
    return head;

  Node*prev,*cur,*next;
  prev=NULL;
  cur=head;

  while(cur!=NULL)
  {
    next=cur->next;
    cur->next=prev;
    prev=cur;
    cur=next;
  }

  return prev;
}

No Round 4. Total 8 students were selected and I was one of them.

Other question asked from other interviewees were:

• Find Kth largest element
• Detect Loop in a linked list
• buzz-fizz question
• SQL queris
• Make a DB schema for Resume
• Design google form supporting features for Single correct, Text box and one more type answers. Seeing the complexity later it was reduced to design only for Single correct answer type questions.

The interview process clearly focused on DSA, DBMS and Design problems.

Some wwere asked about their projects and intern works also.

Notes:
I had prepared DS well, but still did blunders in R1. Multiples times I was on backfoot, but every time I thought no worries let’s do the rest good. This could be happed because similar thing had happed with me in past and I for this time I had decided to not give up at anytime even for a second. You will be up and low in interview, but make sure to have a mentality that let’s do the rest good.
No Design question was asked from me.(little luckier).

Hard work of 2 years paid off well. But remember, Never Settle.

Please upvote, it took me hours to document each and every step of the interview.