hii sir,
sir… i would like to know about how to apply off campus placements and how to knw information about openings and all ..i mean can you write a section in your blog dedicated to off campus placements.

my placement session is near… so i need your help…

I did not apply off-campus to any company so might not be the best resource for you. Still, from what I know, get to know about your seniors and where do they work and ask them if there are openings in their firms. Resumes which are sent through a referral are generally given higher priority than the ones which are uploaded to company websites. So, instead of uploading to /jobs of reputed firms just try to get a referrer and then send your resume.

Regarding the openings of jobs in companies, naukri.com, monster.com etc. are resources which many companies use to hire. But it takes a lot of time to get interview calls from these websites. Still, you can know about the openings via weekly emails that they send. But for prominent firms you have to use a referral, especially if you are a college fresher. Still try to ask to some person who actually applied to a company through off-campus.

U have an array of 1000 entries, and another array of a million entries. U should output the intersection of both arrays. I hav thought of hashing but its costly method. Other than Hashing, associative arrays is there any other method? Is B tree useful here?

Do you mean Binary Tree or the B Tree which is used in Databases?
If it is binary search tree that you mean, then it is even worse than hashing solution, because, it will also use up space but give you a bad order O(nlogn). Hashing would give you O(n).
It is actually a trade-off between time and space. If you can sacrifice space, then hashing is best else sort the larger list and do a binary search.
Building any complex data structure will cost both space and time. So you should be aware of the resources and requirements.
PS: These are discussive problems with no definite solution, only better approaches. 🙂

Google Inc is coming to our campus for recuritment.
It would be very nice if u could tell me the type question they ask in interview also state wat is their favourite type of questions and wat is the procedure for the written round.

Thanks in advance.

Looking for ur response as soon as possible because i havent got much time. 🙂

Hey .. I didnt go through the written round process of google but yes in interviews you can easily expect unheard algorithmic problems and atleast 1 design problem. I am sorry I can’t be very specific because I am an employee :). But you can safely assume that mugging up more n more problems won’t help, so try to practice a bit harder problems and try doing design problems. 🙂

Congratulations to you and thanx for being a regular visitor 🙂

BTW I had 1 phone screen and 4 onsite interviews. And I have put up a lot of sample questions here. I would suggest you also go through the Programming Problems series of my blog because they contain contest style problems which are slightly tougher. Writing a solid code for any given problem always gives you a distinct advantage 🙂

Can you tell me the solution to this problem that is optimized.

public long[] GetMultiplesOfTwoLessThan(int num)
eg if num is given as 30, output array should contain {1,2,4,8,16}. It shouldn’t contain 32 since 32 is more than the given number.
Another exp: if num is 300 then output will be {1,2,4,8,16,32,64,128,256}

dear sir,
to the problem: Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. Ex. find if a*b*cd*, or *win or *def* exists in the text.

can u please provide a hint to how to proceed for a solution to this? I can think of using suffix tree, but how to take care of wild cards?

Hey ..
Have you read about Grammars (CFGs etc.) in compilers? That should help a lot here. There are standard methods to parse those grammars and you could formulate the regex as one of those.

I have’nt studied compilers in my course yet, but yes i have learnt automata theory.
but how about this approach-
I divide the query string into substrings (delimiter is *), store it in an array, and then i scan the text for the substrings. If they appear in the same order as in my query string, then i have found the part of the text the query string matches…
And when * occurs at beginning or end of query string, we take that as a special case and also display the whole text before the first substring (which is abc in case of *abc*hg) and in similar way if * occurs at end, we display the whole text after last substring.
correct me if i am wrong here…

Can you please suggest a solution to this question ?

Given an array of ‘n’ random integers. Given an integer 1<=n. Find the k numbers such that the minimum difference of all the possible pairs of k numbers is maximum (maximum among other minimum differences for various possible selections of k numbers ).

Sir, i m in 4th yr n i hav some doubts….as you said that u dint appear in the written round for google den how did u apply for it, i mean was it off-campus??…I also want to know about the selection procedure of Microsoft and the type of ques being asked in it specifically…weather i shud concentrate upon practising more frm online contests or i shud prepare otherwise ….MS is gonna visit our college soon so looking for ur response as soon as possible…
Thanx in advance!!!

a. I did not apply myself, my college placement committee forwarded the resume for me. Hence I got a call.
b. M$ has a written test (which typically has design, test and coding problem) and then 4-5 rounds of interviews. Questions are typically not rigorously algorithmic but yes they demand production quality code first hand. So coding practice should be good.
Thats all I know about M$, sorry didn’t appear for their test/interviews. But the questions here should definitely help. 🙂

Given a co-ordinate (x,y) of a knight. How will you find the probability that the knight remains on chess board after n moves. A move of knight can be any random valid move(means any out of 8, if present in middle of board)

hi Avi,
I like ur blog very much……and I m almost a regular visitor in dis blog.Recenly I hav appeared 4 Amazon.But cant crack it.I m trapped in the below question.can u help me 2 solve it pls??

. Given a number of nodes N of a binary tree , how many structurally different full binary trees are possible.
A binary tree is said to be full binary tree , if for every node in the tree there exists exactly zero or 2 children.

I am a newbie to algorithms and their implementations. Do we also need to consider choosing appropriate programming language may c,c++, or java depending on the application? I have my first task to build a trie structure and then do dictionary matching.Please suggest me how should I proceed.

Modified 2 color sort problem i.e. you are given an array of integers containing only 0s and 1s.You have to place all the 0s in even position and 1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and without taking extra memory (modify the array in-place).

There is a priest in a certain village who performs Pooja at 3 temples and to reach each temple he has to cross a river. These rivers have a magical property because of which when he crosses the river the flowers that he carries double. He starts in the morning comes to first river and plucks some flowers from a tree on river bank. As he crosses the river his flowers double. He offers some of them to the deity in the first temple and proceeds to second river. As he crosses second river his flowers double. He offers same number of flowers to deity in second temple and proceeds to third river. As he crosses third river his flowers double. He offers same number of flowers to deity in third temple and does not have any flower left. Now can you tell me how many flowers does he pluck from the tree and how many he offers to each deity?

Hello sir, i’m pursuing B.E. computer science and i’m in third year. I have a doubt. Can you please tell how important cg is? What will the cut-offs be for companies like google and microsoft?

Can anyone solve this .. I have an array as an input to my function eg A[1,3,5] and i want my output of the array to be the product of all the digits divide by the ith element .ie [15,5,3]

hello sir,
i m student of 3rd yr… i m looking for summer internship in a reputed company like google , MS or any reputed university providing internship project.. Can u please guide me through the process i should follow for internship…
with regards
prashant

hii sir,

sir… i would like to know about how to apply off campus placements and how to knw information about openings and all ..i mean can you write a section in your blog dedicated to off campus placements.

my placement session is near… so i need your help…

thanks in advance

🙂 😀

Hi jalaj,

I did not apply off-campus to any company so might not be the best resource for you. Still, from what I know, get to know about your seniors and where do they work and ask them if there are openings in their firms. Resumes which are sent through a referral are generally given higher priority than the ones which are uploaded to company websites. So, instead of uploading to

/jobsof reputed firms just try to get a referrer and then send your resume.Regarding the openings of jobs in companies, naukri.com, monster.com etc. are resources which many companies use to hire. But it takes a lot of time to get interview calls from these websites. Still, you can know about the openings via weekly emails that they send. But for prominent firms you have to use a referral, especially if you are a college fresher. Still try to ask to some person who actually applied to a company through off-campus.

Hope this helped.

U have an array of 1000 entries, and another array of a million entries. U should output the intersection of both arrays. I hav thought of hashing but its costly method. Other than Hashing, associative arrays is there any other method? Is B tree useful here?

Do you mean Binary Tree or the B Tree which is used in Databases?

If it is binary search tree that you mean, then it is even worse than hashing solution, because, it will also use up space but give you a bad order O(nlogn). Hashing would give you O(n).

It is actually a trade-off between time and space. If you can sacrifice space, then hashing is best else sort the larger list and do a binary search.

Building any complex data structure will cost both space and time. So you should be aware of the resources and requirements.

PS: These are

discussiveproblems with no definite solution, onlybetter approaches. 🙂hi sir……

Google Inc is coming to our campus for recuritment.

It would be very nice if u could tell me the type question they ask in interview also state wat is their favourite type of questions and wat is the procedure for the written round.

Thanks in advance.

Looking for ur response as soon as possible because i havent got much time. 🙂

Hey .. I didnt go through the written round process of google but yes in interviews you can easily expect

unheardalgorithmic problems and atleast 1designproblem. I am sorry I can’t be very specific because I am an employee :). But you can safely assume that mugging up more n more problems won’t help, so try to practice a bit harder problems and try doing design problems. 🙂How many interviews did u give…. 🙂

Sir,I already know that u r a googler…..i read ur blog quite regularly…..I thought that u could provide me some sample questions.

and btw Thanks to this amazing blog of urs I have already got placed in samsung… 🙂

but i am really looking forward to this opportunity.

Congratulations to you and thanx for being a regular visitor 🙂

BTW I had 1 phone screen and 4 onsite interviews. And I have put up a lot of sample questions here. I would suggest you also go through the

Programming Problemsseries of my blog because they contain contest style problems which are slightly tougher. Writing a solid code for any given problem always gives you a distinct advantage 🙂Can you tell me the solution to this problem that is optimized.

public long[] GetMultiplesOfTwoLessThan(int num)

eg if num is given as 30, output array should contain {1,2,4,8,16}. It shouldn’t contain 32 since 32 is more than the given number.

Another exp: if num is 300 then output will be {1,2,4,8,16,32,64,128,256}

This problem was discussed here

dear sir,

to the problem:

Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. Ex. find if a*b*cd*, or *win or *def* exists in the text.can u please provide a hint to how to proceed for a solution to this? I can think of using suffix tree, but how to take care of wild cards?

Hey ..

Have you read about Grammars (CFGs etc.) in compilers? That should help a lot here. There are standard methods to parse those grammars and you could formulate the regex as one of those.

I have’nt studied compilers in my course yet, but yes i have learnt automata theory.

but how about this approach-

I divide the query string into substrings (delimiter is *), store it in an array, and then i scan the text for the substrings. If they appear in the same order as in my query string, then i have found the part of the text the query string matches…

And when * occurs at beginning or end of query string, we take that as a special case and also display the whole text before the first substring (which is abc in case of *abc*hg) and in similar way if * occurs at end, we display the whole text after last substring.

correct me if i am wrong here…

Can you please suggest a solution to this question ?

Given an array of ‘n’ random integers. Given an integer 1<=n. Find the k numbers such that the minimum difference of all the possible pairs of k numbers is maximum (maximum among other minimum differences for various possible selections of k numbers ).

@harsh

The method which you describe will have standard issues. Please refer to KMP Algorithm for it.

Sir, i m in 4th yr n i hav some doubts….as you said that u dint appear in the written round for google den how did u apply for it, i mean was it off-campus??…I also want to know about the selection procedure of Microsoft and the type of ques being asked in it specifically…weather i shud concentrate upon practising more frm online contests or i shud prepare otherwise ….MS is gonna visit our college soon so looking for ur response as soon as possible…

Thanx in advance!!!

@Isha

a. I did not apply myself, my college placement committee forwarded the resume for me. Hence I got a call.

b. M$ has a written test (which typically has design, test and coding problem) and then 4-5 rounds of interviews. Questions are typically not rigorously algorithmic but yes they demand production quality code first hand. So coding practice should be good.

Thats all I know about M$, sorry didn’t appear for their test/interviews. But the questions here should definitely help. 🙂

Given the number of nodes to be n. What are the number of unique general trees, binary trees and BSTs that can be formed?

Given a co-ordinate (x,y) of a knight. How will you find the probability that the knight remains on chess board after n moves. A move of knight can be any random valid move(means any out of 8, if present in middle of board)

hi Avi,

I like ur blog very much……and I m almost a regular visitor in dis blog.Recenly I hav appeared 4 Amazon.But cant crack it.I m trapped in the below question.can u help me 2 solve it pls??

. Given a number of nodes N of a binary tree , how many structurally different full binary trees are possible.

A binary tree is said to be full binary tree , if for every node in the tree there exists exactly zero or 2 children.

Example: When N = 5 , No. of possible trees = 2

Hey,

I don’t prefer giving out answers directly so I guess this link along with doing the qns for n=3,4,5,6,7 would give u the required direction.

but I dont think this formula can b directly used………

We have 2 derive da algo 4 dat formula……………

G’Day

I am a newbie to algorithms and their implementations. Do we also need to consider choosing appropriate programming language may c,c++, or java depending on the application? I have my first task to build a trie structure and then do dictionary matching.Please suggest me how should I proceed.

thanks

rasagnya

Hi,

Could you kindly help me out with this problem

Modified 2 color sort problem i.e. you are given an array of integers containing only 0s and 1s.You have to place all the 0s in even position and 1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and without taking extra memory (modify the array in-place).

For Example :

Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}

Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1}

There is a priest in a certain village who performs Pooja at 3 temples and to reach each temple he has to cross a river. These rivers have a magical property because of which when he crosses the river the flowers that he carries double. He starts in the morning comes to first river and plucks some flowers from a tree on river bank. As he crosses the river his flowers double. He offers some of them to the deity in the first temple and proceeds to second river. As he crosses second river his flowers double. He offers same number of flowers to deity in second temple and proceeds to third river. As he crosses third river his flowers double. He offers same number of flowers to deity in third temple and does not have any flower left. Now can you tell me how many flowers does he pluck from the tree and how many he offers to each deity?

Hello sir, i’m pursuing B.E. computer science and i’m in third year. I have a doubt. Can you please tell how important cg is? What will the cut-offs be for companies like google and microsoft?

Can anyone solve this .. I have an array as an input to my function eg A[1,3,5] and i want my output of the array to be the product of all the digits divide by the ith element .ie [15,5,3]

Assuming array inddex starts from 1

B[1] = (1*3*5) /1 = 15

B[2] = (1*3*5) /3 = 5

B[3] = (1*3*5) /5 = 3

hello sir,

i m student of 3rd yr… i m looking for summer internship in a reputed company like google , MS or any reputed university providing internship project.. Can u please guide me through the process i should follow for internship…

with regards

prashant