McAfee Interview Question: Design a data structure where... | Glassdoor

McAfee

## Interview Question

Software Development Engineer Interview(Student Candidate) Bengaluru (India)

# Design a data structure where insertion, deletion, data

access and get random element are all done in O(1), i.e., constant time. (Without using STL or Hash tables)

1

I suggested a solution using hash tables, but the interviewer said that was an expected answer and too obvious a solution. I still haven't found an alternative answer.

Interview Candidate on Feb 21, 2013
0

we should use a queue...its complexity is big o(1).

gurjas on Aug 5, 2014
0

public class Practice{
static int[][] a=new int[10][10];
static int maxIndex=-1;
public static void main(String[] args){
insert(20);insert(12);insert(17);insert(20);insert(12);insert(17);
delete(5);
System.out.println(getData(5));
System.out.println(randE());
}
static void insert(int data){
++maxIndex;
a[maxIndex][0]=maxIndex;
a[maxIndex][1]=data;
}
static void delete(int idx){
a[idx-1][0]=a[maxIndex][0];
a[idx-1][1]=a[maxIndex][1];
--maxIndex;
}
static int getData(int idx){
return a[idx-1][1];
}
static int randE(){int k=new java.util.Random().nextInt(maxIndex);return a[k][1];}
}

A 2D array data Structure... Check..

Santanu Naskar on Aug 6, 2014