A quiz asked by Morgan Stanely

[tao xiao]

Given a single linked list find the middle element by using only 1 for
loop.

Requirement: memory consumption O(1), time complexity: O(n)

[Jeff Huang]

package tapp;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Random;

import org.junit.Test;

/**

 * <ol>

 * <li>MyLinkedList is a facet of {@link List} provide only an one way iterator for 

 * standard {@link List} interface to represent LinkedList concept.

 * <li>This algorithm use two {@link Iterator}s to traverse the LinkedList in only one loop.

 * </ol>

 * 

 */

public class MorganStanelyTest {

// Provide only iterator interface to avoid using convenient methods like

// size(), get(N)

static class MyLinkedList<T> {

final LinkedList<T> provider = new LinkedList<T>();

public MyLinkedList(List<T> provider) {

this.provider.addAll(provider);

}

public Iterator<T> iterator() {

return provider.iterator();

}

public T getRealMidElementForComparing() {

if (provider.isEmpty()) {

return null;

}

return provider.get((provider.size() + 1) / 2 - 1);

}

}

private static final int MAX_ELEMENT = 10;

private MyLinkedList<Integer> setupLinkedList() {

final List<Integer> provider = new ArrayList<Integer>();

final Random random = new Random();

int targetSize = random.nextInt(MAX_ELEMENT);

while (--targetSize >= 0) {

provider.add(random.nextInt());

}

return new MyLinkedList<Integer>(provider);

}

@Test

public void testLinkedList() {

MyLinkedList<Integer> list = setupLinkedList();

Iterator<Integer> iteratorCounter = list.iterator();

Iterator<Integer> iteratorMiddle = list.iterator();

Integer mid = null;

int counter = 0;

while (iteratorCounter.hasNext()) {

++counter;

if (counter % 2 == 1) {

mid = iteratorMiddle.next();

}

iteratorCounter.next();

}

assertEquals(list.getRealMidElementForComparing(), mid);

System.out.println("mid == " + mid);

}

}

[tao xiao]

Unfortunately the solution here is incorrect due to underlying
implementation of linkedlist getsize being one for loop and get
element being another for loop, therefore 2 for loops in this
solution.

Hint no getsize required

[Jeff Huang]

Really? There is only one loop here.

@Test

public void testLinkedList() {

MyLinkedList<Integer> list = setupLinkedList();

Iterator<Integer> iteratorCounter = list.iterator();

Iterator<Integer> iteratorMiddle = list.iterator();

Integer mid = null;

int counter = 0;

while (iteratorCounter.hasNext()) {

++counter;

if (counter % 2 == 1) {

mid = iteratorMiddle.next();

}

iteratorCounter.next();

}

assertEquals(list.getRealMidElementForComparing(), mid);

System.out.println("mid == " + mid);

}

[Seabook]

int mid = list.getSize() / 2.
list.get(mid);

That easy?

Thanks,
Seabook

[tao xiao]

That's right, I missed ur test case.

Bingo!!

[Seabook]

Cant use my way?

[Seabook]

saw ur comment here:

Unfortunately the solution here is incorrect due to underlying
implementation of linkedlist getsize being one for loop and get
element being another for loop, therefore 2 for loops in this
solution.

Use Key's way, wahaha. That's a stupid question and how picky it is.

[Seabook]

One question here. What if a linkedlist contains even elements. For Example, a linkedlist with 4 elements, which one is gonna be the middle one? 2 and 3, However, your problem description is memory consumption is O(1).

Thanks,
Seabook

[Seabook]

How is your Amazon interview, bro?

[Huanwen Qu]

......