Data Structure and Order Notations
Results 1 to 7 of 7

Thread: Data Structure and Order Notations

  1. #1
    Senior Member codenamevirus's Avatar
    Join Date
    Jun 2005
    Location
    Faridabad, Haryana, India
    Posts
    298

    Data Structure and Order Notations

    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
    CodeNameVirus

  2. #2
    Senior Member
    Join Date
    Oct 2005
    Posts
    106
    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 good-natured, 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)

  3. #3
    Senior Member codenamevirus's Avatar
    Join Date
    Jun 2005
    Location
    Faridabad, Haryana, India
    Posts
    298
    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
    CodeNameVirus

  4. #4
    Senior Member
    Join Date
    Oct 2005
    Posts
    106
    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++
    "The Texan turned out to be good-natured, 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)

  5. #5
    Senior Member codenamevirus's Avatar
    Join Date
    Jun 2005
    Location
    Faridabad, Haryana, India
    Posts
    298
    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
    CodeNameVirus

  6. #6
    Jaded Network Admin nebulus200's Avatar
    Join Date
    Jun 2002
    Posts
    1,356
    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)).
    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)

  7. #7
    Member
    Join Date
    May 2006
    Posts
    39
    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
  •  

 Security News

     Patches

       Security Trends

         How-To

           Buying Guides