Big O – How to calculate it?

Say that you need to perform a task, and that there are 2 algorithms, say A and B for performing that task. Let A finishes the task in time TA and B finishes it in time TB. If we can show that TA is less than TB, then algorithm A is indeed faster than algorithm B.

We test both the algorithms for an input of size n0, and we see that TA(n0) < TB(n0). That means that algorithm A is indeed faster than algorithm B for input size n0. But we won’t be using the same input size n0 all the time. We need to be able to use different input sizes depending on the application. But if we can show that TA(n) < TB(n) for all values of n > 0, we can prove that algorithm A is indeed faster than algorithm B, irrespective of the input size. But we have no idea on how big or small n is, and a function is not always less than or equal to another function throughout the entire set of input sizes. To solve that, we have the asymptotic analysis.

Asymptotic analysis removes all the dependencies like hardware, OS, compiler and various other factors, and gives us a relation based purely on input size n. There are various classes of asymptotic, like the big O, theta, big Omega, little o, and little omega. Each of these can be used to calculate a relation between the running time of an algorithm (for time complexity) with its input size n. All other factors are ignored.

Big notation is used for creating an upper bound for an algorithm. It means that whatever happens, the algorithm shall not take more time than what’s shown by the big O notation. So big O notation are used mainly for worst case analysis. We shall strip off low order terms and constants to generate a relation purely on the input size n.

Say that you need to search for a telephone number from a listing of telephone numbers, What shall you do? You shall start at the top and goes down to the bottom, by comparing each telephone number with the number that you need to search for. This is what call a sequential search or linear search. If you add 1 more telephone number to the listing, you shall need to search for 1 more number only (assuming that the number you need to find has not be found). So if you add n telephone numbers, you just need to search atmost n times to find the number. So we call it linear time complexity or O(n).

Suppose you need to search for a word in a dictionary, say “Good“. Will you start at A in the dictionary and then do a linear search for every single word in the dictionary, until you find the word? No, you wont. Because linear search is time consuming in this occasion. So what shall we do? We shall try to get to the middle of the dictionary. The word we need to find shall be in either of the halves. We shall go to the either of the halves and keep dividing the dictionary, until we find our word. Since we halve the dictionary at each step, the number of steps get divided by 2 in each step. That means that its a logarithmic complexity or O(log n). In asymptotic analysis, we do not think about the base of the logarithms. The reason is because to convert from a logarithm of one base to another, we just need to multiply by some constant, and since we ignore constants in asymptotic analysis, they have no importance.

Suppose you need to find the element in an array at the index 5 (So you need to find the value of a[5]). You do not have to search through a[0] to a[5] to determine the value at a[5]. A simple lookup at the a[5] shall get you the answer. Whatever the value of the element at a[5], you just need a simple lookup. It means that the time for the operation does not depend on the size, and rather needs only a constant time. This is what we call constant complexity or O(1).

When we say that the running times of 2 algorithms are asymptotically the same, it doesn’t mean that their running times are the same. For example 100n lg n and 2n lg n are asymptotically same (because the constants are ignored), though their values are not.

How do I get an internship at Google?

Among all the internships that Google offers, Software Engineering internship is the favorite and have more number of openings. Given below is the list of qualifications that Google seeks in their prospective interns,

  • Experience in systems software or algorithms
  • Excellent implementation skills (C++, Java, Python)
  • Knowledge of Unix/Linux or Windows environment and APIs
  • Familiarity with TCP/IP and network programming

These are their preferred qualifications, and you need to make sure that you do indeed qualify. Have a look at Students – Google Careers.

To get the internship, the first step should be making sure that you do get an interview. More than 50k apply for Google every summer, and only about 25k get the first interview. So you need to make sure that you get that first interview. Its not easy as it sounds. When you submit your application, you need three things: resume, cover letter and transcript.

Google needs transcript because they do look at how you have done in your CSĀ  subjects. If you are not a CS student, make sure that you do some CS courses, be it in your university or through Coursera, Edx or similar sites. Its better to have good scores in these subjects. Low scorers doesn’t mean they don’t have the required knowledge. Its just that high scorers simply had put in the effort and hence probably are hard workers.

In the cover letter, write why you are suitable for the internship. Have a look at the qualifications, and make your cover letter accordingly. Say for example, they need people proficient with TCP/IP and networking, make a networking app like a simple HTTP server, a port scanner or something similar.

In the resume, you need to have something worth looking at. At Google, candidate selection is done through various stages. Only if you pass all those stages shall you get the first interview. The best way is through employee referrals. If you know someone who works at Google and can refer you, your chances of getting that interview is very much improved.

Make sure you do some personal projects. Contribute to open source. Mastering the basics of Python is an easy task. Learn Tkinter or some other GUI based libraries and make some GUI apps. Host it on Github. Continue making more projects.

Once you get the first interview, then all that matters is how you perform in the interview. You need to be thorough with data structures and algorithms. Study from CLRS and other algorithms book. Implement them in your language of choice. Start competitive programming.

Get that interview at Google

Google receives about 3 million applications a year. Thats roughly about 12000 applications every business day. A simple LinkedIn search reveals that Google has some 1200 recruiters all over the globe, which means every Google recruiter handles on average 10 applications every business day. That’s some pretty wide hole for any applicant to get noticed by a recruiter, right?

Wrong. A recruiter has much more work than to look through applications 8 hours a day. They need to scour through LinkedIn, StackOverflow, Github and other job boards in search for prospective candidates. They to need evaluate skill set, experience and education and reach out to prospective candidates for a friendly chat. They need to manage the whole recruitment process, making sure that the interviews are conducted efficiently and professionaly. They need to write reports for job openings, hires and post hire summaries for hiring managers. They need to mentor and provide guidance to recruting coordinators. They need to perform reference checks, salary recommendations, salary negotiation, handle offer acceptance/decline situations and offer generation. Which means they have a hell lot of work, and can be picky on who to call for interviews. Afterall, its 10 times more difficult getting into Google than Harvard.

There are plenty of ways by which you can land an interview:

  • Employee referrals – This has the highest chance of success, assuming that the employee actually knows you and had worked under/with you. Otherwise, it might not carry much weight, and yet might still land you the interview.
  • Applying on career site – Though its pretty easy to submit an online application in Google, chances are you shall be waiting forever for them to contact you.
  • Get noticed by a recruiter – A good LinkedIn, Github, StackOverflow profile or even a technical blog can get the attention of a recruiter and land you your interviews.

Resume

Your first point of entry is a resume. A recruiter on average spends about 6 seconds glancing through your resume. Unless your resume satisfy certain characteristics, you wont even pass the resume screen.

  • Stick to a 1 page resume format.
  • Focus on accomplishments and not responsibilities.
  • Have some open source contributions and pet projects of your own. Create a mobile or web app.
  • Stop making a CV and start writing a resume. Recruiters have no interest in knowing your birthday or marital status!
  • Do not write in paragraphs.
  • Stop writing Objective section. It brings nothing new to table.

Education

Plenty of people say that where you did your education won’t matter at Google. Its true to some extent, as the engineers interviewing you won’t care about your alma mater. But your recruiter will. To them, your college is yet another paramater in a search query to reduce the number of prospective candidates. A recruiter always try to reduce the probability of a bad hire getting in, even though it might reject good candidates too.

But once you landed your first job, your alma mater wont matter much. Only your experience and your company do. So even if you don’t get into Google on your first try, try getting into some good startup and gain some experience. Then apply to Google!