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

Software Engineering Interview Questions - 1

1.  Given a time-sheet of employees entrance and exit from  an office over a period of month, provide an algorithm to find the number of employees at any given point of time.

Time-Sheet  Format
Date                    In                 Out
mm:dd:yyyy     hr:min:sec     hr:min:sec
01:01:2012     06:00:00       16:00:00
.................      .............        .............
14:01:2012    06:30:00         17:05:00
.................     ..............        ..............


Given query time   03:01:2012     00:00:00
Find all the employees in the office at the given time.




2.  Develop a method to sort an array of strings such that all the anagrams are next to each other.
     Hint: sort each string alphabetically.  Now, all the anagrams will have the same string representation. Then, either perform a lexicographical sort or use the string as key to hash in a hash-map




3.  Given an array of strings , find the first unique occurring string.
     For example let  S= {"ab","ac","ab","bd","ac","edf"} be an array of strings. The first unique string is "bd".


4.  Given an integer N, find all the prime numbers less than or equal to N.
      Hint:  Use Sieve of Eratosthenes algorithm
               

5.  Find the Nth prime number.
     Answer: No such general formula exists. There are few constrained  formulations. 
     Details:   prime number types ,  formula of primes,  formula of primes 2 , formula of primes 3, formula of primes 4



6.  Given a file of billion of numbers, write a program to remove the duplicates.



7. Given a matrix of 1's and 0's, write a program to find
    a) Largest square sub-matrix of only 1's
    b) Largest rectangular sub-matrix of only 1's


8.  Find the median of two sorted arrays.


9.  Find the Kth largest element in an unsorted array or find top-k elements in an array.

     ( Hint:  Selection Algorithm (median-of-median linear time algorithm) )