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.