Infosys interview prep

11 practice questions on the topics candidates reported from Infosys interviews, with answers. The questions are ours; each one links to the interview report that names its topic.

Practise them as a timed round

DSA 7

DSAEasy

In an unweighted graph, which algorithm finds the path with the fewest edges from a start vertex to every other vertex?
1. Depth-first search
2. Kruskal's algorithm
3. Topological sort
4. Breadth-first search
Show the answer

D. Breadth-first search

BFS visits vertices in order of their distance in edges, so the first time it reaches a vertex is along a shortest path. DFS can reach a vertex by a long path first.

This topic is named in a candidate’s interview report: Specialist Programmer interview, 2026, on GeeksforGeeks.
DSAMedium

For a positive integer n, what does (n & (n - 1)) == 0 tell you?
1. n is even
2. n is odd
3. n has exactly two set bits
4. n is a power of two
Show the answer

D. n is a power of two

n - 1 flips the lowest set bit of n and every bit below it, so n & (n - 1) clears the lowest set bit. The result is zero only when n had exactly one set bit: 1, 2, 4, 8 and so on.

This topic is named in a candidate’s interview report: HackWithInfy SP interview, 2022, on GeeksforGeeks.
DSAEasy

Folders hold files and other folders, nested to any depth. Which data structure models this most naturally?
1. A queue
2. A stack
3. A circular array
4. A tree
Show the answer

D. A tree

Each folder is a node whose children are its files and subfolders, under one root. Listing everything inside a folder is a traversal of its subtree. Links that make a file reachable from two places turn the tree into a graph.

This topic is named in a candidate’s interview report: HackWithInfy SP interview, 2022, on GeeksforGeeks.
DSAMedium

What is the length of the longest common subsequence of "STONE" and "LONGEST"?
1. 2
2. 3
3. 4
4. 5
Show the answer

B. 3

dp[i][j] is the answer for the first i letters of one word and the first j of the other: equal letters give dp[i-1][j-1] + 1, otherwise the larger of dp[i-1][j] and dp[i][j-1]. "ONE" appears in order in both words. O(mn) time.

This topic is named in a candidate’s interview report: Specialist Programmer interview, 2026, on GeeksforGeeks.
DSAMedium

In this grid, 1 is land and 0 is water, and land joins up, down, left and right. How many islands are there?
```
1 1 0 0
0 1 0 1
1 0 0 1
0 0 1 0
```
1. 3
2. 5
3. 4
4. 2
Show the answer

C. 4

The top-left 1s form one island; the two 1s in the right column form another; the lone 1 at row 3, column 1 and the lone 1 at row 4, column 3 are one each: 4. A DFS from each unvisited land cell is O(rows x columns).

This topic is named in a candidate’s interview report: Specialist programmer interview, 2024, on Reddit.
DSAMedium

Moving only right or down, how many paths lead from the top-left to the bottom-right of a 3 x 4 grid of cells?
1. 12
2. 7
3. 10
4. 35
Show the answer

C. 10

Every path makes 2 down moves and 3 right moves in some order: C(5, 2) = 10. The DP version adds the counts from above and from the left, which also handles blocked cells.

This topic is named in a candidate’s interview report: Specialist programmer interview, 2024, on Reddit.
DSAMedium

In "surrounded regions", every O not connected to the border is turned into X. What is the usual approach?
1. Flip every O to X
2. Sort the grid
3. Flood-fill from each O on the border to mark the safe ones, then flip every unmarked O to X
4. Check each O against every border cell
Show the answer

C. Flood-fill from each O on the border to mark the safe ones, then flip every unmarked O to X

Only regions that touch the edge escape. Marking them first with DFS or BFS from the border makes the rest a single pass, O(rows x columns).

This topic is named in a candidate’s interview report: Specialist programmer interview, 2024, on Reddit.

Java 1

JavaMedium

How long does get(key) usually take on a java.util.HashMap and on a java.util.TreeMap, each with n entries?
1. Both O(1)
2. Both O(log n)
3. HashMap O(log n); TreeMap O(1)
4. HashMap O(1) on average; TreeMap O(log n)
Show the answer

D. HashMap O(1) on average; TreeMap O(log n)

HashMap hashes the key straight to a bucket. TreeMap is a red-black tree kept sorted by key, so every get and put costs O(log n), but it can also give the keys in order, the first or last key, or every key in a range.

This topic is named in a candidate’s interview report: Specialist Programmer interview, 2026, on GeeksforGeeks.

Operating systems 2

Operating systemsMedium

How does a mutex differ from a counting semaphore?
1. A mutex lets one holder in at a time and is released by its owner; a semaphore allows up to N and anyone may signal it
2. They are two names for the same thing
3. A semaphore can only be used between processes
4. A mutex lets N threads in at once
Show the answer

A. A mutex lets one holder in at a time and is released by its owner; a semaphore allows up to N and anyone may signal it

A mutex is for mutual exclusion over one resource, owned by the thread that locked it. A counting semaphore counts available slots, such as 5 database connections, and is also used for signalling between threads.

This topic is named in a candidate’s interview report: Specialist programmer interview, 2024, on Reddit.
Operating systemsEasy

What is the difference between concurrency and parallelism?
1. They are the same
2. Concurrency always makes a program faster
3. Parallelism needs only one core
4. Concurrency is dealing with several tasks in overlapping time, possibly by switching on one core; parallelism is actually running tasks at the same instant on several cores
Show the answer

D. Concurrency is dealing with several tasks in overlapping time, possibly by switching on one core; parallelism is actually running tasks at the same instant on several cores

A web server handling many slow connections on one thread is concurrent; splitting a big computation over 8 cores is parallel. Concurrent code needs synchronisation such as mutexes either way.

This topic is named in a candidate’s interview report: Specialist programmer interview, 2024, on Reddit.

Machine learning 1

Machine learningMedium

What is chain-of-thought prompting?
1. Asking a language model to reason step by step, or showing worked examples with their reasoning, before it gives the answer
2. Sending several prompts to different models in a chain
3. Training a model on chained documents
4. Restricting the model to one-word answers
Show the answer

A. Asking a language model to reason step by step, or showing worked examples with their reasoning, before it gives the answer

Writing out intermediate steps tends to improve multi-step reasoning such as arithmetic. Few-shot prompting is the related idea of putting a handful of example inputs and outputs in the prompt.

This topic is named in a candidate’s interview report: Specialist programmer interview, 2024, on Reddit.

Prep for other employers

All employers

DSA 7

In an unweighted graph, which algorithm finds the path with the fewest edges from a start vertex to every other vertex?

For a positive integer n, what does (n & (n - 1)) == 0 tell you?

Folders hold files and other folders, nested to any depth. Which data structure models this most naturally?

What is the length of the longest common subsequence of "STONE" and "LONGEST"?

In this grid, 1 is land and 0 is water, and land joins up, down, left and right. How many islands are there?

Moving only right or down, how many paths lead from the top-left to the bottom-right of a 3 x 4 grid of cells?

In "surrounded regions", every O not connected to the border is turned into X. What is the usual approach?

Java 1

How long does get(key) usually take on a java.util.HashMap and on a java.util.TreeMap, each with n entries?

Operating systems 2

How does a mutex differ from a counting semaphore?

What is the difference between concurrency and parallelism?

Machine learning 1

What is chain-of-thought prompting?

Prep for other employers