M.Zimmerman6
BAN USER- 0of 0 votes
AnswersGiven two arrays, A and B, both containing integers, find values that appear in both arrays and output them.
I knew the fastest answer to this, which is basically adding array A to a hashmap and then checking if that map contains each element of B, which is an O(n) operation, but uses memory in O(n) as well. The interviewer then asked if I could figure a way of doing this with a complexity of O(n) without using any extra memory, basically just O(1) for memory.
Is this possible? I could not think of a simple quick solution for this on the fly, but I imagine it is possible.
Here is the code I wrote during the interview.import java.util.*; public class ArrayFun { public static void main(String[] args) { int[] a = {1,2,3,4}; int[] b = {2,5,6,7,3,2}; ArrayList<Integer> matches = ArrayFun.findMatches(a,b); for (int i = 0;i<matches.size();++i) { System.out.println(matches.get(i)); } } public static ArrayList<Integer> findMatches(int[] a, int[] b) { HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); ArrayList<Integer> matches = new ArrayList<Integer>(); for (int i = 0;i<a.length;++i) { map.put(a[i],0); } for (int i = 0;i<b.length;++i) { if (map.get(b[i]) != null && map.get(b[i]) == 0) { map.put(b[i],1); matches.add(b[i]); } } return matches; } }
Also, another quick question, is it typical for a phone interviewer to only ask you one question? I think it would be kind of difficult to ask more than one technical question, including coding, in such a short amount of time, i.e. < 1 hour
- M.Zimmerman6 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays
This solution would only work for problems with numbers greater than 0. So that would have to be a condition in the function as well.
- M.Zimmerman6 January 16, 2013Instead of having to really manage the sizes of your array and allocation and stuff like that, simply use an ArrayList, it will handle all of the background grunt work for you, and will offer constant time insert and delete.
- M.Zimmerman6 January 05, 2013I really do not see why we need to over complicate things. We can do everything in O(n) complexity with no extra space aside from a couple variables. Just like this
public class arrayFunctions {
public static void main(String args[]) {
int temp[] = {3,2,6,1,1,1,2,4,7,8,9};
arrayFunctions test = new arrayFunctions();
System.out.println(test.nextLargest(temp,4));
}
public int nextLargest(int arr[], int value) {
int currDiff = -1*(int)Math.pow(2,31);
int nextVal = value;
int diff = 1;
for (int i = 0;i<arr.length;i++) {
diff = value-arr[i];
if (arr[i] > value && diff > currDiff && diff != 0) {
nextVal = arr[i];
currDiff = diff;
}
}
return nextVal;
}
}
You simply put in an array, and the integer for which you want to find the next largest value of. It wil run in O(n) time. Simple
- M.Zimmerman6 December 18, 2012The issue with this code, while it may be fast, if the input array is large, you are basically doubling the amount of memory needed. In a case where there are a few thousand elements, it is not a big deal, but if you have several million or billion elements, it could end up being a problem
- M.Zimmerman6 December 10, 2012I have some simple string reversal code that uses recursion, sometimes they like to see that kind of stuff.
public String reverseString(String s) {
if (s.length() <= 1) {
return s;
}
return reverseString(s.substring(1,s.length())) + s.charAt(0);
}
It is fairly straigh forward
- M.Zimmerman6 December 08, 2012The solution I am posting will return all elements that occur an odd number of times. I am not sure if that is what is entirely desired, but hey, food for thought. Also, there is no need for maps/hashmaps
public static ArrayList<Integer> findOdd(int[] a) {
int max = 0;
for (int i = 0;i<a.length;i++) {
if (a[i] > max) {
max = a[i];
}
}
int[] counts = new int[max+1];
for (int j = 0; j < a.length; j++) {
counts[a[j]]++;
}
ArrayList<Integer> oddCounts = new ArrayList<Integer>();
for (int k = 0;k<counts.length;k++) {
if ((counts[k] % 2) == 1 ) {
oddCounts.add(k);
System.out.println(k);
}
}
return oddCounts;
}
Maybe I am not understanding the question correctly, but why can you not do something simple like the code I have below. You can simply iterate over the array once, which and get all of the values you need. Basically it will given you the end points of each non-overlapping arrays of a given range.
public class arrayTest {
public static void main(String args[]) {
int[] a = {0,3,1,5,7,9,8,13};
int range = 3;
for (int i = 0;i<a.length;i++) {
if ((i%(range+1)==range) || ((i%(range+1)) ==0)) {
System.out.println(a[i]);
}
if (i == (a.length-1) && ((i % (range+1)) != range)) {
System.out.println(a[i]);
}
}
}
}
With this method you will need to be mindful of the length. So you need to keep track of it when traversing the tree
- M.Zimmerman6 November 20, 2012It took me about a week to hear back from the first phone interview to schedule a second. It may vary from person to person and with how busy the recruiting people are.
- M.Zimmerman6 November 14, 2012Please note what my question was asking. I want to do it with complexity O(n) and memory complexity of O(1). Yours has a higher computational complexity. While it may not use memory, it will take longer to run on large datasets.
- M.Zimmerman6 November 08, 2012Okay, that is what I figured. My interview went almost exactly the same way. I talked with the interviewer about my favorite project I have worked on for a good 10 minutes, then we tried getting the coding site to work, and then worked on code for about 20-25 minutes, and then talked for another 15 or so.
Just making sure my experience was not wildly different from everyone else. Thanks and best of luck to you!
Really? I find that hard to believe unless you are a super typer. I mean just explaining everything in detail over the phone for one problem can take a bit of time. We were also trying to use a collaborative text editing site that was being finicky and slow.
- M.Zimmerman6 November 08, 2012
Answer 1 seems overly complicated. Simply sort the list, and the iterate through keeping track of what ranges your have seen.
Here is a simple mock up of this in MATLAB
This should work in n*log(n) time complexity time just because of the sort function, else it is O(n) with O(n) space complexity as well
- M.Zimmerman6 July 08, 2013