Question: AppDynamics On-Campus Interview Experience | Difference Array | Greedy Problem | Number of Regions N Lines Divide Plane

Entering edit mode

Role: Software Engineer(SWE)

Online Assessment (First shortlisting)

Consisted of 10 MCQs of Medium Level and 3 coding questions (all compulsory and non-proctored) and the result is given based on all the rounds combined.

3 coding questions were, easy to medium level.

Difference Array | Range update query in O(1)
Click here to Practice
Submit Problem to OJ
Number of Regions N Lines Divide Plane (formula based question, search google for explanation)
Click here to Practice
Submit Problem to OJ
Greedy Problem

9 were shortlisted for interviews.

Coding round

Workstyle Assessment

This is a special round that assesses you based on decisions you make in the workstyle environment. There will be questions based on debugging, making decisions for you and your colleagues, and managerial decisions based on facts and reports. There is no time limit but try to complete it in 2-3 hours.

Round 1

First Round: Technical round

The round started with a basic introduction and then moved two DSA questions

Q1: Given an array A[], write a function that segregates even and odd numbers. The functions should put all even numbers first, and then odd numbers.

Example:

Input = {12, 34, 45, 9, 8, 90, 3} Output = {12, 34, 8, 90, 45, 9, 3}

Click here to Practice

In the output, the order of numbers can be changed, i.e., in the above example, 34 can come before 12 and 3 can come before 9.

Q2: Check if each level of a binary tree is a palindrome or not (Hint: Level order traversal of tree)

The round ended with few questions regarding internships and projects.

Verdict: Qualified for the next round.

Round 2

Second Round: Technical round

Second round was also a technical round with 3 questions

Class design question on Tic Tac Toe.
How to implement call logs list in mobile phone (Write code and explain data structures used).
How is Hash Map implemented?

The interviewers are very friendly and help you to reach to the solution, even if you get stuck at any question.

Verdict: Qualified for the next round.

Round 3

Third Round: Tech+HR round

How to convert decimal to binary (number can be negative too)
Difference between C and C++
Explain OOPS concepts
Explain forms of Normalization
Explain OSI Model

And along with these basic HR questions and few situation based questions.

Bonus Tip

Make sure you also ask few questions to the interviewer, to carry on the conversation, like what roles are open for full time joiners etc.

Final Verdict: Selected

ADD COMMENT • link

Entering edit mode

Question 1 (Online assessment)

Overview

Given an array of integers and queries of the form l r x
Add the value x from index l to index r

Approach

We can keep a difference array diff such that diff[i]=array[i]-array[i-1]

With this, we can do updates in O(1) by increasing doing diff[l]+=x and diff[r+1]-=x

Then the final array would be array[i]+prefixsum(diff[i])

Proof of the solution

When we add x to diff[i] then, in all the values till index r. This value is added as we are taking the prefix sum. We subtract x from diff[r+1] so that when we take the prefix sum this value is not added in the index>r.

Solution ``` int l,r,x; for(int i=0;i<k;i++){ cin >> l >> r >> x; diff[l-1]+=x; diff[r]-=x; } int val=0; for(int i=0;i

ADD COMMENT • link

Entering edit mode

Question 3 (First Round Q-1)

Overview

Given an array of integers we have to separate even and odd numbers.
The even numbers should be put first and odd numbers should be put after.

Solution

Initialize a variable let's say even_index as 0.
Now iterate through the array from beginning to end. If the element at the current index is even swap(a[even_index],a[current_index]) and increment even_index by 1.
Do the above procedure till you reach the end of the array. In this way, all the even elements will come in the beginning and all the odd elements will come in the end and hence will be separated from each other.

Code

ll n;
cin &gt;&gt; n;
vector&lt;ll&gt; a(n);
for (ll i = 0; i &lt; n; i++)
{
    cin &gt;&gt; a[i];
}
ll even_index = 0; // initialize valriable as 0

for (ll i = 0; i &lt; n; i++)
{
    if (a[i] % 2 == 0) // If the current element is even
    {
        // swap the element
        swap(a[i], a[even_index]);
        even_index++;
    }
}
for (ll i = 0; i &lt; n; i++)
{
    cout &lt;&lt; a[i] &lt;&lt; " ";
}
cout &lt;&lt; endl;
return;

ADD COMMENT • link

Entering edit mode

Question 2 (Online Assessment)

Description

Number of regions N "non parallel lines" divide the plane.

Approach

Let us look at the problem in an iterative way.

The first line divides the plane into 2 regions. After that, the Second line cuts both the regions into 2 more parts. Hence answer for 2 is 4.

For the third line, the plane is divided into 3 out of the 4 regions (for 2 line case) are divided into 2 more parts. And so on....

Hence, for the nth line, n more regions are created. While for the first line, 2 regions were created.

Therefore, the answer comes out to be 2+2+3+4+5...n = 1+1+2+3...+n = n*(n+1)/2 +1

int solve(int n)
{
    return (n*(n+1))/2+1;
}

This can be done in O(1). Take care of integer overflows.

ADD COMMENT • link 23 months ago hardik kapoor 130