CodeSignal General Coding Assessment (GCA) — Questions and Answers

Question 1: What is the amortized time complexity of appending to a dynamic array (e.g., Python list or Java ArrayList)?

O(log n)
O(1) (Correct answer)
O(n)
O(n²)

Correct answer: O(1)

Although occasional resizing is O(n), doubling the capacity each time makes the amortized cost of each append O(1).

Question 2: When comparing data structures, the way memory is used and the time it takes to perform operations are key factors. Which term describes the measure of how the runtime of an algorithm scales with the size of the input?

Space Complexity
Algorithmic Efficiency
Memory Allocation
Time Complexity (Correct answer)

Correct answer: Time Complexity

Time complexity is a concept in computer science that deals with the quantification of the amount of time taken by a set of code or algorithm to process or run as a function of the amount of input. It's a critical metric for comparing the performance of algorithms and data structure operations.

Question 3: What distinguishes a stable sorting algorithm from an unstable one?

Stable sorts always run in O(n log n)
Stable sorts preserve the relative order of equal elements (Correct answer)
Stable sorts work only on numeric data
Stable sorts never use extra memory

Correct answer: Stable sorts preserve the relative order of equal elements

A stable sort guarantees that records with equal keys appear in their original input order in the sorted output.

Question 4: An array contains integers 1–n with one duplicate and one missing value. Which approach finds both in O(n) time and O(1) space?

Use a hash set to track seen values
Use XOR and arithmetic sum/sum-of-squares formulas (Correct answer)
Nested loops comparing every pair
Sort and scan for adjacent duplicates

Correct answer: Use XOR and arithmetic sum/sum-of-squares formulas

XOR paired with arithmetic identities (expected sum and sum-of-squares vs actual) isolates both the duplicate and missing value in two passes without extra space.

Question 5: To find the single non-repeating element in an array where every other element appears exactly twice, which operation is applied across all elements?

AND all elements
OR all elements
XOR all elements (Correct answer)
NOT all elements

Correct answer: XOR all elements

XOR of any number with itself is 0, so paired elements cancel out and the unique element remains.

Question 6: The Lowest Common Ancestor of two nodes u and v in a rooted tree can also be found by reducing it to a Range Minimum Query (RMQ) problem. What is the preprocessing time for this approach?

O(N log N) (Correct answer)
O(N^2)
O(sqrt(N))
O(N)

Correct answer: O(N log N)

Euler tour + sparse table preprocessing for RMQ takes O(N log N) time and enables O(1) LCA queries thereafter.

Question 7: What two properties must a problem have to be solvable with dynamic programming?

Sorted input and unique solution
Greedy choice and independence
Optimal substructure and overlapping subproblems (Correct answer)
Linear time and constant space

Correct answer: Optimal substructure and overlapping subproblems

DP requires optimal substructure (optimal solution uses optimal sub-solutions) and overlapping subproblems (same subproblems recur).

Question 8: In the coin change problem, what should be returned if no valid coin combination can make the target amount?

-1 (Correct answer)
0
Infinity
null

Correct answer: -1

Returning -1 is the conventional signal that no valid combination exists for the given amount.

Question 9: What is the result of sorted([3,1,4,1,5,9], key=lambda x: -x)?

[1, 1, 3, 4, 5, 9]
[9, 5, 4, 1, 3, 1]
[3, 1, 4, 1, 5, 9]
[9, 5, 4, 3, 1, 1] (Correct answer)

Correct answer: [9, 5, 4, 3, 1, 1]

Negating each value as the sort key sorts in descending order, yielding [9, 5, 4, 3, 1, 1].

Question 10: You are given a task to find the first non-repeating character in a string. For the string 'aabbcdeff', the correct output is 'c'. Which data structure is most suitable for solving this problem efficiently by tracking character counts?

A stack
A hash map (or dictionary) (Correct answer)
A queue
A 2D array

Correct answer: A hash map (or dictionary)

A hash map is ideal for this scenario. You can iterate through the string once to build a frequency count of each character in the hash map. Then, you can iterate through the string a second time and use the hash map to check the count of each character. The first character with a count of 1 is the answer. This approach typically has a time complexity of O(n), where n is the length of the string.

Question 11: What space optimization reduces the LCS DP table from O(m×n) to O(min(m,n))?

Divide and conquer split
Pure memoization
Recursion with stack compression
Using only two rows at a time (rolling array) (Correct answer)

Correct answer: Using only two rows at a time (rolling array)

Since each row depends only on the previous row, storing just two rows reduces space from O(m×n) to O(n).

Question 12: In the context of graph coloring, what is the chromatic number of a bipartite graph with at least one edge?

It depends on the number of vertices
1
2 (Correct answer)
3

Correct answer: 2

Any bipartite graph with at least one edge requires exactly 2 colors, as it has no odd-length cycles.

Question 13: In the 'house robber' problem, what does dp[i] typically represent?

The total money in all houses up to i
The maximum money robbed from the first i houses without robbing two adjacent (Correct answer)
The index of the house to rob at step i
The number of houses skipped up to position i

Correct answer: The maximum money robbed from the first i houses without robbing two adjacent

dp[i] holds the maximum loot achievable from the first i houses while respecting the no-adjacent constraint.

Question 14: What is the minimum number of operations to convert 'kitten' to 'sitting' using edit distance (Levenshtein)?

4
3 (Correct answer)
2
5

Correct answer: 3

kitten→sitten (substitute k→s), sitten→sittin (substitute e→i), sittin→sitting (insert g) = 3 operations.

Question 15: Which of the following is the correct time complexity of a simple recursive Fibonacci solution without memoization?

O(n log n)
O(2^n) (Correct answer)
O(n)
O(n²)

Correct answer: O(2^n)

Without memoization, each call branches into two recursive calls, resulting in an exponential O(2^n) call tree.

Question 16: In BFS on an unweighted graph, the first time a node is dequeued, its distance from the source is guaranteed to be:

The shortest path distance (Correct answer)
Undefined until all nodes are processed
An overestimate
The longest path distance

Correct answer: The shortest path distance

BFS explores nodes in non-decreasing order of distance, so the first visit gives the exact shortest path.

Question 17: A GraphQL API resolves a list of 100 posts and each post resolver independently queries the database for its author. What anti-pattern is this?

Resolver waterfall
N+1 query problem (Correct answer)
Over-fetching
Schema stitching failure

Correct answer: N+1 query problem

The N+1 problem occurs when fetching N items triggers N additional queries (one per item), which DataLoader solves by batching them into a single query.

Question 18: What is the time complexity of Radix Sort on n integers each with d digits in base b?

O(n * d²)
O(n + d)
O(d * (n + b)) (Correct answer)
O(n log n)

Correct answer: O(d * (n + b))

Radix Sort performs d passes of counting sort, each taking O(n + b), giving total O(d * (n + b)).

Question 19: What is the space complexity of Merge Sort when sorting an array (not a linked list)?

O(1)
O(n log n)
O(log n)
O(n) (Correct answer)

Correct answer: O(n)

Merge Sort requires an auxiliary array of size n to store merged results, giving O(n) auxiliary space.

Question 20: What is a linked list advantage over an array?

Faster random access
Efficient insertion and deletion without shifting elements (Correct answer)
Less memory usage
Built-in sorting

Correct answer: Efficient insertion and deletion without shifting elements

Linked lists can insert and delete elements in O(1) time once the position is found, without moving other elements.

Question 21: Which of the following graph representations uses O(V + E) space?

Edge list only
Incidence matrix
Adjacency matrix
Adjacency list (Correct answer)

Correct answer: Adjacency list

An adjacency list stores each vertex once and each edge (or two half-edges for undirected), totaling O(V + E) space.

Question 22: A GPS navigation system models a road network as a graph where cities are vertices and roads are edges with weights representing travel time. To find the quickest route from a starting city to a destination, which algorithm is the most appropriate choice, assuming all travel times are positive?

Prim's Algorithm
Dijkstra's Algorithm (Correct answer)
Topological Sort
Breadth-First Search (BFS)

Correct answer: Dijkstra's Algorithm

Dijkstra's algorithm is specifically designed to find the shortest path from a single source to all other nodes in a weighted graph with non-negative edge weights. This makes it the ideal choice for finding the quickest route in a road network where edge weights represent travel time.

Question 23: An undirected graph has 5 vertices and is fully connected (complete graph). How many edges does it have?

10 (Correct answer)
5
8
20

Correct answer: 10

A complete graph on n vertices has n(n-1)/2 edges; for n=5 that is 5×4/2 = 10.

Question 24: What is an interface in object-oriented programming?

A concrete class that provides default behavior for all its methods
A special constructor used exclusively by abstract classes
A way to achieve multiple concrete inheritance through class extension
A contract specifying methods a class must implement, without providing implementation details (Correct answer)

Correct answer: A contract specifying methods a class must implement, without providing implementation details

An interface defines a contract of method signatures that any implementing class must fulfill, enabling loose coupling and polymorphism.

Question 25: Which approach finds all pairs in an array that sum to a target value in O(n) time?

Use nested loops comparing every pair
Sort and apply binary search for each element
Sort the array and use two pointers
Store seen values in a hash map and check target − current element (Correct answer)

Correct answer: Store seen values in a hash map and check target − current element

A hash map lookup for target − arr[i] achieves O(1) per element, giving O(n) overall for one pass.

Question 26: An array of 0s and 1s must be partitioned so all 0s come before all 1s. Which algorithm does this in O(n) with O(1) space?

Dutch National Flag (two-pointer partition) (Correct answer)
Merge sort with custom comparator
Quicksort with 0/1 pivot
Counting sort with two passes

Correct answer: Dutch National Flag (two-pointer partition)

Two pointers (left and right) swap misplaced elements until they meet, achieving O(n) time and O(1) extra space.

Question 27: Merge sort on a linked list is preferred over QuickSort because:

Merge sort uses less memory on linked lists
Merge sort is always faster
QuickSort cannot be implemented on linked lists
Linked lists allow O(1) merging without extra space (Correct answer)

Correct answer: Linked lists allow O(1) merging without extra space

Merging linked list nodes requires only pointer reassignment (O(1) extra space), unlike arrays which need auxiliary buffers.

Question 28: Which of the following statements about string and array manipulation is generally TRUE across most programming languages like Python, Java, and JavaScript?

Accessing an element in an array by its index is typically an O(n) operation.
Strings are mutable, meaning their characters can be changed in place after creation.
Arrays have a fixed size after creation and cannot be expanded.
Strings can often be treated as arrays of characters, allowing for indexed access to individual characters. (Correct answer)

Correct answer: Strings can often be treated as arrays of characters, allowing for indexed access to individual characters.

In many programming languages, strings are implemented as sequences of characters that can be accessed by an index, similar to arrays. While strings are often immutable (meaning they cannot be changed in place), they still allow for this array-like read-only access. In contrast, arrays are typically mutable and not fixed-size (in languages with dynamic arrays/lists), and indexed access is a constant time, O(1), operation.

Question 29: What is the worst-case time complexity of removing an element from the middle of a dynamic array (list)?

O(n log n)
O(log n)
O(1)
O(n) (Correct answer)

Correct answer: O(n)

Removing from the middle requires shifting all subsequent elements left by one, which is O(n) in the worst case.

Question 30: A video platform needs to transcode uploaded videos into 5 quality levels. Which architecture component handles this best?

Client-side transcoding in the browser
Synchronous HTTP call from the upload handler
Cron job polling the file system every minute
Asynchronous message queue feeding a worker pool (Correct answer)

Correct answer: Asynchronous message queue feeding a worker pool

An async queue decouples upload from transcoding, allows horizontal scaling of workers, and prevents upload timeouts on long-running jobs.

Question 31: When using Union-Find (Disjoint Set Union) to count connected components in a matrix, what operation determines if two cells are in the same component?

Find with path compression on both cells and compare roots (Correct answer)
Check if both cells have the same direct parent
BFS from one cell to check if it reaches the other
Merge the sets of both cells unconditionally

Correct answer: Find with path compression on both cells and compare roots

The Find operation (with path compression) returns the root representative of each cell's set; equal roots mean same component.

Question 32: Which data structure is most commonly used to implement a disjoint set (Union-Find) with path compression and union by rank?

Balanced BST
Hash map of parent arrays
Linked list
Array-based parent pointers (Correct answer)

Correct answer: Array-based parent pointers

Union-Find is typically implemented with a parent array plus a rank/size array, giving near-O(1) amortized operations.

Question 33: Which scenario represents a use case where a stack is the natural choice?

Finding the shortest path in a weighted graph
Processing print jobs in the order they arrive
Evaluating a mathematical expression with nested parentheses (Correct answer)
Storing a phone book for fast name lookup

Correct answer: Evaluating a mathematical expression with nested parentheses

Parenthesis matching and expression evaluation use a stack to track open brackets and pending operations in LIFO order.

Question 34: Given an M×N matrix, you need to find the number of distinct islands (connected groups of 1s, where connectivity is 4-directional). You run DFS and mark visited cells. What is the time complexity?

O((M*N)^2)
O(M*N*log(M*N))
O(M*N) (Correct answer)
O(M+N)

Correct answer: O(M*N)

Each cell is visited at most once during the DFS traversal, giving O(M*N) overall time complexity.

Question 35: What is the average-case time complexity of QuickSort and why?

O(n) because partitioning is linear
O(n log n) because random pivots yield balanced partitions on average (Correct answer)
O(n²) due to pivot selection
O(log n) because it is divide-and-conquer

Correct answer: O(n log n) because random pivots yield balanced partitions on average

With random pivot selection, expected partition sizes are balanced, giving a recurrence of T(n) = 2T(n/2) + O(n) which solves to O(n log n).

Question 36: What is the time complexity of building a max-heap from an unsorted array of n elements?

O(n²)
O(log n)
O(n log n)
O(n) (Correct answer)

Correct answer: O(n)

Bottom-up heap construction runs in O(n) because lower levels do less work, and the sum telescopes to linear time.

Question 37: Euler's formula for a connected planar graph states V - E + F = 2. If V=6 and E=12, how many faces F does the graph have?

6
10
8 (Correct answer)
4

Correct answer: 8

F = 2 - V + E = 2 - 6 + 12 = 8 faces, including the outer infinite face.

Question 38: What are the base case values for dp[0][j] and dp[i][0] in the edit distance problem?

Both are 1
Both are 0
dp[0][j] = j and dp[i][0] = i (Correct answer)
Depends on string content

Correct answer: dp[0][j] = j and dp[i][0] = i

Converting an empty string to a length-j string requires j insertions, and converting length-i to empty requires i deletions.

Question 39: What does the 'k' represent in the time complexity O(n + k) of Counting Sort?

Range of input values (Correct answer)
Number of swaps
Number of comparisons
Stack depth

Correct answer: Range of input values

k is the range (max - min + 1) of the input values, which determines the size of the counting array.

Question 40: A programmer is working on a memory-constrained embedded system and needs to sort an array of sensor readings in-place. Which of the following sorting algorithms has the best auxiliary space complexity for this task?

Radix Sort
Heap Sort (Correct answer)
Merge Sort
Tim Sort

Correct answer: Heap Sort

Heap Sort is an in-place sorting algorithm with a space complexity of O(1), meaning it requires a constant amount of extra memory regardless of the input size. Merge Sort requires O(n) auxiliary space, making it unsuitable for this scenario. Radix and Tim Sort can also have higher space requirements.

Question 41: What does 'optimal substructure' mean in the context of dynamic programming?

The optimal solution to the problem contains optimal solutions to its subproblems (Correct answer)
Subproblems are solved independently without overlap
All subproblems are the same size
The problem can always be solved greedily

Correct answer: The optimal solution to the problem contains optimal solutions to its subproblems

Optimal substructure means you can construct the global optimal answer by combining optimal answers to smaller subproblems.

Question 42: Given sorted array [1, 2, 3, 4, 5, 6, 7] and a target sum of 9, what is the pair found using the two-pointer approach?

(1, 8)
(2, 7)
(3, 6) (Correct answer)
(4, 5)

Correct answer: (3, 6)

Two pointers start at 1 and 7 (sum=8, too low→advance left); at 2 and 7 (sum=9, found) — but (3,6) also sums to 9 and pointers would find it depending on implementation; the first found is (2,7). Actually pointers find 2+7=9 first.

Question 43: What is the GCD of 48 and 18?

6 (Correct answer)
9
12
3

Correct answer: 6

Applying the Euclidean algorithm: gcd(48,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)=6.

Question 44: You are given a non-empty Binary Search Tree (BST). Which of the following traversal methods will visit the nodes in ascending sorted order of their values?

Level-order Traversal
Post-order Traversal
Pre-order Traversal
In-order Traversal (Correct answer)

Correct answer: In-order Traversal

In-order traversal visits the left subtree, then the root node, and finally the right subtree. Due to the inherent property of a BST (left children are smaller, right children are larger), this 'Left-Root-Right' pattern naturally processes the nodes in ascending order of their values.

Question 45: What is the time complexity of finding the k-th smallest element using a min-heap of size n?

O(k + n)
O(k log n) (Correct answer)
O(n)
O(n log k)

Correct answer: O(k log n)

Building the heap is O(n), then extracting the minimum k times costs O(k log n) total.

Question 46: Which of the following best describes an abstract class?

A class that cannot be instantiated directly and may contain abstract methods subclasses must implement (Correct answer)
A class that contains only static methods and no instance methods
A class that inherits from two or more parent classes simultaneously
A class with no fields, only method signatures

Correct answer: A class that cannot be instantiated directly and may contain abstract methods subclasses must implement

An abstract class cannot be instantiated on its own; it serves as a blueprint that concrete subclasses extend and whose abstract methods they must implement.

Question 47: What is a binary heap used for?

Efficiently finding the minimum or maximum element and implementing priority queues (Correct answer)
Binary search
Storing text data
Network routing

Correct answer: Efficiently finding the minimum or maximum element and implementing priority queues

Binary heaps maintain a partial ordering that allows O(1) access to the min or max element and O(log n) insertion.

Question 48: In the 'word search' problem, you search for a word in a matrix by moving to adjacent cells (up, down, left, right). Why must you mark cells as visited during DFS and unmark them on backtrack?

To permanently eliminate explored cells from the matrix
To allow the same cell to be reused in other candidate paths while preventing reuse within the current path (Correct answer)
Because the problem requires each cell to be visited exactly once globally
To reduce the time complexity from exponential to polynomial

Correct answer: To allow the same cell to be reused in other candidate paths while preventing reuse within the current path

Temporary marking prevents using the same cell twice within one path but allows it for entirely different paths explored via backtracking.

Question 49: What does 'overlapping subproblems' mean in dynamic programming?

Each subproblem has a unique solution
Every subproblem is solved exactly once by design
The same subproblems recur multiple times during the recursive computation (Correct answer)
Subproblems are mutually exclusive

Correct answer: The same subproblems recur multiple times during the recursive computation

Overlapping subproblems occur when naïve recursion solves the same subproblem repeatedly, which DP avoids by caching.

Question 50: When merging two sorted arrays of sizes m and n into a single sorted array, what is the optimal time complexity?

O(m · n)
O((m + n) log(m + n))
O(m + n) (Correct answer)
O(max(m, n))

Correct answer: O(m + n)

A two-pointer merge traverses each array exactly once, producing the sorted result in O(m + n) time.

Question 51: Which keyword is used in Java, C++, and JavaScript to create a new instance of a class?

create
instance
new (Correct answer)
init

Correct answer: new

The `new` keyword allocates memory and invokes the constructor to create a new object instance in most OOP languages.

Question 52: In a 3-way QuickSort (Dutch National Flag partition), what problem does it solve compared to standard 2-way QuickSort?

It is faster on random data
It guarantees O(n log n) worst case
It handles arrays with many duplicate keys efficiently (Correct answer)
It eliminates the need for a pivot

Correct answer: It handles arrays with many duplicate keys efficiently

3-way partitioning groups equal elements together, so arrays with many duplicates achieve O(n) or near-linear performance instead of O(n²).

CodeSignal General Coding Assessment (GCA)

The CodeSignal GCA is a 70-minute technical assessment with 4 coding tasks of increasing difficulty, evaluating problem-solving, data structures, algorithms, and code quality. Scored 200–600.

Questions

70 min

Time Limit

50%

To Pass

Checking for saved progress...

Exam Rules

You can skip questions and return to them later
Flag questions for review before submitting
No feedback shown until you submit the entire exam
Unanswered questions count as wrong — answer everything
10 pretest questions are mixed in and don't affect your score
Timer auto-submits when time runs out
Your progress is auto-saved every 30 seconds