CORE JOBS
Data Structures and Algorithms interview questions
Short answers on the fundamentals, for the technical round of core-job interviews. 24 questions for CSE/IT and DS & AI students; the numericals show the working.
Companies do not publish their interview questions; these are ours.
Arrays, stacks, queues and linked lists
Linear structures notesHow does a stack convert an infix expression to postfix?
Scan the expression left to right. Operands go straight to the output. An operator first pops operators from the top of the stack while they have higher precedence (or equal precedence, if it is left-associative), stopping at an opening bracket, then is pushed. An opening bracket is pushed, a closing bracket pops until its opening bracket, and at the end the stack is emptied to the output.
A 2-D integer array has 20 rows and 30 columns, stored in row-major order from base address 1000, with 4 bytes per element and indices starting at 0. Find the address of A[5][7].
The address of A[5][7] is 1628.
WORKING
- Elements before row 5:
- Offset within row 5 is 7, so the element index is
- Address
What is the difference between an array and a singly linked list in access and insertion cost?
An array gives access by index but inserting in the middle costs because elements shift. A singly linked list needs to reach the -th element but inserts once the position is known. The list also spends memory on pointers and has poorer cache behaviour.
Trees, binary search trees and binary heaps
Trees & heaps notesIn a binary tree, how is the number of leaves related to the number of nodes with two children, and why?
The number of leaves is one more than the number of nodes with two children: . A tree with nodes has edges, which equals . Substituting gives the result.
A binary tree has 9 nodes with two children and 6 nodes with exactly one child. How many nodes does it have in total?
The tree has 25 nodes.
WORKING
- Leaves:
- Total
Why does building a binary heap from an array of n elements take linear time rather than n log n?
Build-heap runs sift-down on each internal node from the bottom up, and the total is . A node at height costs , and about nodes sit at that height. The sum of over all heights is , because most nodes are near the leaves.
What does an AVL tree guarantee, and how does it keep that guarantee?
An AVL tree keeps the heights of every node's two subtrees within 1 of each other, so its height is and search, insert and delete all cost . After an insert or delete, rotations restore the balance. A plain binary search tree can degrade to height on sorted input.
Asymptotic complexity and recurrences
Complexity notesWhat is the difference between Big O, Omega and Theta notation?
Big O gives an upper bound on growth, Omega gives a lower bound, and Theta gives both at once, so the function grows at exactly that rate up to constants. Saying an algorithm is allows it to be much faster, while says its cost really is quadratic.
Consider
for (i = 1; i < n; i = i * 2) for (j = 0; j < n; j++) count++;with n = 1024. What is the final value of count, starting from 0?The statement runs 10240 times.
WORKING
- Outer loop: , stopping when
- Outer iterations
- The inner loop runs times per outer iteration
- Total
Solve using the Master theorem.
Here , and . Since matches , the second case applies and . This is the recurrence of merge sort: two half-size subproblems and a linear combine step.
Why does asymptotic analysis ignore constants and lower-order terms?
It describes how cost grows as the input becomes large, and for large the dominant term decides the growth. Constants depend on the machine and compiler, so they say little about the algorithm itself. For small inputs they still matter: a quadratic method with a small constant can beat an one.
Searching, sorting and hashing
Sorting & hashing notesWhat is the difference between merge sort and quicksort?
Merge sort is in the worst case, is stable, and needs extra space for arrays. Quicksort is in the worst case but on average, sorts in place apart from its recursion stack, and is usually not stable. A bad pivot choice causes its worst case.
Why can no comparison-based sort beat comparisons in the worst case?
A comparison sort can be drawn as a binary decision tree in which every possible ordering of the input reaches its own leaf. With distinct keys there are at least leaves, so the tree height is at least . The longest path is the worst-case number of comparisons.
A hash table has 7 slots, numbered 0 to 6, with hash function h(k) = k mod 7 and linear probing with step 1. Keys 10, 17 and 24 are inserted in that order into an empty table. In which slot does 24 land?
Key 24 lands in slot 5.
WORKING
- , so 10 goes to slot 3
- is taken, so probe slot 4: 17 goes there
- is taken, slot 4 is taken, so probe slot 5
- Slot 5 is free
Binary search runs on a sorted array of 1000 elements, comparing the key with one middle element per step. At most how many comparisons are needed?
At most 10 comparisons are needed.
WORKING
- Each comparison halves the range, so the worst case is
- , so the floor is 9
Greedy, dynamic programming and divide-and-conquer
Design techniques notesWhat is the difference between a greedy algorithm and dynamic programming?
A greedy algorithm makes one locally best choice at each step and never revisits it, so it is fast but correct only for problems where that choice can be proved safe. Dynamic programming solves overlapping subproblems once, stores the answers and combines them, so it finds the optimum for problems with optimal substructure, including many where greedy fails.
Why does choosing items by highest value-to-weight ratio fail for 0/1 knapsack, although it works for fractional knapsack?
Items cannot be split in 0/1 knapsack, so the best-ratio choices can leave unusable capacity. With capacity 50 and (weight, value) items (10, 60), (20, 100), (30, 120), the ratio rule takes the first two for 160, but items 2 and 3 give 220. Fractional knapsack can fill the gap.
How does the dynamic programming solution for the longest common subsequence work?
Let be the LCS length of the first characters of one string and the first of the other. If the characters match, ; otherwise it is the larger of and . Filling the table takes time for lengths and .
Graphs
Graph algorithms notesWhat is the difference between BFS and DFS?
BFS uses a queue and visits vertices level by level, so it finds shortest paths by edge count in an unweighted graph. DFS uses a stack or recursion and goes deep first, giving discovery and finish times used for edge classification, topological sort and strongly connected components. Both take with adjacency lists.
Why does Dijkstra's algorithm fail on graphs with negative edge weights?
Dijkstra finalises a vertex when it is removed from the queue, assuming no later path can be shorter. A negative edge can make a later path cheaper, so a finalised distance may be wrong. Bellman-Ford handles negative edges in and also detects negative cycles.
What is the difference between Kruskal's and Prim's algorithms for minimum spanning trees?
Kruskal sorts all edges and adds the cheapest one that does not form a cycle, using union-find, in . Prim grows a single tree from a start vertex, always adding the cheapest edge leaving it, in with a heap. Both are correct because of the cut property.
The Floyd-Warshall algorithm runs on a graph with 100 vertices. How many relaxation steps does it perform, counting one per triple of vertices?
It performs 1000000 relaxation steps.
WORKING
- Floyd-Warshall has three nested loops over , and
- Each loop runs over all vertices
- Steps
Programming in Python
Python notesWhy does a mutable default argument such as
def f(x, L=[])behave unexpectedly in Python?The default value is created once, when the function is defined, not on each call. So every call that omits the argument uses the same list, and appends build up across calls. The usual fix is to default to
Noneand create a new list inside the function.What does
-7 // 2give in Python 3, and why?It gives -4. The operator
//is floor division, which rounds toward negative infinity, not toward zero. The remainder follows the same rule, so-7 % 2is 1, and the identity(a // b) * b + a % b == aalways holds.
More interview questions: Digital Electronics · Programming in C · Computer Organization and Architecture · Probability and Statistics · Machine Learning · Linear Algebra · Database Management and Warehousing · Artificial Intelligence · Operating Systems · Computer Networks
Who hires and how they select: IT jobs for CSE/IT · IT jobs for DS & AI
Data Structures and Algorithms: notes, formula sheet and past questions