← Bitkernel Interview Insights

Bitkernel·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Had a technical screen for a Software Engineer role at Bitkernel that leaned heavily on CS fundamentals. The heap sort question was multiple choice but don't let that fool you, you still need to actually trace through the algorithm step by step.

Questions Asked (1)

Q1

Given the array [7, 6, 3, 5, 4, 1, 2], after building a max-heap and performing the first extraction step (swap the root with the last element, then heapify the remaining elements), what does the array look like?

Algorithms & Data Structures
Author's notes

Multiple choice saved me a little here but I still had to work through it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, build a max-heap from the given array by applying the heapify process from the last non-leaf node up to the root. Then, perform the first extraction step: swap the root (maximum element) with the last element, reduce the heap size by one, and heapify the root to restore the max-heap property. Finally, present the resulting array after these operations.

Pro tip: Clarify whether the heap is represented as a binary tree or an array, and explicitly state the array indices used for parent-child relationships (e.g., for 0-indexed arrays, children of i are 2i+1 and 2i+2). This shows attention to detail and avoids off-by-one errors.

1. Build the max-heap

Starting from the last non-leaf node (index floor(n/2)-1) and moving up to the root, perform sift-down operations to ensure each subtree satisfies the max-heap property. After this, the array becomes a valid max-heap.

2. Identify the root and last element

The root (index 0) holds the maximum element. The last element is at index n-1. Note their values before swapping.

3. Swap root with last element

Exchange the values at index 0 and index n-1. This moves the maximum element to its final sorted position at the end of the array.

4. Reduce heap size and heapify

Decrease the heap size by 1 (so the last element is excluded from further heap operations). Then, perform sift-down on the new root (index 0) to restore the max-heap property among the remaining elements.

5. State the resulting array

After heapify, the array represents the heap after the first extraction. Present the final array in the order of indices 0 to n-1.

Key Points to Mention

  • Max-heap property: each parent is greater than or equal to its children.
  • Heapify (sift-down) process: compare parent with children and swap with the larger child if needed, recursively.
  • Array representation of a binary heap: for 0-indexed arrays, left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
  • Extraction step in heap sort: swap root with last element, reduce heap size, then heapify.
  • Time complexity: building heap is O(n), each extraction is O(log n).
  • The final array after first extraction is not fully sorted; only the maximum element is in its final position.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.