This collection evaluates algorithmic problem-solving skills, mastery of fundamental data structures (arrays, strings, hash maps, stacks, queues, trees, graphs, linked lists) and the ability to reason about time and space complexity.
Below are fifteen independent coding problems commonly discussed in software engineering interviews. For each one, write an efficient algorithm and be prepared to explain the time and space complexity, as interviewers may ask for optimizations or follow-up improvements.
nums
and an integer
target
, return the indices of two distinct elements whose values add up to
target
. You may assume exactly one valid answer exists, and you may return the indices in any order.
k.
Given an integer array
nums
and an integer
k
, return the number of contiguous subarrays whose sum is exactly
k
.
nums
, return an array
answer
where
answer[i]
is the product of all elements of
nums
except
nums[i]
. Do not use division, and aim for linear time.
s
, return the length of the longest contiguous substring that contains no repeated characters.
s
and
t
, return the smallest substring of
s
that contains every character of
t
, including duplicates. If no such substring exists, return an empty string.
k[encoded_part]
, where the substring inside brackets should be repeated
k
times, return the fully decoded string. For example,
3[a2[c]]
becomes
accaccacc
.
'1'
represents land and
'0'
represents water, return the number of islands. Cells are connected horizontally and vertically.
beginWord
, an
endWord
, and a dictionary
wordList
, transform the begin word into the end word by changing exactly one letter at a time. Every intermediate word must exist in
wordList
. Return the length of the shortest valid transformation sequence, or
0
if no such sequence exists.
numCourses
labeled from
0
to
numCourses - 1
and a list of prerequisite pairs
[a, b]
, meaning course
b
must be taken before course
a
. Return
true
if it is possible to finish all courses, otherwise return
false
.
p
and
q
, return their lowest common ancestor. The lowest common ancestor is the deepest node that has both
p
and
q
as descendants, where a node may be a descendant of itself.
k
singly linked lists, each sorted in ascending order. Merge them into one sorted linked list and return its head.
val
,
next
, and
random
pointers, where
random
may point to any node in the list or be
null
. Return a deep copy of the entire list.
n x n
matrix, rotate it 90 degrees clockwise without using another matrix for the final result.
nums
, return the length of the longest strictly increasing subsequence. Aim for an algorithm better than
O(n^2)
if possible.