Google Interview Question Software Engineer / Developers
how to use graph or b-tree and graph to store street view images.
function: SEARCH: we could use latitude,longtitude,and other parameters to locate an image on a map to index an image. Use the index to search the image
question: how to store an image on physical drive? is this a file system management problem?
I think the question here is how to store high quality pictures so i guess some kind of efficient compression algo with btree&graph to locate a image on the map.
How about a 3-D array indexed by latitude, longitude and alignment(N E W S)? To move along the street, either change the alignment or increment positional parameters. We also need another data structure to map physical addresses to latitude and longitude.
although it sounds graph but practically it does not look like a graph is ideal for street view where u are just interested in immediate connections
I guess we need to use some kind of 3D polar coordinate system.
A position/location/point can be represented by 2 (or 3, when in future "altitude" gets in the game) coordinates (x,y) and angle of viewing w.r.t. the East direction.
Store and Build indexing of compressed pictures using this coordinate system.
Further, we'll also need some logic to play with retrieved images when only the rotation angle is changed ie when someone is panning around, while at the same location (x,y). Then, retrieved images should show up as contiguous pan..
Obviously "angle with east" need to be discretized for indexing/lookup.
Note that street-view also has a zoom-in function which basically just magnifies/zooms that image limited-ly.
B-Tree + Graph ?
- Anonymous March 10, 2010