Author Archives: Zrzahid

Topological Sort

Given a graph G(V,E), find the topological sorted list of vertices. First of , what is topological sorting? From wikipedia, topological sort (sometimes abbreviated toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v […]

Top K or K-most frequent words in a document

Given a document (or stream) of words. Find the top k most frequent words in the document (or stream). For example, if stream = “aa bb cc bb bb cc dd dd ee ff ee dd aa ee”. That is, {“dd”=3, “ee”=3, “ff”=1, “aa”=2, “bb”=3, “cc”=2}. Then top 3 most frequent words are: {“dd”, “ee”, […]

The Word Ladder Game – Word Navigation

Change a word into another by changing only only one character at a time. All intermediate words should be contained in a dictionary. This problem is pretty simple if we can choose a proper data structure. Let’s begin with a simple example. Say, we have a dictionary of words, the word to navigate from. and […]

The 
Maximum
 Gap
 Problem : 
Pigeonhole 
Principle


Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)? For example, we have a unsorted array, a=[5, 3, 1, 8, 9, 2, 4] of size n=7 then the sorted version is [1, 2, 3, 4, 5, 8, 9]. The output of the […]

Swap alternate nodes in a singly linked list

Given a single Linked List. Swap every other alternate nodes. For example, given 1–>2–>3–>4–>5–>null then output 3–>4–>5–>2–>1–>null. Note that, the list was transformed in several steps. First step, swap 1 and 3 i.e. 3–>2–>1–>4–>5–>null Second step, swap 2 and 4 i.e. 3–>4–>1–>2–>5–>null last step, swap 1 and 5, i.e. 3–>4–>5–>2–>1–>null We can observe that, each […]