Adobe Interview Question
Computer ScientistsCountry: United States
Interview Type: In-Person
Good one and elegant as per my understanding.
even though if some one impose duplicate stuff, later on. (they did actually), this solution seems impressive to me.
Thx
#include <iostream>
#include <string>
#include <limits>
#include <bitset>
#include <fstream>
using namespace std;
#define BIT_MAX 10000
//If you INT_MAX, the program will be wrong
//So I define a BIT_MAX here
int main(){
bitset<BIT_MAX> ints_pos;
bitset<BIT_MAX> ints_neg;
bool ints_zero=false;
const char*file_name_l1="l1.txt";
ifstream file_read(file_name_l1);
if(file_read.fail()){
cout<<"Fail to open file"<<endl;
return 0;
}
int n;
while(!file_read.eof()){
file_read>>n;
if(n>0)
ints_pos.set(n-1);
else if(n<0)
ints_neg.set(-1*n-1);
else
ints_zero=true;
}
file_read.clear();
file_read.close();
file_read.open("l2.txt");
while(!file_read.eof()){
file_read>>n;
int index=20-n;
if(index>=INT_MAX)
continue;
//cout<<index<<endl;
if(index>0){
if(ints_pos[index-1]){
cout<<"("<<n<<","<<index<<")"<<endl;
}
}
else if(index<0){
if(ints_neg[-1*index-1]){
cout<<"("<<n<<","<<index<<")"<<endl;
}
}
else{
if(ints_zero)
cout<<"("<<n<<","<<index<<")"<<endl;
}
}
return 0;
}
Sort L1 increasing and L2 decreasing.(order of nlogn)
Start two pointer from the head of L1 and L2.
step 1::find sum if 20 make pair ..
if less than 20 increase L1 pointer
else increase L2 and repeat step 1.
Use Merge Sort ...During merging it will not require extra space because two sorted linked list in place can be merged ...
I think this is a very elegant and obvious solution. But still looking for something better.
I gave this as a first answer. Before I could finish speaking (forget about even designing or coding), I was asked to think better.
@Geek this is O(nLog(n)) so better than this would be like Linear time. Do you know any better than this. If yes, then please tell us. :)
@Shivam, what about this part? it's o(n^2)
Start two pointer from the head of L1 and L2.
step 1::find sum if 20 make pair ..
if less than 20 increase L1 pointer
else increase L2 and repeat step 1.
----
I gave second solution to create a hashTable with a Hash Function to limit HashTable size. the size of the Hash Table I choosed based upon my Hash Function was in logn space.
I did the same for both lists.
now it reduced my problem to find values in a container of L1 with size logn and container of L2 with size logn.
@Geek. Can you tell me the hash function for this ? Becuase it would totally depend on your hash function what the order is.
@Shivam
Well, I did use the
(LinkListElement % N) + digit_in_LinkListElement*10^digit_in_N
i.e. if LinkListElement = 100 and N = 23
Hashfunction will return 4+3*10^2= 304
It will have collisions and for that I used list.
I also suggested converting one linked list to a BST. and then search might have been in logn order. creating BST is n log n.
but space requirement jumped to 1.5 times the original list.
Put the first list in a hash map.
Then for each node in second list search (x = Sum - Node) in the map.
If you got this value in map, you got your pair.
Complexity O(n)
If the input list list size is huge (in TB) then it’s totally unrealistic to put all the nodes in a hash map.
In such cases you can go for the algo suggested by 'MI' above solution, but performance is a concerned there n log (n) for search and same for sorting.
If you are lucky and have a cluster of nodes then you can divide the first list data on cluster nodes, and sort using merge sort. Complexity n log (n). Remember its one time job.
Then divide the sorted data among nodes in the cluster and put on hash map.
Create a range based index map, for finding which node can possibly contain searched value.
Then for each node in the second list we need to search (X = Sum - Node), in the range index map and followed by cluster node map, if value found on map then we got our pair.
Complexity O(n).
Perhaps I did not get your map concept. If you search in the map for the number Sum-Node, then the order of your program goes O(n^2). Because you are iterating the second list which is O(n) and inside it searching the map for this value which is also O(n).
Please correct me if I am wrong.
step 1 loop through L1 and for each value in L1 do a simple math. p = N - L1[i] and push in hash map.
so for the example above values will be.
28= -8
-7=27
0 =20
56=-36
6 =14
-8 =28
0 =20
72 =-52
1000 =-980
-33 =53
so far O(n) space and O(n) time
loop through the L2 and for each L2[i] check in the Hashmap if exists then print N - L2[i] and L2[i]
O(m) time
hence big O is O(n)
public class ListPair {
// Returns list of the pairs
// with the addition equal to
// the sum mentioned.
public List<Pair> getPair(int sum, LinkedList<Integer> l1, LinkedList<Integer> l2) {
List<Pair> res = new ArrayList<Pair>();
Collections.sort(l1);
Collections.sort(l2, new MyComparator());
int oneIndex=0, twoIndex=0;
Pair pair = null;
while(oneIndex<l1.size() && twoIndex<l2.size()) {
if(l1.get(oneIndex)+l2.get(twoIndex)==sum) {
pair = new Pair(l1.get(oneIndex),l2.get(twoIndex));
res.add(pair);
twoIndex++;
oneIndex++;
} else if (l1.get(oneIndex)+l2.get(twoIndex)>sum) {
twoIndex++;
} else {
oneIndex++;
}
}
return res;
}
public static void main(String[] args) {
LinkedList<Integer> l1 = new LinkedList<>();
LinkedList<Integer> l2 = new LinkedList<>();
l1.add(1);
l1.add(2);
l1.add(6);
l1.add(-4);
l1.add(-2);
l1.add(4);
l1.add(5);
l1.add(-7);
l2.add(1);
l2.add(3);
l2.add(6);
l2.add(-4);
l2.add(-3);
l2.add(2);
l2.add(5);
l2.add(-7);
List<Pair> list = new ListPair().getPair(3, l1, l2);
for(Pair pair : list) {
System.out.println(pair.getV1() +" :: "+pair.getV2());
}
}
}
class MyComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
if(o1.intValue() < o2.intValue()) {
return 1;
} else {
return -1;
}
}
}
class Pair {
private int v1;
private int v2;
public Pair(int v1, int v2) {
this.v1 = v1;
this.v2 = v2;
}
public int getV1() {
return v1;
}
public void setV1(int v1) {
this.v1 = v1;
}
public int getV2() {
return v2;
}
public void setV2(int v2) {
this.v2 = v2;
}
}
int list1[] = {-1,3,4,5,-6,-7,-8};
int list2[] = {11,53,74,85,16,17,18};
int NUMBER = 10;(Suppose)
String pair = "";
for(int i=0;i<list1.length;i++){
for(int j=0;j<list2.length;j++){
if(list2[j]+list1[i]==NUMBER) {
pair=pair+"("+list1[i]+","+list2[j]+")";
}
System.out.println("pairs are "+pair);
}
}
Step 1:sort L! in increasing order and L2 decreasing order.
Step2:-strat pointer from L1 is i and and L2 is j
where m is smallest arrey length;
while(j<m)
{
if(a[i]+b[j]==sum)
{ cout<<a[i]<<b[j]<<endl;i++;j++;}
else
{ if(a[i]+b[j]>sum) j++;
else
i++;
}
}
our program time complexity is O(nlog n);
If we can sort both lists in memory, in takes n lg(n).
But if we can sort both lists in memory, we can sort just one list, and for the other list, for each number, just look up its complement. So, it pays to first check the list sizes and then sort the smaller one. But if neither fits in our memory of size m, we can process the shorter list in chunks of size m, each time sorting m numbers, and for each chunk of size m, process the 2nd list. This takes:
iterations * (sorting + searching)
n/m (m lg(m) + n lg(m)) = n/m * (n+m) lg(m)
If we use a hash lookup, which is sufficient, we get: n/m (m + n)
So this seems to be a win. And, we can ensure there's no bad behavior in the hash, if we write our own which throws an exception when there are too many conflicts. At this point we can stop filling the hash, run the second list through it, and then iterate again.
Note that it also makes sense to ensure our hash is good for this case. I'd start out making the conflict list a linked list, then perhaps sort long ones into arrays before running the n numbers through it... On the other hand, maybe it's not worth the effort...
I am assuming that duplication does not matter: say
- freshboy December 12, 2012list1 = 10, 10
list2 = 20
target N = 30,
then we only need to output (10, 20). We do not need to output (10, 20), (10, 20)
If the list sizes are small, everyone knows the solution based on hash_set. The tricky part here is the list size (billions of integers). There are 4 billion integers, which requires 16GB memory if we store them in the memory ---- too large.
We can play the trick if bitmap encoding: we use 4 billion bits to represent the integers, which takes 512MB (much more reasonable now). If an integer appears in list1, we set the corresponding bit. The mapping is like this: calculate the byte offset using the first 29 bits, then calculate the bit to set using the last 3 bits (an integer has 32 bits in total).
After we store list1 using this compact way, we can check every element in list2 to see if there is an element in list1 to make the sum equal to N.
This is a linear time solution.