Hadoop Learner's Guide 1: Steps to install Hadoop on Windows with Cygwin

1. Create a folder "c:\training"

2. Download JDK version 1.7 for OS 32-bit/64-bit for JAVA
    a) URL:  http://www.oracle.com/technetwork/java/javase/downloads/index.html
    b) Download jdk-7u25-windows-x64.exe in folder "training"
    c) Create a folder "java" in folder "training"

3. Install Java
    a)  Click jdk-***.exe to install java
    b)  Give installation directory as C:\training\java

4. Download and Install Cygwin for OS 32-bit/64-bit
    a) URL: http://www.cygwin.com
    b) Click setup-x86_*.exe to download and install Cygwin
    c) Create a folder "cygwin64" in folder "training" ->   "C:\training\cygwin64\"
    d)  Follow instructions in Section "7.3 Installing Cygwin"at "http://docs.oracle.com/cd/E24628_01/install.121/e22624/preinstall_req_cygwin_ssh.htm" to install Cygwin.

       Run the setup executable, then click Next to proceed.
       

       On the Choose Installation Type screen, select Install from Internet, then click Next.

       

      On the Choose Installation Directory screen, enter C:\training\cygwin64\ as the Root Directory, then click Next.
       

      On the Select Local Package Directory screen, select a directory on your local machine C:\training\package\ where you want to store the downloaded installation files, then click Next.

     
      
     On the Select Connection Type screen, select appropriate settings to connect to the internet, then click Next.

     

     On the Choose Download Site(s) screen, select any site from the available list, then click Next.
          

    Add following packages for installation: openssh, openssl, unzip, zip
 
    On the select packages screen, ensure that you select the following packages, then click Next:
     From the Archive category, select unzip and zip as follows:



   From the Net category, select openssh and openssl as follows:



   After selecting the packages and clicking Next, the Resolving Dependencies screen is displayed. Click Next to proceed.

  On the Installation Status and Create Icons screen, do not make any changes. Click Finish to complete the installation process.

  
 
5. Setup and Start SSHD daemon
    a) Follow steps 1-3 for Section "7.4 Configuring SSH after installing Cygwin" of "http://docs.oracle.com/cd/E24628_01/install.121/e22624/preinstall_req_cygwin_ssh.htm".
    b) Navigate to the ~\training\cygwin64\ directory, right-click the cygwin.bat file and select Run as administrator.

          c) For question, if privilege separation should be used, answer  no.

*** Query: Should privilege separation be used? <yes/no>: No

    d) For question, if sshd should be installed as a service, answer yes.

*** Query: Do you want to install sshd as a service?
*** Query: <Say "no" if it is already installed as a service> <yes/no>: yes

    e)
 *** Query: Enter the value of CYGWIN for the deamon: [] bin mode ntsec
   f)*** Query: Do you want to use a different name? no
   g) *** Query: Create new privileged user account 'cyg_server'? (yes/no) yes

*** Query: Please enter the password: 

*** Query: Renter:

If the configuration is successful, you will see the following message:

Host configuration finished. Have fun!

   h)  To start Cygwin SSHD

Perform these steps:

1. Right-click on My Computer, and select Manage.
2. In the Computer Management dialog box that appears, go to Services and Applications, and select CYGWIN sshd.
3. Click CYGWIN sshd, then click the Start button.

  h) If the SSH daemon does not start up, view the c:\cygwin\var\log\sshd.log file for information on why the start up failed.

  i)  To test ssh

      > ssh localhost

         Password:

6. Setup passphraseless ssh so that password is not required

If you cannot ssh to localhost without a passphrase, execute the following commands:
$ ssh-keygen -t dsa -P '' -f ~/.ssh/id_dsa 
$ cat ~/.ssh/id_dsa.pub >> ~/.ssh/authorized_keys

Test:

>ssh localhost

No password required this time

6. Download and Install Hadoop 1.2.1 for Single Node

  a) URL: http://apache.mesi.com.ar/hadoop/common/hadoop-1.2.1/hadoop-1.2.1.tar.gz
      Download it in C:\training\
      Other urls : http://apache.mesi.com.ar/hadoop/common/
  b) Unzip the hadoop-1.2.1.tar.gz in C:\training
  c) Edit following configuration files
      c.1) Add following to c:\training\hadoop-1.2.1\conf\core-site.xml  
             <configuration>

       <property>
         <name>fs.default.name</name>
         <value>hdfs://localhost:9000</value>
       </property>
      </configuration>

    c.2) Add following to c:\training\hadoop-1.2.1\conf\hdfs-site.xml
           <configuration>

       <property>
         <name>dfs.replication</name>
         <value>1</value>
       </property>
     </configuration>

   c.3)  Add following to c:\training\hadoop-1.2.1\conf\mapred-site.xml
          <configuration>

       <property>
         <name>mapred.job.tracker</name>
         <value>localhost:9001</value>
       </property>
     </configuration>

7. Setup JAVA_HOME

    a) Set JAVA_HOME in Windows
         Create a new variable JAVA_HOME as follows:  Right-click on My Computer and go to Properties. In the System Properties window, click Advanced. In this tab, click Environment Variables. Then Add a User Variable JAVA_HOME.

Variable Name: JAVA_HOME
Variable Value: C:\training\java\jdk_1.7.0_21

  b) Set JAVA_HOME in Cygwin
       b.1) On Cygwin command line, type
              export  JAVA_HOME=/cygdrive/c/training/java/jdk_1.7.0_21 ( Linux style path name)
              or
              export JAVA_HOME=c:\\training\\java\jdk_1.7.0_21 (Notice the use of two \\ to give path)
       b.2) Add the export command in ~/.bashrc

  c) Set JAVA_HOME in hadoop scripts

            Edit C:\training\hadoop-1.2.1\conf\hadoop-env.sh to set JAVA_HOME

      JAVA_HOME=/cygdrive/c/training/java/jdk_1.7.0_21
      or
      JAVA_HOME=$JAVA_HOME  ( As it was exported in shell )


8. Start Hadoop

Format a new distributed-filesystem:
$ /cygdrive/c/training/hadoop-1.2.1/bin/hadoop namenode -format

Start the hadoop daemons:
$ /cygdrive/c/training/hadoop-1.2.1/bin/start-all.sh

The hadoop daemon log output is written to the ${HADOOP_LOG_DIR} directory (defaults to ${HADOOP_HOME}/logs).

Browse the web interface for the NameNode and the JobTracker; by default they are available at:

• NameNode - http://localhost:50070/
• JobTracker - http://localhost:50030/

Stop the hadoop daemons:

$ /cygdrive/c/training/hadoop-1.2.1/bin/stop-all.sh

Programming Interview Questions - 14

Q1. Given a calendar of events, design an algorithm to find all the overlapping events.


Q2. Given a sorted array of numbers containing duplicates, find the last occurrence of a given number.


Q3. Write a function which outputs itself.

Hint: Quine computing


Q4. Given two numbers x and y having equal number of digits, rearrange x such that x is greater than y and difference d = (x-y) is the least among all the x's possible by its rearrangement.
Example: x = 1234
               y = 2410
Rearranged x is 2413


Q5.  We have given a matrix A[m][n] where each cell is either 0 or 1. Adjacent cells ( top, bottom, left, and right ) having similar value (1 or 0) are considered connected. An island is a set of connected cells. Design an algorithm to count the numbers of the dis-connected islands.

Programming Interview Questions - 13

Q1.  Given an unsorted array of -ve's, +ve's, and zeros, design an algorithm to arrange the numbers such that all the -ve's are in the left, zeroes are in the middle, and all the +ve's are in the right of the array.

Hint1: Dutch national flag problem
Hint2: Quick sort with 0 as pivot such that all -ve's are left of first zero and all the duplicate zeroes and +ve's are right of the first zero.  Duplicate zeroes and +ve's may be in nay order. So, we again apply quicksort on right sub-array with 1 as pivot.


Q2.  Given two sorted arrays A and B of size (m+n) and m respectively, design an algorithm to merge A and B in-place.


Q3.  Count the number of 1's in a number's representation.

Hint:    while(num > 0) { count++ ;  num = num & (num-1);}


Q4.  Given an array of N numbers, find a set of k numbers whose sum is maximum.
Hint: Find top-k greatest numbers. Construct a max heap in O(n) time and  retrieve top-k in O(k log n).


Q5. Given two arrays A and B of  N and M elements each, write an algorithm to find min(|A[i]-B[j]|).

Hint: Sort each of the arrays in the ascending order. Use an algorithm similar to merge sort to find adjacent pairs of A and B in the combined sorted array. In place of creating a new sorted array, in the merge process itself, find the pairs and take the difference. Find the pair with the smallest difference.


Q6.  Given a string of characters, find the longest substring made up of only three distinct characters.

E.g. Given string s =  abcdaaabbcccefbccc
Here the longest substring having 3 distinct characters is "aaabbccc".

Hint:  Use the principle of Knuth-Morris-Prat algorithm. Remember the position of three characters.


Q7.  Given an array of  integers, design an algorithm to put all the zeros in the beginning of the array.

Hint: 1. Use the principle of quick-sort.
        2. Scan from both ends of the array using a left index  ( i from 0 to n-1, i++)  and a right index ( j from n-1 to 0, j-- ). Exchange a non-zero element on the left with a zero element on the right.  Repeat this until the i < j.


Q8. Given  N  two-dimensional co-ordinates (X_i, Y_i ), find the line passing through the most co-ordinates.

Hint: Hough Transform


Q9.  Given an array of +ve integers and the option to change any integer to it negative value as per required, design an algorithm to find the minimum sum  S >= 0 and all the changes required.


Q10.  Given a sorted list of non-overlapping intervals A= {(4-8),(10-12), (17-23), (25-31)}, design following functions
(a) Given a new interval (a-b), insert it into A such that the list is still sorted and the intervals are non-overlapping.  We can merge all the intervals that overlap with the new interval.
e.g.: Insert (9,24) into A.
       Result list A = {(4-8),(9-24),(25-31)}

Important Java Questions

1. Differentiate between procedural programming and object oriented programming.
2. What are interfaces?
3. Describe some advantages of interfaces.
4. What are abstract classes?
5. What are the differences between an interface and an abstract class?
6. What is method overriding and method overloading?
7. What is polymorphism?
8. What is difference between aggregation and composition association?
9. What are immutable objects? How to make an object immutable?
10. What is deadlock and livelock?
11. How to achieve synchronization in a multi-thread java programming? Method level synchronization and Block level synchronization. Static method synchronization.
12. How to implement a thread?
13. Difference between a thread and a process.
14. Describe a scenario where a deadlock happens.
15. How to handle exceptions in Java?
16. What is a Singleton and how to implement it?
17. Difference between Hashmap and Hashtable?
18. Difference between Vector  and LinkedList?
19. Regular Expressions in Java?
20. Difference between inheritence and composition ?
21. Difference between comparator and comparable interfaces?
21. Design patterns in oops programming?
22. What are re-entrant locks?
23. Difference between implicit and explicit locking?
24. What are marker interfaces?
25. What is the difference between a concurrent hashmap and concurrency achieved using synchronized keyword?
26.What is the difference between an enumerator and an iterator? Which is fail-safe and which one is fail-fast?
27. What is difference between a volatile variable and a ThreadLocal variable?
28. can an interface declare a private method?
29. can a constructor throw an exception?
30. A method declaration in an interface has throws exception. is it necessary for implementing class to throw an exception?
31. What are generics?
32. How to determine the datatype of a generic type?
33. What is a race condition in a software?
34. What is a phantom reference?

Software Engineering Interview Questions - 12

Q1. Given N points in a 2-Dimensional space, find a point (x, y) which minimizes the sum to all the given points.

Hint: Its an important problem studied in operations research as facility location problem.  The problem has a variety of form. The above problem is Ferment Weber Problem.

a) For L1 norm (also see Lp space, Normed Vector Space from linear algebra), its the median that minimizes the sum. See the derivative of an absolute function for an insight.

b) For L2 or Euclidean distance  ( see Euclidean Space for more details), there is no closed form solution as discussed in Ferment Weber Problem.

Note: See the difference from centroid as used in k-means clustering or centre of mass.


Q2.  Design an algorithm to count the number of binary strings of size n that can be formed with the constraint that a 0  has a 1 in its immediate left.

Example:  101010 -> Right
                001010 ->Wrong

Hint: F(n) = F(n-1) + F(n-2)
        Let's suppose that the rightmost bit is 0. Then the 2nd rightmost bit has to be 1. This gives F(n-2) binary strings. If the rightmost bit is 1. Then, we get F(n-1) binary strings.




Q3.  Given a matrix  MxN of numbers, find the sub-matrix with the largest sum.

Hint: 2-Dimensional Kadane Algorithm

Flow of execution:

Input Matrix

      C1   C2   C3  C4  C5  C6
R1
R2
R3
R4
R5

Compute Sum1


                                  C1   C2   C3  C4  C5  C6
R1
R1+R2
R1+R2+R3
R1+R2+R3+R4
R1+R2+R3+R4+R5

Perform 1-D Kadane for each row from row R1 to R5.

Compute Sum2.

                              C1   C2   C3  C4  C5  C6
--
R2
R2+R3
R2+R3+R4
R2+R3+R4+R5

Perform 1-D Kadane for each row from R2 to R5.

...... Continue
Complexity O(N^3)

Q4. Given a matrix MxN with 0's and 1's where 0 means a lake and 1 means land, design an algorithm to find the shortest path from [0, 0] to [1, 1].

Hint: Use flood fill algorithm which is similar to a Breadth First Search on a graph.



Q5. Given a sorted array of numbers where each number is repeated multiple times, design an algorithm to find the first occurrence of a given number.

Hint: Binary search


Q6. Given an array of numbers where every number except one is repeated, efficiently find the number.

Hint: Use XOR


Q7.  Design an algorithm to find two non-repeating numbers in an array where other numbers are repeated.

Hint:  Use XOR with Divide and Conquer. An XOR of all the numbers is only the XOR of the two non-repeating numbers. Take a set bit of the result.  Le it be the kth bit. This bit is set because the corresponding bits in the non-repeating numbers are opposite. Now divide all the numbers into two groups, one having the kth bit as 0 and the other having kth bit as 1. Take XOR of each of the groups. The resultants are the non-repeating numbers.

X & ~(X-1) gives the least significant set bit. (X-1) has the property to shift the least significant set bit to left.

The idea can be recursively used to find k non-repeating numbers.


Q8.  Given an array of numbers where all the numbers are repeated odd number of times except one which is repeated even number of times, design an algorithm to find the number which is repeated even number of times. 


Q9.  Given an array of numbers where some numbers occur only ones, some are repeated twice and only one number occur thrice, design an algorithm to find the number that occur thrice.


Q10. Given an array of numbers where all number occur three times except one which occur only once, design an algorithm to find the number that occur only once.

Interesting Problems on Trees - 3

Q1. Given a Preorder traversal of a Binary Search Tree, reconstruct the tree.

Hint: First node is root. Scan the traversal till we get a value greater than the root.  Then, the left part forms the left subtree whereas right part forms the right subtree.

Q2. Given a Preorder traversal of a Binary Search Tree, design an algorithm to verify if each non-leaf node has only one children.

Hint:  a) If a node has only one children then all its children are greater ( for right subtree) or lesser ( for a left subtree ) than it.  IN preorder traversal all the children of a node comes after the node. So, we just need to check if all the nodes are greater or lesser. To do it efficiently, we can use the property that the largest node is the rightmost node whereas the smallest node is the leftmost node.

b) Construct a BST from Preorder traversal. First node is root. Scan the traversal till we get a value greater than the root.  Then, the left part forms the left subtree whereas right part forms the right subtree.


Q3. Two nodes in a binary search tree are swapped, design an algorithm to correct the tree.

Hint: Perform an inorder traversal. At each step verify if we are getting a sorted sequence by inorder traversal. This can be obtained by comparing a number with its successor and predecessor. If the node does not satisfy the constraint,  then remember the node. Finally, fix the two nodes which have been swapped.


Q4.  Given a Binary Search Tree and two numbers x and y, find the shortest path ( minimum number of hops) between the numbers.

Hint: Perform a simultaneous search for the  numbers in the BST. The first node where the search splits is the least common ancestor the numbers.  Taking this as reference node, find the depth of each of the nodes from this reference node. Sum of the depths is the length of the shortest path.


Q5.  Given two binary search tree, merge these in-place to get a new binary search tree.

Java source code:
Main class: MergeTwoBST.java 
Other classes: BinaryTree.java , Node.java , NodeInt.java , NodeStr.java 
Input File: UnorderedNumberSequence

Software Engineering Interview Questions - 11

Q1. Give an algorithm to serialize a binary tree into stream, and then reconstruct the binary tree from the stream.

Hint:  a) If binary tree is in array, we can serialize ans deserialize in a straight forward manner. 

         b) Preorder and Inorder traversal.

         c) Serialize using pattern {parent} {left subtree} {right subtree} recursively.

Q2.  Print all the M size combinations of a N size set in a sequence such that each set of the sequence can be obtained from its preceding set by removing one element and adding a new element. 

Q3. Find all the duplicates in a given Binary Search Tree without using any extra space. 

Hint: Use an inorder traversal and match the current node with the last node to check if they are duplicates.

Q4. Given a list of numbers A= {5, 10, 15, 20, 21, 23} and associated probability of occurrence P={ 0.1, 0.3, 0.05. 0.13, 0.02,  0.4} such that sum(P[i]) = 1, construct a Binary Search Tree that minimizes the expected access time of the nodes  given a message having the numbers in A. The cost of access of a node at depth d (the number of comparisons required to access the node at depth d ) is d+1.  Let n be a node at depth d in the BST with probability of occurrence p, then the minimization function is sum(p(n)*(d+1) over all n)

Hint: Use dynamic programming.


Q5. Given two tumblers of capacity 5 (m) liters and 3 (n) liters where m-n=k, design a technique to measure 4 (x) liters.
Note: This is famous as puzzle. Here, we want an actual algorithm to do it.


Q6.Write an algorithm to solve Tower of Hanoi .


Q7.  Given a N x N matrix of numbers, design an  efficient algorithm to perform a 90 degree rotation of the  matrix.

Hint:  Assume matrix A to be made up of layers similar to an Onion. Perform a  layer by layer rotation starting from the outermost layer to the innermost layer. To perform a rotation at a given layer, start from any corner and move the corner elements in clockwise directions by n-1 steps. We start from A[0][0]. We
move as follows:
A[0][0] -> A[n-1][0] -> A[n-1][n-1] -> A[0][n-1] -> A[0][0]
Then move, A[0][1] -> A[n-2][0] -> A[n-1][n-2] -> A[1][n-1] -> A[0][1] and so on.


Q8.  Given a linked list where each node also has a pointer to some arbitrary node in the list, design an algorithm to clone the linked list.


Hint:  Let A be a linked list. Insert a new node in front of the every node of A and copy value from the previous node to create a new linked list B.  Now to copy the arbitrary pointers use following logic

B(Current).Next.Arbitray_Pointer = B(Current).Arbitrary_Pointer.Next

Finally restore the original linked list as follows:

Original_Head = Original_Current = B(Head)
Clone_Head= Original_Current.Next
-- Begin For loop
Clone_Current = Original_Current.Next
Original_Current .Next = Clone_Current .Next
Original_Current  = Original_Current .Next
--End loop


Q9.  Given a histogram, find the maximum area rectangle within the histogram.

Hint: For each bar, the largest rectangle obtained by the bar would be:
 The  height of the bar (h) *
 The maximum left extension without decreasing the bar height  (l) *
 The maximum right extension without decreasing the height of the bar (r) .

To efficiently obtain l and h use following idea of stack.
Initialize a stack with top of the stack, TOS= 0
Compute l as ( i - TOS)

For bar i = 1, l = i - TOS = 1 - 0 = 1
Push bar 1 is the stack, TOS = 1
For bar i = 2,  pop out bars til we find a bar of height smaller than second bar, and recompute TOS
l = i - TOS
...

Similarly compute r.

All this will have a time complexity of O(n)


Q10.  Given an array of integers, design an algorithm to find:
          a) the largest sub-array whose elements can be arranged into a continuous sequence.
          b) the longest continuous sequence.


Hint (b) Sort and then do a linear scan. For fixed interval,  a bitset can be used.

Starting Oracle Database Enterprise Manager

1. Switch user to root
    su root
     or
    sudo su

2. Set ORACLE_SID
    ORACLE_SID = ORCL
    export ORACLE_SID

3. Set ORACLE_HOSTNAME
    ORACLE_HOSTNAME= localhost
    export ORACLE_HOSTNAME

4. emctl start dbconsole

    emctl is available in bin folder in Oracle  installation folder
    oracle/product/11.2.0/dbhome_1/bin

5. Access oracle enterprise manager using the URL: https://localhost:1158/em

Software Engineering Interview Questions - 10

Q1. Find the square root of  a number x.

   Hint: Use Newton Raphson method or Bisection Method / Binary Search Method.

           Let  y^2=x  =>  y^2 - x = 0

           Let f(y) = y^2 -x

           y_n = y_(n-1) - f(y)/f ' (y)

Q2.  Given an array of numbers, find the first number that is unique in the array.

Hint:  Use a LinkedHashMap

Different implementations of Map in java are :  Hashtable (obsolete), HashMap (Supports null key and null value ),  LinkedHashMap,  TreeMap (Red-Black tree Navigable Key Sorted Map),  EnumMap ( Uses Enum keys and sorted on natural order of Enum keys),  ConcurrentSkipListMap (SkipList based implementation ), ConcurrentHashMap (Supports concurrency), IdentityHashMap (Uses reference-equality rather than Object-equality for comparing keys), and  WeakHashMap.


Q3.  There is a file which has n numbers in the nth line. For example,
         7
         2 9
         8 3 1
         2 7 9 1
       Now, starting from the top and moving down using the adjacent numbers in the below row, find the maximum sum of such a path. For example, adjacent numbers for 2nd number 9 in the row 2 are 8, 3, and 1 in row 3.

Hint: Use dynamic programming. Start from nth row and traverse back. Let the input file is stored in a half matrix/ 2-D array A. For an element at A[i][j],
A[i][j] = max(sum(A[i][j]+A[i+1][j]), sum(A[i][j]+A[i+1][j-1]),sum(A[i][j]+A[i+1][j+1]))
Pick the max sum for i = 0, i.e., 0th row.


Q4. Given n points on a circle, find the different number of ways of drawing non-intersecting chords between the n points.

Hint: Motzkin number


Q5. Given an unsorted array A where ith element A[i] is within k position from its position j in the sorted array, i.e., |j-i|=k, design an algorithm to efficiently sort the array.

Hint: Sort using a heap of size 2k. Create a minimum heap using the first 2K elements A[0 - (2k-1)]. Remove the head of the heap which is the smallest element and place at A[0]. Reorganize the heap. Insert A[2k] element in the heap. Remove the head and place at A[1]. Continue till we reach the end of the array.     This gives sorted array till A[n-k]. Finally, a heap sort is used on the remainder of the heap to get the last (2k-1) elements in sorted order.  Time complexity: O(N logk).


Q6. Given a palindrome date 2001/10/02, find the next date which is palindrome.

Hint: 20011002 is palindrome. increment 2001 till we get last 2 digits which gives a possible month when the digits are flipped. That is the next date.

Q7. Given an unsorted array of numbers, find the longest sub-array whose elements form a continuous sequence.
Example: A = {12, 1, 19, 16, 15, 18, 17, 2, 5}
Answer: {19, 16, 15, 18, 17}




Q8.  Given a stream of characters, design an algorithm to find a given string in it.

Hint: Knuth-Morris-Pratt Algorithm


Q9. Given a sorted array of numbers having multiple duplicates, find the first occurrence of a given number.


Hint: Perform a binary search.  Once we find the element at ith position, we check if A[i-1] < 0 or i=0. If not, we continue search in the left sub-array.

Q10.  Given an array of numbers and a set of operators ( +, -, *, /), find the smallest number that can not be formed by the numbers and operators. Order of the numbers in the array needs to be maintained while forming an expression with the operators.

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.