## HardCode

BAN USER- 0of 0 votes

AnswersGiven two arrays A[6] and B[3], both the arrays have 3 elements each. Both of them are sorted, need to return the merged array A[] after merging with array B[]. Need to do this inplace.

- HardCode in India| Report Duplicate | Flag | PURGE

Expedia Software Engineer / Developer Data Structures - -1of 1 vote

AnswersGiven an N by M matrix with values of N and M, and co-ordinates of a particular dot. Need to return true if the dot lies inside the matrix, false otherwise. Just develop the condition for this.

- HardCode in India| Report Duplicate | Flag | PURGE

Expedia Software Engineer / Developer Data Structures

- 3 Answers
**Interview**I am currently employed with Infosys since past 8 months and i am very passionate about development and looking for a switch, I am not from a well known college & I suppose this is the reason i am not getting any good calls, could you please help what should I do?

- HardCode June 24, 2012| Flag | PURGE

yes there is i believe,

the trick is to maintain three pointers running from the last of each array, compare the three values and put the largest at the last index of the resultant array (assuming first array has the extra space). decrement it and keep repeating this until any of the arrays exhaust.

One thing to note here is that after above step need to check if the indexes have exhausted or not and need to iterate them separately if required.

Complexity: O(m+n+p) (where m,n,p are the length's of each array respectively)

Have a solution, to have 2 stacks, one keeping the data as given and other keeping the same data in reverse order,

When needs to be added from back, add to second stack and viceversa.

In needs to be added or deleted from between, check the number of pop() operation required if traversed from front or back and choose the smaller, thus making it optimal.

Is the array given sorted?? (example given in question I assume so)

If yes then the solution can be to read the array from start and end together, say with indexes s and e respectively. Sum the values at the indexes and see if the sum is greater than given value then decrements e and if smaller then increment s. If the sum is found then print the pair and together increment and decrements s and e respectively till s!=e. This also will handle negative numbers.

O(n) complexity...

O(nlogn) solution.

1. Loop the array from 0 to n-1. Pick every element, say picked element has index "p".

2. Find the "ceil" of the picked number on the array from index "p+1" to "n-1".

3. Replace the number with the ceil value, as desired.

4. Use Binary Search to find the ceil value O(logn).

5. Doing for all n elements thus O(n*logn).

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

This is just a different way of asking the problem "Finding the maximum size square matrix with all zero's in a given matrix of 0's and 1's". Where I's can be considered as matrix points covered by buildings and otherwise.

- HardCode May 20, 2015