Interview Question

Software Development Engineer 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)
Answer

Interview Answer

3 Answers

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

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up