## 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.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

This is how I tried to solve this in C.

- Geek June 22, 2017