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) )