## Amazon Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

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

save first node pointer
create an empty set
while next node is not the first node
check if the node value is already present in the set
if present, current value is a duplicate
else add node value to a set and go to next node

O(n)

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

I feel space complexity is O(n), is there anyway, we can do better than this with O(n) time complexity?

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

Considering the problem statement that node values are int, bit vector (with each bit position representing an int value) can be used instead of set or hash table. turn on bits while traversing through list nodes and check if each bit was already turned on.

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

it will stop when there is the duplicate value of the first node.

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

@ sri : what if the values are greater ..say 1000 ,or greater ..
bit vector would work for numbers until 32 or 64 .....

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

its o(n^2) , for each value u have to search that it is present in set or not .

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

@Anonymous
No, Set can be implemented using a hash table. Think of Java's HashSet, for which each lookup is O(1). Ergo, N lookups would cost O(N).

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

How will you implement a set in c?

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

``````boolean containsDups(Node slist){

Node curr = slist;
HashSet<Integer> set = new HashSet<Integer>();
do{

if(set.contains(curr.value))
return true;
else {
}
curr = curr.next;
} while(curr != slist);

return false;
}``````

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

Use a slow and fast pointer to detect the loop. When loop is detected replace the fast pointer with the start and increment both until they meet, i.e., the start of the loop. Check for duplicates in using the value of slow pointer. Running time O(n)

``````package datastructure;

import java.util.HashMap;

public class CircularDuplicate {
public static boolean isDuplicate(SNode s) throws Exception{
HashMap<Integer, Boolean> table= new HashMap<Integer, Boolean>();
SNode fast=s;
SNode slow=s;
if(fast.next==null)
throw new Exception("not circular");
fast=fast.next.next;
table.put(slow.v, true);
slow=slow.next;
while(fast!=slow){
if(fast==null || fast.next==null)
throw new Exception("not circular");
fast=fast.next.next;
if(table.get(slow.v)!=null)
return true;
else
table.put(slow.v, true);
slow=slow.next;
}
fast=s;
while(fast!=slow){
if(table.get(slow.v)!=null)
return true;
else
table.put(slow.v, true);
slow=slow.next;
fast=fast.next;
}
return false;
}
public static void main(String[] args) throws Exception{
SNode s= new SNode(1);
s.next=new SNode(2);
s.next.next=new SNode(3);
s.next.next.next=new SNode(4);
s.next.next.next.next=new SNode(5);
s.next.next.next.next.next=new SNode(1);
s.next.next.next.next.next.next=new SNode(7);
s.next.next.next.next.next.next.next=s.next.next;
System.out.print(isDuplicate(s));
}
}
class SNode{
public SNode next;
public int v;
public SNode(int v){
this.v=v;
}
}``````

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

I think that the problem is not related to the detection of loops in a linked list. Rather, it is a circular list and so it warps the start and end nodes with a loop.
We can detect the point to stop as : slist->nxt_pointer = slist;

while(slist->next_pointer != slist) {
}// out of the loop whenever completed one full traversal of the list

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

Sorry..it will be:

list *curr = slist;
while(curr != slist) {
// do processing
curr = curr->nxt_pointer;
}// out of the loop whenever completed one full traversal of the list

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

Yes. U r right if your circle start at the first node.

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

@BoredCoder: small correction in ur pseudo code. the first line should be:
list *curr = slist->next;

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

We can calculate the length of the circular list in O(n) time. Then do a O(n^2) comparision to check for duplicates. Here's my code for it :

bool hasDuplicates(node* slist){
node* start = slist;
node* n = slist;
node* m;
int len = 0;

//Calculate the length
if(n != NULL)
count++;

//Calculate the length

while(n->next != start){
count++;
n = n->next;
}

n = slist;
m = slist;

// check if some dupliacte is present
for( int i = 0 ; i < count ; i++){
m = n;
for( int j = i + 1; j < count ; j++){
m = m->next;
if( m->val == n->val)
return true;
}
n = n->next;
}

return false;
}

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

is there a better way to do this? with better time complexity?

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

if the data in the linked is within limited range ..then we can optimise search ...by using Hash.........in O(1) time ....

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

traverse the link list and keep the value in a hash table
while inserting the value in hash if it is found that the value is already in the list then it is the duplicate

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

Can you provide a code snippet that how you make a hash table with this data ?

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

traverse the link list and keep the value in a hash table
while inserting the value in hash if it is found that the value is already in the list then it is the duplicate

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

add linked list items into dictionary and then traverse and find duplicates. Here is c# code

class Program
{
static void Main(string[] args)
{
CircularList cl = new CircularList();
cl.insertToStart(0);
cl.insertToStart(1);
cl.insertToStart(2);
cl.insertToStart(3);
cl.insertToStart(4);
cl.insertToStart(4);
cl.insertToStart(4);
cl.insertToStart(5);
cl.traverse();
Console.WriteLine(cl.isDuplicate().ToString());
}
}

class CircularList
{
Dictionary<int, bool> d = new Dictionary<int, bool>();

private listNode tail;
private int size = 0;

private class listNode
{
public int item;
public listNode next;
}

private listNode find(int index)
{
listNode cur = new listNode();
for (int i = 0; i < index; i++)
{
cur = cur.next;
}
return cur;
}

public void insertToStart(int item)
{
listNode newNode = new listNode();
{
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
}
}
else
{
newNode.item = item;
tail.next = newNode;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
}
}
++size;
}

public void insertToEnd(int item)
{
listNode newNode = new listNode();
{
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
}
}
else
{
tail.next = newNode;
tail = newNode;
newNode.item = item;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
}
}
++size;
}

public bool isDuplicate()
{
bool var = false;
{
if (d[tmp.item] == true)
{
var = true;
break;
}
else
{
var = false;
}
tmp = tmp.next;
}
return var;
}

public void traverse()
{
{
Console.WriteLine(tmp.item.ToString());
tmp = tmp.next;
}
}
}

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

do merge sort on list (by fixing start and end pointer)
then scan once , compare with neighbour node if equal return true
no space required.
time complexity nlog n+ 0(n) = 0 (nlog n)

any thought ?

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

Is it possible to do a merge sort on List.. i dont think so.. Merge sort is possible only in arrays

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

Possible solution:
Time complexity: worst case: (n)
Space complexity: worst case: (n)

Input Data structure: Singly linked list.

``````class Node{
Integer value;
Node next;
}
boolean hasDuplicates(Node start){
HashSet<Integer> set = new HashSet<Integer>();
Node current = start;
do{
if(set.contains(current.value)){
return true;
}else{
current = current.next;
}
}while(current != start);

return false;
}``````

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

/* finding duplicate using hash table */

{
int return_val=0;
int hashtable={NULL}; /* table has to be modified based on the data range */
while (fast != slow ) /* assumed the given link list is circular */
{
if(hashtable[slow->data]==0)
hashtable[slow->data]=true;
else if(hashtable[slow->data] >= 1)
{
return return_val=1; /* found duplicate */
} /* objective was just to print true incase duplicate found */

}
if(fast==slow) /* its used to find the start of the circle */
{ /* when the slow reaches the circle, the fast would also
do a roatation so we can make sure that we check for duplicate */
while (slow != fast)
{
if(hashtable[fast->data]==0)
hashtable[fast->data]=true;
else if(hashtable[fast->data] >= 1)
{
return return_val=1; /* found duplicate */
}

}
return 0; /* no duplicate */ /* it also means that we traversed the entire link list now */
}

}

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

2 hash tables. 1 keeps track of Node addresses and the other keeps track of the number of duplicates of a certain value.

O(n) time complexity and O(2n) space complexity-

HashTable B <value, number that this value has occurred in our traversal>

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

This is my java code using arraylist. But using hashset would have a lesser time complexity.

``````class Nodedup{
Nodedup next;
int data;
Nodedup(int x){
data=x;
}
}
public class CircularLLDuplicate {

Nodedup root;
ArrayList<Integer> l=new ArrayList<Integer>();
boolean FindDup(Nodedup r){
Nodedup temp=r.next, start=r;
while(temp!=start){

if(l.contains(temp.data)){

return false;
}
temp=temp.next;
}

return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub

}

}``````

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.