Interview Question

Interview(Student Candidate) Bangalore (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)

Interview Answer

3 Answers


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

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

gurjas on Aug 5, 2014

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.