Expedia

  www.expedia.com
Work in HR? Unlock Free Profile

Expedia Software Developer Intern Interview Question

I interviewed in Bellevue, WA and was asked:
"Give me 5 different ways of finding the median (middle element) of a linked list. For the sake of simplicity, assume the list has odd number of ints. Also mention the runtime for each. Follow up: What's the fastest way you could find the median? What is the runtime? Oh.. and yes, code your answer(s) in any language of your preference."
Tags: technical, data structures, algorithm, coding
Add Tags [?]
Answer

Part of a Software Developer Intern Interview Review - one of 283 Expedia Interview Reviews

Answers & Comments

1
of 1
vote
Hint: think of different data structures you could use here
- Interview Candidate on Aug 27, 2012
0
of 0
votes
function Node(data){
    this.data=data;
    this.next=null;
}
function LinkedList(){
    this.head=null;
    this.add=function(node){
        node.next=this.head;
        this.head=node;
    }
}
var myList = new LinkedList();
for(var i=0;i<9;i++)
    myList.add(new Node(Math.random()));

var tmp = [];

var cur=myList.head
while(cur){
    if(cur) tmp.push(cur)
    cur=cur.next;
}
console.log(tmp[Math.ceil(tmp.length/2)].data)
- grim face on Sep 7, 2012
0
of 0
votes
function Node(data){
    this.data=data;
    this.next=null;
}
function LinkedList(){
    this.head=null;
    this.add=function(node){
        node.next=this.head;
        this.head=node;
    }
}
var myList = new LinkedList();
for(var i=0;i<9;i++)
    myList.add(new Node(i));

var cur=myList.head
var half=myList.head
var i=0;
while(cur){
    if(i%2) half = half.next;
    cur=cur.next;
    i++;
}
console.log(half);
- grim face on Sep 7, 2012

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

Tags are like keywords that help categorize interview questions that have something in common.