Since some student readers have requested me to feature more computer science interview questions, let’s continue our discussion from last month, with a few more interview questions.
1. You are given two strings, S1 and S2. You are asked to transform String S1 into String S2 by means of the following two operations, namely, insertion and deletion of a character. Each insertion will incur a penalty of 1 and each deletion will incur a penalty of 2. Can you find the minimum cost needed to transform S1 into S2 and also the set of transformations which result in this minimum cost?
2. Consider the same problem discussed in Question (1). Given two Strings S1 and S2, and also the minimum cost needed to transform S1 into S2, can you find the set of transformations, namely the insertion and deletion, which will result in transforming S1 into S2 with the above specified minimum cost? Is this solution unique? Or can there be multiple sets of such transformations which can result in transforming S1 into S2 with the same minimum cost?
3. You are given a large piece of text T and a small string s1 whose length is N. You are asked to find out the closest approximate match to s1 which is present in T. The closest approximate match to S1 is the string s2, which can be transformed into s1 with minimum cost by means of inserting a new character or deleting a character at each of the different positions of the string. Can you write a C program to find the closest approximate match given the text T and string S1? What is the complexity of your code?
4. You are given a large piece of text T of length ‘m’ and a small string s1 whose length is ‘n’. You are asked to find out whether S1 is NOT a sub-string of T. (Note that the question is not to find out if S1 is a sub-string, but to find out if S1 is NOT a sub-string.) Can you write a C function ‘IsNotASubString’ which can perform this task? What is the complexity of your code? If you use the naïve sub-string comparison function, we know that the complexity would be of the order of O(mn). How can you reduce this complexity?
5. Given an integer k, find all its factors. What is the time complexity of your code?
6. Given a set S of integers from 1 to N where N can be quite large, you are asked to find the set of factors for each integer in the set S. In this case, if you reused the code that you wrote for Question (5), what would be the time complexity of your program? Is it possible to reduce the time complexity of your program?
7. Given a set S of integers from 1 to N where N can be quite large, you are asked to find the set of prime numbers in the given set S. Would you be able to re-use the code you wrote for Questions (6) and (7)? If so, how can it be done? What is the time complexity of your solution?
8. Given two arrays A and B of integers where the array lengths are unequal (A is of size m and B is of size n), you are asked to write a program which can compute the following: A-B, A Set Union B (AUB), and A intersection B. What is the complexity of your code?
9. You are given a set S of N random strings <s1, s2, … Sn>. Some of the strings are anagrams of each other. You are asked to write a function which can group the anagrams together into sub-groups. The non-anagrams are each placed in their own sub-groups. For example, given the set S: <“now”,“Star”, “src”, “new”, “car”, “cat”, “tac”, “rac”, “won”, “rats”, “not”>,
your function should emit the following sub-groups:
<“star”, “rats”>,
<“src”, “car”, “rac”>,
<“cat”, “tac”>,
<“now”, “won”>,
<“new”>,
<“not”>.
What is the time and space complexity of your code?
10. You are given a directed graph G <V,E> where V is the set of vertices and E is the set of edges. You are given two vertices N1 and N2. You are asked to write a program to calculate how many paths exist between N1 and N2. What is the time and space complexity of your code?
11. Consider the problem discussed in Question (10) above. Now you are asked to find out how many paths exist between each pair of vertices <v1, v2> that are present in graph G. What is the time complexity of your code? Would you be able to reuse your solution from Question (10)? If you can do so, does it increase the complexity of your code? Explain why.
12. You are given an array of unsorted N integers. You are asked to write a program which can return the Kth largest value and Kth smallest value in the array, where K can be an arbitrary integer. What is the time and space complexity of your code? Can you do this without sorting the array?
13. You are given two lists of integers, L1 and L2. You are asked to write a program which can merge the two lists, L1 and L2, and create a list L3. What is the time complexity of your solution if the two lists L1 and L2 are unsorted lists of integers? What is the time complexity of your solution if the two lists L1 and L2 are already sorted? If you are now asked to do the merging of lists in place, what would be the time complexity for both the following cases: (a) unsorted lists, and (b) sorted lists?
14. Given an array of N integers, you are asked to write a program that checks whether the array is an arithmetic sequence. An arithmetic sequence is one in which there is a constant difference between two consecutive elements in the sequence. For example, the sequence <1,5,9,13,17, 21> forms an arithmetic sequence, whereas the sequence <1,4,7,10, 12, 15, 18,20> does not form a arithmetic sequence. What is the time complexity of your code?
15. You are given a large piece of text and asked to write a program that can compute the frequencies of different characters in the text. For instance, given the text,“I came to see you,” the output should be:
<(I,1), (c,1), (a,1), (m,1), (e,3), (t,1), (o,2), (t,1), (y,1), (u.1)>. First assume that the text consists of English language characters and is of fixed size. What is the time and space complexity of your solution? You are now told that the text can consist of any Unicode character. How would you modify your earlier solution to handle this?
16. Given an array of N integers, you are asked to write a program that can check whether the array can be split into two sub-arrays, A1 and A2, such that the sum of elements in A1 has the same value as the sum of elements in A2. For example, given the array A as <5, 10, 15, 20>, it is possible to split it into two sub-arrays A1 = <5,20> and A2 = 10, 15> whose sum of elements are equal.
17. You are given a sorted list of N integers and asked to create a binary search tree. What is the time complexity of your solution? Can you explain whether the binary search tree that gets constructed is a unique solution? If yes, explain why it has to be unique. If not, give a counter-example.
18. Given a directed unweighted graph G(V,E), where V is the set of vertices and E is the set of edges, find a spanning tree for the graph. (Note that you are asked to find a spanning tree and not a minimum spanning tree.) Is the spanning tree you construct unique for a given graph? If yes, explain why. If not, give a counter-example.
19. You are given two lists of integers, L1 and L2, such that L1 is of length N and L2 is of length M. N is very much longer than M. You are asked to find a sub-sequence in L1 that can cover all elements in L2. Note that the sub-sequence can also contain elements not present in L2. What is the time complexity of your solution?
20. You are given an array of N integers. The elements of the array can either be positive or negative. Find all triples in the array such that their sum is zero.
If you have any favourite programming questions/software topics that you would like to discuss on this forum, please send them to me, along with your solutions and feedback, at sandyasm_AT_yahoo_DOT_com. Till we meet again next month, happy programming!
