Design a Facebook Near-By Friends app.

package com.androidinterview.nearby.geo;

// What comes back to the client, and it is not a coordinate. A friend is
// nearby, under a kilometre, and that is the entire payload. Returning exact
// positions would mean every requester learns where their friends live to
// house level precision, which the feature never needed in order to work.
public enum DistanceBucket {

    HERE(200), CLOSE(1_000), NEARBY(5_000), FAR(Integer.MAX_VALUE);

    private final int maxMetres;

    DistanceBucket(int maxMetres) {
        this.maxMetres = maxMetres;
    }

    public static DistanceBucket of(int metres) {
        for (DistanceBucket bucket : values()) {
            if (metres <= bucket.maxMetres) return bucket;
        }
        return FAR;
    }
}

package com.androidinterview.nearby.geo;

import java.util.ArrayList;
import java.util.List;

// Why nearby is a prefix match rather than a distance calculation.
//
// A geohash interleaves the bits of a latitude and a longitude and writes the
// result in base thirty two. Two points that share a prefix are in the same
// cell, and a longer prefix is a smaller cell, so who is within two kilometres
// becomes a range scan on an indexed string column. Distance against every row
// is the version that gets slower as the whole user base grows rather than as
// one friend list grows.
public final class GeoHash {

    private static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

    // Roughly how wide a cell is, in metres, at each precision. Approximate
    // because cells narrow towards the poles, which is fine, the precision is
    // chosen to be at least the radius asked for and the exact filter runs
    // afterwards on a handful of candidates.
    private static final int[] CELL_METRES = {5_000_000, 1_250_000, 156_000, 39_100, 4_890, 1_220, 153, 38};

    private GeoHash() {
    }

    public static String encode(double lat, double lon, int precision) {
        double latMin = -90, latMax = 90, lonMin = -180, lonMax = 180;
        StringBuilder hash = new StringBuilder(precision);
        boolean evenBit = true;
        int bit = 0;
        int index = 0;

        while (hash.length() < precision) {
            if (evenBit) {
                double mid = (lonMin + lonMax) / 2;
                index = index * 2 + (lon >= mid ? 1 : 0);
                if (lon >= mid) lonMin = mid; else lonMax = mid;
            } else {
                double mid = (latMin + latMax) / 2;
                index = index * 2 + (lat >= mid ? 1 : 0);
                if (lat >= mid) latMin = mid; else latMax = mid;
            }
            evenBit = !evenBit;
            if (++bit == 5) {
                hash.append(BASE32.charAt(index));
                bit = 0;
                index = 0;
            }
        }
        return hash.toString();
    }

    // The longest prefix whose cell is still at least as wide as the radius,
    // which is the smallest cell that can hold the search.
    public static int precisionFor(int radiusMetres) {
        for (int precision = CELL_METRES.length; precision >= 1; precision--) {
            if (CELL_METRES[precision - 1] >= radiusMetres) return precision;
        }
        return 1;
    }

    // The eight cells around this one, and the edge case every first
    // implementation misses. A friend fifty metres away can sit on the far side
    // of a boundary and share no prefix at all, so the query is this cell plus
    // its neighbours and the exact distance filter runs on the handful that
    // come back.
    public static List<String> neighbours(String hash) {
        double[] cell = bounds(hash);
        double latStep = cell[1] - cell[0];
        double lonStep = cell[3] - cell[2];
        double lat = (cell[0] + cell[1]) / 2;
        double lon = (cell[2] + cell[3]) / 2;
        List<String> around = new ArrayList<>(8);
        for (int dLat = -1; dLat <= 1; dLat++) {
            for (int dLon = -1; dLon <= 1; dLon++) {
                if (dLat == 0 && dLon == 0) continue;
                double nLat = Math.max(-90, Math.min(90, lat + dLat * latStep));
                double nLon = ((lon + dLon * lonStep + 540) % 360) - 180;
                around.add(encode(nLat, nLon, hash.length()));
            }
        }
        return around;
    }

    // Decoding back to the cell's bounds is the same walk as encoding, read in
    // reverse, and it is all the neighbour step needs.
    private static double[] bounds(String hash) {
        double latMin = -90, latMax = 90, lonMin = -180, lonMax = 180;
        boolean evenBit = true;
        for (int i = 0; i < hash.length(); i++) {
            int index = BASE32.indexOf(hash.charAt(i));
            for (int b = 4; b >= 0; b--) {
                boolean high = ((index >> b) & 1) == 1;
                if (evenBit) {
                    double mid = (lonMin + lonMax) / 2;
                    if (high) lonMin = mid; else lonMax = mid;
                } else {
                    double mid = (latMin + latMax) / 2;
                    if (high) latMin = mid; else latMax = mid;
                }
                evenBit = !evenBit;
            }
        }
        return new double[] {latMin, latMax, lonMin, lonMax};
    }
}

package com.androidinterview.nearby.location;

// The battery half of the answer. A fixed interval is the wrong shape, because
// a phone on a desk produces the same location eight hundred times and a phone
// in a car produces a genuinely different one every few seconds. The cadence
// follows detected activity, from the activity recognition API rather than
// from a timer, and the fused provider runs at balanced accuracy rather than
// asking for continuous GPS.
public final class UpdatePolicy {

    // STILL is zero rather than a slow interval. Still means stop asking, and
    // resuming is driven by the activity transition rather than by polling to
    // find out whether the phone moved.
    public enum Activity {
        STILL(0), WALKING(60_000), CYCLING(30_000), DRIVING(15_000);

        public final long intervalMillis;

        Activity(long intervalMillis) {
            this.intervalMillis = intervalMillis;
        }
    }

    private final int batchSize;
    private final long maxBatchAgeMillis;

    public UpdatePolicy(int batchSize, long maxBatchAgeMillis) {
        this.batchSize = batchSize;
        this.maxBatchAgeMillis = maxBatchAgeMillis;
    }

    // Fixes are queued and sent together. One radio wake for eight updates
    // costs a fraction of eight wakes, and on a bad connection the queue simply
    // grows and flushes on reconnect instead of the feature failing.
    public boolean shouldFlush(int queued, long oldestQueuedAt, long nowMillis) {
        return queued >= batchSize || (queued > 0 && nowMillis - oldestQueuedAt >= maxBatchAgeMillis);
    }
}

package com.androidinterview.nearby.share;

import java.util.HashMap;
import java.util.Map;

// Sharing is per friend and expires by itself. A single global toggle is the
// design that goes wrong, because the person who turned it on for one evening
// two years ago is still broadcasting.
//
// A grant is one directional. Mutual visibility is two grants, one each way,
// and nothing here quietly turns one into the other.
//
// This runs on the server as well, and the server copy is the one that counts.
// The nearby query intersects the geospatial index with the grants other people
// have made to the requester, so a client can never ask about somebody who did
// not share with it.
public final class SharePolicy {

    // Keyed by friend id, so the value is only ever the expiry.
    private final Map<String, Long> grants = new HashMap<>();

    public void share(String friendId, long untilMillis) {
        grants.put(friendId, untilMillis);
    }

    // Revoking deletes the stored cell as well as the grant. Hiding a position
    // the server still holds is not a privacy story.
    public void stop(String friendId) {
        grants.remove(friendId);
    }

    public boolean sharingWith(String friendId, long nowMillis) {
        Long expiresAt = grants.get(friendId);
        return expiresAt != null && expiresAt > nowMillis;
    }

    // The foreground service notification is not decoration and not optional.
    // If anything is being published at all, the user can see that it is.
    public boolean indicatorVisible(long nowMillis) {
        return grants.values().stream().anyMatch(expiresAt -> expiresAt > nowMillis);
    }
}

package com.androidinterview.nearby.geo

private const val BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

// Roughly how wide a cell is, in metres, at each precision. Approximate
// because cells narrow towards the poles, which is fine, the precision chosen
// is at least the radius asked for and the exact filter runs afterwards on a
// handful of candidates.
private val CELL_METRES = intArrayOf(5_000_000, 1_250_000, 156_000, 39_100, 4_890, 1_220, 153, 38)

// Why nearby is a prefix match rather than a distance calculation.
//
// A geohash interleaves the bits of a latitude and a longitude and writes the
// result in base thirty two. Two points sharing a prefix are in the same cell,
// and a longer prefix is a smaller cell, so who is within two kilometres
// becomes a range scan on an indexed string column. Distance against every row
// is the version that gets slower as the whole user base grows rather than as
// one friend list grows.
fun geoHash(lat: Double, lon: Double, precision: Int): String {
    var latMin = -90.0
    var latMax = 90.0
    var lonMin = -180.0
    var lonMax = 180.0
    val hash = StringBuilder(precision)
    var evenBit = true
    var bit = 0
    var index = 0

    while (hash.length < precision) {
        if (evenBit) {
            val mid = (lonMin + lonMax) / 2
            if (lon >= mid) { index = index * 2 + 1; lonMin = mid } else { index *= 2; lonMax = mid }
        } else {
            val mid = (latMin + latMax) / 2
            if (lat >= mid) { index = index * 2 + 1; latMin = mid } else { index *= 2; latMax = mid }
        }
        evenBit = !evenBit
        if (++bit == 5) {
            hash.append(BASE32[index])
            bit = 0
            index = 0
        }
    }
    return hash.toString()
}

// The longest prefix whose cell is still at least as wide as the radius, which
// is the smallest cell that can hold the search.
fun precisionFor(radiusMetres: Int): Int =
    CELL_METRES.indexOfLast { it >= radiusMetres }.let { if (it < 0) 1 else it + 1 }

// The eight cells around this one, and the edge case every first implementation
// misses. A friend fifty metres away can sit on the far side of a boundary and
// share no prefix at all, so the query is this cell plus its neighbours and the
// exact distance filter runs on the handful that come back.
fun neighbours(hash: String): List<String> {
    val (latMin, latMax, lonMin, lonMax) = bounds(hash)
    val latStep = latMax - latMin
    val lonStep = lonMax - lonMin
    val lat = (latMin + latMax) / 2
    val lon = (lonMin + lonMax) / 2
    return listOf(-1, 0, 1).flatMap { dLat ->
        listOf(-1, 0, 1).mapNotNull { dLon ->
            if (dLat == 0 && dLon == 0) {
                null
            } else {
                geoHash(
                    (lat + dLat * latStep).coerceIn(-90.0, 90.0),
                    (lon + dLon * lonStep + 540) % 360 - 180,
                    hash.length,
                )
            }
        }
    }
}

// Decoding back to the cell's bounds is the same walk as encoding, read in
// reverse, and it is all the neighbour step needs.
private data class Bounds(val latMin: Double, val latMax: Double, val lonMin: Double, val lonMax: Double)

private fun bounds(hash: String): Bounds {
    var latMin = -90.0
    var latMax = 90.0
    var lonMin = -180.0
    var lonMax = 180.0
    var evenBit = true
    for (character in hash) {
        val index = BASE32.indexOf(character)
        for (b in 4 downTo 0) {
            val high = (index shr b) and 1 == 1
            if (evenBit) {
                val mid = (lonMin + lonMax) / 2
                if (high) lonMin = mid else lonMax = mid
            } else {
                val mid = (latMin + latMax) / 2
                if (high) latMin = mid else latMax = mid
            }
            evenBit = !evenBit
        }
    }
    return Bounds(latMin, latMax, lonMin, lonMax)
}

// What comes back to the client, and it is not a coordinate. A friend is
// nearby, under a kilometre, and that is the whole payload. Exact positions
// would tell every requester where their friends live to house level
// precision, which the feature never needed in order to work.
enum class DistanceBucket(val maxMetres: Int) {
    HERE(200), CLOSE(1_000), NEARBY(5_000), FAR(Int.MAX_VALUE);

    companion object {
        fun of(metres: Int) = entries.first { metres <= it.maxMetres }
    }
}

package com.androidinterview.nearby.location

// The battery half of the answer. A fixed interval is the wrong shape, because
// a phone on a desk produces the same location eight hundred times and a phone
// in a car produces a genuinely different one every few seconds. The cadence
// follows detected activity, from the activity recognition API rather than a
// timer, and the fused provider runs at balanced accuracy rather than asking
// for continuous GPS.
//
// STILL is zero rather than a slow interval. Still means stop asking, and
// resuming is driven by the activity transition rather than by polling to find
// out whether the phone moved.
enum class Activity(val intervalMillis: Long) {
    STILL(0), WALKING(60_000), CYCLING(30_000), DRIVING(15_000)
}

// Fixes are queued and sent together. One radio wake for eight updates costs a
// fraction of eight wakes, and on a bad connection the queue simply grows and
// flushes on reconnect instead of the feature failing outright.
class UpdatePolicy(private val batchSize: Int, private val maxBatchAgeMillis: Long) {

    fun shouldFlush(queued: Int, oldestQueuedAt: Long, nowMillis: Long): Boolean =
        queued >= batchSize || (queued > 0 && nowMillis - oldestQueuedAt >= maxBatchAgeMillis)
}

package com.androidinterview.nearby.share

// Sharing is per friend and expires by itself. A single global toggle is the
// design that goes wrong, because the person who turned it on for one evening
// two years ago is still broadcasting.
//
// A grant is one directional. Mutual visibility is two grants, one each way,
// and nothing here quietly turns one into the other.
//
// This runs on the server too, and the server copy is the one that counts. The
// nearby query intersects the geospatial index with the grants other people
// have made to the requester, so a client can never ask about somebody who did
// not share with it.
class SharePolicy {

    private val grants = mutableMapOf<String, Long>()

    fun share(friendId: String, untilMillis: Long) {
        grants[friendId] = untilMillis
    }

    // Revoking deletes the stored cell as well as the grant. Hiding a position
    // the server still holds is not a privacy story.
    fun stop(friendId: String) = grants.remove(friendId)

    fun sharingWith(friendId: String, nowMillis: Long) = (grants[friendId] ?: 0) > nowMillis

    // The foreground service notification is not decoration and not optional.
    // If anything is being published at all, the user can see that it is.
    fun indicatorVisible(nowMillis: Long) = grants.values.any { it > nowMillis }
}