Data Structure and Order Notations

[codenamevirus]

hi

This question comes from a friend who's about to get interviewed in Microsoft 2-3 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

[Arkimedes]

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!

[codenamevirus]

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

[Arkimedes]

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 McGraw-Hill, 2001. ISBN 0-262-03293-7.. 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++

[codenamevirus]

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

[nebulus200]

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, red-black 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)).

[linlover929]

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.