Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The problem smells of ranges, and one of the good data-structures for this problem would be a Segment Tree. <a href="http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=lowestCommonAncestor#Segment_Trees" rel="noreferrer">Some</a> <a href="http://en.wikipedia.org/wiki/Segment_tree" rel="noreferrer">resources</a> to help you get started.</p> <p>The root of the segment tree can represent the addresses (0.0.0.0 - 255.255.255.255). The left sub-tree would represent the addresses (0.0.0.0 - 127.255.255.255) and the right sub-tree would represent the range (128.0.0.0 - 255.255.255.255), and so on. This will go on till we reach ranges which cannot be further sub-divided. Say, if we have the range 32.0.0.0 - 63.255.255.255, mapped to some arbitrary city, it will be a leaf node, we will not further subdivide that range when we arrive there, and tag it to the specific city.</p> <p>To search for a specific mapping, we follow the tree, just as we do in a Binary Search Tree. If your IP lies in the range of the left sub-tree, move to the left sub-tree, else move to the right sub-tree.</p> <p>The good parts:</p> <ol> <li>You need not have all sub-trees, only add the sub-trees which are required. For example, if in your data, there is no city mapped for the range (0.0.0.0 - 127.255.255.255), we will not construct that sub-tree.</li> <li>We are space efficient. If the entire range is mapped to one city, we will create only the root node!</li> <li>This is a dynamic data-structure. You can add more cities, split-up ranges later on, etc.</li> <li>You will be making constant number of operations, since the maximum depth of the tree would be 4 x log2(256) = 32. For this particular problem it turns out that Segment Trees would be <strong>as fast as van-Emde Boas trees</strong>, and require lesser space (O(N)).</li> <li>This is a simple, but non-trivial data-structure, which is better than sorting, because it is dynamic, and easier to explain to your interviewer than van-Emde Boas trees.</li> <li>This is one of the easiest non-trivial data-structures to code :)</li> </ol> <p>Please note that in some Segment Tree tutorials, they use arrays to represent the tree. This is probably not what you want, since we would not be populating the entire tree, so dynamically allocating nodes, just like we do in a standard Binary Tree is the best.</p>
    singulars
    1. This table or related slice is empty.
    1. POGiven a flat file of IP Ranges and mappings, find a city given an IP
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USreddragon
    1. USreddragon
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIsn't a segment tree overkill here, since the ranges are nonoverlapping? My understanding is that segment trees are good when the ranges could potentially overlap, but I would imagine in this particular case that there isn't any overlap.
      singulars
      1. PO
      1. UStemplatetypedef
    2. COI am not sure if I get your comment. It is probably because the ranges in the Segment Tree are being confused with what we want to store. We want to store IP address ranges, lets call them values. Now, the values don't overlap as such. But the ranges of values do overlap, for eg., (0.0.0.0 - 255.255.255.255) is the root node, and all the values would lie under this range.
      singulars
      1. PO
      1. USreddragon
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload