Monday, July 23, 2012

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

No comments:

Post a Comment