Software Engineering Interview Questions - 9

Q1. Compress a given string using Huffman Encoding.


Q2. Given two integers a and b, find their
       a) greatest common divisor (gcd)
       b) least common multiple (lcm)

Hint: a) Use euclidean division algorithm
                  gcd(a, 0) = a
                  gcd(a,b) = gcd (b, a mod b)

        b) Use relation lcm(a, b) = (|a*b|)/gcd(a, b)


Q3. Design an algorithm to efficiently compute binomial coefficient C(n , k).

Hint: Use recurrence formula
       C(n, k)= C(n-1, k-1) + C(n-1, k)
       C(0, k )=  0 for all integers k>0
       C(n, 0) = 1 for all integers n>=0

       Similarly, there is pascal's rule and pascal's triangle


Q4.  Design an algorithm to evaluate a fully parenthesized  infix expression/Polish Notation.
Example: (((2 * 5) - (1 * 2)) / (11 - 9))

Hint: Use a single stack data structure with operator precedence.


Q5.  Design an algorithm to evaluate a partially parenthesized infix expression.
Example:  (2 * 5 - 1 * 2) / (11 - 9)

Hint:  Use a character stack that stores the operators, a number stack for operands, and follow precedence rule.


Q6.  Design an algorithm to evaluate a prefix expression.

Example: / -  * 2 5 * 1 2 - 11 9

Hint: Read the whole expression in a stack and perform operation from last to first.


Q7.  Design an algorithm to evaluate a postfix expression/Reverse Polish Notation.
     

Q8. Design an algorithm to convert a fully parenthesized infix expression into prefix expression.


Q9. Design an algorithm to convert a fully parenthesized infix expression into postfix expression.
Hint: a) Use a character stack to store operators. Print the operands. Pop operands when we get a closing bracket.
b) Shunting-Yard  Algorithm


Q10. Given a graph G={V, E} where V is the set of vertices and E is the set of edges with unit weight and two vertices S and T, design an algorithm to find the smallest path between the nodes.

Hint: Perform a bidirectional Breadth First Search from both S and T.

Highlighting relevant snippet in document search

Problem Statement

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.

Source code

Java source code with test cases. 

Instructions for executing the program

1. BRIEF DESCRIPTION

This program performs exact case sensitive matching of given query words to doc words.
It does not perform any stemming, spell check, synonym matching, and  has no support
for regular expressions and logical conditions in query.

Following characters are used as delimeters:
{' ','?','!',',','.',';',':','+','*','-','/','{', '}','[',']','(',')'}
Whenever, the program find a matching query keyword in the program, it
extracts a snippet of character length 150. Thus, a list of snippets are
generated. Snippets are ranked using a score based technique.
The highest snippet is returned as a result with the query keywords highlighted.
If there is no exact match in the page/document for any of the query keywords, NO
result is returned

2. CODE FILES IN THE APPLICATION
Constants.java
Controller.java
ErrorMessages.java
RenderOutput.java
SnippetMaker.java
SnippetRanker.java
Tokenizer.java

TestCases.java


3. ENVIRONMENT REQUIREMENT
Language: Java
Need JRE 1.4 or higher


4. COMPILATION
   a) create a folder snippetHighlight  (case sensitive)
   b) copy all the *.java files into it
   c) change to  snippetHighlight  directory
   d) type command
      javac Constants.java  ErrorMessages.java  Tokenizer.java SnippetMaker.java SnippetRanker.java  RenderOutput.java Controller.java TestCases.java


If the system fails to compile giving error that a class is not found than please fix the classpath as described in following article: http://download.oracle.com/javase/1.3/docs/tooldocs/win32/javac.html


5. EXECUTION WITH TEST CASES
   a) change to parent directory of snippetHighlight folder
   b) Type command
       java snippetHighlight.TestCases 0
       java snippetHighlight.TestCases 1
       java snippetHighlight.TestCases 2
       java snippetHighlight.TestCases 3
       These are four test cases to run the program.
     

6. PROVIDING OWN TEST CASES

   1) Look into file TestCases.java for details
 
   Each test method creates an instance of class  Controller
   Then it passes two strings.
   First string is doc string
   Second string is list of query keywords
 
   Here is the code snippet
 
   Controller  control = new Controller();
   control.snippetHighlight(pageStr, queryStr);    


7. NON SUPPORTED  FUNCTIONALITIES
a. This program does not provide functionality for spell checking on query or page.
  This can be included using edit distance check using dictionary and character sampling.
b. This program has no support for operators like OR, AND, REGEX, etc. for query.
c. This program does not perform stemming.
d. This program does not use synonyms of query word.
  This can be done using word graph like WORDNET or a Dictionary. This program provides framework in the code to plug this service.

Given an array A, find its size-K minimum array

Q.  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:

Input Array: A={3, 56, 48, 12, 2, 51,10, 14}
Queue Q if size 4   
Output Array: minArray[A.length]

i = 0,  Q= {3}, min:3, minArray={3}
i = 1,  Q = {3, 56}, min:3, minArray={3,3}
For i=1, we append A[1] to queue Q. We need to determine if the new element A[1] is minimum or a previous element is minimum.  Starting from the head of the Q, we compare A[1]  with each element Q[j] where j < i. If Q[j] > A[i], we remove it. We continue this till we get an element Q[j] such that Q[j] <= A[i].

i = 2, Q = {3,56,48}, min: 3, minArray={3,3, 3}
i = 3, Q ={3,56,48,12}, min: 3, minArray = {3, 3, 3,3}
i = 4, Q = {2}, min: 2, minArray={3, 3, 3, 3, 2}
For i = 4,  queue Q is already of size 4. So we remove the first element from the head of the Q. Then, we append A[4] to Q. We determine the next minimum element by comparing A[4] with other  elements in the queue Q[j], j < i, starting from the head.  If Q[j] > A[i], we remove it. We continue this till we get an element Q[j] such that Q[j] <= A[i].

i = 5, Q={2, 51}, min: 2, minArray={3 , 3, 3, 3, 2, 2}
i = 6, Q= {2,51,10}, min: 2, minArray={3, 3, 3, 3, 2, 2, 2}
i = 7, Q={2, 51, 10, 14}, min:2, minArray =  {3, 3, 3, 3, 2, 2, 2, 2}

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.
  

Interesting Problem on Trees - 2

Q1. Given a Binary Search Tree and a node, modify the Binary Search Tree to make the given node as the root.

Q2.  Given a Binary Tree, find two nodes which are at the farthest distance.

Hint: Duke's CS 

Q3. Given a Binary Tree, print the nodes in vertical order.

Example:

Hint:

Order the nodes by the number we get for each of them.


Q4.  Given a sorted array, design a method to find out how many Binary Search Trees can be created for the sorted array.


Q5. Given two Binary Search Tree,  discuss and algorithm to generate a unified sorted list.


Q6. Given a Binary Tree, give a method to obtain the sum of all the nodes.


Q7. Given a Binary Search Tree, find the in-order successor of each of the nodes.


Q8. Given a Binary Search Tree, replace the value of each node with the sum of all its in-order successors.




Q9. Given a binary tree, design a method to find its depth.

Hint: Depth(T)= 1+ max( depth(T.left), depth(T.right))




Q10.  Given a binary tree and a sum S, design a method to verify if there is a path from root to any of the nodes whose sum is equal to S.


Hint:  verify(node, sum)
         {
             Sum = sum - node.value;
             if(sum == 0)  {
                        print result
                        Exit
            }
            else{
                if(sum.left != null) verify(sum.left, Sum);
                if(sum.right != null) verify(sum.right, Sum)
            }
         }
     
             

Software Engineering Interview Questions - 7

Q1. Given 3 arrays of numbers A, B and C, design a method to find all the triplets (i, j, k) such that A[i] - B[j] = C[k].

Q2.  Given a stream of characters, design an algorithm to verify efficiently if the string received at any point of time is a palindrome.

Q3. Given two sorted arrays of numbers, design an algorithm to find
      a) median of the arrays
      b) a given number k in the arrays
      c) first k smallest number

Hint: a) Perform a binary search on the two arrays
        b) Perform simultaneous binary search on both arrays
        c) Merge the two sorted arrays on line with merge sort.

Q4. Given a matrix/2D-array where each row and each column is sorted in ascending order, design an algorithm to find
       a) median of the matrix
       b) a given number k
       c) first k smallest number


Q5.  You are standing with N-1 other people in a circle. Starting from a random person, every kth person is removed till a single person is left. Design an algorithm to make sure that you are the last person left.

 Hint: Josephus Problem


Q6.  Given a matrix M of numbers, discuss an efficient algorithm to generate another matrix M' such that M'[i,j] is the sum of all the elements M[k,l] for 0<=k<=i and 0<=l<=j.

Hint:  M'[i, j] = M[i,j]+M'[i-1,j]+M'[i,j-1]-M'[i-1,j-1]


Q7.  Efficiently find the median of an unsorted array.

Hint. Selection Algorithm

Q8.  Given an array A of n numbers, design a method to generate another array B such that B[i]= A[0] x ... x A[i-1] x A[i+1] x ... x A[n], i.e., B[i] is the product of all the elements of A except A[i].


Hint. Generate C such that C[i] = A[0] x ... x A[i]
        Generate  D such that D[i] = A[i] x ... x A[n]
        Then, B[i] = C[i-1] x D[i+1]


Q9.  Given an infinite string  a,b,c,d,e,f,g,h, ...,u,v,w,x,y,z,aa,ab,ac,ad,ae,af,ag,ah, ..., ba,bb, bc, ...,bx,by,bz,...., give an algorithm to find the kth string.

Hint: If we treat each string as a number, then we see that its a number system of base 26.


Q10.  Given an array if n numbers, generate all the subsets of size k such that any two subset has only one element in common. For simplicity lets assume that n = k*l

Software Engineering Interview Questions - 6

Q1.  Given an 2-D array MxN of numbers, write a program to print the array in clockwise or anti-clockwise. For clockwise, it should be like First row, last column, last row, and then first row and so on.

Q2.  Given an array of non-zero numbers, find the first subarray (contiguous set of numbers) that sum to zero. 

     Related reading : Subset sum problem 

     

Hint: The problem can be solved in O(n) time complexity. 

Construct a cumulative sum array S. The ith value of S, i.e., S[i], contains the sum of all the values from S[0] to S[i].  If any of the values S[j] is 0, then the subarray S[0-j] is the answer and the algorithm terminates. Otherwise, if these is any subarray whose sum is ), then there must be duplicate sum values in S. Next, the task is to find the first sum which is a duplicate.  Create a HashMap<K,V> from the sum array. Key K in the HashMap<K, V>  is the sum S[i] in the array S. The value V is a linked list of the positions at which the sum occurs. Traverse the hashmap to find the smallest index of the sum that repeats.  

Q3. Design an algorithm to efficiently compute the value of a^b.

 Hint. Use divide and conquer called exponentiation by squaring. 

 A survey of fast exponentiation methods

Q4.  Given an array A such that A[i] = A[i]+1 or A[i]= A[i]-1. Design an efficient algorithm to determine if a given number k is present in A or not.

Q5.  Given a number N and K, design an efficient method to verify if N^N = K.

        Hint: Use log to verify  if N*log(N) is equal to K. 

Q6.  Given an array of numbers, design an algorithm to 

       a) find the longest increasing sub-array (contiguous elements).

       b) find the longest increasing sub-sequence ( elements are not required to be contiguous).

Hint: a) Longest increasing subarray can be solved in O(n) time complexity by a sequential scan of the array. 

        b)  Longest increasing sub-sequence is solved by dynamic programming. 

Q7. Given an array of numbers, design an algorithm to find the top-k most frequent numbers. 


Q8. Reverse first k elements of a n-size linked list. 




Q9.  In an unsorted array of first N +ve integer numbers, there is one duplicated and one missing number. Design a mechanism to find the missing and the duplicate number. 


Hint: 
Let denote a number from 1 to N as A[i]
Let denote a given number by B[i] 
Let the missing number be X. Let the duplicate number be Y. 
Sum of the first N +ve integer numbers  S'=  sum(A[i]) = N*(N+1)/2
Let the sum of the given numbers be S = sum(B[i])

Equation 1:  S'-S = Y - X 

Equation 2:   product(A[i]/B[i])  for  1< i < N  = X/Y

Q10.  Design a quicksort with two pivots. Also analyze its complexity. 

  

Software Engineering Interview Questions - 5

Q1. Given an array of integers, arrange the array such that all the positive and negative integers are grouped in contiguous manner and the relative ordering of elements in each group is preserved. 

Example: [ 2, 12, -3, 0, 4, -2, -6, 1]

Answer: [ 2, 12, 4, 1, 0, -3, -2, -6]

Q2. Given an array of integers, find the maximum sum of contiguous elements. 

     Hint: Kadane's Algorithm 

     Kadane's Algorithm for a Matrix

Q3. Given a circular linked list of integers, find the maximum sum of contiguous elements.

Q4. There are 3 employees. They need to compute the average of their total salary without communicating the true salary of each other. Design a mechanism for the same. 

Hint: These are important questions for secure distributed computing.  A naive mechanism is as follows: 

Let A, B, and C are the employees with salary a , b, and c respectively. 

Each employee adds a random amount to their salary, i.e., a+x, b+y, and c+z

They broadcast their fake salaries.

Average of fake salaries =  ((a+b+c/3)  + (x+y+z/3))

Now use a circular protocol. A takes the average and subtracts x/3 from the fake average. A sends the result to either B or C. B subtracts y/3 from the fake average and sends it to C. Finally, C subtracts z/3 and broadcasts the actual average.

Q5.  Design an algorithm to write all the permutations of a given string.

Q6. Given an unsorted array of size n, what is the minimum number of comparisons that are required to find out the median.

Q7.  Given a set, design an algorithm to generate its power set. 

Q8.  Given two very large arrays of numbers. Design an efficient algorithm to 

        a)  Find all the common elements in the two arrays. 

        b)  Find the dot product of the two arrays. 

Hint  a.1) Bloom filter is the fastest approach but probabilistic.

         a.2) Put each array in a hashset. Let the smaller hashset be A and the larger be B. Test each element of A if it is present in B. 

         a.3) Sort both the arrays. Perform a mechanism like merge sort to detect common elements. 

        b.1) Create a hashmap for each array. Store the non-zero values in a hashmap with the position of the value as key. Let the smaller hashmap be A and the larger be B.  For each value in A, search it in B and multiply. Some of all the multiplications would the dot product. 

Q9.  Given 3 strings,  design an algorithm to find out all ways in which first and second string can be used to generate the third string. 

Q10.  We have a set of 10,000 numbers. Each number use b bits, e.g., b = 16. Design an algorithm to sort the set. 

Hint: Important thing to note is that it is a set of numbers, therefore there are no duplicates. Secondly, the maximum bit used by any number is b = 16. This limits the maximum and minimum number that may be in the in the set. For example, for b = 16 and unsigned integer, min_number = 0 and max_number = 65535. For b = 16 and signed integer, min_number = -32768 and max_number = 32767.  

We take a bit array of the size of (maximum number - minimum number +1). We find the index i of a number in the bit array,  i = number + |min_number. Flag on the bits corresponding to the numbers in the array. Finally, traverse the bit array to get the numbers in the sorted order. 

Interesting Problems on Trees - 1

Q1. In-place convert a Binary Search Trees  into a sorted doubly linked list.

Q2. Find the sum of the nodes at a given level. Root is considered to be at level zero.

Q3. Find the sum of the nodes which are at a given distance d from any of their leaf nodes. Distance between two nodes is measured as the smallest number of edges that needs to be traversed to reach from one to the other.

Q4.  Write a program to insert and delete a value from a Ternary Search Tree. A ternary search tree has 3 children.  A ternary search tree belongs to the family of tries/prefix trees.

Q5.  Merge two Binary Search Trees to create a new Binary Search Tree.

Q6. a) Given two nodes of tree, find the lowest common ancestor of the nodes.
        Tarjan's lowest common ancestor algorithm
         Least Common Ancestor Problem
    b) Given two values and a binary search tree, find their lowest common ancestor.
         Hint : Search for both the number simultaneously. The lowest common ancestor is the node where the search path bifurcates, i.e., the search path of one value goes to he left and other goes to the right.

Q7.  Find the difference of the number of the left children to the number of right children for each node in a binary tree.

Q8.  Given a Binary Tree, find the shortest path from root whose sum is S.

Q9. Design an algorithm to find if two trees are isotropic.

Q10. Design an algorithm to print the boundary of a binary tree. Boundary consists of the left most nodes, the leaf nodes, and the rightmost nodes. The order of output is top to bottom, left to right and finally bottom to top.

Example:

Boundary: 1 2 4 7 8 9 6 3

Hint:  Preorder traversal till the leftmost node, print remaining leaves, reverse print preorder traversal till the rightmost leaf

Software Engineering Interview Questions - 4

Q1. Reverse the bits of an integer in-place, e.g., 11001 -> 10011.

Q2. A list contains repeated numbers. All numbers are repeated odd number of times except one that is repeated even number of times.  Find the number that is repeated even number of times.

Q3. Remove duplicates from a heap.

Q4. Given a document and set of words, design an algorithm to find the smallest window that contains all the keywords at least once. Sequence of the words is immaterial.  Let the words of a document are incrementally assigned  positions starting from 0 for the first word. Then, the length of a window for a set of words is the difference in the position of the last word and the first word.

Example:

Words set:  Buddhism, Gautama

Document:    In the late Vedic period, around the 5th century BCE, the small chiefdoms of the Ganges Plain and the north-western regions had consolidated into 16 major oligarchies and monarchies that were known as the mahajanapadas. The emerging urbanisation and the orthodoxies of this age also created the religious reform movements of Buddhism and Jainism, both of which became independent religions. Buddhism, based on the teachings of Gautama Buddha attracted followers from all social classes excepting the middle class; chronicling the life of the Buddha was central to the beginnings of recorded history in India.Jainism came into 

We see that there are two occurrences of word "Buddhism". The highlighted part of the document is the smallest window containing both the words Buddhism and Gautama.

Q5.  There are N players in a tournament.  Each player has played against every other player. Results of each game is known. Arrange the players in a row such that for any ith player, all the players winning against her is on the left and all the players losing against her are on the right.

Hint: Create a DAG of the players. Each player is a vertex in the DAG. A directed edge from a player A to B implies that A has won the match against B.  A topological sorting will either give a ordering or detect a cycle in which case there is no such ordering.

Q6.  a)  Given an array of numbers and a value N, find all the pairs which sum to N.

     b)  Given an array of numbers and a value N, find all the combinations of numbers in the array which sum to N.

     c)  Given an array of numbers and a value N, find a combination of  the numbers in the array having the least size that sums to N.

Example:

A = 2, 10, 12 , -5 , 0, -3, 1, 5

N = 5

a) Pairs: 10, -5 and 0, 5

b) Combinations: 1) 5 (size 1);

                           2) 10, -5 (size 2);

                           3)  0, 5 (size 2);

                           4)  2, -3 , 1, 5 (size 4);

                           5)  2, -3 , 1, 5, 0 (size 5);

                           6) 10, -5 (size 2)

                           7) 12, -5, -3, 1 ( size 3 )

c) Combination of the least size : a) 5 (size 1)

Hint: a.1) Put the numbers in a hashmap.  For every number A[i] in the array, find the residue R = (N-A[i]). Search R in the hashmap.

         a.2) Sort the array.  For every number A[i] in the array, find the residue R = (N-A[i]). Perform a binary search for R in the array. Take care of duplicates.

         b) A recursive solution. Sort the array.  For every number A[i] in the array, find the residue R = (N-A[i]). Perform the search for R in subb-array A'=  [A[i+1], ..., A[length(A)-1]]

Q7.     Given two strings, design an algorithm to print all the interleavings of the two strings. Here interleaving means that the if a character B comes after character A in a string, then B should also come after A in the interleaved string.

Example:

String1 = AB and  String2 = CD

Interleaved Strings:

ABCD, ACBD, ACDB, CABD, CADB, CDAB

Q8.  Sort a binary array [0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1].

Hint: Perform a quick sort using 0 as pivot. It has O(n) time complexity.

Q9.  A data stream is a sequence of unsorted numbers received or transmitted over a period of time.  A machine is  receiving a data stream. Design a data structure and an algorithm to efficiently report the median  whenever a new number is received by the machine in the stream.

Q10.  Given an array of unsorted numbers, design a  algorithm to find all the pairs (i,j) such that for i < j,  A[i] > A[j].

Hint: A O(n log n) solution possible using the idea of quick sort and binary search tree. Use quick sort to build a BST. An idea for the solution. 

Software Engineering Interview Questions - 3

1.  Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Would you rather go first or second? Does it matter?

Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

2.   Find an unbiased decision from a biased coin. When we have a biased coin, then the probability of a head and a tail is not the same.

3. Given a dictionary of words, find all the words that are made up of two words in the dictionary. For example, mango => man + go.

4.  A parking lot is unoccupied 1/3 of the time.  But, you find it empty for nine consecutive days in a row.

Find the probability that it will be empty on the tenth day.

5. Given a list of alternatively sorted numbers, e.g,  20 1 25 3 29 10 30 12., design an efficient algorithm to find a given number in the list.

6. There are M sorted lists. Each list has N numbers.  Design an algorithm to find the kth smallest number.

    or

    There is a big file containing M*N numbers.  There are M machines having just enough memory to keep N numbers. Design an algorithm to generate a sorted list of all the numbers or find the kth largest/smallest element or find the median.

Hint:  Merge sort using a Binary Heap Structure. Leaf nodes retrieve a number from each of the lists. A parent node contains the max/min of the leaves.

7.  Design a stack which performs push, top, pop, range, and size in a constant time or with complexity O(1). Range is defined as the difference of the maximum number in the stack to the minimum number.

Hint: Use two stacks. First for keeping the numbers and the second for keeping the range for each position in the stack.

8.  There are M employees in an enterprise. Each employee has a preference for working with others.  Each employee rates another employee as a  like, dislike, or neutral. A manager is given the task to form minimal number of groups of the employees such that no group has a employee that dislike any other employee in the same group. 

Solution: Let X be the set of employees of size M. Create a graph G with a vertex set V of size M and an edge set  E..   Define a bijective mapping function between X and V, i.e., every employee is mapped to exactly one vertex v in V and vice-a-versa.   Put an edge between two vertices uv if  at least one of them dislikes the other, i.e., create a dislike graph.  Create a complement/inverse G' of the graph G. G' is a graph defined on the same set of vertices V as G, but has an edge between any two vertices uv if and only if there is no edge between u and v in G.   Now the problem is to find the minimum number of  non-overlapping/disjoint cliques that covers all the vertices. We can find resemblance of the problem to the well known NP-Hard problems of set cover and cliques in a graph in computational complexity theory. We can reduce the set-cover problem to  our problem, thus proving that it is NP-Hard.  A naive approach would be to iterate through following steps.  Find a vertex with the maximum edge degree. Remove  the largest clique from the graph including the vertex. Repeat the process till all the vertices in the graph are covered. 

9. Given a large list of numbers, design an efficient algorithm to find the frequency of each number. 

Hint: Use a Hashmap.

10.  A machine is continuously receiving a stream of numbers. Give a method to report the current average. 

Hint: Remember that keeping the sum is not  a viable option as the value may overflow the register. 

New_Number_Count = Old_Number_Count +1

New Average = (Old Average * Old_Number_Count / New_Number_Count) + (New_Number / New_Number_Count)

For very very large stream, we may again have the problem of underflow for a small New_Number. The value of  (New_Number / New_Number_Count) can be smaller than the register can support. 

Topological Sorting of a Directed Acyclic Graph and Cycle Detection

Introduction

A  topological ordering or sorting of the vertices of a directed acyclic graph is a linear ordering of its vertices such that for every edge uv,  the parent u comes before the child v.  Topological sorting of directed graph with cycles is not possible.  Topological sorting defines the order in which tasks must be done. For example, courses in a college can be taken only after satisfying the prerequisites. We can define a define a directed relationship between the courses, and then order them to know which course can be taken when. Further details about the topological sorting can be obtained from the references.

Program with Examples

Code: Here is a java code to perform topological sorting of a DAG. It also detects if the input directed graph has cycles. TopologicalSorting.java.

Execution Instructions: To execute the program, put the java file and the input file in the same directory. Change the input file path name in the code at the 29th line. Compile the java code and execute it.

Input Files: Below are examples with corresponding input files. Input files represent the graph as parent and its children. A vertex u is called a parent of a vertex v if there is a directed edge from u to v. Each row in the file represent a vertex followed by a list of its children. 

a) Input DAG 1

Input File: DAG_Sort_1.txt

A C

C G F

F H

B D F

D G

E D

E G

Output : E A B C D F G H

b) Input DAG 2

Input File: DAG_Sort_2.txt

A C

C G F

F H

B D F

D G

E D

E G

H G

Output: E A B C D F H G

c)  Input DAG 3

Input File: DAG_Cycle.txt

A C

C G F

F H

B D F

D G

E D

E G

H G

G F

Output: DAG has Cycles

References

1. Wikipedia article.
2.  Algorithm 
3.  Graph algorithm video lecture
4.  The Stony Brook Algorithm Repository

Software Engineering Interview Questions - 2

1. Find the maximum element in array which is first strictly  increasing and then strictly decreasing.
      Example:   A =  {2, 3, 4, 5, 7, 15, 14, 13, 12}
      Answer:  15
      Hint: Use binary search with following check
              Given a position i in the array,
              (a) If A[i+1] > A[i] > A[i-1], then search in right sub-array [i-N]
              (b) If A[i+1] < A[i]  < A[i-1], then search in left sub-array [0-i]
              (c)  If   A[i] > A[i-1] > and A[i] >  A[i+1], then A[i] is the maximum element


2.  Given an unsorted array whose some of the parts are sorted, design an algorithm to efficiently sort the full array in ascending order.
     Example:  A = { 12, 8, 19, 2, 3 , 4, 5, 1, 17, 3, 13}
     Array A has a contiguous set of elements which are pre-sorted  A[3-6]= {..... 2, 3, 4, 5, .......}
     Hint:  Use Merge-Sort


3.  Given the market-price of a car at regular intervals over a period of time T, design an algorithm to find when should a person buy the car and sell it again to get the maximum profit.
     Example
     Time:   1      2       3    4       5     6     7
     Price:   10    15     9    19     22   21   21
     Here, the person should buy the car for 9 at time 3 and sell it for 22 at time 5 to have maximum profit.

     Java source code: MaximumProfitInterval.java

4.  Design a stack data structure to perform insert, pop, and minimum in O(1) time.
       Hint: Use two stacks

5.  Given an array of numbers such that every number except one is duplicated, find the number that is not duplicated.
       Hint: Use XOR bitwise operation


6.  Design a data structure to perform median and max in a constant time.
       Hint:  Use two heaps

7.  How to create three stacks in a given array so that space is maximally utilized. 


8.  Write a program to sort a stack using standard stack functions of  pop, push, top, isEmpty, and isFull.
      Hint:  Use two stacks.

9.  a. Bit manipulation
       b. Bit manipulation
       c. Bit Hacks
       d. Wiki Article

10.  There are N houses, where N is some integer. Each house can be painted in either Red, Green or Blue. The cost of coloring each house in each of the colors is different.  Figure out how to color each house so no two adjacent houses have the same color and the total cost of coloring all the houses is as low as possible.


Hint: It is a simplified version of graph coloring problem with minimal cost.  The problem has been studied extensively and has many variations. This can be solved using dynamic programming.

Upgrade Firmware of Router With DD-WRT for Super Performance

1. Upgrading Firmware of  a Cisco Linksys Router WRT160N V3

All the digital devices come with firmware that power their functionality. Similarly, our routers come with a firmware provided by the manufacturer which promises a standard performance. This may not be satisfactory for most of us. The router can be upgraded with open-source firmware to unleash its hidden power and features.  DD-WRT is an open-source alternative firmware for routers. Its software unlocks features and settings that aren’t accessible normally. Here are the steps to upgrade Cisco Linksys Router WRT160N V3 with DD-WRT firmware:

1. Find the make and model of your router

    Make : The manufacturer and the router name. Here the manufacturer is "Cisco" and Router name is "Linksys".

    Model : It is found at the bottom panel of the router. Here the model number is "WRT160N V3".

   See the technical specification of the router to find the flash size which is 4MB.

2. Search for the model WRT160N  in DD-WRT database and select the revision V3. This confirms that the  router is supported by DD-WRT.

3. Download the firmware "NEWD K2.6 Mini Generic".

 
 
   Note:  To download the most recent build, use ftp://dd-wrt.com/others/eko/V24-K26/.  Download the file with wrt160nv3 in the file name. 

4. Perform 30/30/30 reset of the router using following steps
    a) Reset button is at the back of the router along with the ethernet cable ports and the power point.
    b) Press the resent button for 30 seconds with the power cord plugged in.
    c) With the resent button still pressed, remove the power cord, and  keep the reset button pressed  for 30 more seconds.
    d) With the resent button still pressed, plug in the power cord. Led lights on the front panel of the router blinks. Keep the reset button pressed till all the lights blink for the second time. Just after the blink, release the reset button. Let the router reboot. Once the router is rebooted, we can see the wireless light glowing.
5. Switch off the wireless adapter of your laptop and all other laptops connected to the router.
6. Connect your router with the laptop using an ethernet cable.
7. Navigate to http://192.168.1.1/ in a browser. Use username: admin and password: admin or username: root and password : admin to get the basic-setup page of Cisco Linksys.
8. Navigate to Management tab -> Upgrade Firmware tab.
9. Choose the firmware file and upload it.
10. Upon successful completion of the upload, we will redirected to a page with the message that the upgrade is successful. Keep the page as it is.
11. Again reset the router as in step 4.
12. Go to the page in step 10 and click continue. We should be at a new page "dd-wrt.com control panel".

Note: If it does not work, again navigate to http://192.168.1.1/ in a browser. We should be able to see the new "dd-wrt.com control panel".
13. Navigate to Wireless tab -> Basic Settings tab, and configure the wireless.  Save and apply the settings. Given a name to the wireless in "Wireless Network Name (SSID)".

14. Navigate to Wireless tab -> Wireless Security tab, and configure the wireless security. Use the following values for the settings
      a)  Security Mode : WPA2 Personal
      b)  WPA Algorithms : AES
      c)  Provide the shared key.
      d)  Save and apply the settings.

Reference

1. DD-WRT website
2. Upgrading WRT160N V3
3. Flashing with DD-WRT
4. Recovering from a Bad Flash
5. DD-WRT Forum

Beginner's Guide for Android Apps Development

1. Android SDK installation 

   Follow all the steps described at Google Android Development to install Android SDK and Eclipse
   Make sure to run SDK Manager as administrator. Firewalls may create problem in getting tools and platforms from repository.

2. Developing First App ( Google's Official Training Link )

     Instructions for Getting Started with Android Apps Development Using Eclipse

     1.  In Eclipse, File -> New -> Other will open a select wizard. 

      

     

    2.  Configure Android Application and Project Settings  

     (a) Select Android Applications Project and click Next

     (b) Specify the name of the Application 

     (c) Specify  the name of the Project.  Typically it can be same as Application name. It is used be Eclipse as a  namespace. 

     (d) Select a version of the SDK API to build the app. This should have all the APIs directly accessed by the app.

     (e) Select a version of the "Minimum Required SDK". This tells what is the lowest version of SDK API that the APP supports. Lower API diversifies the app to may devices whereas a high app gives more feature.

     (f) Check the box for "Create custom launch Icon".

     (g) Check the box for "Create Project in the Workspace".

     (h) Click Next

       

   3.  Configure Launch Icon

   Click Next to go to "Configure Launch Icon" wizard. Make the selections as per your liking. This icon appears for your app on the device. 

     4.  Create Activity

         An activity facilitates user interaction. It is a single, focused thing that a user can do. All activities interact with the user.

      (a)   If you choose not to check the "Create  Activity" box, a default activity class is created. Otherwise, choose one of the two options: BlankActivity and MasterDetailFlow. 

      (b)  Click Next.

         

      

5.  Configure the Activity

     (a) Specify an activity name which is also the name of the class created.

     (b) Given the name of the layout

     (c) Select a Navigation Type. It may require to change the SDK API version selected for build earlier.

     (d) Leave the Hierarchical Button empty

     (e) Title the activity

     (f) Click Finish

  

6. Now we are ready to build and execute the first app. This also gives a foundation to make changes and develop advanced application

7.  Executing the first Android App  on a Real Device or Emulator

   (a) Launch the Android Virtual Device Manager in Eclipse by selecting Window -> AVD Manager, or clicking the AVD Manager icon in the Eclipse toolbar. 

   (b) In the Android Virtual Device Device Manager panel, click New.

   (c)  Fill in the details for the AVD. Give it a name, a platform target, an SD card size, and a skin (HVGA is default)

   (d) Click Create AVD.

 (e)  Select the new AVD from the  Android Virtual Device Manager  and click Start.

 (f)  After the emulator boots up, unlock the emulator screen.

 (g)  Close the AVD Manager.

 (h)  Run the application by either "right clicking on the project" and then selecting "Run As" -> "Android    Application" or choose "Run" from menu and then click "Run". We should getting following output on the emulator 

Further Reading:

   1. Tutorial