Expedia Interview Question: Give me 5 different ways of f... | Glassdoor

Interview Question

Software Developer Intern Interview Bellevue, WA

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
Answer

Interview Answer

4 Answers

3

Hint: think of different data structures you could use here

Interview Candidate on Aug 27, 2012
0

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

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
0

public int findLinkedListMedian() {
        Link fastLink = head, slowLink = head;

        while(fastLink != null) {

            fastLink = fastLink.next;
            fastLink = fastLink.next;
            slowLink = slowLink.next;
        }
        return slowLink.key;
    }

Anonymous on Feb 4, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.