## yossee

BAN USERYour output comes to:

5789

4789

789

89

2369

369

69

9

8

6

2345

345

45

5

I doubt the interviewer was look for this. Either he would want all possible subsets or he would want none. Your code misses out on some sequences like 568 or a singular 2. If no subsets are expected then the correct output should probably be:

5789

4789

2369

569

469

2368

568

468

2345

I can't really figure out how to produce this though. If someone does, please help

The above algorithm can be further optimized. Take first element, binary search the position where the other one should be to make the sum. If it exists return it. If not, take the smaller number on that position (if say the number u need to make the sum is 8, but u find that there are only 7 and 9 - u should take 7 now). Now do a recursion swapping the numbers. The output number should be the pivot, and find a higher index in the top part of the array where you expect the sum to be. Keep swapping and recur until you find the sum or end up with only two numbers.

This will always reduce the set in half. Thus it is log n. The above algorithm goes sequentially on one side which cannot be less than linear complexity. This algorithm will binary search on both sides.

example:

findSum(new int[]{1,3,5,10,11,15,25,36,50},35);

first iteration: pivot=1, expected 34

binary searched between 3 to 50 we found 25,36 position but no 34

next iteration: pivot=25, expected 10

binary searched between 3 to 15 and found 10

Suppose you have all these variables declared and initialized.

int m,n,target;

int[][] A;

int r,c; // for row and column

// initialize here

//calling the method

find(int A, m, n, target, r, c);

//Now r and c will have the changed values

Just the fact that there is an '&' in the method signature makes it a reference. If you are really interested I would suggest further reading on pointers and references. However, if C/C++ is not your primary language, you should mention that in your interview. The interviewer should not really be expecting that knowledge.

Yes, you can. Even a single dimensional array satisfies. But that is not how you want to do it in an interview. That is not a coding practice in use. A person reading your code would never know you are making the array just so you can get output from a method. While interviewing they are really looking for your object oriented skills. So it much more advisable to make a class and use it's object.

- yossee April 01, 2012Yes, I did a lot of stupidity with this one myself. Finally after the interview I designed a class just to play with multiple coordinates and returned it's object. That is the Java way. Hate this lack of multiple returns in Java. In C and C++ you can do it using pointers or references. Guess what, even C# has an "out" keyword for specifying a return argument in your methods.

- yossee March 31, 2012I believe you were thinking of a backtracking solution by "keep increasing the low value to high value". If it was on your mind, you should have mentioned the idea. Seems a good optimization but could be annoying to program, especially in an interview. You would require a method which takes a string and gives the next string in the sequence. You would also require a smarter data structure to store the phone pad alphabets which would make it easier to query the next alphabet given the previous one.

- yossee March 26, 2012**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

A question for the interviewer would be - are we allowed to use a data store. In that case, you can have a sorted linked list to store the largest 50 or so integers and store the rest in the data store. Searching in a constant size list should take constant time - of course the constant itself is proportional to the size of the list. The moment you encounter a larger number, you extend the list and then pop out the smallest number from the tail and put it in a data store. If you occasionally encounter a number smaller than the smallest in the list, just search in data store.

- yossee May 31, 2022