Most viewed posts

781

https://walkccc.me/CLRS/

This website contains nearly complete solutions to the bible textbook - Introduction to Algorithms Third Edition, published by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

hope this helps :)

782

$$\textbf{Contents}$$

Web Page

Syllabus: 

 Topic Covered in Videos Video link from GO Youtube channel
  GO Videos
784

$\textbf{ECIL GET INTERVIEW EXPERIENCE}$

Experience shared by Saswat Swarup:

$\textbf{IOCL interview preparation and experience}$

Experience shared by Kishan Kumar:

Previous Year NIELIT Papers: Link

785
I-Interviewer, M-Me

Subject Chosen- Design and Analysis of Algorithms

I- You are comfortable with C right?

M- Yes.

I- You’ve an matrix, find the first occurrence of six consecutive ones in a row and replace by 101010, write a complete code including the declaration, skip taking the inputs maybe…

M- #include <stdio.h>

int main()
{
int i,j,n,c;
for(i=0;i<n;i++)
{ c=0;
  for(j=0;j<n;j++)
  {
    if(j!=(n-1)&&a[i][j]==1&&a[i][j+1]==1)c++;
    else c=0;
    if(c==5)break;
  }

( The code is incomplete, but due to time constraint which I guess they said to be 4-5 minutes, he said just tell me what you’re trying to do and then tried to explain.)

I- Given an array P with each element P[i] being a point in geometrical space, where consecutive array elements form a line,i.e., (P[0],P[1]), (P[1],P[2])…...(P[n-2],P[n-1]), (P[n-1],P[0]) are lines. Overall array P forms a polygon, you’ve libraries which can calculate intersection of lines and angle between lines in constant time. How’ll you check if they form a convex or concave polygon?

M- For all three consecutive point triplets (x,y,z) taken from the array, the angle formed by the line (x,y) and (y,z) should be less than 180 degree for convex.

I- For the same polygon, how will you check if they form a simple polygon or not?

M- calculate all possible lines and see if for all possible cases, any line other than adjacent ones intersect.

I- What’s the complexity?

M- exponential.(but I was wrong I guess)

I- Find in O(n^2), can show a pseudocode of what you’re doing...

M- gave a little vague pseudocode with mistakes.

The correct pseudocode might be:

for(i iterates over n lines)

    for(j iterates over lines starting from first to (i-1)th line and non adjacent to ‘i’th line)

        if(intersect(i,j))//intersect takes constant time

         { printf(“not a simple polygon”);

         break;}

        if(i==n) printf(“simple polygon”);

I- I think you get the logic, say it orally?

M- Since lines are formed by consecutive points, and there are ‘n’ lines in total, will iterate over all the n lines and check if it intersects the previous ones using the constant intersect checking function from the pre built library, this will give n^2.

(P.S.:- All of my algo questions were centered around this polygon thing, apology if I might have missed some questions)
786

I have been receiving a lot of messages related to college admissions. So, I’ll be doing a live streaming of QnA in youtube this Saturday at the below link. Please add any specific queries as comments to this blog so that I can be prepared :)

Edit: Time updated to April 2, 4:30 pm IST

https://www.youtube.com/watch?v=ybffnxiyDPg

787
Two query in single post.

1)I have been called for written/interview for Ph.D(after B.Tech) at IIT GN on 7th May.ISRO is also conducting written test on the same.Please comment on which should I ditch.

AIR 958(CS-Gen)

2)I have been called up for MS(R) at IIT Mandi on 14th May.ISI CAL has also written test on same day.Which should I choose?

And how good is CS in IIT Mandi?

Please Help!!
788

I Had only studied for 2 months for GATE 2018 and scored 517. When I checked IITB Cutoff For SC category, I found out that It was 500. So I satisfy their Cut Off for admission process. But does it mean I'll get a seat for Mtech ? an interview at least ? ... I know it is not a very good score, and I have already decided to study for GATE 2019. But still... I was wondering if it is possible for me to get admission this year... Also, Can anyone please explain what exactly the difference is between merely satisfying requirements and getting admission

 

PS: Any small detail will help, So, Please comment as soon as possible as I don't know whether I should fill the admission form or not ! ... and deadline is 11 - April - 2018

789

Applications for admission in M.Tech. (CSE, ECE & CB) 2023 starts from 20th March 2023.

For more details visit :

https://www.iiitd.ac.in/admission/mtech/2023

https://www.iiitd.ac.in/admission/mtech/2023/cse-details

https://www.iiitd.ac.in/admission/mtech/2023/faq

 

Good Luck aspirant...

790

GATE + TIFR updated book is now availble - you can download from http://book.gateoverflow.in

791

Topic was permutations and combinations. Some of the students said sir we already know this topic and we have studied it in 11th standard. So why waste time on it?

Sir smiled and said — I know.

Then he asked a question — “how many arrangements are possible for the word ‘bombay’”? And I think everyone must have solved this question. Then later on in the same class moving forward to a much more complex topic (identical ball in the box problem, circular permutations etc) we were so much concentrated on finding solution of these tough questions that our sir didn’t even took pen and answered all the complex questions in a tenth of a second.

He must have solved it in his mind, one may think. But how fast? Did he already knew what he was going to teach that day and so must have memorized all the answers, but then why would’ve he had said that now you make the questions using your imagination and I will answer them at the same speed. And he did that again. Then, at last when he answered how he was so fast in calculating those answers he said

I don’t know.

I know how to calculate the arrangements of the word Bombay and so I applied the same logic in every complex topic. He said he never crammed any formula (we used to cram formulas for these complex problems).

Not only for this subject, he did the same thing with every subject. Few years later, today when I was reading a quote by Mark Twain on the internet that — if you tell the truth, you don’t need to remember anything took me back to those days. It is we who make the problem complex ourself (in life too) and then feel bad for not able to solve. I can say this with my whole confidence that whatever subject he taught us I never tried to cram anything. I only uncovered what was covered at first, the whole truth. I religiously followed my teacher. I worked hard for a year but still after giving GATE (2020) examination (AIR 1248) only IIT Indore and IIITB were ready to send me an admission letter. This was a failure for me because I was studying to get into IIT Bombay. Clearly I rejected IIT Indore and IIITB.

Few days later when giving interviews to get a job, one of the interviewers said that you must be regretting now that you have wasted 1 year in preparation. I gently replied, Sir I have no regrets and I do agree that I failed. I accept that I am a failure. I still call myself a failure sometimes cause of failing a lot so often. But I have no regrets.

I am actually happy that I failed because after preparing so hard for that one year I realized that the destination was not the end goal rather it was the journey which we overlook often. In that 1 year I learnt how to deal with fear, anxiety, depression, family pressure, financial issues when all of them attack at the same time and on top of that you get diagnosed with MDD (major depressive disorder). If you don’t know about MDD it’s good. Physical pain is nothing when compared to the mental agony. MDD is a mental illness. On one side were these demons and on the other side was me alone. I was in tears during that time. I have no count of how much I would’ve cried during those days.

Here, one might ask — “why crying over a trivial exam?” A single piece of paper wouldn’t decide your future. Yes it’s true. But the journey which will lead you to the exam will decide what kind of person you will become. Remember the journey matters not any piece of paper ofcourse, if you continue to prepare till the end.

My frustration increased tremendously everyday to beat the topper in our coaching center (he got AIR 13 that year btw). It went on the whole year. I was determined that I will beat this guy. Me failing in GATE was the symbolic death of me against those demons which every aspirant must face in their journey. But as written in Shrimad Bhagavad Gita that those who die in war go to heaven too. I am proud that facing all those demons I accepted death instead of leaving the battleground.

So what if one may die because it’s the journey which leads to the destination is considered more important than the destination itself.

I learnt a lot in that one year of preparation for GATE. To date I am proud that I get to be taught by someone whom every part of personality I admire. Now sometimes I teach the same things to other needy students which I learnt from my teacher.

This was my story. If an average student from tier-3 college suffering with MDD can get 1248 rank in GATE then why can’t you get AIR 1. Always aim the highest. On then one end I was fighting with fear, anxiety, family issues,suicidal thoughts because of MDD and on the other end somewhere deep I knew that I will beat that AIR 13 student in this year’s exam. I always aim high. Aiming lower is a sin. Never do that. Aim so high that you aren’t even hesitant to die for your aim. It’s not like people who get AIR 1,2,3 doesn’t feel pain, stress. Even the strongest of the strong feel fear.

Karna was feeling fear too in the final battle v/s Arjuna, as said by his charioteer.

When our sir said “how many arrangements are possible of the word ‘bombay’?” he must’ve unconsciously said to every student sitting there that their target is IIT Bombay. That’s what I think.

So that one year of preparation has made me a very strong person from inside. Whenever I aim, I aim for highest. Aiming low is a sin. Don’t be a sinner.

Current situation: I am working in a startup and earns enough that the thoughts to go in FAANG doesn’t enter in my mind. I teach some students too. I am still suffering from MDD and I take medications for it. I lift weights and it’s been 3 years doing that.

My website: https://darshan.sh

792
I have found gateoverflow.com great help. Specially previous year paper that were put by site for practice purpose were great help in last time of preparation and they also boost my confidence. And all of the answers on previous year are well debated and beautifully explained. Thanks to Arjun Suresh Sir who made it possible.

PS i got AIR 174 in 2017
793

Science and Engineering Research Board (SERB), a Statutory body of the Department of Science and Technology, Government of India has launched SERB Overseas Visiting Doctoral Fellowship (SERB-OVDF) Scheme for creating a talented pool of internationally active and trained manpower.

The Scheme offers opportunities for PhD students admitted in the Indian institutions for gaining exposure and training in overseas universities / institutions of repute and areas of importance to country for period up to 12 months (extendable up-to a maximum of six months on case-to-case basis, based on performance evaluation) during their doctoral research.

The selected fellows will be paid a monthly fellowship amount equivalent to US $ 2000, one-time Contingency / Preparatory allowances of Rs. 60,000/- to cover visa fee, airport transfer charges, medical insurance etc. The selected fellows will also be provided shortest route economy class air fare from their place of work in India to the place of the host institute and back. One additional to and fro travel cost would also be provided to the fellow, if the period of stay is one year or more. Students should make their own arrangement for accommodation etc. One visit, each by the Indian supervisor to the Overseas Institution where the student is working and overseas faculty to the host Indian Institution of the student during the tenure of the fellowship is also admissible under the Scheme.

Call for proposals under this scheme will be open from 1st May to 30th June, 2018. Eligible researchers are encouraged to submit their proposals through online system (www.serbonline.in).

Important to note that the application is considered only if the student/supervisor engages in collaborative research with the foreign host.

To know more about the scheme, kindly visit the link below:

 http://serbonline.in/SERB/ovdf

 With regards

Team SERB Online

794

GATE(CS)-2018 AIR - 491 Marks-56 Category-General Like you all, I was an ordinary student having AIR 1,02,786 in JEE. Got into tier-3 college ; struggled with the Engineering Graphics; 96 rank out of 130 rank in IT branch; Broken after failing in 1st semester in college; trying to find what to do in life; GATE or CAT or UPSC or ARMY or MS(USA). searched whole internet, seen that in CAT you need high percentage of marks in 10th and 12th which was not in my case in 12th. even if you clear toughest exam CAT with the competition all around India; you need to face the interview which is really really tough. Also in CAT the work experience plays a key role which as a fresher I would not be having. Also because of diversity policy in MBA colleges, the entrance of engineer becomes tough. Being in general category and failing in first semester, I thought even if I prepare for CAT, I will screw my BTech which eventually will harm the interview of CAT. I am MCQ fan. I love playing with four options by my side.so I know I am not going to write UPSC as they ask aspirants to write an essay and GK which I am not at all interested. My parents didnot allow me to go to ARMY. Also I didnot want/unable  to take loan in order to do masters in USA as my father rejected the request. With all in mind in the 1st year break,I decided to appear for GATE. In the third semester, I started finding tutions for GATE(both online and offline).In 4th semester I took online classes from well-known teacher as I liked his way of teaching. I struggled with the syllabus; struggled with college exams as every month there was an exam waiting for me. Hear the GATEOVERFLOW community, GEEKSFORGEEKS helped me a lot with solutions of previous years.Fast Forward sixth semester came, I started preparing for campus interview as backup.Left GATE. got selected in Infosys. after resting for few days, I started preparing for gate. I realised that I have forgotten the concepts.I again tried to study but this time not to enter IIT. but to get a good job in Bengaluru.I applied for another company and left GATE to prepare for Interview.Company rejected me.At that point I came home and started solving DBMS. which I was not able to solve any of the five I tried to solve.One month before the exam, I left GATE preparation, On the Makar Sakranti , My father came to know that I have left preparation as I was flying kites whole day. fast forward GATE exam day, I went to the centre with zero expectation seen the screen, I was waiting since three years.solved the questions without any fear, without any expectation ,full of confidence, somewhat fear of negative marking. thought paper was easy. everyone who had prepared will get good marks. forgot the paper and got in internship mode. Shocked seeing marks in Praggys app. Thought everyone would be getting these many marks. This was not the case now.Others felt the paper tough. Seeing rank AIR - 491 on screen looks awesome.

795

I have achieved AIR 8 in GATE CS 2024 as well as AIR 17 in GATE DA 2024 in my final year of B Tech. and all this was possible because of my parents' support as well as my friends who helped me throughout my preparation. I am thankful to GateOverflow for providing a platform for quality discussions and GO Classes for providing the best test series for GATE CS with very good conceptual questions which helped me build my problem-solving skills.

As I had not taken any coaching, I dedicated some time in starting of my preparation to find the best resources. Though there were many resources that I have studied from throughout my preparation, I am sharing some of the resources that I found were excellent for building basic concepts.

List of standard books that I followed:

Subject

Name and Author

Algorithm and DS

  • Introduction to Algorithms, by CLRS (3E)
  • Algorithm Design, Jon Kleinberg and Éva Tardos

Discrete Mathematics

  • Discrete mathematics and its applications by Kenneth H. Rosen (Indian 7E)

Computer Networks

  • Data Communications and Networking by Behrouz A. Forouzan (5E)
  • Computer Networking: A Top-Down Approach (7E)

Theory of Computation

  • An Introduction to Formal Languages and Automata by Peter Linz (6E)
  • Introduction To the Theory Of Computation - Michael Sipser

Compiler Design

  • Compilers: Principles, Techniques, and Tools

Digital Logic

  • Digital Logic and Computer Design by M. Morris Mano

Computer Organization

  • Computer Organisation by Carl Hamacher
  • Computer Organization and Design: The Hardware/Software Interface by David A Patterson and John L. Hennessy (5E)

Operating System

  • Operating Systems by Avi Silberschatz, Greg Gagne, and Peter Baer Galvin (International 9E)

Databases

  • Fundamentals of Database Systems by Ramez Elmasri and Shamkant B. Navathe (7E)
  • Database System Concepts Book by Abraham Silberschatz, Henry F. Korth, and S. Sudarshan
     
Probability
  • First Course in Probability, by Sheldon Ross

List of Courses/Video Lectures I followed:

Subject

Course/Resource Links

Algorithm and DS

Amazing  and intuitive lectures

Can audit the course and find quiz online (quiz questions are very good!)

Discrete Mathematics

Very good lectures with proofs and intuition!

Computer Networks

Best Videos on Computer Network

Theory of Computation

Best lectures for TOC and very intuitive (Must Watch for TOC!)

Computer Organization

Will cover basic of OS and COA

Best videos I found for Multilevel Paging and Cache

Operating System

Will cover basic of OS and COA

Digital Logic

Covers everything

DBMS

All three courses are very good

Compilers

Very good Course but some topics for GATE are not covered so refer NPTEL/Book

Linear Algebra

Best lectures for Linear Algebra

Highly recommend these videos for intuition

Probability

Best Lectures on Probability!

https://www.probabilitycourse.com/

Calculus

Very good videos on Calculus

Group Theory

(On Coursera, there is an option to audit the course and watch videos for free and can also find the quiz questions online)

Some points about resources:

  • Some of the courses have content beyond the GATE syllabus as well some of which I studied because I was enjoying that, but that can be easily be filtered out by looking at the topics in GATE syllabus pdf.
  • Multiple books/courses do not necessarily mean I studied from both resources fully, I referred to other books/course when some topic had little content in one resource or I had doubts even after studying from one resource.
  • Discussion is very important when learning something since it provides different approaches to the problem. I had discussions on GATE subjects and other related things with my friends in college which made me realize gaps in my knowledge and also helped me see new ways to approach many problems. For this, can also join groups online.
  • For doubt solving, I would recommend searching various resources (top university articles/ppts or books) for the specific topics and reading discussions on stackoverflow or gateoverflow. It might take time but you will learn much more about the topic after thinking about it yourself and reading the discussion with different approaches.
  • Some subjects require more time than others, so don’t try to rush any subjects.
  • PYQs are the most important part of preparation, don’t skip them.
  • Can also try out NPTEL assignments or relevant assignments of top universities.
  • The only trick I know about solving questions faster is to practice more questions, so I can only recommend the same trick.
  • Revision is necessary.
  • Try to reduce Silly Mistakes! (Most Important! Mere aise questions glt hai exam me silly mistakes ki vjh se jo bina preparation walo ne bhi shi kiye honge)
  • Don’t be restricted to just the resources shared, explore, prepare well and enjoy learning

 

There are many other things which can be found on many toppers’ interview on youtube but I feel like some of those things are subjective. Some make long notes, some make short notes, some don’t make notes and some even keep a notebook of mistakes. I made long notes of some subjects, short for some and for some did not make any notes (don't recommend this though).

For test series, I fully recommend GO Classes test series since their questions were from very good and standard resources (Some questions I recognized from the assignments of top university/courses in the tests :P) which will help in building concept as well as applying all those concepts (Loved the AIMTs since a lot of aspirants are giving exam at the same time so it feels like real GATE exam). I personally don’t think there is need for multiple test series as I couldn’t even attempt all the tests in GO Classes test series until the end and was able to attempt only 5 test from one other test series.

Most of these resources I had compiled from various blogs(mentioned below) and https://gatecse.in/

Some useful blogs for more resources:

 

796

Some memory based questions:

  1. Time complexity to find the maximum element in the min heap and explain the method?
  2. Given an array of length $n$ and a number $x$ find out two such elements in the array such that their sum is equal to the number $x.$
  3. Given an array of length $n,$ find two numbers such that their sum is equal to the rest of $n-2$ elements if there exist such case?
  4. Two linked lists are given and due to programming error end node of first linked list is now pointing to some node of second linked list, how will you find that node? and you don't know which one is $1^{\text{st}}$ linked list and which one is $2^{\text{nd}}.$ The data values are not distinct.
  5. Define joint probability in terms of conditional probability?
  6. How will you find a cycle in a directed graph? some questions on forward edge and back edge.
  7. Sort an array of $n$ elements with k distinct elements optimally. How will you find the distinct elements in the array optimally
  8. A $n\ast n$ matrix is given such that $A_{ij} = A_{ji},$ what will be the rank of this matrix?
  9. How many different values a random variable can take with zero variance and why?
  10. Prove that a directed acyclic graph has atleast one vertex with zero indegree.
  11. Various ways to solve subset sum . Variations of the same problem.
  12. Algorithm to get maximally connected graph having two components.
  13. Suppose we have $A\ast B.$ If we know determinant of $A$ is $1.$ What can we tell about Rank of $A\ast B$ in terms of $B.$
  14. Give $O(k\log k)$ algorithm for finding $k$ minimum element.
  15. Prove two vertices of a graph have same degree.
797
Hello folks,

I am very thankful to GateOverflow which makes my dream comes true... I am selected as a Assistant Engineer in PTCUL and all credits goes to GO and all helpful members of this site. From this site I had learn a lot. I just do all previous CBSE NET papers and GATE papers from this site, and go through the comments of each answers and learn many things about the topics which are new for me.. So guysss do ur hardwork...one day u will get ur destination... God bless uhh alll :)
798

Reaching Gandhinagar

The airport nearest to IITGn is Sardar Vallabhbhai Patel International Airport in Ahmedabad. Once at airport, it takes 20-25 minutes and approximately Rs. 300 to reach the campus. Once in campus, report to Gate 2. Though they didn’t mention about providing accommodation but once I was there, they allotted me a room in their hostels with a nominal charge of Rs. 250 per day. The dining hall was next to the hostels. Dining charges were Rs. 49 for lunch and dinner, Rs. 35 for breakfast. The rooms were quite awesome, each had an air-conditioning system installed and other things unlikely to be found in an IIT hostel.


The Interview Day


They asked all the CSE students to assemble in a hall. After an orientation session about the intake and the general guidelines, they divided the students into two batches for the written test. The written test, as they were trying to hint, was focussing majorly on testing the ability of students to code.


Coding Test


The coding test was on the platform of HackerRank. The test supports almost all the languages. The use of STL and languages like Python were also available. The coding questions were:
1. We are given a keyboard. Standing on a key, it takes 0 second to press the key. 1 second to move to all the adjacent keys and 2 second to all the keys next to the adjacent keys i.e.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Suppose we’re standing on key 4, it takes zero second to press the key, 1 second to go on keys 1, 2, 5, 7 and 8 and 2 seconds to go on keys 3, 6 and 9. Given two strings, one containing the configuration of a keyboard and the other one denoting the sequence of number to be types, find the time the system will take to type the complete sequence.
e.g. str1 = “123456789”; str2 = “15235”
key 1 = 0s
moving on key 5 from 1 takes 1s
moving on key 2 from 5 takes 1s
moving on key 3 from 2 takes 1s
moving on key 5 from 3 takes 1s
Therefore, the answer is 4.
2. Given an array, find an index, such that the summation of all elements on the left of the index is equal to the summation of elements on the right.
e.g. arr = [1,2,3,4,6]
ans: 3 (0 based indexing)
3. Given an upper limit U, lower limit L and variable K, find a and b such that L<=a<b<=U and a^b<=k is maximum.
4. Given a sequence of numbers, for each duplicate number present in the sequence, increment it until all the elements in the sequence become unique, such that their sum is minimum as possible.
5. (I don’t remember the language of this question)
Given an adjacency matrix, find the number of connected components in that graph.
Following this, there were 15 MCQs problems based on caching, time and work, graph theory, algorithms, probability and data structures.
Out of approximately 250 students, 75 students were shortlisted for the interview. The interviews began at 2 and were done by 6 in the evening.


Interview


Q. Introduction: done
Q. Given two very big numbers, unable to be held by any variable, how will you add them?
A. Reverse them and store them in array and add each cell etc.
Q. Given two numbers, without using comparator and arithmetic operator, how will you tell whether they are equal or not?
A. XOR them inside if statement and not(!) the whole
Q. Did any projects on machine learning?
A. Explained digit recognition using back propagation algorithm with structure of perceptron models, learning rate, mean squared root error and all.
Q. Any questions from our side?
A. No Sir.
This was my interview experience at IITGn, I made it to the final admit list. Hope it helps.

799

There is nothing much available about the JEST exam anywhere so decided to make a collection of the questions which were asked in this year’s exam. Hope it will help future aspirants.

Here is the link:JEST 2019

If you find any question missing, post it as a comment, I will add it to the list.

800

We are happy to announce a scholarship test for the students who want to prepare for GATE 2023. 

Exam starts

 

DATE: 7th AUGUST 2022
STARTING AT: 2:00 PM

Scholarship up to 100% for 200 Students

Top 25 rankers - 100% scholarship

26-50 rankers - 75% scholarship

51-100 rankers - 50% scholarship

101-200 rankers - 20% scholarship

Syllabus: C programming and Discrete Mathematics (Graph Theory, Set Theory, Combinatorics, Functions, Recurrence Relations)

WATCH GO CLASSES C-PROG, DISCRETE MATHEMATICS COURSES TO MAXIMIZE THE CHANCES OF GETTING FULL SCHOLARSHIP

Full video about the test: https://www.youtube.com/watch?v=hmxgaZIVX50

Registration of Scholarship Test: https://docs.google.com/forms/d/e/1FAIpQLSf4gi8R3MaOtQpto_t1lVKHNeXiRaNva992QWS-UerPMhDkQw/viewform