## Adobe Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "hashtable.h"

{
return null;

hashtable tbl<int>; //assuming i have a hash table or map

while (cur1)
{
cur1 = cur1->next;
}

while (cur2)
{
int val = 0;
val = tbl.get(&cur2);

if (val == 1) return cur2;
else cur2=cur2->next;
}

return null;
}

I would claim that this has O(max(m,n)) runtime assuming the two lists have m and n elements respectively.

hash table insertion takes O(m) time and second iteration takes O(n) time. Hence, O(m) + O(n) <= O(max(m,n)).

Comment hidden because of low score. Click to expand.
0

A hash table is more overhead than needed. Just extend your linked list structure to hold a flag if you've seen the node before. Then when you get to it again, you'll know you hit a repeat and you're done. Same time complexity (though technically faster), less space given any reasonable implementation of a hash table.

Comment hidden because of low score. Click to expand.
0

To Anonymous,
One issue with your solution is that you are assuming you have the power to modify the node structure.
What if you are given two linked lists and then you are asked to solve this problem? surely you wouldn't suggest copying the original node to your type of node to form a replica of the lists, would you :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont think you need a hashtable. This can be solved using a simple algorithm. Let the 2 lists be listA and listB.

len1 = length_of(listA)
len2 = length_of(listB)

number of common elements = (len1-len2)

now, u can easily find the first common element.

Comment hidden because of low score. Click to expand.
0

no , this is wrong.

Comment hidden because of low score. Click to expand.
0

It's correct.
Diff_num = len1 - len2;
Then, we can use two pointers (P1 and P2). P1 moves forward Diff_num first, then P1 and P2 proceed a step, respectively, and compare the nodes they are pointing. If they are same and not NULL, it is the common node.

Comment hidden because of low score. Click to expand.
0

Great!!!!!!
Looking for the same!!!!!!!!!

Comment hidden because of low score. Click to expand.
0

Don't u think if don't know the length in advance then u need 2 traverse both list 2 find out the length n then start comparing so required time O(m)+O(n)+O(min(m,n) which is not gud!!!!!!!!!

Comment hidden because of low score. Click to expand.
0

that is equal to O(max(m,n) time and O(1) space
that is gud.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Duh!! people.. seriously... this is as horrible a solution as any!! how can so many of you accept it lying down :)
(n)-
-z
(m)-
Both lists end meet and end at 'z'... the number of common elements in this list is 1

len1 = length_of(listA) = n+1
len2 = length_of(listB) = m+1
number of common elements = (len1-len2) = abs(m-n)
This is not always 1!!

Comment hidden because of low score. Click to expand.
0

oops.. i'm sorry... eelschn's solution actually works.. didn't see that before.. sorry for my wisecracks :D

Comment hidden because of low score. Click to expand.
0

Perfect soln

Comment hidden because of low score. Click to expand.
1
of 1 vote

horrible!!!
consider
list1 = a b c d e
list2 = e f g h i
as per the given solution: num of common elements = 5-5=0...but we have e as the common element...
as per someone elses solution th the loop...we need to start P1 by diff i.e. 0 in this case.....and then move P1 and P2 one node at a time....guys...both the solutions are hopeless....

Comment hidden because of low score. Click to expand.
0
of 0 vote

if they are not, increment the head pointer that was previously not incremented or the pointer that is BEHIND.

Comment hidden because of low score. Click to expand.
0
of 0 vote

steps:

1) create a dummy node

2)start traversing from both the heads simultaneously

3)As you traverse, make the next pointer of each node point to the dummy node.

4) if the next pointer of a node is already pointing to the dummy, then we have found the beginning of the common sequence

NOTE: This spoils the whole linked list though.

Comment hidden because of low score. Click to expand.
0

hmm. not exactly sure what you mean. i think this problem fails in all cases if you try to traverse incrementally from both lists because the lists might have different lengths up to the joining part. my solution works, but is there one without external mememory required?

Comment hidden because of low score. Click to expand.
0

yes using constant memory it can be done.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nunbit's solution is the only one I can think of too

Comment hidden because of low score. Click to expand.
0
of 0 vote

giving an example of my solution

INITIAL;
a-b-c-d-
-g-h-i
x-y-z

STEP 1:
Move pointers from 'a' and 'x' to 'b' and 'y'.
Make 'a' and 'x' point to a dummy variable say DUMMY

a-
DUMMY
x-
b-c-d-
g-h-i
y-

STEP 2:
Check if 'b' or 'y' point to DUMMY. Since they don't, follow the same step as before
Move pointers from 'b' and 'y' to 'c' and 'g'.
Make 'b' and 'y' point to DUMMY

a-
b-
- DUMMY
x-
y-

c-d-
- g-h-i

STEP 3:

Check if 'c' or 'g' point to DUMMY. Since they don't, follow the same step as before
Move pointers from 'c' and 'g' to 'd' and 'h'.
Make 'c' and 'g' point to DUMMY

a-
b-
c-
- DUMMY
x-
y-
g-

STEP 4:

Check if 'd' or 'h' point to DUMMY. Since they don't, follow the same step as before
Move pointers from 'd' and 'h' to 'g' and 'i'.
Make 'd' and 'h' point to DUMMY

a-
b-
c-
d-
- DUMMY
x-
y-
g-
h-

STEP 5:
Check if 'g' or 'i' point to DUMMY. 'g' DOES POINT TO DUMMY. SO 'g' is the beginning of the common path!!!!!!!

report 'g'

NOTE: You can do this without using the extra memory by pointing the first list elements to the head of the second list and the second list to the first. That assumes there is no LOOP in the lists.

Hope iam clear!! :)

Cya
Ved.

Comment hidden because of low score. Click to expand.
0

how can you check if a node pointed to dummy? you still need to use Hashtable here

Comment hidden because of low score. Click to expand.
0

Hey Ved...
As you said.. it wrecks up the list... when you are through every node (till the point you got the hit) will point to dummy...
What you are trying to do is colour/mark each node as u see it.. so that next time someone see it they know that it was seen before (hence that must be the common node)...
The first solution (hash table) is another flavour of the same strategy, though a much more cleaner and apt one :)..
So I really wonder why you even proposed it :)

Comment hidden because of low score. Click to expand.
0

wont work when list 1 is very big than list two...list two will get finished while one wont even reach the common node
eg
a-s-d-f-g-h-j-k-l-z-x-c
b-n-x-c

a,s,d,f point to dummy and bnxc also.....

Comment hidden because of low score. Click to expand.
0
of 0 vote

When they are equal, that is the first common node.

Comment hidden because of low score. Click to expand.
0
of 0 vote

unfortunately the sizes of the list may not be equal :(

Comment hidden because of low score. Click to expand.
0
of 0 vote

Doesn't the 2nd post solve the question correctly!!!
I dont seem to agree with the rest of the posts.

Comment hidden because of low score. Click to expand.
0

Nope!! only the first one solves it

Comment hidden because of low score. Click to expand.
0
of 0 vote

What if we have duplicates in the list?

Comment hidden because of low score. Click to expand.
0
of 0 vote

well first get the length of each of the link list lets say.
length of the first list = M
-------------second list = N

Diff = M-N

now move M nodes beforehand in the longer list.
then start moving the pointers in both the list when the two
pointers are equal u get the common node.
hope this is clear.

Comment hidden because of low score. Click to expand.
0

Exactaly

Comment hidden because of low score. Click to expand.
0
of 0 vote

if no memory overhead required then solution by aditya is best otherwise solution posted by anonymous in post 2 is best in time complexity,although Ved is also trying to do the same thing indirectly but the whole list gets disrupted, logically his algo is also correct.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The proposed solution if fine except one case, If the length of the tail is very-very long. In this case you cannot calculate length of lists it will be waste of time. You should come with another, more time consider solution that has time complicity of 0(length of head1 + length of head2).

Comment hidden because of low score. Click to expand.
0

u can see the solution posted by anonymous in post 2.

Comment hidden because of low score. Click to expand.
0
of 0 vote

how wud u maintain the flag node wise... i think u need a hashtable for that... so post 1 is absolutely correct.. both of u r saying the same thing

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey Ravikant...did u appear for interview at adobe. If yes, pls let us all know the questions.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys...
If we take difference of lenth of the 2 lists (m-n)
and just skip first (m-n) nodes of the longer list .. as we can b sure they wont b the common part.
On reaching (m-n+1) node of longer list, we are left with 2 lists of size n where last few nodes are common. Then just compare node 1-o-1 till u reach the common portion
this is O(m - length of common portion).

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
return NULL ;
if ( l > 0 )
while ( l > 0 )
{
cur1 = cur1->next ;
--l;
}
else if ( l < 0 )
while ( l < 0 )
{
cur2 = cur2->next ;
l++ ;
}
while ( cur1!= cur2 )
{
cur1->next ;
cur2->next ;
}
// now cur1 and cur2 are pointing to the same element
// print or return the node
cout << cur1->data ;
return cur1 ;
}

int length( node *node )
{
int count = 0 ;
while ( node != NULL )
{
count++ ;
node= node->next ;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach would be

function FindFirstCommonElement()

len 1 = length of first linked list (traverse it all the way to find it)
len 2 = length of second linked list (traverse it all the way to find it)

diff = len1 - len2 (absolute difference of their lengths)

if (diff >= 0)
{
for i = 1 to diff{
}
}else{
for i = 1 to |diff|{
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have another solution, reverse the two lists, use two pointers to traverse both lists, the first k nodes should be of the same value so one pointer should point to a value that is the same as the second pointer, keep moving the pointers until two pointers meet different values.

Comment hidden because of low score. Click to expand.
0

I like Wie solution. Its damn cool.
Reversing the lists would take O(m + n). And then another O(Diff) time to look at the first common nodes. So total would be O(m + n).

Comment hidden because of low score. Click to expand.
0

Can reversing the two lists solve this problem?

a-b-c-d-e-f-g-h-i
x-y-z-w-g-h-i

After reversing the first list:

i-h-g-f-e-d-c-b-a (g now points to f instead of h which changes the second list)
x-y-z-w-g-f-e-d-c-b-a

After reversing the second list:

i-h-g-w-z-y-x
a-b-c-d-e-f-g-w-z-y-x (g now points to w instead of f which changes the first list)

You are now left with a problem similar to the original problem with g-w-z-y-x as the common nodes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think Aditya's solution is good

Comment hidden because of low score. Click to expand.
0
of 0 vote

does this mean that the 2 lists are sorted???

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is simple math problem:
a-b-c-d-e-f-
g-h-i
x-y-z-w-

a to f: x number of nodes
x to z: y number of nodes
g to i: z number of nodes
len(1) = x+z
len(2) = y+z
reverse list from a or x, you will pass x+y nodes.
so you know what is z.
Call me genuis

Comment hidden because of low score. Click to expand.
0

how can I pass x + y when reversing the list? can you explain more?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't really understand how some folks to reverse the linked list, with my limited understanding, two linked list could be sth. like this:

a-b-c-d-e-f-
g-h-i
x-y-z-w-

BUT can never be:

-a-b-c-d-e-f-
g-h-i
-x-y-z-w-

HOW can a node has two pointers to next ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Reversing two lists is good solution.

1. Reverse List A need O(n)
2. reverse List B need O(m)
3. from new heads (old 'tail'), set two pointers to traverse the two lists, when we found they point to diff node, we can know where the diff begins.

Total cost: O(m) + O(n) + "O(0)~O[min(m,n)]"

But I thing I'm still not sure: If we reverse List A first in place, will this operation break the List B since one node can't has two pointers to the next ? could anybody explain what exactly happen when reverse joint Linked List in this case ?

Comment hidden because of low score. Click to expand.
0

<--- a --->X<--- b --->
|
c
|
|
X is common node.
a + b = L1 (length of list 1)
c + b = L2 (length of list 2)

Reverse List 1 and traverse list 2 again.
You will get c + a = L3 (length of new list 2)

We have three equations and three unknowns (a,b,c).
Find value of 'a'. and traverse List 1 for 'a' number of nodes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

i dont understand why so many ppl are cramming over some simple query...
first 2 soln are cool....and rest crap...
the concept of reversing the two list is complete bulshit...we can'nt have a node pointing to two things at a time...and David pointed it out correctly....guys plz dont waste others valuable time by posting crappy materials ....plz avoid that...if u dont know just watch what others have to say on that instead of disturbing the flow....

Comment hidden because of low score. Click to expand.
0

subrtacrt l1-l2 lenths;

say its 3;
now start from 4th node of l1 and first node of l2; keep comparing....

Comment hidden because of low score. Click to expand.
0
of 0 vote

hi,guys, the followings are my solution, which takes O(n)(n>m) time. The idea is that we compare the value of element from the end of the lists. Instead of reverse the list, we can use recursion to get the solution. The following are the code, comments are welcome.

int commonlinkedList(list* l1, list* l2) {
static int comVal;
if (l1 == NULL && l2 == NULL)
return comVal;
else {
if (l1 == NULL)
else if (l2 == NULL) {
}
else {
}
if (l1->val == l2->val)
comVal = l1->val;
}
return comVal;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is a question which needs to be answered as .....DEPENDS ON THE SIZE OF LIST A AND B
case 1:
if (m-n) is small then traversing both and subtracting the m-n and using 2 pointers method works

case 2:
if one of m/n is very small then other
make a hashmap of smaller list and traverse the bigger and keep checking if the given node is being duplicated...

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is a question which needs to be answered as .....DEPENDS ON THE SIZE OF LIST A AND B
case 1:
if (m-n) is small then traversing both and subtracting the m-n and using 2 pointers method works

case 2:
if one of m/n is very small then other
make a hashmap of smaller list and traverse the bigger and keep checking if the given node is being duplicated...

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.