
September 1st, 2006, 09:33 AM
#1
Senior Member
Data Structure and Order Notations
hi
This question comes from a friend who's about to get interviewed in Microsoft 23 months from now.
He asked me about the references, where he would find the actual implementation of Data Structure and Order notation in the making of projects(which are generally made in MS).
All I got from him is, he wants to know how do we actually use Data Structures and Order Notation concepts in the making of real cool projects.
Thank u all

September 1st, 2006, 06:23 PM
#2
Senior Member
Well, measuring the usefulness of data structures, you use the big O notation.
Things like quadratic search has a big O notation of O(n^2), a binary search is O(n log n) (methinks...), and so on. And where n log n is LESS than n^2, then a binary search is FASTER than a quadratic search.
I hope that helps!
"The Texan turned out to be goodnatured, generous and likeable. In three days no one could stand him." Catch 22 by Joseph Heller.
Buddies? I have no buddies...
Give the BSD daemon some love (proud FreeBSD user)

September 1st, 2006, 06:31 PM
#3
Senior Member
Well, measuring the usefulness of data structures, you use the big O notation.
Things like quadratic search has a big O notation of O(n^2), a binary search is O(n log n) (methinks...), and so on. And where n log n is LESS than n^2, then a binary search is FASTER than a quadratic search.
I hope that helps!
Thanks for the above things Arkimedes. But, I dun think its really gonna help my friend in a more significant way or may be, I wasnt clear enough.
My friend wants to know about Data Structures and Order Notation and he wants to know it all(and not just the definitions!!)
Thanks

September 1st, 2006, 06:54 PM
#4
Senior Member
Oh, in that case, if you are capable of going to a University's library and look for a book called Introducion to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. MIT Press and McGrawHill, 2001. ISBN 0262032937.. It's all about data structures, when you would use them, how effecient they are, etc.
Just what your friend is looking for methinks.
There are also the following links:
A famous Data Structure educator's webpage
Data Structure page
Course Notes
Data Strucutures for C++
"The Texan turned out to be goodnatured, generous and likeable. In three days no one could stand him." Catch 22 by Joseph Heller.
Buddies? I have no buddies...
Give the BSD daemon some love (proud FreeBSD user)

September 1st, 2006, 06:57 PM
#5
Senior Member
Now, that has a lot of info that wud help him. I wud like to assign u some greenies but it says I must spread some point before I can giv more to u!
Thnx again

September 1st, 2006, 07:39 PM
#6
Well, measuring the usefulness of data structures, you use the big O notation.
Things like quadratic search has a big O notation of O(n^2), a binary search is O(n log n) (methinks...), and so on. And where n log n is LESS than n^2, then a binary search is FASTER than a quadratic search.
I hope that helps!
Big O is, at least as best I can remember, used to compare sorting effeciencies of various data structures (for example avl trees, redblack trees, binary trees, hashes, heaps, linked lists, stacks, etc). Basically you can count n as the number of loops, so if an algorithm/procedure is only run once, its order of complexity O(n) would be 1...if in that procedure it had a for loop, then it would be n...if it had two nested for loops it would be n^2 (n for first loop * n for second loop), where you can basically 'drop' the constants off since they are considered to be minor/irrelvant when compared to the scope of 'n' as it approaches an infinite value. Some of the more complex algorithms (especially trees) will have a n log n complexity usually because of ways data is stored internally in the structure (you'd have to read the particulars of each struture to understand why, but usually it should be fairly evident by the code structure, just look for how it goes through the data structure and you can come up with the O(n)...(in most cases).
If you friend is 'vague' on these fundamental concepts and ideas, they would be very well served to read up substantially before an interview with Microsoft (or even postpone it until they are prepared rather than potentially leaving a bad impression (my opinion, not trying to be negative as bad as it comes across)).
There is only one constant, one universal, it is the only real truth: causality. Action. Reaction. Cause and effect...There is no escape from it, we are forever slaves to it. Our only hope, our only peace is to understand it, to understand the 'why'. 'Why' is what separates us from them, you from me. 'Why' is the only real social power, without it you are powerless.
(Merovingian  Matrix Reloaded)

September 28th, 2006, 12:14 PM
#7
First, I assume I shouldn't be posting on this after such a long time since the last post but I feel there are some vital points I need to make.
My first point. Arkimedes if the guy doesn't know data structures Introduction to Algorithms will be too complicated for the guy.
nebulus you are correct about big0 notation. But, I will finish off where you left off... Big O notation is used to help compare algorithms so you can tell which will take more time and which will be more efficient.
An example would be
sum = 0;
for ( int count = 1; count <= n; count++
sum = sum + count;
the problem will do more iterations based on n. The higher n the more iterations. This is bigO n. written O(n). as n gets bigger so does your problem.
an alternate way to do that would be
sum = ((n +1 * n) / 2
this is bigO of 1 because no matter how large n is it will do the same amount of work. For 5 you do the same iterations through as you would for 5000. O(1).
as for datastructures there are plenty of books that you can read to get information on them. A good/bad one is Nell Dale's C++ Data Structures. If your friend is going to read it just to learn good, but don't depend on the answers in the back of the book. I used it my freshman year and they were all wrong. THat was 3 years ago so another Edition should be out by now.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

