CodeSignal General Coding Assessment (GCA) — Questions and Answers

Question 1: 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?

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

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 2: An undirected graph has 5 vertices and is fully connected (complete graph). How many edges does it have?

20
5
8
10 (Correct answer)

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 3: Which traversal of a Binary Search Tree visits nodes in ascending sorted order?

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

Correct answer: In-order

In-order traversal (left → root → right) visits BST nodes from smallest to largest.

Question 4: 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)
An overestimate
Undefined until all nodes are processed
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 5: You are tasked with sorting a list of customer objects based on their purchase date. If two customers have the same purchase date, their original relative order must be preserved. Which of the following sorting algorithms is most suitable for this requirement?

Merge Sort (Correct answer)
Heap Sort
Quick Sort
Selection Sort

Correct answer: Merge Sort

The requirement to preserve the relative order of elements with equal keys means a stable sorting algorithm is needed. Among the choices, Merge Sort is a stable algorithm. Heap Sort, Quick Sort, and Selection Sort are all unstable sorting algorithms and do not guarantee that the original order of equal elements will be maintained.

Question 6: In the 'surrounded regions' problem, you flip all 'O' regions not connected to the border to 'X'. What is the most efficient first step?

Mark all 'O' cells reachable from any border cell using BFS/DFS (Correct answer)
Use union-find to connect all 'O' cells to a virtual border node
Iterate over every cell and check if it touches the border
Convert all 'O' to 'X' then restore connected ones

Correct answer: Mark all 'O' cells reachable from any border cell using BFS/DFS

Starting BFS/DFS from border 'O' cells and marking them safe in one pass avoids redundant work and is O(M*N).

Question 7: Which approach does Prim's MST algorithm use to select the next edge?

BFS level-by-level expansion
Always pick the cheapest edge crossing the cut between visited and unvisited vertices (Correct answer)
Random edge selection with rollback
Sort all edges globally then pick cheapest non-cycle edge

Correct answer: Always pick the cheapest edge crossing the cut between visited and unvisited vertices

Prim's grows the MST from a starting vertex by always selecting the minimum-weight edge connecting the visited set to an unvisited vertex.

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

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

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 9: A program needs to manage a sequence of tasks where the last task added is the first one to be processed. This processing order is crucial for the program's logic. Which of the following data structures is specifically designed to handle this Last-In, First-Out (LIFO) behavior?

Stack (Correct answer)
Linked List
Queue
Heap

Correct answer: Stack

A stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. This behavior is known as Last-In, First-Out (LIFO).

Question 10: Given a 2D matrix represented as a flat array with row-major order, what is the index of element at row r, column c in an n-column matrix?

r * c + n
r * n + c (Correct answer)
c * n + r
r + c * n

Correct answer: r * n + c

Row-major layout stores row r starting at index r*n, so element (r, c) is at r*n + c.

Question 11: What algorithm solves the Longest Increasing Subsequence in O(n log n) time?

Binary search with patience sorting (Correct answer)
Floyd-Warshall
Two-pointer sliding window
Merge sort decomposition

Correct answer: Binary search with patience sorting

Using binary search to maintain a sorted 'pile' structure (patience sorting) achieves O(n log n) for LIS.

Question 12: Which dynamic programming strategy works top-down by caching results of already-solved subproblems?

Tabulation
Memoization (Correct answer)
Greedy
Backtracking

Correct answer: Memoization

Memoization is a top-down technique that stores previously computed results to avoid redundant calculations.

Question 13: Which algorithm finds the maximum subarray sum in O(n) time?

KMP Algorithm
Boyer-Moore Algorithm
Floyd-Warshall Algorithm
Kadane's Algorithm (Correct answer)

Correct answer: Kadane's Algorithm

Kadane's Algorithm iterates once through the array tracking the current and global maximum subarray sum in O(n) time.

Question 14: 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)
O((M*N)^2)
O(M*N) (Correct answer)
O(M*N*log(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 15: When merging two sorted arrays of sizes m and n into a single sorted array, what is the optimal time complexity?

O(max(m, n))
O((m + n) log(m + n))
O(m + n) (Correct answer)
O(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 16: What is a key difference between a shallow copy and a deep copy of an object?

Shallow copies are faster to create
Deep copies share memory with the original
Shallow copies work only on primitives
Deep copy duplicates nested objects; shallow copy only copies top-level references (Correct answer)

Correct answer: Deep copy duplicates nested objects; shallow copy only copies top-level references

A shallow copy copies the container but not nested objects, which are still shared; a deep copy recursively copies everything.

Question 17: What is (7 × 8) mod 5?

2
3
1 (Correct answer)
6

Correct answer: 1

7 × 8 = 56, and 56 mod 5 = 1 because 56 = 11 × 5 + 1.

Question 18: What modification to standard binary search allows finding the first occurrence of a target in a sorted array with duplicates?

Switch to linear scan when duplicates are detected
When arr[mid] == target, store mid and search the left half to find the first occurrence (Correct answer)
Sort the array again removing duplicates first
Return immediately when arr[mid] == target

Correct answer: When arr[mid] == target, store mid and search the left half to find the first occurrence

Instead of returning on a match, record the index and continue narrowing the search to the left half to find the leftmost occurrence.

Question 19: What is the time complexity of checking whether two strings are anagrams by sorting both?

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

Correct answer: O(n log n)

Sorting each string takes O(n log n), which dominates the O(n) comparison step.

Question 20: Why can't a greedy ratio (value/weight) approach always find the optimal solution for 0/1 knapsack?

Items cannot be fractionally selected, so the highest-ratio item may waste capacity (Correct answer)
It runs too slowly for large inputs
It is always optimal for 0/1 knapsack
Items must be sorted by weight instead

Correct answer: Items cannot be fractionally selected, so the highest-ratio item may waste capacity

In 0/1 knapsack, items are taken whole, so a high-ratio item might leave unusable capacity that smaller items could fill better.

Question 21: What does ''.join(reversed('hello')) return?

['o','l','l','e','h']
'olleh' (Correct answer)
None
'hello'

Correct answer: 'olleh'

reversed() yields characters in reverse order, and ''.join() concatenates them into the string 'olleh'.

Question 22: What is the primary advantage of using an in-place sorting algorithm like QuickSort over Merge Sort?

QuickSort is stable; Merge Sort is not
QuickSort is always faster
QuickSort has better worst-case guarantees
QuickSort uses O(log n) stack space vs Merge Sort's O(n) auxiliary array (Correct answer)

Correct answer: QuickSort uses O(log n) stack space vs Merge Sort's O(n) auxiliary array

QuickSort sorts in place (needing only O(log n) stack space for recursion), while Merge Sort requires an O(n) auxiliary buffer for merging.

Question 23: Which data structure makes Heap Sort possible, and what is its defining property?

BST: left child < root < right child
Hash Table: O(1) lookup
Trie: prefix-based ordering
Binary Heap: parent >= children (max-heap) (Correct answer)

Correct answer: Binary Heap: parent >= children (max-heap)

Heap Sort uses a binary max-heap where every parent is ≥ its children, enabling O(1) access to the maximum element.

Question 24: What is the space complexity of an in-place array reversal algorithm?

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

Correct answer: O(1)

In-place reversal swaps elements using a constant number of temporary variables regardless of array size.

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

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

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 26: What does the Observer design pattern define?

A pattern where one object acts as a transparent proxy for another
A one-to-many dependency so that when one object changes state all dependents are automatically notified (Correct answer)
A pattern that allows an object to appear to change its class when its internal state changes
A pattern that encapsulates an algorithm inside an object so it can be swapped at runtime

Correct answer: A one-to-many dependency so that when one object changes state all dependents are automatically notified

Observer sets up a publish-subscribe mechanism where subject objects maintain a list of observers and notify them all whenever their state changes.

Question 27: In CSS, which property controls the order in which flex items appear visually without changing the DOM order?

order (Correct answer)
z-index
align-self
flex-direction

Correct answer: order

The CSS `order` property lets you reposition flex (or grid) items visually while their source order in the DOM remains unchanged.

Question 28: What is a key difference between a tree and a graph?

Trees store only integers; graphs store any data
A tree is a connected acyclic graph; a graph may have cycles and disconnected components (Correct answer)
A graph always has a root node; a tree does not
A tree can have cycles; a graph cannot

Correct answer: A tree is a connected acyclic graph; a graph may have cycles and disconnected components

A tree is a special case of a graph that is connected, undirected (structurally), and contains no cycles.

Question 29: Which of the following problems is best solved using a monotonic stack?

Computing GCD of all array elements
Computing the next greater element for each position (Correct answer)
Detecting a cycle in a linked list
Finding the maximum element in an array

Correct answer: Computing the next greater element for each position

A monotonic stack efficiently resolves 'next greater element' queries by popping elements that are smaller than the current one.

Question 30: Which technique does Shell Sort use to improve upon Insertion Sort?

It sorts elements far apart first using decreasing gap sequences (Correct answer)
It applies merge steps to sublists
It uses a different comparison operator
It avoids comparisons entirely using counting

Correct answer: It sorts elements far apart first using decreasing gap sequences

Shell Sort moves elements large distances early by using a gap sequence, reducing the number of shifts needed in final passes.

Question 31: In the Longest Common Subsequence problem, what does dp[i][j] represent?

Length of LCS of the first i chars of s1 and first j chars of s2 (Correct answer)
Length of the common prefix
Number of matching characters at positions i and j
Index of the last common character

Correct answer: Length of LCS of the first i chars of s1 and first j chars of s2

dp[i][j] stores the length of the LCS considering only the first i characters of s1 and the first j characters of s2.

Question 32: What is the invariant maintained after each pass of Selection Sort?

The first i elements are the i smallest elements in sorted order (Correct answer)
All elements in the right half are larger than the left half
Adjacent elements are always in order
The array is fully sorted

Correct answer: The first i elements are the i smallest elements in sorted order

After i passes, Selection Sort has placed the i smallest elements in their final sorted positions at the beginning of the array.

Question 33: Which operation on a stack is used to view the top element WITHOUT removing it?

dequeue()
peek() (Correct answer)
pop()
push()

Correct answer: peek()

peek() (also called top()) returns the top element while leaving the stack unchanged.

Question 34: Which traversal order of a BST produces elements in sorted order?

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

Correct answer: In-order

In-order traversal (left → root → right) of a BST visits nodes in non-decreasing key order.

Question 35: What is the recurrence for the classic 0/1 knapsack DP when item i has weight w[i] and value v[i]?

dp[i][c] = dp[i][c-1] + v[i]
dp[i][c] = dp[i-1][c] * v[i]
dp[i][c] = dp[i-1][c] + v[i]
dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) if c >= w[i] (Correct answer)

Correct answer: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) if c >= w[i]

For each item you choose the best of skipping it (dp[i-1][c]) or taking it (dp[i-1][c-w[i]]+v[i]) when capacity allows.

Question 36: What is the space complexity of a recursive depth-first search on a graph with V vertices and E edges?

O(E)
O(V + E)
O(1)
O(V) (Correct answer)

Correct answer: O(V)

DFS uses O(V) stack space in the worst case (a path graph causes recursion depth V).

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

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

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 38: In the edit distance DP table, what operation does a diagonal move represent when the characters at positions i and j differ?

Skip
Insertion
Deletion
Substitution (Correct answer)

Correct answer: Substitution

A diagonal transition with differing characters adds 1 for the substitution operation, replacing one character with another.

Question 39: What does the expression `n & (n-1)` evaluate to when n is a power of 2?

n
n-1
1
0 (Correct answer)

Correct answer: 0

A power of 2 has exactly one set bit; subtracting 1 flips all lower bits, so ANDing gives 0.

Question 40: 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?

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

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 41: 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^2)
O(N)
O(sqrt(N))
O(N log N) (Correct answer)

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 42: A programmer needs to reverse the order of words in a given string, where words are separated by single spaces. For example, 'codesignal is awesome' should become 'awesome is codesignal'. Which of the following approaches is the MOST efficient in terms of time complexity for a typical programming language?

Reverse the entire string, and then iterate through the reversed string to reverse each individual word in place.
Iterate through the string from end to start, building each word character by character, and append them to a new string.
Split the string by spaces into an array of words, reverse the array, and then join the words back together with spaces. (Correct answer)
Use a stack data structure. Push each word onto the stack, and then pop them off one by one to form the new string.

Correct answer: Split the string by spaces into an array of words, reverse the array, and then join the words back together with spaces.

Splitting the string into an array of words, reversing the array, and joining it back is generally the most efficient and readable approach. Most language's built-in split, reverse, and join functions are highly optimized. The other methods involve more complex manual iteration or data structure overhead, which can be less performant.

Question 43: What is the output of [x**2 for x in range(5) if x % 2 == 0]?

[0, 4, 16] (Correct answer)
[1, 9, 25]
[4, 16]
[0, 1, 4, 9, 16]

Correct answer: [0, 4, 16]

Even values in range(5) are 0, 2, 4; squaring them yields [0, 4, 16].

Question 44: Given a DAG, Kahn's algorithm for topological sort initializes a queue with nodes that have:

In-degree 0 (Correct answer)
Minimum edge weight
Out-degree 0
Maximum out-degree

Correct answer: In-degree 0

Kahn's starts with all nodes having in-degree 0 (no dependencies), then repeatedly removes them and decrements neighbors' in-degrees.

Question 45: In a segment tree built on an array of N elements, what is the time complexity of a range query?

O(N log N)
O(log N) (Correct answer)
O(N)
O(1)

Correct answer: O(log N)

A segment tree answers range queries in O(log N) by traversing at most O(log N) nodes per query.

Question 46: Which property distinguishes a complete binary tree from a full binary tree?

A full binary tree must be balanced; a complete binary tree need not be
A complete binary tree has all nodes with 0 or 2 children; a full binary tree fills levels left to right
They are identical concepts with different names
A complete binary tree fills all levels left-to-right with the last level possibly incomplete; a full binary tree has every node with exactly 0 or 2 children (Correct answer)

Correct answer: A complete binary tree fills all levels left-to-right with the last level possibly incomplete; a full binary tree has every node with exactly 0 or 2 children

Complete binary trees fill each level left to right (last level may be partial), while full binary trees require every node to have 0 or 2 children.

Question 47: Which property must an array satisfy for binary search to work correctly?

Array must be sorted (Correct answer)
Elements must be unique
Array length must be a power of 2
Elements must be integers

Correct answer: Array must be sorted

Binary search relies on the sorted order to determine which half to discard at each step.

Question 48: In Dijkstra's algorithm using a min-heap, what is the time complexity for a graph with V vertices and E edges?

O(E log E)
O(V * E)
O((V + E) log V) (Correct answer)
O(V^2)

Correct answer: O((V + E) log V)

Using a binary min-heap, each edge relaxation costs O(log V), giving O((V + E) log V) overall.

Question 49: A utility company is planning to connect several towns with a new power grid. The goal is to ensure every town is connected to the grid while minimizing the total length of power lines used. This problem is a classic application of finding what structure in a graph?

An Eulerian Path
A Shortest Path
A Hamiltonian Cycle
A Minimum Spanning Tree (MST) (Correct answer)

Correct answer: A Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is a subgraph that connects all vertices in a weighted, undirected graph with the minimum possible total edge weight, without forming any cycles. This directly corresponds to the problem of connecting all towns with the least amount of cable.

Question 50: What is 5 XOR 3 in decimal?

7
2
6 (Correct answer)
8

Correct answer: 6

5 is 101 and 3 is 011 in binary; XOR gives 110, which equals 6 in decimal.

Question 51: What is the worst-case time complexity of QuickSort when the pivot is always the smallest or largest element?

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

Correct answer: O(n²)

When the pivot is always the min or max, each partition produces one empty subarray and one of size n-1, leading to O(n²) recursive calls.

Question 52: For the string 'aabcccdddd', what is the run-length encoding?

'a2b1c3d4' (Correct answer)
'2a1b3c4d'
'a2bc3d4'
'aabcccdddd'

Correct answer: 'a2b1c3d4'

Run-length encoding records each character followed by its count: 'a'×2, 'b'×1, 'c'×3, 'd'×4 → 'a2b1c3d4'.

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