Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
I feel space complexity is O(n), is there anyway, we can do better than this with O(n) time complexity?
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.
@ sri : what if the values are greater ..say 1000 ,or greater ..
bit vector would work for numbers until 32 or 64 .....
@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).
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;
}
}
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
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
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;
}
//Duplicate not found
return false;
}
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
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 head;
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();
cur = head;
for (int i = 0; i < index; i++)
{
cur = cur.next;
}
return cur;
}
public void insertToStart(int item)
{
listNode newNode = new listNode();
if (head == null)
{
head = newNode;
tail = head;
head.next = tail;
head.item = item;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
else
{
newNode.item = item;
newNode.next = head;
tail.next = newNode;
head = newNode;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
++size;
}
public void insertToEnd(int item)
{
listNode newNode = new listNode();
if (head == null)
{
head = newNode;
tail = head;
head.next = tail;
head.item = item;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
else
{
tail.next = newNode;
newNode.next = head;
tail = newNode;
newNode.item = item;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
++size;
}
public bool isDuplicate()
{
listNode tmp = head;
bool var = false;
while (tmp.next != head)
{
if (d[tmp.item] == true)
{
var = true;
break;
}
else
{
var = false;
}
tmp = tmp.next;
}
return var;
}
public void traverse()
{
listNode tmp = head;
while (tmp.next != head)
{
Console.WriteLine(tmp.item.ToString());
tmp = tmp.next;
}
}
}
how about !
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 ?
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{
set.add(current.value);
current = current.next;
}
}while(current != start);
return false;
}
/* finding duplicate using hash table */
int find_duplicate(node **head)
{
node *result=*head;
int return_val=0;
int hashtable[50]={NULL}; /* table has to be modified based on the data range */
node *slow=*head;
node *fast=*head;
fast=fast->link->link;
while (fast != slow ) /* assumed the given link list is circular */
{
fast=fast->link->link;
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 */
slow=slow->link;
}
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 */
slow=*head;
while (slow != fast)
{
slow=slow->link;
fast=fast->link;
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 */
}
}
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 A <address, boolean (visited already?)>
HashTable B <value, number that this value has occurred in our traversal>
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;
}
l.add(temp.data);
temp=temp.next;
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
CircularLLDuplicate link=new CircularLLDuplicate();
link.root=new Nodedup(1);
link.root.next=new Nodedup(2);
link.root.next.next=new Nodedup(3);
link.root.next.next.next=new Nodedup(4);
link.root.next.next.next.next=new Nodedup(5);
link.root.next.next.next.next=link.root;
System.out.println(link.FindDup(link.root));
}
}
save first node pointer
- sri December 18, 2012create 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)