5 weeks ago

John 910

Hyderabad

Tentative Location: Bangalore, Hyderabad

CTC: 32.85 LPA

In-hand: 17.85 LPA

Shortlisting criteria:

CGPA - 7

ELIGIBLE BRANCHES - (btech/idd) CSE, ECE, MAT, EEE, Phy

Number of Rounds: 4

ROUND-1

Round 1 was coding round in which there were multiple sets , my set consisted of 1 coding question, in which an array was given and a max_price and min_price was given and we have to find the number of subarrays in which the maximum element is the max_price and minimum element is the min_price. Other than coding questions there was 1 question based on SQL, and another question based on rest API, you can practice questions on SQL and Rest API from HackerRank. Other than this there were 6 MCQs based on data structures and algorithms.

ROUND-2

Round 2 was offline interview round, the interviewer first started with a brief introduction, then as I was from electronics background, he asked me to tell some of the subjects that I have studied in my last 1 or 2 sems, I named them after that he asked me some questions on digital electronics, which were about logics gates, De Morgan's Law and implementation of some gates using NAND gate. After this he asked me to write code for removing duplicate elements from a sorted linked list and reversing it. I wrote the code on paper and completely explained it to him, he was satisfied and then he moved on to my resume and asked me to explain one of my project based on opencv and Machine Learning, I explained it to him step by step and he was totally convinced with my explanation, there were no cross questions after that and this round of interview ended here.

ROUND-3

Round 3 was also an offline interview round, this time also the interviewer started with an introduction, after that he looked at my written work from the previous interview, and then he started asking some of the OOPS concepts . He asked me about a pure virtual function and Abstract class. I explained to him both.

Next he asked me to explain my Google Internship project . I explained my working and the use cases of the product in depth and he was totally satisfied . As I worked in Java during my internship , the interviewer asked me about garbage collection in java , I was not able to answer it.

Then the interviewer moved on to the coding part and asked me to write the code of swapping two numbers without using a third variable, I wrote the code on paper and explained it to him, then he asked a question in which there are numbers from 1 to n and 1 number is repeated and we have to find the repeated number, I told him the approach in which we can sum up all the given numbers and subtract the sum of numbers from 1 to n from that, thus this will give our repeated number.

At the end he asked as if I had any questions for him. I asked him about his favorite part about Oracle and the work culture out there.

ROUND-4

Round 4 was an HR round, and the interviewer started with a brief introduction about me. He then asked me about why I want to work in Oracle. I answered him by stating the awesome work culture out there and the supportive environment. He then reversed the question and asked me what Oracle will get on hiring me. I answered him by pointing out my strengths and points of interest which would favor Oracle (I said that Oracle will get a totally hardworking and enthusiastic person who is very strict to deadlines). He was happy with my answer.

Then he asked me about my Google Internship project, I explained it to him starting with the goal, motivation, scope, tech stacks used and difficulties I faced during the project, he then asked me whether it was a solo project or a team project, I told him that it was a solo project, then he was impressed a lot and even told me that this is really great that you have completed this whole project in just 2 and half months even while using java for the first time. That was a plus point for me.

He then asked me about what failure is according to me and whether you have ever faced failure according to your definition. I told him that according to me if I worked a lot for something and still can't achieve it, I define it as my failure. And I told him that I have faced failure during the first semester of my college and my grades totally represents it, he further asked me how did I faced that situation and I told him that I am not a person who is used to failure and after that fall down of mine I worked so hard to achieve what I have lost, further I said to him that you can see the grades in my second semester in my resume, that was the result of my outcome. (My resume had a big change in the grades from first to second semester which I showed him ) He was very happy from my reply.

Then he asked me whether I faced a situation in which I thought that I could make a software to make this process better. He also asked about my greatest achievement, and where I think I will be in 5 years. He also asked me if I have any future study plans, if yes then what and why. He even asked me that as I am from an electronics background so does being an electronics student helped me to grow in the coding field, if yes how. I explained each and everything very positively to him and he was totally satisfied. At last he told me that it was a very nice conversation and thus it ended really well.

RESULTS

7 people got the offer and luckily I was one of them.

11 weeks ago

Ayush Gangwani 1.2k

New Delhi

Solution to Coding Round Problem 1

First of all, the problem can be solved in a total of O(N^3) or O(N^2) time by naively bruteforcing L and R, but it will result in TLE (Time Limit Exceeded) as N≤2×10^5. So we will introduce the way to solve this problem in a total of O(N) using a proper algorithm.

First, although this problem asks to find the number of pairs of integers (L,R) that satisfy certain condition, but from another point of view, it can be rephrased as follows:

How many subarrays AL​,AL+1​,…,AR​ of A have the maximum value X and the minimum value Y ?

Transforming the problem on counting (L,R) into that of counting segments makes easier to break down. However, the problem is still troublesome, so let us take a closer look at what kind of subarrays satisfy the condition in order to simply the problem. Consider the following case:

A=[4,2,5,4,3,4,2], X=4, Y=2

In this example, A3​=5 is troublesome. Since A3​=5 is greater than X=4, any subarrays that contains A3​ does not satisfy the condition. Such an element imposes us a rather complex case division. On the second thought, as any subarrays that contains A3​ does not satisfy the condition, we can just remove A3​ from the sequence and split it off at that element, and count the number of subsequences for each sequences. That is, letting A1​ the first two element and A2​ the last four elements, we can solve the problem for the following two cases:

• A1​=[4,2], X=4, Y=2

• A2​=[4,3,4,2], X=4, Y=2

and then find the sum to obtain the overall answer.

This is the same in a general case. If Ai​ does not satisfy X≤Ai​≤Y, we may remove Ai​ to split the sequence off, and find the number for each subsequences.

Let B be a sequence that was split off by the operation above. All we have to solve is the following Subproblem 1.

Subproblem 1

• How many subarrays BL​,BL+1​,…,BR​ of B has the maximum value X and the minimum value Y? Here, each element of B is between Y and X (inclusive).

The condition emphasized by boldface is added compared to the original problem. In fact, we can make use of this condition to further rephrase the subproblem. As we know that each element is between Y and X, “the maximum and minimum value is X and Y, respectively” if and only if “X and Y are both contained in the subsequence.” Therefore, it is sufficient to solve the following subproblem fast enough:

Subproblem 2

• How many subarrays BL​,BL+1​,…,BR​ of B contains both X and Y?

If we can solve the problem in a linear time, that is, in O(∣B∣) time, then the overall complexity will be O(∑B∈(the set of divided subsequences of A)​B)=O(N), as the sum of lengths of subsequences does not exceed N.

There are several ways to solve Subproblem 2. We will introduce it one by one.

Solution 1: Sliding Windows

Hereinafter we denote BL​,BL+1​,…,BR​ by “segment [L,R].”

In Subproblem 2, the following property holds:

• If segment [k,l] contains [i,j], that is, if i,j,k, and l satisfy 1≤k≤i≤j≤l≤∣B∣, then if segment [i,j] satisfies the condition, [k,l] also satisfies the condition.

In this case, we can count the number of segments that satisfy the condition by the following algorithm.

• First, let L=R=1.
• While L does not exceed N, do the following operation.
  • While [L,R] does not satisfy the condition, add 1 to R.
  • Once a [L,R] that satisfies the condition has been found, we know that every segment [L,x] (R≤x≤B) satisfy the condition, so add that amount to the answer.
  • Add 1 to L.

The algorithm of iterating through all minimal segments by sliding the both ends one by one like this is called “sliding window” trick. Since the number of times that L and R are incremented is bounded by ∣B∣, the total complexity is O(∣B∣) if the condition is judged in an O(1) time each.

The following is a pseudocode

calc(B, X, Y):
  i, j, countX, countY, res = 0, 0, 0, 0, 0
  while i != len(B):
    while j != len(B) and (countX == 0 or countY == 0):
      if B[j] == X:
        countX += 1
      if B[j] == Y:
        countY += 1
      j += 1
    if countX > 0 and countY > 0:
      res += len(B) + 1 - j
    if B[i] == X:
      countX -= 1
    if B[i] == Y:
      countY -= 1
    i += 1
  return res

solve(A, X, Y):
  i, ans = 0, 0
  while i != N:
    B = []
    while i != N and Y <= A[i] <= X:
      B.append(A[i])
      i += 1
    if len(B) != 0:
      ans += calc(B)
    else:
      i += 1
  return ans

Solution 2: inclusion-exclusion principle

Another model solution is that of using inclusion-exclusion principle. Inclusion-exclusion principle is very frequently used in combinatorics problems. Especially, when there are two conditions, the following two equations are well known.

• (The set where at least one of P and Q is true) = (The set where Pis true)+(The set where Q is true)−(The set where both P and Q are true)​

• ​(The set where both P and Q are true)=(The entire set)−(The set where P is true)−(The set where Q is true)+(The set where both P and Q are true)​

If you remember the high school class of “set and logic,” it may be easier to understand using Venn’s diagram.

What we want to find is the number of subsequences that “contains both X and Y.” By applying inclusion-exclusion principle to this condition, it can be represented as follows:

​ (All sequences)−(Sequences that does not contain X)−(Sequences that does not contain Y)+(Sequences that contains neither X or Y).​

In fact, “sequences not containing blah blah” is easier to count than “sequences containing blah blah,” so the problem can be solved by applying inclusion-exclusion principle like this. (For details, refer to the sample code.) The time complexity is O(∣B∣).

f(a):
  ret, s = 0, 0
  for x in a:
    if x == 1:
      ret += s * (s + 1) // 2
      s = 0
    else:
      s += 1
  ret += s * (s + 1) // 2
  return ret

solve(N,A,X,Y):
  __, X_, _Y, XY = [0] * N, [0] * N, [0] * N, [0] * N
  for i in range(N):
    if not (Y <= A[i] and A[i] <= X):
      __[i], X_[i], _Y[i], XY[i] = 1, 1, 1, 1
    if A[i] == X:
      X_[i], XY[i] = 1, 1
    if A[i] == Y:
      _Y[i], XY[i] = 1, 1
  return (f(__) - f(X_) - f(_Y) + f(XY))

3 months ago

Ujjwal Srivastava 320

Bengaluru

Round 3 Q-2

Overview

• Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

• There is only one repeated number that occurs twice in nums, return this repeated number.

• Try to solve the problem without modifying the array nums and using only constant extra space.

Solution

• An easy and efficient approach would be to calculate the sum of numbers in the array nums. Let it be sum1.
• Calculate the sums of numbers from 1 to n which is ((n)*(n+1))/2. Let it be sum2.
• At last, the answer would be sum1-sum2 because sum1 contains 1 extra element apart from elements from 1 to n.

Pseudo Code

ll n = nums.size();
n--;
ll sum = 0;
for (auto it : nums)
    sum += it;

ll sum2 = ((n) * (n + 1)) / 2;
return (sum - sum2);

3 months ago

Lokesh Wagh • 0

Prayagraj

#include <bits/stdc++.h>
using namespace std;
void clear(stack<int>&st){
  while(!st.empty()){
    st.pop();
  }
  
}
int main() {

  int n,x,y;
  cin>>n>>x>>y;
  vector<int>arr(n);
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  
  int xoccur = n;
  int yoccur = n;
  int xgreateroccur = n;
  int ysmalleroccur = n;
  long long count = 0;
  for(int i=n-1;i>=0;i--){
    if(arr[i] == x){
      xoccur = i;
      
    }
    if(arr[i] == y){
      yoccur = i;
    }
    if(arr[i] > x){
      xgreateroccur = i;
    }
    if(arr[i] < y){
      ysmalleroccur = i;
    }
    int st = max(xoccur,yoccur);
    int ed = min(xgreateroccur,ysmalleroccur);
    count += max(ed - st,0);
  }
  cout<<count<<"\n";
  return 0;

}


question 1 solution