Geek
BAN USER- 2of 2 votes
AnswersGiven An Array with N integer with values ranging from 1 to N. there is only one duplicate in the Array.
- Geek in United States
Find out Duplicate value.
i.e.
A = { 10,6,3,4,7,5,2,4,9,1}
values from 1 to 10.
in this example, Duplicate element is 4.
N could be quite large.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou do have two linked list L1 and L2. The size of linked lists is huge and in billions. Linked List contains numbers (both negative and positive). For simplicity you can assume they are all integers.
- Geek in United States
You have been given a number say N. now you need to find out all of the pairs where one element from L1 + one element from L2 = N.
i.e.
L1 = 28, -7, 0, 56, 6, -8, 0, 72, 1000, -33
L2 = 53, 20, 27, -52, 99, 14, -8
N = 20
The answer will be:
(28, 8), (-7, 27), (0, 20), (6, 14), (0, 20), (72, -52)
more questions at http://dsalgointerview.wordpress.com/| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm
@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.
@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.
This is how I tried to solve this in C.
- Geek June 22, 2017