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 […]
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”, […]
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 […]
A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings […]
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 […]
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 […]
Given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete. A variant of this problem could be formulated as – Given a […]
Given an array of random integers, find subarray such that sum of elements in the element is divisible by k. For example, For A=[2, -3, 5, 4, 3, -1, 7]. The for k = 3 there is a subarray for example {-3, 5, 4}. For, k=5 there is subarray {-3, 5, 4, 3, -1, 7} etc. […]
Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ? Suffix Tree Definition A suffix tree ST for an m-character string S is a rooted directed tree with exactly m leaves numbered […]
Declaring a static variable in Java, means that there will be only one copy, no matter how many objects of the class are created. The variable will be accessible even with no Objects created at all. However, threads may have locally cached values of it. When a variable is volatile and not static, there will […]