Programming interview questions

Discuss all those difficult questions here.

Programming interview questions

Postby akbar » Fri Jan 25, 2008 12:22 am

I thought about starting a discussion on programming-specific interview questions only.

The two different ways to apply operator overloading in C++ are by creating operator functions either as a member or as a Friend function of a class.

Can anyone explain the respective (dis)advantages of operator member functions versus "friend" functions?
akbar
 
Posts: 28
Joined: Fri Aug 10, 2007 7:12 pm

Postby mj » Fri Jan 25, 2008 5:05 am

Well I tend to avoid anything that is harder to keep track of.

Friends are part of the implementation of a class but defined elsewhere so a pain to keep under control. (perhaps they are aptly named!)
mj
Site Admin
 
Posts: 1380
Joined: Fri Jul 27, 2007 7:21 am

Postby akbar » Mon Jan 28, 2008 12:00 am

I would need some help on answering the following interview question:

find an algorithm to see if two words are acronyms.

It seems to be a classic, so If anyone has coded anything related, that would be very helpful.
Thanks in advance.
akbar
 
Posts: 28
Joined: Fri Aug 10, 2007 7:12 pm

Postby mj » Mon Jan 28, 2008 1:39 am

well the easy solution is sort both of them and then see if they're the same

this is n log n complexity but if we 're truly doing words n would be small anyway.

i'll have a think about an O(n) algorithm
mj
Site Admin
 
Posts: 1380
Joined: Fri Jul 27, 2007 7:21 am

Postby crnt2 » Mon Jan 28, 2008 9:07 am

I don't even understand the question.

By "acronym" do you mean a word formed by the initial letters of a phrase, e.g. IMHO for "in my humble opinion"?

Or do you mean "anagram", which is a re-arrangement of letters in a word to form a new word, e.g. "rides" and "sired".
crnt2
 
Posts: 18
Joined: Tue Dec 04, 2007 7:01 pm
Location: Cambridge

Postby akbar » Mon Jan 28, 2008 9:36 am

Sorry if the question was too obscure (I quoted it as it was in the interview test).
acronyms are words formed using the first syllabs of a set of words (here only pairs of words) used to name something. The typical example is:

Modem of "Modulator-Demodulator".

The trick is to make sure that the acronym formed are name-sounding, which implies checking potential combination on a database of words.

You can check the wiki on "acronyms" for further details.

Thanks in advance for any help.
akbar
 
Posts: 28
Joined: Fri Aug 10, 2007 7:12 pm

Postby mj » Mon Jan 28, 2008 10:37 pm

If you truly expected to assess whether the word sounds right, this question is truly ridiculous and it's worrying that anyone would ask it.

But if it simply to check whether you can one word from chopping the first letters of a phrase it sounds reasonably easy.
mj
Site Admin
 
Posts: 1380
Joined: Fri Jul 27, 2007 7:21 am

Postby akbar » Mon Jan 28, 2008 11:29 pm

I was merely explaining what an acronym is in real life, sorry if I created any confusion.

The interview question was nothing more than the line I quoted, if checking prefixes combinations on a dictionnary is all there is to do it is an easy question.

Thanks for the clarification.
akbar
 
Posts: 28
Joined: Fri Aug 10, 2007 7:12 pm

Postby sargon » Thu Feb 07, 2008 4:15 am

There is an O(n) algorithm for anagrams if you hash the letters. Scan the first word and maintain a count of each letter by incrementing the corresponding position in a 26 sized array. Then scan the second word and decrement this time.

They are anagrams iff the resulting count array has each element set to zero.

This assumes that your space of letters is the english alphabets. In general, you can use a hash table.
'

Acronyms are quite hard. Take for example "Modulator-demodulator". There is no logical explanation to use modem over modemo. Also, take SETI-search for extraterrestrial intelligence- there is no way to know which syllables to pick up to create the acronym.

That said, there are smarter (statistical) techniques to handle these kind of conditions. For example, by searching through a large corpus, you might pick up correlations between several words and corresponding acronyms. This associative structure can then be used to tell if two words are acronyms.
sargon
 
Posts: 12
Joined: Fri Oct 19, 2007 7:22 pm

Postby sargon » Thu Feb 07, 2008 4:36 am

Here are a couple.
1. I want to implement a matrix class in C++
However, I am crazy about having [][] operator.
So, if I have a matrix class
and an object :
matrix M;

I want to be able to do M[i][j].

Write a class to implement it.
Can you think about any drawbacks with this approach?


2.here is another one
Suppose I have a small montecarlo program that uses about 20 constants (say 20 points on an imp-vol curve). The monte carlo program runs the same function in a loop several million times.
The program is like this:
int[] vol={1,2,3,4...20};
For i=1:n
{
for j=1:20
{
volsq[i]=vol[i]*vol[i];
}
output=compute(volsq);

end
}

Can you think of a couple of ways to speed up this program?
sargon
 
Posts: 12
Joined: Fri Oct 19, 2007 7:22 pm


Return to Interview questions

Who is online

Users browsing this forum: No registered users and 1 guest

cron