கூகிள் நேர்முகத்தேர்வு கேள்விகள்

Google Interview Questions ::Total there are five Technical Interviews followed by Management round.So here are the questions.

Google Interview Round 1 ::

What is the Space complexity of quick sort algorithm? how do find it? Solution:

Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that* in-place partitioning is used. This requires O(1). * After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration. The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.

What are dangling pointers?
Solution:
A dangling pointer is a pointer to storage that is no longer allocated. Dangling pointers are nasty bugs because they seldom crash the program until long after they have been created, which makes them hard to find. Programs that create dangling pointers often appear to work on small inputs, but are likely to fail on large or complex inputs.

Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.
Solution:
The simple recurrence relation governing this problem is f(N)=f(N-1) +f(N-2)(why?),which is a fibonacci sequence.Nth state can be arrived directly by taking 2 step movement from N-2 or 1 step from N-1.Remember N-2 -> N-1 -> N is not a direct path from N-2th state to Nth state.Hence the no of solutions is no of ways to reach N-2th step and then directly taking a 2 jump step to N + no of ways to reach N-1th step and then taking 1 step advance.
You are given biased coin. Find unbiased decision out of it? Solution:Throw the biased coin twice.Classify it as true for HT and false for TH.Both of these occur with probability=p*(1-p),hence unbiased. Ignore the other 2 events namely HH and TT.
On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.

Google Interview Round 2 ::

You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.Solution: The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array.Sum of first N natural numbers=N*(N+1)/2and S=N*(N+1)/2 - K.Now putting this other way around we get K=N*(N+1)/2 -S !!Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.We solve this problem by solving 2 essential equations.They are X+Y=N*(N+1)/2 -S---------->(1)X*Y=N!/P-------------------(2) where S and P are the cumulative sum and product of the array entries.
You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.Solution: The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution.Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be ZNow X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.
Questions on my project please be prepare well about your project
How do you search for a word in a large database.
How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'.

Google Interview Round 3 ::

You have given an array. Find the maximum and minimum numbers in less number of comparisons. Solution:only 3n/2 comparisons are necessary to find both the minimum and the maximum. To do this, we maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, however, at a cost of two comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then compare the smaller to the current minimum and the larger to the current maximum, at a cost of three comparisons for every two elements.
You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n). Solution:All the numbers are positive to start with.Now, For each A[i], Check the sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a repetition if it's negative.Finally all those entries i,for which A[i] is negative are present and those i for which A[i] is positive are absent.

Google Interview Round 4 ::

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
Solution:[c] bool test(A,B,C) { i=j=k=0; while(k < C.size()) { if(i < A.size() && C[k]==A[i]) {i++,k++; } else if(j < B.size() && C[k]==B[j]) { j++,k++; } else return false } return (i == A.size() && j == B.size()); }
[/c]

The above algorithm doesn't work when C[k]=A[i]=B[j], essentially throwing one in to a dilemma whether to accept the character from A or B.
Given two sorted arrays A and B.
Find the intersection of these arrays A and B.Solution:The intersection can be found by using a variation of merge routine of the merge sort.
If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?Solution:In this case for each entry of smaller array,we can run a binary search routine on the larger one to know its presence.

Google Interview Round 5 ::

If you get into Google, which products are you going to work on?
What is TCP, UDP. what is reliability, unreliability, give examples of these?

source:cracktheinterview.org

59 comments:

Anonymous said...

xanax online pharmacy buy cheap generic xanax online - ways get high xanax

Anonymous said...

generic xanax xanax vs klonopin high - buy alprazolam no prescription needed

Anonymous said...

can you buy xanax online xanax dosage in cats - xanax dosage amounts

Anonymous said...

generic xanax buy cheap xanax no prescription - valor alprazolam 0 5mg

Anonymous said...

xanax online wellbutrin and xanax for anxiety - pictures of 1mg xanax

Anonymous said...

buy tramadol online tramadol for dogs side effects panting - tramadol yellow pill

Anonymous said...

buy tramadol online 400 mg tramadol high - tramadol for dogs is it the same for humans

Anonymous said...

buy carisoprodol buy carisoprodol usa - do drug tests test carisoprodol

Anonymous said...

buy tramadol online tramadol 50 mg order online - tramadol 50mg tablets get you high

Anonymous said...

xanax online xanax effects sperm - xanax 901

Anonymous said...

tramadol online no prescription tramadol online no prescription overnight delivery - tramadol hcl tablets 50 mg

Anonymous said...

buy carisoprodol buy carisoprodol online cheap - carisoprodol 350 mg tablets information

Anonymous said...

generic xanax generic xanax 3 mg - xanax dosage for dogs by weight

Anonymous said...

buy tramadol online is tramadol online real - tramadol hcl veterinary use

Anonymous said...

generic xanax what does xanax and alcohol do to the body - buy xanax online 2mg

Anonymous said...

buy tramadol online tramadol for dogs human consumption - tramadol withdrawal valium

Anonymous said...

buy carisoprodol carisoprodol 350mg tablets price - carisoprodol soma wiki

Anonymous said...

where to buy xanax online no prescription buy xanax echeck - xanax generic alprazolam

Anonymous said...

buy tramadol online can you buy tramadol internet - tramadol hcl usa

Anonymous said...

buy carisoprodol carisoprodol dosage high - buy vicodin online no prescription overnight

Anonymous said...

buy cialis professional online cheap cialis once day - cialis black

Anonymous said...

xanax online xanax dosage and administration - buy xanax online with no prescription needed

Anonymous said...

tramadol online pharmacy tramadol 50 mg for headaches - tramadol 50 mg image

Anonymous said...

buy cialis online cheap cialis online canadian pharmacy - buy cialis mississauga

Anonymous said...

buy cialis online generic cialis for daily use - cialis online venezuela

Anonymous said...

xanax online xanax side effects glaucoma - xanax pillen wiki

Anonymous said...

buy cialis generic generic cialis kopen - where to buy cheap cialis

Anonymous said...

xanax online buy generic xanax online - xanax effects blood pressure

Anonymous said...

http://landvoicelearning.com/#57594 tramadol during pregnancy - tramadol 50 mg for migraine

Anonymous said...

buy tramadol tramadol 50 mg can you get high - tramadol for dogs best price

Anonymous said...

http://buytramadolonlinecool.com/#56411 tramadol no prescription free shipping - tramadol hcl 100 mg

Anonymous said...

buy tramadol cheap tramadol online - tramadol 50 mg injection

Anonymous said...

buy tramadol online tramadol hcl 100mg side effects - order tramadol online no rx

Anonymous said...

http://landvoicelearning.com/#62431 purchase tramadol usa - buy tramadol online 100mg

Anonymous said...

http://landvoicelearning.com/#51438 buy tramadol online paypal - tramadol withdrawal pregnancy

Anonymous said...

http://blog.dawn.com/dblog/buy/#41639 tramadol 50 mg - tramadol hcl 50 mg tab street value

Anonymous said...

learn how to buy tramdadol order tramadol online reviews - best website buy tramadol

Anonymous said...

buy tramadol tramadol 100mg no prescription - tramadol 50mg and itching

Anonymous said...

tramadol 50 mg buy tramadol 150 mg - online tramadol no prescription overnight

Anonymous said...

buy tramadol cheap online cheap tramadol - lethal dose tramadol

Anonymous said...

http://landvoicelearning.com/#21906 can buy tramadol online legally - signs tramadol overdose dogs

Anonymous said...

buy tramadol medication tramadol for dogs same as for people - legal buy tramadol usa

Anonymous said...

buy tramadol online cod overnight tramadol overdose death - tramadol withdrawal kratom

Anonymous said...

ways to buy ativan online who makes generic ativan - buy ativan from canada

Anonymous said...

buy tramadol online tramadol from usa no prescription - buy tramadol money order

Anonymous said...

http://reidmoody.com/#51208 ativan addiction 1mg - ativan online

Anonymous said...

buy xanax online buy alprazolam cheap no prescription - xanax 30mg

Anonymous said...

buy tramadol online tramadol 50mg 180 tablets - buy tramadol 180

Anonymous said...

buy xanax online xanax effects with alcohol - buy xanax online spain

Anonymous said...

http://ranchodelastortugas.com/#50238 generic xanax pictures of pills - generic xanax side effects

Anonymous said...

buy tramadol overnight shipping buy tramadol online mastercard overnight - tramadol buy usa

Anonymous said...

http://ranchodelastortugas.com/#51462 xanax pills alcohol - much do 1mg xanax cost

Anonymous said...

http://ranchodelastortugas.com/#37284 generic xanax buspar - xanax for anxiety treatment

Anonymous said...

http://ranchodelastortugas.com/#37284 xanax dosage for cats - xanax pills alcohol

Anonymous said...

http://ranchodelastortugas.com/#64581 buy xanax answers - xanax 1 mg yellow

Anonymous said...

xanax drug order generic xanax online - online pharmacy no prescription xanax

Anonymous said...

http://bayshorechryslerjeep.com/#6828 what does xanax high do - order xanax online legally

Anonymous said...

http://bayshorechryslerjeep.com/#2902 xanax withdrawal low dose - xanax type of drug

Anonymous said...

http://www.achildsplace.org/banners/tramadolonline/#9652 buy tramadolnext day - order tramadol online cod