Questions d'entretien

Entretien pour Software Development Engineer In Test (SDET)

-

Microsoft

Given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in. What's the O notation for what you just wrote? Can you make it faster? Can you find an O(n) solution? Implement the O(n) solution

Répondre

Réponses aux questions d'entretien

16 réponse(s)

4

Put all the numbers from the array into a hash. So, keys will be the number and values of the keys be (sum-key). This will take one pass. O(n). Now, foreach key 'k', with value 'v': if k == v: there is a match and that is your pair. this will take another O(n) pass totale O(2n) ~ O(n)

gee le

1

Easiest way to do it. Written in python. If you consider the easiest case, when our summed value (k) is 0, the pairs will look like -50 + 50 -49 + 49 -48 + 48 etc.... etc... So what I do is generalize the situation to be able to shift this k value around. I also allow us to change our minimums and maximums. This solution assumes pairs are commutative, i.e. (2, 3) is the same as (3, 2). Once you have the boundaries that you need to work with, you just march in towards k / 2. This solution runs in O(n) time. def pairs(k, minimum, maximum): if k >= 0: x = maximum y = k - maximum else: x = k + maximum y = minimum while x >= k / 2 and y <= k / 2: print str(x) + " , " + str(y) + " = " + str(x + y) x = x - 1 y = y + 1

Mitchell le

1

here is my solution using hash table that runs in O(2n) => O(n): public static String findNums(int[] array, int sum){ String nums = "test"; Hashtable lookup = new Hashtable(); for(int i = 0; i < array.length; i++){ try{ lookup.put(array[i], i); } catch (NullPointerException e) { System.out.println("Unable to input data in Hashtable: " + e.getMessage()); } } int num2; int num1; for (int i = 0; i < array.length; i++){ num2 = sum - array[i]; Integer index = (Integer)lookup.get(num2); if ((lookup.containsKey(num2)) && (index != i)){ num1 = array[i]; nums = array[i] + ", and " + num2; return nums; } } //System.out.println(lookup.get(-51)); return "No numbers exist"; }

Sen le

1

The number you're looking for is T. You can just create an array of size 101. Then you loop through the array, and drop each number i in cell of index i-50. Now you do a second pass, and for each number, you look at the number at index T-i-50. If there's something there, you have a pair.

Annymous le

1

@Mike "if( (i + sum-i) == sum)" will always give you "sum".

Anonymous le

2

@Mike: if (sum == 0) does not imply 0,0. It implies -50,50; -49,49; -48,48,...

Matthew le

0

Has anyone found the O(n) solution??? I'm having trouble with this one...

EB le

0

typedef pair Pair; list l; //create an empty list of tuples pairofsum(l,10); // an example of how to call the function which adds to your list of tuples the possible pairs of the sum void pairofsum(list& l,int sum) { if(sum==0) { Pair p; loadPair(p,0,0); l.push_back(p); for(int i=1;i<51;i++) { loadPair(p,i, -i); l.push_back(p); } } else if (sum<0) { Pair p; for(int i=0;i+-sum<51;i++) { loadPair(p,i,-(i+-sum)); l.push_back(p); } for(int i=1;i<=-sum/2;i++) { loadPair(p,-i,sum+i); l.push_back(p); } } else { Pair p; for(int i=1;sum+i<51;i++) { loadPair(p,-i,sum+i); l.push_back(p); } for(int i=0;i<=sum/2;i++) { loadPair(p,i,sum-i); l.push_back(p); } } } void loadPair(Pair& p, int f, int s) { p.first=f; p.second=s; }

C++ Solution O(n) le

0

Solution with no duplicates: @Test public void findPairsTest() { // TestCases // Alternately you can put this test cases in dataprovdier findPairs(50); findPairs(20); findPairs(-20); findPairs(-50); findPairs(0); } private void findPairs(Integer sum) { HashMap inputPair = new HashMap(); HashMap outputPair = new HashMap(); for(int i=-50; i<=50; i++) { inputPair.put(i, sum-i); } // print pairs for(Integer key : inputPair.keySet()) { Integer potentialOtherNum = inputPair.get(key); if(inputPair.containsKey(potentialOtherNum) && potentialOtherNum < key) { outputPair.put(key, potentialOtherNum); } } System.out.println(outputPair.entrySet().toString()); }

Indrani le

0

Use two pointers, one at the begin, one at the end, let us call the pointer begin and end, the array is named nums. If nums[begin]+nums[end]>target, end--;if end

Utilisateur anonyme le

0

Half=sum/2; i=1; While (half+i -51) { first = half-i; second = half+i; System.out.println(“” + first + “, “ + second); }

Utilisateur anonyme le

0

half=sum/2; i=1; While (half+i \ -51) { first = half-i; second = half+i; System.out.println(“” + first + “, “ + second); }

Utilisateur anonyme le

0

Weirdly the less than and greater than signs make the text between them invisible. The conditional statement is supposed to say Half=sum/2; i=1; While (half+i LESSTHAN 51 && half-i GREATERTHAN -51)

Utilisateur anonyme le

0

Here is my C# implementation. It runs O(N) and doesn't include duplicate pairs (e.g. including [50,-50] as well as [-50,50]). static void FindPairs(int sum) { for (int i=-50; i=-50) { Console.WriteLine(i + " " + otherNum); } } }

Bryan Evans le

5

O(n^2) solution is just two double for loops. O(n log n) solution will use a binary tree O(n) solution will use a hash table

Utilisateur anonyme le

1

O(n) solution possibility (no need for a data structure) void findpairs(int sum) { //given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in. if (sum == 0) { cout 0) { for(int i = 0; i((sum/2)-1) && i>-26; i--) { if( (i - sum+i) == sum) { cout << i << " " << sum+i << "\n"; } } } }

Mike le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.