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