Katkat
Back

Solve common array/graph interview problems

Art AdvisorsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate matrices for grid traversal, apply BFS for shortest-path discovery in string transformations, and optimize sorting or counting logic for metric calculations.

Part 1: Word Ladder Shortest Path

Given two words, beginWord and endWord, and a wordList, find the length of the shortest transformation sequence from beginWord to endWord such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the wordList. Return 0 if no such sequence exists.

Example: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 (Sequence: "hit" -> "hot" -> "dot" -> "dog" -> "cog")

Part 2: H-Index Computation

Given an array citations where citations[i] is the number of citations a researcher received for their i-th paper, compute the H-index. The H-index is defined as the maximum value h such that the researcher has published at least h papers that have each been cited at least h times.

Example: Input: citations = [3, 0, 6, 1, 5] Output: 3 (The researcher has 3 papers with at least 3 citations)

Constraints

  • For Part 1: All words are the same length. 1 <= wordList.length <= 5000.
  • For Part 2: 0 <= citations.length <= 10^5.
  • Provide efficient solutions for both; ideally O(M * N) for the transformation and O(N log N) or O(N) for the H-index.

Hints

Hint 1

For the word transformation, model the problem as an unweighted graph where an edge exists between two words if they differ by exactly one character.

Hint 2

For the H-index, sorting the citations in descending order allows you to easily check the condition for each index.

Hint 3

Alternatively, consider using a frequency array or counting sort to compute the H-index in linear time.

Follow-up questions

  • How would you optimize the word transformation if the word list contained millions of words?
  • If the citation array is too large to fit in memory, how would you calculate the H-index using a streaming approach?
  • How does your choice of graph traversal algorithm for the word ladder impact memory usage if the word list is highly dense?