System design interviews can be a daunting part of the interview process for Android Engineers. While the focus often leans towards architecture, performance, scalability, and reliability, many system design concepts are transferable to mobile development, especially when working with Kotlin and Jetpack Compose. In this article, we’ll explore 12 essential algorithms that play a pivotal role in system design, offering insights into how they can be used effectively in Android Kotlin Compose-based applications.
1. Bloom Filter: Reducing Costly Lookups
A simple example of a Bloom Filter to prevent unnecessary database or network lookups.
class BloomFilter(val size: Int, val hashFunctions: List<(String) -> Int>) {
private val bitSet = BitSet(size)
fun add(element: String) {
hashFunctions.forEach {
val hash = it(element) % size
bitSet.set(hash)
}
}
fun contains(element: String): Boolean {
return hashFunctions.all {
val hash = it(element) % size
bitSet.get(hash)
}
}
}
// Usage Example
val bloomFilter = BloomFilter(
size = 1000,
hashFunctions = listOf(
{ input: String -> input.hashCode() },
{ input: String -> input.length.hashCode() }
)
)
bloomFilter.add("John")
println(bloomFilter.contains("John")) // Should return true
println(bloomFilter.contains("Alice")) // Likely false
2. Geohash: Location-Based Services
Using Geohash for nearby locations.
// Example using Geohash library
import org.geohash.GeoHash
import com.google.android.gms.maps.model.LatLng
fun getNearbyGeohash(latitude: Double, longitude: Double): String {
val geohash = GeoHash.withCharacterPrecision(latitude, longitude, 7)
return geohash.toBase32()
}
val geohash = getNearbyGeohash(37.7749, -122.4194) // San Francisco
println("Geohash: $geohash")
3. Hyperloglog: Estimating Unique Elements
This can be implemented by tracking unique user IDs or events in a mobile app.
// Using Hyperloglog for tracking unique views
val uniqueUsers = mutableSetOf<String>()
fun addUniqueUser(userId: String) {
uniqueUsers.add(userId)
}
fun getUniqueUserCount() = uniqueUsers.size
// Simulate adding users
addUniqueUser("user1")
addUniqueUser("user2")
addUniqueUser("user1")
println("Unique users: ${getUniqueUserCount()}")
4. Consistent Hashing: Efficient Data Distribution
A consistent hashing example to distribute tasks.
class ConsistentHashing(private val nodes: List<String>) {
fun getNode(key: String): String {
val hash = key.hashCode()
val nodeIndex = Math.abs(hash % nodes.size)
return nodes[nodeIndex]
}
}
val nodes = listOf("Node A", "Node B", "Node C")
val consistentHash = ConsistentHashing(nodes)
println(consistentHash.getNode("user1")) // It could print "Node B"
5. Merkle Tree: Verifying Data Integrity
Example of a Merkle Tree used for verifying data integrity.
data class MerkleNode(val hash: String, val left: MerkleNode? = null, val right: MerkleNode? = null)
fun createMerkleTree(data: List<String>): MerkleNode {
if (data.size == 1) {
return MerkleNode(data[0])
}
val mid = data.size / 2
val left = createMerkleTree(data.subList(0, mid))
val right = createMerkleTree(data.subList(mid, data.size))
val combinedHash = (left.hash + right.hash).hashCode().toString()
return MerkleNode(combinedHash, left, right)
}
val tree = createMerkleTree(listOf("A", "B", "C", "D"))
println("Root Hash: ${tree.hash}")
6. Raft Algorithm: Consensus in Distributed Databases
A simplified simulation of Raft’s consensus in Android.
// Simulate Raft leader election process
class RaftLeaderElection(val nodes: List<String>) {
private var leader: String? = null
fun electLeader(): String {
leader = nodes.random()
return leader!!
}
}
val raft = RaftLeaderElection(listOf("Node A", "Node B", "Node C"))
println("Leader is: ${raft.electLeader()}")
7. Lossy Count: Estimating Item Frequencies
Using the Lossy Count algorithm to estimate frequencies of items.
class LossyCount(val threshold: Int) {
private val counts = mutableMapOf<String, Int>()
fun add(element: String) {
counts[element] = counts.getOrDefault(element, 0) + 1
}
fun getFrequencies(): Map<String, Int> {
return counts.filter { it.value >= threshold }
}
}
val lossyCount = LossyCount(2)
lossyCount.add("Apple")
lossyCount.add("Apple")
lossyCount.add("Banana")
println(lossyCount.getFrequencies()) // Expected: {Apple=2}
8. QuadTree: Spatial Partitioning
A basic implementation of QuadTree for location-based services.
class QuadTree(val boundary: Rect, val capacity: Int) {
private val points = mutableListOf<LatLng>()
private var divided = false
fun insert(point: LatLng): Boolean {
if (!boundary.contains(point)) return false
if (points.size < capacity) {
points.add(point)
return true
}
if (!divided) {
subdivide()
}
// Insert into the appropriate quadrant
return true
}
private fun subdivide() {
divided = true
// Divide into 4 quadrants
}
}
data class LatLng(val latitude: Double, val longitude: Double)
data class Rect(val latMin: Double, val latMax: Double, val lonMin: Double, val lonMax: Double) {
fun contains(point: LatLng) = point.latitude in latMin..latMax && point.longitude in lonMin..lonMax
}
val rect = Rect(37.0, 38.0, -122.5, -123.0)
val quadTree = QuadTree(rect, 2)
val point = LatLng(37.7749, -122.4194)
quadTree.insert(point)
9. Operational Transformation: Real-Time Collaboration
Basic collaboration on shared data.
// Simulate real-time text collaboration
class OperationalTransformation {
var document = StringBuilder()
fun applyOperation(op: String) {
document.append(op)
}
fun getDocument() = document.toString()
}
val ot = OperationalTransformation()
ot.applyOperation("Hello ")
ot.applyOperation("World!")
println("Document: ${ot.getDocument()}")
10. Leaky Bucket: Rate Limiting in APIs
Simple Leaky Bucket algorithm for controlling API rate limits.
class LeakyBucket(val capacity: Int, val leakRate: Int) {
private var waterLevel = 0
fun addRequest() {
if (waterLevel < capacity) {
waterLevel++
println("Request added. Water level: $waterLevel")
} else {
println("Bucket full, try again later.")
}
}
fun leak() {
if (waterLevel > 0) {
waterLevel -= leakRate
}
}
}
val bucket = LeakyBucket(capacity = 5, leakRate = 1)
bucket.addRequest() // Should succeed
bucket.addRequest() // Should succeed
bucket.leak() // Leaks 1 unit
11. Rsync: File Synchronization
Simplified rsync simulation for syncing files.
fun syncFiles(source: String, destination: String) {
println("Syncing files from $source to $destination")
// Simulate file sync
}
syncFiles("localFile", "remoteServer")
12. Ray Casting: Collision Detection
A basic example for collision detection in Android.
// Simulate ray casting for collision detection in 2D space
fun isCollision(ray: Line, objectShape: Rect): Boolean {
return ray.intersects(objectShape)
}
data class Line(val start: Point, val end: Point) {
fun intersects(rect: Rect): Boolean {
// Logic to check if the line intersects the rectangle
return true
}
}
data class Point(val x: Int, val y: Int)
data class Rect(val x: Int, val y: Int, val width: Int, val height: Int)
val ray = Line(Point(0, 0), Point(5, 5))
val rect = Rect(2, 2, 2, 2)
println(isCollision(ray, rect)) // Will print true if there's a collision
Each of these algorithms can be adapted to Android Kotlin Compose for efficient, scalable applications, enabling you to optimize performance and user experience.
📢 Feedback: Did you find this article helpful? Let me know your thoughts or suggestions for improvements! 😊 please leave a comment below. I’d love to hear from you! 👇
Happy coding! 💻✨
Posts
0 comments:
Post a Comment