Showing posts with label Interview Coding. Show all posts
Showing posts with label Interview Coding. Show all posts

Building a Scalable Architecture for an eCommerce App with Jetpack Compose

Design a scalable architecture for an eCommerce app built with Jetpack Compose. This architecture will support key features like offline product caching, real-time inventory updates, paginated product listings, and modular UI with feature separation. We’ll focus on best practices for scalability, maintainability, and modularity, ensuring the app can handle future growth efficiently.

Overview of the App Architecture

The architecture for this app will be based on Clean Architecture, separating concerns into Presentation, Domain, and Data layers. We will also modularize the app to ensure flexibility, and each feature (e.g., Product, Cart, Inventory) will be handled in a separate module.

We'll incorporate Jetpack Compose for UI, Room for offline caching, Paging 3 for efficient product listing, and Firebase/Realtime Database or WebSocket for real-time inventory updates.

Layered Architecture Breakdown

1. Presentation Layer (UI)

The Presentation Layer is responsible for the user interface and user interactions. With Jetpack Compose, we can easily build reactive and dynamic UIs. The UI will be composed of Composables, while ViewModels will handle the UI state and interact with the Domain layer.

Key Components:

  • Jetpack Compose: For building the user interface in a declarative way.

  • ViewModel: Handles state management and communicates with the Domain layer.

  • StateFlow/LiveData: For managing UI state like loading, success, and error states.

  • Navigation: Jetpack Navigation Compose to manage the app's navigation.

Example Composables:

@Composable
fun ProductListScreen(viewModel: ProductListViewModel) {
    val products by viewModel.products.collectAsState()
    val isLoading by viewModel.isLoading.collectAsState()
    val isError by viewModel.isError.collectAsState()

    if (isLoading) {
        CircularProgressIndicator()
    } else if (isError) {
        Text("Error fetching products")
    } else {
        LazyColumn {
            items(products) { product ->
                ProductItem(product = product)
            }
        }
    }
}

2. Domain Layer

The Domain Layer holds the business logic and use cases. This layer abstracts the data layer and provides clean interfaces for the Presentation layer to interact with. The domain layer consists of Use Cases and Repository interfaces.

Key Components:

  • Use Cases: Define business logic, such as fetching products, pagination, and handling inventory.

  • Repositories: Interface that defines data-fetching operations like fetching products, updating inventory, and more.

Example Use Case:

class GetProductListUseCase(private val productRepository: ProductRepository) {
    suspend operator fun invoke(page: Int): Result<List<Product>> {
        return productRepository.getPaginatedProducts(page)
    }
}

3. Data Layer

The Data Layer handles data fetching, caching, and the communication with external services (like APIs and Firebase). This layer includes repositories for both remote data (API calls) and local data (Room Database). We’ll use Room for offline caching and Paging 3 for efficient data loading.

Key Components:

  • Room: Used for offline caching of products and inventory data.

  • API Services: Retrofit or Ktor for interacting with remote APIs for products and real-time updates.

  • Firebase/Realtime Database: Used for real-time inventory updates.

  • Paging 3: Efficiently handles pagination for product lists.

Offline Caching Example with Room:

@Entity(tableName = "product")
data class ProductEntity(
    @PrimaryKey val id: Int,
    val name: String,
    val price: Double,
    val stockQuantity: Int
)

@Dao
interface ProductDao {
    @Insert(onConflict = OnConflictStrategy.REPLACE)
    suspend fun insertProducts(products: List<ProductEntity>)

    @Query("SELECT * FROM product")
    suspend fun getAllProducts(): List<ProductEntity>
}

Repository Example:

class ProductRepositoryImpl(
    private val apiService: ApiService,
    private val productDao: ProductDao
) : ProductRepository {

    override suspend fun getPaginatedProducts(page: Int): Result<List<Product>> {
        val productsFromCache = productDao.getAllProducts()
        if (productsFromCache.isNotEmpty()) {
            return Result.success(productsFromCache.map { it.toDomain() })
        }

        try {
            val response = apiService.getProducts(page)
            productDao.insertProducts(response.products.map { it.toEntity() })
            return Result.success(response.products.map { it.toDomain() })
        } catch (e: Exception) {
            return Result.failure(e)
        }
    }
}

4. Real-Time Inventory Updates

For real-time inventory updates, we can use Firebase Realtime Database or WebSocket. When the stock quantity of a product changes, the app will update the product's data in real time, and the UI will reflect the updated information.

Firebase Example:

class FirebaseInventoryRepository {
    private val database = FirebaseDatabase.getInstance().getReference("inventory")

    fun observeInventoryUpdates(productId: Int, callback: (Int) -> Unit) {
        database.child("products").child(productId.toString()).child("stockQuantity")
            .addValueEventListener(object : ValueEventListener {
                override fun onDataChange(snapshot: DataSnapshot) {
                    val stockQuantity = snapshot.getValue(Int::class.java) ?: 0
                    callback(stockQuantity)
                }

                override fun onCancelled(error: DatabaseError) {
                    // Handle error
                }
            })
    }
}

5. Modularization

To ensure that the app remains maintainable as it grows, we will modularize the codebase. Each feature, such as the Product module, Cart module, and Inventory module, will be developed in separate modules.

This separation ensures that each module is responsible for one feature and can be developed and tested independently. It also improves build times and allows for easier team collaboration.

Modularization Example:

// In build.gradle for 'product' module
dependencies {
    implementation project(":core")
    implementation "androidx.compose.ui:ui:$compose_version"
}

6. Offline Handling and Connectivity

The app should handle offline scenarios gracefully, providing users with cached data when they are not connected to the internet. We can use the ConnectivityManager to check the network status and display cached products when offline. When the network is available, the app should fetch real-time data.

Offline Strategy:

  • Room Database: Cache products and inventory locally.

  • Network Status: Use ConnectivityManager to determine if the app is online or offline.

7. Real-Time Sync with Firebase

Firebase can be used for real-time syncing of inventory data. Using Firebase Realtime Database, the app can listen for changes to inventory quantities and update the UI instantly. Alternatively, WebSocket can be used to get real-time updates from the backend.

My thoughts

This architecture leverages modern Android tools like Jetpack Compose, Room, Paging 3, Firebase, and Clean Architecture to build a scalable and maintainable eCommerce app. The use of modularization ensures that each feature is self-contained, while the domain-driven design keeps the business logic separated from the UI.

By incorporating offline caching, real-time updates, and pagination, this architecture provides a robust foundation for building a seamless, scalable eCommerce experience that performs well even in scenarios with slow or no network connectivity.

📢 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! 💻

System Design Interviews in Android

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! 💻✨

Cracking the Senior Android Engineer Interview: What to Expect from Start to Finish

Stepping into the interview process for a Senior Android Engineer role can be both exciting and challenging. Whether you’re preparing for your dream job at a big tech firm or a promising startup, understanding the structure and topics across each interview stage is crucial.

In this blog, we’ll break down the commonly asked topics from the initial recruiter round to the final bar-raiser interview, including everything from Kotlin coding to system design and behavioral assessments.


 Initial HR/Recruiter Screening

This is mostly a soft round to gauge your fit for the role and company culture.

Topics:

  • Summary of your Android development experience

  • Key projects you've worked on (apps, user base, challenges)

  • Current role, notice period, and salary expectations

  • Why you're exploring new opportunities

  • Communication skills and professional demeanor


Online Technical Coding Round

Here the focus is on core problem-solving skills using Kotlin.

Topics to Prepare:

  • Data Structures & Algorithms:

    • Arrays, LinkedLists, Trees, Graphs, HashMaps

    • Sorting, searching, recursion, backtracking

  • Kotlin-specific Concepts:

    • Coroutines (Job, SupervisorJob, Dispatchers)

    • Flow, StateFlow, and Channels

    • Lambda expressions, extension functions, and delegates

  • Concurrency & Asynchronous Programming in Android

Tools: HackerRank, Codility, or take-home assignments


System Design Interview

This round evaluates how you architect scalable, modular Android apps.

Key Focus Areas:

  • Clean Architecture (Presentation → Domain → Data layers)

  • MVVM vs MVI vs MVP — and when to choose which

  • Real-world design:

    • Offline-first apps

    • Syncing with API and caching (Room, DataStore)

    • Push notifications & background sync (WorkManager)

  • Dependency Injection (Hilt/Dagger2)

  • Multi-module project structuring

Example: “Design a banking app with authentication, balance display, and transaction history”


Android Platform & Jetpack Deep Dive

Here, expect questions on Jetpack libraries, Compose UI, and platform internals.

Topics:

  • Jetpack Compose:

    • State management

    • Recomposition and performance pitfalls

  • Lifecycle Management:

    • ViewModel, LifecycleOwner, LifecycleObserver

  • Jetpack Libraries:

    • Navigation, Room, Paging, WorkManager, DataStore

  • Security:

    • Encrypted storage, biometric authentication, Keystore

  • Accessibility:

    • Compose semantics, TalkBack support, content descriptions


Testing & Debugging

A great Senior Android Engineer writes testable and maintainable code.

What You Should Know:

  • Unit Testing with JUnit, Mockito, MockK

  • UI Testing with Espresso and Compose testing APIs

  • Integration Testing with HiltTestApplication

  • Debugging ANRs, memory leaks (LeakCanary), performance bottlenecks

  • Using tools like Crashlytics, Logcat, StrictMode


CI/CD, DevOps, and Release Management

Modern Android teams value automation and fast feedback cycles.

Topics:

  • CI/CD tools: Jenkins, GitHub Actions, Bitrise

  • Gradle optimization, build flavors, product types

  • Feature flag implementation (Gradle + Firebase Remote Config)

  • Code quality enforcement: Detekt, Lint, SonarQube

  • Secure and efficient release strategies (Play Store, Firebase App Distribution)


Behavioral & Leadership Assessment

This round checks for team collaboration, mentorship, and decision-making skills.

Example Questions:

  • Tell us about a time you led a project or mentored a junior

  • How do you resolve disagreements with product or design teams?

  • What’s your strategy for balancing tech debt vs. feature delivery?

  • How do you stay updated with evolving Android trends?

Tip: Use the STAR method (Situation, Task, Action, Result) to answer.


Bar-Raiser or VP/CTO Round

This is the make-or-break round for many companies.

Focus Areas:

  • End-to-end ownership of features and impact

  • Trade-offs made during architecture decisions

  • Innovation, optimization, or cost-saving initiatives you've led

  • Long-term vision, technical leadership, and culture fit


🔚 Final Thoughts

Landing a Senior Android Engineer role isn’t just about writing great Kotlin code. It’s about demonstrating architectural mastery, leadership, and a product-first mindset across every round.

Start prepping smart by:

  • Practicing DSA in Kotlin

  • Building or refactoring a multi-module Compose app

  • Designing systems (like a chat app or e-commerce app)

  • Writing testable, clean code

  • Staying up to date with Jetpack and security best practices


What Next?

Want mock interview questions, detailed Kotlin exercises, or a full Android app architecture walkthrough? Drop a comment or subscribe for more deep-dives every week.


🔗 Related Reads:



📢 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! 💻✨

Bit Manipulation - Finding the missing number in a sequence in Kotlin


Problem Statement:

You are given an array containing n distinct numbers from 0 to n. Exactly one number in this range is missing from the array. You must find this missing number using bit manipulation techniques.

Example:

Input: [3, 0, 1]
Output: 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Explanation (using XOR):

A very efficient way to solve this using bit manipulation is to leverage XOR (^), which has these properties:

  • a ^ a = 0 (XOR of a number with itself is zero)
  • a ^ 0 = a (XOR of a number with zero is itself)
  • XOR is commutative and associative

Therefore, if we XOR all the indices and all the numbers, every number present will cancel out, leaving the missing number.


Implementation in Kotlin:

fun missingNumber(nums: IntArray): Int {
    var xor = nums.size // start with n, since array is from 0 to n
    for (i in nums.indices) {
        xor = xor xor i xor nums[i]
    }
    return xor
}

fun main() {
    println(missingNumber(intArrayOf(3, 0, 1))) // Output: 2
    println(missingNumber(intArrayOf(9,6,4,2,3,5,7,0,1))) // Output: 8
    println(missingNumber(intArrayOf(0,1))) // Output: 2
}

Complexity:

  • Time Complexity: O(n) (Iterates through the array once)
  • Space Complexity: O(1) (No extra space used)


Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback to improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Coin Change Problem in Kotlin: Multiple Approaches with Examples

The coin change problem is a classic leet coding challenge often encountered in technical interviews. The problem asks:

Given an array of coin denominations and a target amount, find the fewest number of coins needed to make up that amount. If it's not possible, return -1. You can use each coin denomination infinitely many times.

Here are multiple ways to solve the Coin Change problem in Kotlin, with detailed explanations and code examples. I'll present two distinct approaches:

  1. Dynamic Programming (Bottom-Up approach)
  2. Recursive Approach with Memoization (Top-Down)

Approach 1: Dynamic Programming (Bottom-Up)

Idea:

  • Build an array dp where each dp[i] indicates the minimum number of coins required for the amount i.
  • Initialize the array with a large number (representing infinity).
  • The base case is dp[0] = 0.

Steps:

  • For each amount from 1 to amount, try every coin denomination.
  • Update dp[i] if using the current coin leads to fewer coins than the current value.

Kotlin Solution:

fun coinChange(coins: IntArray, amount: Int): Int {
    val max = amount + 1
    val dp = IntArray(amount + 1) { max }
    dp[0] = 0

    for (i in 1..amount) {
        for (coin in coins) {
            if (coin <= i) {
                dp[i] = minOf(dp[i], dp[i - coin] + 1)
            }
        }
    }
    
    return if (dp[amount] > amount) -1 else dp[amount]
}

// Usage:
fun main() {
    println(coinChange(intArrayOf(1, 2, 5), 11)) // Output: 3
    println(coinChange(intArrayOf(2), 3))        // Output: -1
    println(coinChange(intArrayOf(1), 0))        // Output: 0
}

Time Complexity: O(amount * coins.length)
Space Complexity: O(amount)


Approach 2: Recursive Approach with Memoization (Top-Down)

Idea:

  • Define a recursive function solve(remainingAmount) that returns the minimum coins required.
  • Use memoization to store previously computed results, avoiding redundant calculations.

Steps:

  • For each call, explore all coin denominations and recursively find solutions.
  • Cache results to avoid recomputation.

Kotlin Solution:

fun coinChangeMemo(coins: IntArray, amount: Int): Int {
    val memo = mutableMapOf<Int, Int>()

    fun solve(rem: Int): Int {
        if (rem < 0) return -1
        if (rem == 0) return 0
        if (memo.containsKey(rem)) return memo[rem]!!

        var minCoins = Int.MAX_VALUE
        for (coin in coins) {
            val res = solve(rem - coin)
            if (res >= 0 && res < minCoins) {
                minCoins = res + 1
            }
        }

        memo[rem] = if (minCoins == Int.MAX_VALUE) -1 else minCoins
        return memo[rem]!!
    }

    return solve(amount)
}

// Usage:
fun main() {
    println(coinChangeMemo(intArrayOf(1, 2, 5), 11)) // Output: 3
    println(coinChangeMemo(intArrayOf(2), 3))        // Output: -1
    println(coinChangeMemo(intArrayOf(1), 0))        // Output: 0
}

Time Complexity: O(amount * coins.length)
Space Complexity: O(amount) (stack space + memoization map)


Quick Comparison:

Approach Time Complexity Space Complexity When to Use?
Dynamic Programming (Bottom-Up) O(amount * coins.length) O(amount) Optimal, preferred for efficiency
Recursive with Memoization O(amount * coins.length) O(amount) Easy to understand recursion

Edge Cases Handled:

  • If amount is 0, both solutions immediately return 0.
  • If the amount cannot be composed by given coins, they return -1.

Summary:

  • Dynamic Programming is the optimal, most widely used solution for this problem.
  • Recursive Approach with memoization demonstrates understanding of recursion and memoization principles.

You can select either based on clarity, readability, or efficiency needs. The DP solution is highly recommended in competitive programming or technical interviews for optimal performance. 

Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback to improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Code Challenge: Number of Islands in Kotlin

The Number of Islands problem is a common interview question that involves counting the number of islands in a 2D grid. Each island is made up of connected pieces of land (denoted as '1') surrounded by water (denoted as '0'). The challenge is to count how many separate islands exist in the grid, where an island is formed by horizontally or vertically adjacent lands.



We will discuss multiple ways to solve this problem, explaining their pros and cons. Let's dive into solving this problem using Kotlin.


Problem Definition

Given a 2D binary grid grid, return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. The grid is surrounded by water on all sides.

Example 1:

Input:

[
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "0", "0", "0"]
]

Output:

1

Example 2:

Input:

[
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"]
]

Output:

3

Approach 1: Depth-First Search (DFS)

The most intuitive approach is to use Depth-First Search (DFS). We start from each land cell ('1'), mark it as visited (or change it to water '0'), and recursively check its adjacent cells (up, down, left, right). Every time we find an unvisited land cell, we count it as a new island.

Algorithm:

  1. Traverse the grid.
  2. If we find a '1', increment the island count and use DFS to mark the entire island as visited.
  3. For each DFS, recursively mark the neighboring land cells.

Kotlin Implementation:

fun numIslands(grid: Array<CharArray>): Int {
    if (grid.isEmpty()) return 0
    var count = 0

    // Define DFS function
    fun dfs(grid: Array<CharArray>, i: Int, j: Int) {
        // Return if out of bounds or at water
        if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == '0') return
        // Mark the land as visited
        grid[i][j] = '0'
        // Visit all 4 adjacent cells
        dfs(grid, i + 1, j) // down
        dfs(grid, i - 1, j) // up
        dfs(grid, i, j + 1) // right
        dfs(grid, i, j - 1) // left
    }

    // Iterate over the grid
    for (i in grid.indices) {
        for (j in grid[i].indices) {
            if (grid[i][j] == '1') {
                // Found a new island
                count++
                dfs(grid, i, j)
            }
        }
    }
    return count
}

Time Complexity:

  • O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.

Space Complexity:

  • O(m * n) in the worst case (if the entire grid is land), as we may need to store all cells in the call stack due to recursion.

Approach 2: Breadth-First Search (BFS)

We can also use Breadth-First Search (BFS). Instead of using recursion like in DFS, we use a queue to explore all adjacent cells iteratively. The process is similar, but the main difference lies in the order of exploration.

Algorithm:

  1. Start from an unvisited land cell ('1').
  2. Use a queue to explore all adjacent land cells and mark them as visited.
  3. Each BFS initiation represents a new island.

Kotlin Implementation:

fun numIslands(grid: Array<CharArray>): Int {
    if (grid.isEmpty()) return 0
    var count = 0
    val directions = arrayOf(intArrayOf(0, 1), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(-1, 0))

    fun bfs(i: Int, j: Int) {
        val queue: LinkedList<Pair<Int, Int>>= LinkedList()
        queue.offer(Pair(i, j))
        grid[i][j] = '0' // Mark the starting cell as visited

        while (queue.isNotEmpty()) {
            val (x, y) = queue.poll()
            for (dir in directions) {
                val newX = x + dir[0]
                val newY = y + dir[1]
                if (newX in grid.indices && newY in grid[0].indices && grid[newX][newY] == '1') {
                    grid[newX][newY] = '0' // Mark as visited
                    queue.offer(Pair(newX, newY))
                }
            }
        }
    }

    for (i in grid.indices) {
        for (j in grid[i].indices) {
            if (grid[i][j] == '1') {
                count++
                bfs(i, j)
            }
        }
    }
    return count
}

Time Complexity:

  • O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.

Space Complexity:

  • O(m * n), which is required for the queue in the worst case.

Approach 3: Union-Find (Disjoint Set)

The Union-Find (or Disjoint Set) approach is another efficient way to solve this problem. The idea is to treat each land cell as an individual component and then union adjacent land cells. Once all unions are complete, the number of islands is simply the number of disjoint sets.

Algorithm:

  1. Initialize each land cell as a separate island.
  2. For each neighboring land cell, perform a union operation.
  3. The number of islands will be the number of disjoint sets.

Kotlin Implementation:

class UnionFind(private val m: Int, private val n: Int) {
    private val parent = IntArray(m * n) { it }

    fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x]) // Path compression
        return parent[x]
    }

    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        if (rootX != rootY) parent[rootX] = rootY
    }

    fun getCount(): Int {
        return parent.count { it == it }
    }
}

fun numIslands(grid: Array<CharArray>): Int {
    if (grid.isEmpty()) return 0
    val m = grid.size
    val n = grid[0].size
    val uf = UnionFind(m, n)

    for (i in grid.indices) {
        for (j in grid[i].indices) {
            if (grid[i][j] == '1') {
                val index = i * n + j
                // Try to union with adjacent cells
                if (i + 1 &lt; m &amp;&amp; grid[i + 1][j] == '1') uf.union(index, (i + 1) * n + j)
                if (j + 1 &lt; n &amp;&amp; grid[i][j + 1] == '1') uf.union(index, i * n + (j + 1))
            }
        }
    }
    val islands = mutableSetOf&lt;Int&gt;()
    for (i in grid.indices) {
        for (j in grid[i].indices) {
            if (grid[i][j] == '1') {
                islands.add(uf.find(i * n + j))
            }
        }
    }
    return islands.size
}

Time Complexity:

  • O(m * n), as we perform a union operation for each adjacent land cell.

Space Complexity:

  • O(m * n) for the union-find parent array.

Calling in main():

fun main() {
    val grid1 = arrayOf(
        charArrayOf('1', '1', '1', '1', '0'),
        charArrayOf('1', '1', '0', '1', '0'),
        charArrayOf('1', '1', '0', '0', '0'),
        charArrayOf('0', '0', '0', '0', '0')
    )
    println("Number of Islands : ${numIslands(grid1)}")  // Output: 1
    
    val grid2 = arrayOf(
        charArrayOf('1', '1', '0', '0', '0'),
        charArrayOf('1', '1', '0', '0', '0'),
        charArrayOf('0', '0', '1', '0', '0'),
        charArrayOf('0', '0', '0', '1', '1')
    )
    println("Number of Islands : ${numIslands(grid2)}")  // Output: 3
}



Which Solution is Best?

  1. DFS/BFS (Approaches 1 & 2): These are the simplest and most intuitive solutions. Both have a time complexity of O(m * n), which is optimal for this problem. DFS uses recursion, which might run into issues with large grids due to stack overflow, but BFS avoids this problem by using an iterative approach. If you want simplicity and reliability, BFS is preferred.

  2. Union-Find (Approach 3): This approach is more advanced and has a similar time complexity of O(m * n). However, it can be more difficult to understand and implement. It also performs well with path compression and union by rank, but for this problem, the DFS/BFS approach is usually sufficient and easier to implement.

Conclusion

For this problem, BFS is the recommended solution due to its iterative nature, which avoids recursion issues with large grids, while still being efficient and easy to understand.


Full Problem description in LeetCode


Thank you for reading my latest article! I would greatly appreciate your feedback to improve my future posts. 💬 Was the information clear and valuable? Are there any areas you think could be improved? Please share your thoughts in the comments or reach out directly. Your insights are highly valued. 👇😊.  Happy coding! 💻✨

Coding Challenge: Interview - > Shorten Url

URL shortening involves generating abbreviated versions of long URLs, referred to as "short links." When users access these short links, they are automatically redirected to the original, longer URL. Short links offer various benefits, such as saving space in display, print, messages, or tweets. Furthermore, shorter URLs decrease the likelihood of users making typing errors.

import java.util.*
 
class URLShortener {
    private val idToUrlMap = HashMap<String, String>()
    private val urlToIdMap = HashMap<String, String>()
    private val BASE_URL = "http://short.url/"
    private val ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
 
    fun shortenURL(longURL: String): String {
        if (urlToIdMap.containsKey(longURL)) {
            return BASE_URL + urlToIdMap[longURL]
        }
        val id = generateID()
        idToUrlMap[id] = longURL
        urlToIdMap[longURL] = id
        return BASE_URL + id
    }
 
    fun expandURL(shortURL: String): String {
        val id = shortURL.substring(BASE_URL.length)
        return idToUrlMap[id] ?: "URL not found"
    }
 
    private fun generateID(): String {
        val random = Random()
        val sb = StringBuilder()
        repeat(6) {
            sb.append(ALPHABET[random.nextInt(ALPHABET.length)])
        }
        return sb.toString()
    }
}
 
fun main() {
    val urlShortener = URLShortener()
    val longURL = "https://www.example.com"
    val shortURL = urlShortener.shortenURL(longURL)
    println("Shortened URL: $shortURL")
    val expandedURL = urlShortener.expandURL(shortURL)
    println("Expanded URL: $expandedURL")
}
 

Details of above code with explanation

  • idToUrlMap: This HashMap maps shortened IDs (generated by the shortening process) to their corresponding original URLs. It facilitates the expansion process.
  • urlToIdMap: This HashMap maps original URLs to their corresponding shortened IDs. It helps avoid duplication of shortened URLs for the same original URL.
  • BASE_URL: This constant string represents the base URL for the shortened URLs. All shortened URLs generated by this URL shortener will start with this base URL.
  • ALPHABET: This string contains the characters used to generate the random alphanumeric IDs for shortening URLs.
  • shortenURL(longURL: String): This method takes a long URL as input and generates a shortened URL for it. If the long URL has already been shortened before, it retrieves the existing shortened URL. Otherwise, it generates a new shortened ID, maps it to the long URL, and returns the shortened URL.
  • expandURL(shortURL: String): This method takes a shortened URL as input and returns the corresponding original URL. It extracts the ID from the shortened URL and looks it up in the idToUrlMap. If the ID exists in the map, it returns the corresponding original URL; otherwise, it indicates that the URL is not found.
  • generateID(): This private method generates a random alphanumeric ID of length 6 using characters from the ALPHABET string. It ensures uniqueness for each shortened URL.
Happy Coding ✌

Coding Challenge: Interview - > Rotate Image

 You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

 Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

 

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Solutions:

fun rotate(matrix: Array<IntArray>) {
    val n = matrix.size
    
    // Transpose the matrix
    for (i in 0 until n) {
        for (j in i until n) {
            val temp = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = temp
        }
    }
    
    // Reverse each row
    for (i in 0 until n) {
        var left = 0
        var right = n - 1
        while (left < right) {
            val temp = matrix[i][left]
            matrix[i][left] = matrix[i][right]
            matrix[i][right] = temp
            left++
            right--
        }
    }
}


Here is the more details of each details

Certainly! Let's break down the solution step by step:

  1. Transpose the matrix:

    • To transpose the matrix means to swap its rows and columns. We iterate over the upper triangle of the matrix (i.e., i from 0 to n-1, j from i to n-1) and swap each element with its corresponding element across the diagonal.
    • For example, if we have a matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]], transposing it will give us [[1, 4, 7], [2, 5, 8], [3, 6, 9]].
  2. Reverse each row:

    • After transposing the matrix, we iterate over each row, and for each row, we reverse its elements.
    • This reversal effectively rotates each row by 180 degrees.
    • For example, if we have a transposed matrix [[1, 4, 7], [2, 5, 8], [3, 6, 9]], reversing each row will give us [[7, 4, 1], [8, 5, 2], [9, 6, 3]].

By performing these two operations, we achieve the desired result of rotating the matrix by 90 degrees clockwise. The key insight is that transposing the matrix swaps rows and columns, effectively rotating it by 90 degrees counterclockwise. Then, reversing each row completes the rotation to 90 degrees clockwise. This solution modifies the input matrix in-place without using any extra space.


Happy Coding ✌!