{"id":988,"date":"2026-11-12T09:48:00","date_gmt":"2026-11-12T08:48:00","guid":{"rendered":"https:\/\/grindloop.ai\/blog\/?p=988"},"modified":"2026-11-11T17:03:46","modified_gmt":"2026-11-11T16:03:46","slug":"kotlin-coding-interview-time-complexity","status":"publish","type":"post","link":"https:\/\/grindloop.ai\/blog\/kotlin-coding-interview-time-complexity\/","title":{"rendered":"Kotlin Coding Interview Time Complexity: The List Calls That Make Your Big-O Wrong"},"content":{"rendered":"<p>Your Kotlin coding interview time complexity answer gets checked against the code you actually wrote. Kotlin makes a gap between the two easy to miss. A <code>MutableList<\/code> is an <code>ArrayList<\/code> by default. So <code>next in visited<\/code> scans the whole list. And <code>queue.removeAt(0)<\/code> shifts every element left. Each looks like one cheap call. Put either inside a loop and your O(n) answer can become O(n\u00b2). An interviewer can read the loop and the call together. If they spot the mismatch, that&#8217;s what goes in the notes. The fix is a habit before you say any Big-O. Name the data structure behind each lookup, insert and removal. Then price it out loud. Use a <code>HashSet<\/code> or a <code>BooleanArray<\/code> for membership. Use <code>ArrayDeque<\/code> for a queue. Then state the bound once, with the structures in the sentence. A sample script for that sentence is below.<\/p>\n<h2>Interviewers check your stated Big-O against the lines on screen<\/h2>\n<p>Complexity analysis is on the scorecard. <a href=\"https:\/\/www.techinterviewhandbook.org\/coding-interview-rubrics\/\" target=\"_blank\" rel=\"noopener\">Yangshun Tay&#8217;s coding interview rubrics<\/a> list it under problem solving. One basic signal is that the candidate worked out time and space complexity accurately. Tay is an ex-Meta staff engineer. His handbook is free, though the page carries ads for the paid prep site GreatFrontEnd. His <a href=\"https:\/\/www.techinterviewhandbook.org\/coding-interview-cheatsheet\/\" target=\"_blank\" rel=\"noopener\">coding interview cheatsheet<\/a> asks you to state complexity twice. First for the approach, then again for the code you finished.<\/p>\n<p>The second check is where Kotlin bites. Your approach can be right while your code is slower. An interviewer who reads <code>removeAt(0)<\/code> in a loop may ask what it costs. If you answer &#8220;constant&#8221;, the note can say your analysis was wrong. Our post on <a href=\"https:\/\/grindloop.ai\/blog\/algorithm-round-android-inter\/\">what the algorithm round tests<\/a> covers why practicing in Kotlin matters. Hidden collection costs are one reason.<\/p>\n<h2>The running example is a grid BFS that claims O(rows \u00d7 cols)<\/h2>\n<p>Here&#8217;s a common prompt shape. You get an open grid and need the fewest steps from the top-left cell to the bottom-right. Breadth-first search is the right idea. Each cell enters the queue once, so the approach is O(rows \u00d7 cols). Below is a version that&#8217;s easy to type under time pressure. The code is ours, written for this post.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"\">fun minSteps(n: Int): Int {\n    val queue = mutableListOf(0)          \/\/ cell index = row * n + col\n    val visited = mutableListOf(0)\n    val dist = IntArray(n * n)\n    while (queue.isNotEmpty()) {\n        val cell = queue.removeAt(0)\n        val r = cell \/ n\n        val c = cell % n\n        for ((dr, dc) in listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)) {\n            val nr = r + dr\n            val nc = c + dc\n            if (nr !in 0 until n || nc !in 0 until n) continue\n            val next = nr * n + nc\n            if (next in visited) continue\n            visited.add(next)\n            dist[next] = dist[cell] + 1\n            queue.add(next)\n        }\n    }\n    return dist[n * n - 1]\n}<\/pre>\n<p>It returns the right answer. On a 200 \u00d7 200 grid it prints 398. The candidate says &#8220;O(rows \u00d7 cols)&#8221; and moves on. Two lines make that claim false. They fail in different ways, so the next two sections take them one at a time.<\/p>\n<h2>The visited check scans a list, so the BFS turns quadratic<\/h2>\n<p>Start with <code>next in visited<\/code>. The <a href=\"https:\/\/kotlinlang.org\/docs\/collection-types.html\" target=\"_blank\" rel=\"noopener\">Kotlin collection types page<\/a> says <code>ArrayList<\/code> is the default implementation of <code>MutableList<\/code>. On the JVM, <code>mutableListOf()<\/code> gives you a <code>java.util.ArrayList<\/code>. The <a href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/21\/docs\/api\/java.base\/java\/util\/ArrayList.html\" target=\"_blank\" rel=\"noopener\">Java 21 ArrayList docs<\/a> name four constant-time operations. They are size, get, set and iteration. Add is amortized constant. Everything else runs in linear time. That includes <code>contains<\/code>. Kotlin&#8217;s <code>in<\/code> operator calls <code>contains<\/code>.<\/p>\n<p>So every neighbor check walks the visited list. That list grows to every cell in the grid. With V cells, the search costs O(V\u00b2), not O(V). We timed it on one laptop with Kotlin 2.4.20 on JDK 25. A 200 \u00d7 200 grid took 2.6 seconds with the list. With a <code>BooleanArray<\/code> it took 4 milliseconds. At 400 \u00d7 400 the list version took 52 seconds. The array version took 7 milliseconds. Four times the cells cost twenty times the runtime.<\/p>\n<p>The fix is one type. A <code>BooleanArray(n * n)<\/code> answers &#8220;seen?&#8221; by index in constant time. A <code>HashSet<\/code> works when cells aren&#8217;t numbered, with expected constant time per lookup. Either way, say the cost out loud when you choose it.<\/p>\n<h2>removeAt(0) is linear in the queue, which is the honest answer<\/h2>\n<p>The second line is <code>queue.removeAt(0)<\/code>. Removing from the front of an <code>ArrayList<\/code> shifts every remaining element down one slot. The Java docs put it with the linear-time operations. Our timing shows the shape. Draining 100,000 items with <code>removeAt(0)<\/code> took 0.4 seconds. 200,000 took 1.6 seconds and 400,000 took 6.4 seconds. Doubling the size roughly quadrupled the time. <code>ArrayDeque.removeFirst()<\/code> drained each size in 3 milliseconds or less.<\/p>\n<p>In this grid BFS, though, the list queue barely hurt. We fixed the visited check and tried an 800 \u00d7 800 grid. The list queue took 56 milliseconds. <code>ArrayDeque<\/code> took 26. The queue only holds the current frontier. On an open grid, that&#8217;s a diagonal band of cells. So each <code>removeAt(0)<\/code> costs O(frontier), not O(V). The precise bound is O(V \u00d7 frontier). That&#8217;s still worse than O(V).<\/p>\n<p>That nuance is worth saying in the round, because it shows you can price the call. Say <code>removeAt(0)<\/code> is linear in the queue&#8217;s length. Say the frontier keeps it small here. Then switch to <code>ArrayDeque<\/code> anyway, because other graphs have wide frontiers. The <a href=\"https:\/\/kotlinlang.org\/api\/core\/kotlin-stdlib\/kotlin.collections\/-array-deque\/\" target=\"_blank\" rel=\"noopener\">Kotlin ArrayDeque reference<\/a> describes it as a resizable-array deque. That&#8217;s the structure built for removing at the front.<\/p>\n<h2>Four more Kotlin calls that scan or copy behind a short name<\/h2>\n<p>The same trap shows up beyond lists used as queues. Each looks like a cheap step but scans or copies the data. We checked each one by running it.<\/p>\n<ul>\n<li><code>sorted()<\/code> returns a new sorted list and leaves the original alone. Call it inside a loop and you pay O(n log n) on every pass.<\/li>\n<li><code>toList()<\/code> and <code>toMutableList()<\/code> copy every element. Changes to the copy don&#8217;t touch the original.<\/li>\n<li><code>str += \"x\"<\/code> builds a new string each time. The <a href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/21\/docs\/api\/java.base\/java\/lang\/String.html\" target=\"_blank\" rel=\"noopener\">Java String docs<\/a> say strings can&#8217;t change once created. In our run, 40,000 appends took 168 milliseconds. A <code>StringBuilder<\/code> took under 1.<\/li>\n<li><code>list.indexOf(x)<\/code> is the same linear scan as <code>contains<\/code>, under a different name.<\/li>\n<\/ul>\n<p>Each of these is fine outside a loop. Inside a loop, its cost belongs in your bound.<\/p>\n<h2>A sample script for your Kotlin coding interview time complexity answer<\/h2>\n<p>Here&#8217;s the grid round again, done right. First, the fixed code.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"\">fun minSteps(n: Int): Int {\n    val queue = ArrayDeque&lt;Int&gt;().apply { add(0) }\n    val visited = BooleanArray(n * n).also { it[0] = true }\n    val dist = IntArray(n * n)\n    while (queue.isNotEmpty()) {\n        val cell = queue.removeFirst()\n        val r = cell \/ n\n        val c = cell % n\n        for ((dr, dc) in listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)) {\n            val nr = r + dr\n            val nc = c + dc\n            if (nr !in 0 until n || nc !in 0 until n) continue\n            val next = nr * n + nc\n            if (visited[next]) continue\n            visited[next] = true\n            dist[next] = dist[cell] + 1\n            queue.add(next)\n        }\n    }\n    return dist[n * n - 1]\n}<\/pre>\n<p>Then say the choices as you make them, before typing each one.<\/p>\n<blockquote>\n<p>&#8220;I&#8217;ll use BFS, since every step costs the same. For the queue I&#8217;m using ArrayDeque, not a MutableList. Removing from the front of a list shifts everything, so that&#8217;s linear per call. ArrayDeque removes from the front without shifting. For visited I&#8217;ll use a BooleanArray indexed by row times n plus col. Lookup is constant. A list here would make each check linear and the whole search quadratic.&#8221;<\/p>\n<\/blockquote>\n<p>When you finish, state the bound with the structures in the same sentence.<\/p>\n<blockquote>\n<p>&#8220;Each cell is added to the queue once and removed once. Each removal checks four neighbors with constant-time array lookups. So time is O(rows times cols). Space is O(rows times cols) for the visited array, the distance array and the queue.&#8221;<\/p>\n<\/blockquote>\n<p>If the interviewer pushes on the queue, give the nuance.<\/p>\n<blockquote>\n<p>&#8220;A list queue would still finish fast on this grid. The queue only holds the frontier. But each removal would cost the frontier&#8217;s size. On a graph with a wide frontier that adds up, so ArrayDeque is the safe choice.&#8221;<\/p>\n<\/blockquote>\n<h2>Why the script holds up when the interviewer probes<\/h2>\n<p>The first answer prices each structure at the moment you pick it. The interviewer never has to ask what <code>in<\/code> costs, because you already said. It also names the rejected option and its cost, so the interviewer can see you chose on purpose.<\/p>\n<p>The second answer derives the bound from the code. &#8220;Added once, removed once, four constant checks&#8221; is a count anyone can verify against the screen. That&#8217;s the check the rubric describes. A bare &#8220;O(n)&#8221; asks the interviewer to trust you. A derived one lets them confirm it.<\/p>\n<p>The third answer handles the follow-up without overclaiming. It admits the list would be fast here and explains why. Then it gives the case where the list breaks. An interviewer may probe a correct answer to see whether you know its limits.<\/p>\n<p>A <code>HashSet<\/code> can still fail you in another way. Our Kotlin bug post on <a href=\"https:\/\/grindloop.ai\/blog\/kotlin-hashset-contains-returns-false\/\">HashSet contains returning false<\/a> covers a different trap. That one is about correctness, not speed.<\/p>\n<h2>Run a 30-second cost scan before you say any Big-O<\/h2>\n<p>Practice this until it&#8217;s automatic. Before you state complexity, look at every line inside a loop. Circle each call on a collection or string. For each one, ask what structure sits behind it and whether the call scans or copies. The usual suspects are <code>in<\/code>, <code>indexOf<\/code> and <code>removeAt(0)<\/code>. Watch for <code>sorted()<\/code>, <code>toList()<\/code> and string <code>+=<\/code> too. If one scans or copies, either change the structure or put its cost in your bound.<\/p>\n<p>Do it on your own practice solutions first. Take five problems you solved in Kotlin this month. Run the scan on each and write the corrected bound next to the one you claimed. Where they differ, rewrite the line. Then try the scan on paper, the way our post on <a href=\"https:\/\/grindloop.ai\/blog\/in-person-coding-interview-hand-trace\/\">hand-tracing Kotlin in an in-person interview<\/a> describes. The real round has no profiler, so this scan is your only performance check.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Kotlin coding interview time complexity is checked against your code. Why list contains and removeAt(0) break your Big-O, with a BFS repro and sample script.<\/p>\n","protected":false},"author":3,"featured_media":990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"rank_math_title":"Kotlin Coding Interview Time Complexity: Hidden List Costs","rank_math_description":"Kotlin coding interview time complexity is checked against your code. Why list contains and removeAt(0) break your Big-O, with a BFS repro and sample script.","rank_math_focus_keyword":"Kotlin coding interview time complexity","footnotes":""},"categories":[20],"tags":[48,15,44,52,16,12,45],"class_list":["post-988","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-interview-strategy","tag-algorithm-round","tag-android","tag-coding-interview","tag-hiring-process","tag-interview-prep","tag-kotlin","tag-technical-interview"],"_links":{"self":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts\/988","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/comments?post=988"}],"version-history":[{"count":1,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts\/988\/revisions"}],"predecessor-version":[{"id":989,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts\/988\/revisions\/989"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/media\/990"}],"wp:attachment":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/media?parent=988"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/categories?post=988"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/tags?post=988"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}