## Ceiling in right side for every element in an array

Given an array of integers, find the closest greater element for every element. If there is no greater element then print -1

Examples:

Input : arr[] = {10, 5, 11, 10, 20, 12}
Output : 10 10 12 12 -1 -1

Input : arr[] = {50, 20, 200, 100, 30}
Output : 100 30 -1 -1 -1

A simple solution is to run two nested loops. We pick an outer element one by one. For every picked element, we traverse right side array and find closest greater or equal element. Time complexity of this solution is O(n*n)

A better solution is to use sorting. We sort all elements, then for every element, traverse toward right until we find a greater element (Note that there can be multiple occurrences of an element).

An efficient solution is to use Self Balancing BST (Implemented as set in C++ and TreeSet in Java). In a Self Balancing BST, we can do both insert and ceiling operations in O(Log n) time.

 `import` `java.util.*; ` ` `  `class` `TreeSetDemo { ` `    ``public` `static` `void` `closestGreater(``int``[] arr) ` `    ``{ ` `        ``int` `n = arr.length; ` `        ``TreeSet ts = ``new` `TreeSet(); ` `        ``ArrayList ceilings = ``new` `ArrayList(n); ` ` `  `        ` `        ` `        ``for` `(``int` `i = n - ``1``; i >= ``0``; i--) { ` `            ``Integer greater = ts.ceiling(arr[i]); ` `            ``if` `(greater == ``null``) ` `                ``ceilings.add(-``1``); ` `            ``else` `                ``ceilings.add(greater); ` `            ``ts.add(arr[i]); ` `        ``} ` ` `  `        ``for` `(``int` `i=n-``1``; i>=``0``; i--) ` `           ``System.out.print(ceilings.get(i) + ``" "``); ` `    ``} ` ` `  `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int``[] arr = {``50``, ``20``, ``200``, ``100``, ``30``}; ` `        ``closestGreater(arr); ` `    ``} ` `} `

Time Complexity : O(n Log n)

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Article Tags :

Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.

## TCS NQT 2018 (Recruitment Exam)

I am from “Institute of Engineering and Management, Kolkata”.

Round 1: TCS conducted a National Qualifier Test (NQT) as the first round of recruitment process this year. There was no concept of Campus Recruitment had happened this year. They fixed two specific dates for this NQT exam that was 2nd September 2018 and 3rd September 2018. There were 3 slots for each day. Question sets were the same for all for the same slot but different for either slot.

There were four sections in that online exam with sectional cut offs. four sections are 1. English test 2. Aptitude test 3. Computer proficiency test 4. Coding test.

My slot timing was in the 3rd slot on 2nd. English section was pretty much normal basically fill in the blanks type. In the aptitude section, there are two subsections one is normal and another is advanced. Computer proficiency section was also the same type and many questions were asked from ds and c-programming code snippet. And the last section was the Coding section.

Results were declared via mail on 8th September and I was luckily qualified in the first round. From our college, almost 650 students appeared for that exam and 413 students are qualified for the F2F interview.

Round 2: On the very next day of the first round result declaration I got another mail from TCS for the Interview date and place which was conducted on TCS Gitanjali Park office, Kolkata.

I had my interview on 11th September from 12 p.m and onwards. I arrived at the TCS office at 11.30 a.m. After waiting for a long I got my call around 4.15 p.m.

Now here I am going to share my interview experience. I will write interviewer 1 as I1, interviewer 2 as I2 and myself as M :

.

.

M: May I come in?

I1: Yes.

M: Good afternoon sir, good afternoon ma’am.

<< without giving any reply back >>

I1: Mainak, tell me the basic difference between the Ipv4 and Ipv6?

<<I have not mentioned “networking” in my resume >>

M: …. somehow manage to answer very basic.

I1: Seems not so happy. ” you are giving an answer, like a class 5 child”. Then again asked a question from networking.

I1: what is your final semester subsects?

M: After a big pause… Sorry, sir! I don’t know as currently, I am in 7th sem.

I1: So what is your 7th sem subjects and 6th sem subjects?

M: Ans with confidence.

<<As I was not prepared for this kind of questions. I lose my confidence took permission for having some water in between the interview process>>

I1: Final year project related questions

M: Ans with confidence.

I1: DBMS related questions

I1: Questions related to Extracurricular activities and some questions related to marketing.

M:  Manage to answer every question.

<In between this I2 was only observing me and my answers…. Not a single question was asked by her>

After the Interview, I was asked to wait outside. Again after waiting a long I was asked to leave for the day.

.

.

A few days later, results out and as expected my name was not there in the list.

From the 413 qualified students, only 192 students got the offer letter.

I can say Luck really matters a lot in case of every interview. If you get a good panel you will be hired easily.

Best Of Luck!!!!!!!!!!!!!

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Article Tags :

1

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.