Software Engineering Interview Questions - 8

Q1. Given two unsorted arrays A and B, efficiently determine if A is a permutation of B.

Hint: Create a HashMap<K,V> of A where key K is an element in A and the value V is the frequency of the element. Then, iterate through B to check if each element occurs with same frequency.

   

Q2.  Given two +ve integers A and B of 32-bit unsigned representation, discuss a scenario when the average formula of Avg = A+B/2 will not work.  

Hint: The maximum value of A and B  is (2^32-1). For the maximum value, A+B will overflow. Therefore, we need to use Avg = A/2 + B/2 + (A%2+B%2 )/2

Since, A and B are integers, A/2 and B/2 will be have truncated value of they are odd. Therefore, we need to take this case into account by adding  (A%2+B%2 )/2.

Q3. Given an array A of n number, find any three number A[i], A[j] and A[k] such that A[k]>A[j]>A[i] and k > j>i.

Hint: For each position i, find the minimum value  for sub-array A[0 to i-1] and store it in minArray[i]. This can be done for every i just by one linear search from left to right. Similarly, find the maximum value for each i from sub-array A[i+1 to n-1] and store it in maxArray[i]. This computation again can be done with a linear scan. For each position i, check if minArray[i] < A[i] < maxArray[i] and get the solution. It can be seen that computation of max or min can be merged with the verification. This approach will not generate all the triplets satisfying the property. 

Java source code: FindTriplet.java

Input: It uses a randomly generated input

Q4.  Given a sorted sequence of n numbers which is rotated randomly, find
         a)  the starting point of the sequence
         b) a given number k in the sequence

Hint a) Perform a binary search
           Java source Code: FindStartPoint.java
           Input: It uses a randomly generated input

       b) Perform a binary search

Q5.  Given an array of only three type of characters 'R', 'G' and 'B', sort the array such that all 'R's appear before 'G's and  all 'G's appears before 'B's.

Hint: Use a technique similar to quicksort.
        Java source code: QuickSortCharArray.java
        Input: Uses a random generated input

Q6. Given an array A of n numbers, design a method to generate array B such that B[i] is the minimum of numbers k preceding numbers ( A[i], A[i-1], ..., A[i-k+1] ).

Hint: Use a queue of size K.  A running example and Java source code.

Q7. Given a stream of integers, design an algorithm to find a given integer k in the stream.

Hint: Let the storage space be N, i.e., N integers from stream can be stored in memory.  Store N numbers from the stream at a time. Perform a binary search. Decide whether to terminate the search or continue searching in the stream.


Q8.  Given a large file on disk having 1 billion integers, an in-memory space to store 10 million integers, design an algorithm to sort the file on the disk.

Hint:  External merge sort




Q9.  Given a positive integer N, find a increasing sequence A of natural numbers whose first element is 1 and the last element is N.  For j < i and k< i, any element  A[i] = A[j]+A[k]  or A[i] = 2 x A[j].


Hint: Addition Chain


Q10.  Let X be a set of documents. Let Q be a set of query keywords.  A search for query Q ranks the document as per relevance and returns the most relevant document. A common practice is to highlight the relevant snippets in the document. A snippet is a part of the document that is most relevant to the query. Usually, a snippet will consists query keywords and other contextual words. For a given document D and query Q, design an algorithm to find and highlight the most relevant snippet.

Example: 

Document =>
Java provides built-in support for multithreaded programming. A multithreaded program contains two or more parts that can run concurrently. Each part of such a program is called a thread, and each thread defines a separate path of execution. A multithreading is a specialized form of multitasking. Multitasking threads require less overhead than multitasking processes.
  
Query => "Multithreading Java"


Output=>
[Start-Highlight] Java provides built-in support for multithreaded programming. A multithreaded program[End-Highlight] contains two or more parts that can run concurrently. Each part of such a program is called a thread, and each thread defines a separate path of execution. A multithreading is a specialized form of multitasking. Multitasking threads require less overhead than multitasking processes.


Java source code with test cases.