Bloomberg LP Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: In-Person
1- In first pass use a hashmap to add all elements to that hashmap.
2- in the second pass. check if the hashmap.Contains(Sum-array[i]), If yes you have the pair.
Time Complexity O(n)
Psuedo code. You can use C# generics or C++ template to make it generic.
var dict = new Dictonary(int,int)
for(int i = 0; i < array.length; i ++)
{
if(!dict.Contains(array[i]))
{
dict.Add(array[i],array[i])
}
}
for(int i = 0 ; i < array.length; i++)
{
if(dict.Contains(Sum-arr[i]))
{
Console.Writeline( "{" + arr[i] + "," + (Sum-arr[i]).ToString() + "}");
}
}
~Cheers
package org.test.combo;
public class TestCombo {
public static void main(String[] args) {
int num = 7;
int[] numArr = { 2, 1, 9, 5, 3, 6 };
for (int i = 0; i <= numArr.length - 1; i++) {
for (int j = i + 1; j <= numArr.length - 1; j++) {
if ((numArr[i] + numArr[j]) == num) {
System.out.print("[(" + numArr[i] + "," + numArr[j] + ")]");
}
}
}
}
}
package org.test.combo;
public class TestCombo {
public static void main(String[] args) {
int num = 7;
int[] numArr = { 2, 1, 9, 5, 3, 6 };
for (int i = 0; i <= numArr.length - 1; i++) {
for (int j = i + 1; j <= numArr.length - 1; j++) {
if ((numArr[i] + numArr[j]) == num) {
System.out.print("[(" + numArr[i] + "," + numArr[j] + ")]");
}
}
}
}
}
if repetition is allowed in the input data set, bellow
template <typename T>
std::vector<std::pair<T, T>> printEqualPairs2(std::vector<T> vec, int sum)
{
std::vector<std::pair<T, T>> ret;
std::multiset<T> mulSet;
for (auto i : vec)
mulSet.emplace(i);
for (auto i : vec)
{
auto it = mulSet.find(sum - i);
if (it != mulSet.end())
{
std::pair<T, T> pair(i, *it);
ret.push_back(pair);
mulSet.erase(it);
auto it2 = mulSet.find(i);
if (it2 != mulSet.end())
mulSet.erase(it2);
}
}
return ret;
}
template <typename T>
std::vector<std::pair<T,T>> findPairs(const std::vector<T>& first, T k)
{
std::unordered_set<T> firstSet(first.begin(), first.end());
std::vector<std::pair<T,T>> result;
for(const auto& val: first)
{
auto found = firstSet.find(k-val);
if( found != firstSet.end())
{
result.emplace_back(std::pair<T,T>(*found, val));
firstSet.erase(*found);
firstSet.erase(val);
}
}
return result;
}
int main()
{
std::vector<int> first={1,2,3,4,5,7};
std::vector<std::pair<int,int>> result = findPairs( first, 3);
for( const auto& ele: result)
{
std::cout << " first: " << ele.first << "second: "<< ele.second << "\n";
}
}
In python.
Correct me if am wrong
import json
x1=input("Enter the list:")
x=json.loads(x1)
y=int(input("enter the sum value:"))
setted=set()
#sett=set()
def sum_array(list1,value):
x=0
for i in range(0,len(list1)):
for j in range(0,len(list1)):
if i!=j:
x=list1[i]+list1[j]
if x==value:
setted.add((list1[i],list1[j]))
print("The repeated item is pair is ",setted)
sum_array(x,y)
<T> void pairs(final T[] nums, T sum) {
if (nums == null) return;
final Set<T> numsLeft = Arrays.stream(nums).boxed().collect(Collectors.toSet());
for (int i = 0; i < nums.length; ++i) {
final T diff = sum - nums[i];
if (numsLeft.contains(diff)) {
System.out.println(String.format("%d, %d", nums[i], numsLeft.get(diff)));
numsLeft.remove(nums[i]);
numsLeft.remove(diff);
}
}
}
a is the array and k is the given value
- azambhrgn May 09, 20171- Sort the array
2- Assign two pointer start=0 and end=a.length-1
3- run loop while start < end
a- if(a[start] + a[end] == k), print pair values at start and end index, start++,end--
b- else if(a[start] + a[end] < k) , start++
c- else if(a[start] + a[end] > k) , end--
Time complexity O(nlogn), The above logic will work with all types of data.