j*****s
发帖数: 189 | 1 真的很不爽啊，本来还信心满满的打算好好面，可是我的primary language是c++啊，
非要我写java中的一个collection的东西，还说如果觉得不方便可以用自己习惯的语言
写，可是我连collection有哪些具体的操作都不知道啊。
完了之后三哥说既然不熟就换个问题吧，要实现个blcokingQueue,我不太明白怎么个
blocking法，三哥给我解释，可是三哥的英语我是真的听不懂啊。哎，整的彻底没心情
了。
顺便求助下第一题，有人知道怎么做么？
以下是例子和接口
Example: input: ((1, 3, 5),(4, 7, 3),((2, 3), 4))
1, 3, 5, 4, 7, 3, 2, 3, 4
public class DeepIteratorImpl implements Iterator {
// Constructor
public DeepIteratorImpl (Collection> c) {
// Implementation here
}
public T next() {
// Implementation here
}
public boolean hasNext() {
// Implementation here
}
}
public interface Data {
// Does this Data hold a collection?
public boolean isCollection();
// Returns the collection contained by this Data, or null if it is a
single element
public Collection> getCollection();
// Returns the single element contained by this Data, or null if it is a
collection
public T getElement();
} | A*****i
发帖数: 3587 | 2 blockingQ应该就是thread safe的Q
这个用同步就可以了 | j*****s
发帖数: 189 | 3 嗯，之前没接触过，基本上彻底听不懂三哥说什么，加上第一道题的影响，彻底没心情
了。
【在 A*****i 的大作中提到】
: blockingQ应该就是thread safe的Q
: 这个用同步就可以了
| p*****2
发帖数: 21240 | 4
正常呀。L就是这样。上次我用C面，出的题目C根本没法做，只能临时改C#了，但是C#
我也不熟呀。
【在 j*****s 的大作中提到】
: 真的很不爽啊，本来还信心满满的打算好好面，可是我的primary language是c++啊，
: 非要我写java中的一个collection的东西，还说如果觉得不方便可以用自己习惯的语言
: 写，可是我连collection有哪些具体的操作都不知道啊。
: 完了之后三哥说既然不熟就换个问题吧，要实现个blcokingQueue,我不太明白怎么个
: blocking法，三哥给我解释，可是三哥的英语我是真的听不懂啊。哎，整的彻底没心情
: 了。
: 顺便求助下第一题，有人知道怎么做么？
: 以下是例子和接口
: Example: input: ((1, 3, 5),(4, 7, 3),((2, 3), 4))
: 1, 3, 5, 4, 7, 3, 2, 3, 4
| j*****s
发帖数: 189 | 5 他们怎么想的啊……
顺便求助第一题
【在 p*****2 的大作中提到】
:
: 正常呀。L就是这样。上次我用C面，出的题目C根本没法做，只能临时改C#了，但是C#
: 我也不熟呀。
| p*****2
发帖数: 21240 | 6
他家很看中相关背景的。你那题是道老题，G家经常问。
【在 j*****s 的大作中提到】
: 他们怎么想的啊……
: 顺便求助第一题
| j*****s
发帖数: 189 | 7 那怎么做啊，我还是没思路。
【在 p*****2 的大作中提到】
:
: 他家很看中相关背景的。你那题是道老题，G家经常问。
| b*******l
发帖数: 590 | 8 虽然我c#天天用，可是突然让我离开Visual Studio默写语法，我也肯定没戏。 | j*****s
发帖数: 189 | 9 好吧，第一题你有思路么？
【在 b*******l 的大作中提到】
: 虽然我c#天天用，可是突然让我离开Visual Studio默写语法，我也肯定没戏。
| l*******b
发帖数: 2586 | 10 tree一样的结构？用一个stack of iterators来写？
不太明白，iterator 和 collection的实现应该有关呀。看例子没给 flat container
的iterator
【在 j*****s 的大作中提到】
: 好吧，第一题你有思路么？
| r****i
发帖数: 528 | 11 试着解第一题：
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class DeepIteratorImpl implements Iterator {
//use a flat list to store all elements
private int currIndex;
private ArrayList flatC;
// Constructor
public DeepIteratorImpl (Collection> c) {
currIndex=-1;
flatC=new ArrayList();
getElement(c, flatC);
}
//get all the elements from the collection
private void getElement(Collection> c, ArrayList flatC)
{
for(Data item : c)
{
if(item.isCollection())
{
getElement(item.getCollection(), flatC);
}
else
{
flatC.add(item.getElement());
}
}
}
public T next() {
if(null==flatC)
return null;
T t=flatC.get(currIndex);
currIndex++;
return t;
}
public boolean hasNext() {
return null!=flatC&&flatC.size()>0&&currIndex
}
}
第二题：
import java.util.LinkedList;
public class BlockingQueue {
private LinkedList list;
private int limit;
public BlockingQueue(int limit)
{
this.limit=limit;
list=new LinkedList();
}
public synchronized void put(T t) throws InterruptedException
{
if(list.size()==limit)
{
list.wait();
}
list.add(t);
list.notifyAll();
}
public synchronized T get() throws InterruptedException
{
if(list.size()==0)
{
list.wait();
}
T t=list.pop();
list.notifyAll();
return t;
}
}
他们家刚把俺锯掉，算法题没见过不熟悉的话短时间很难一下写出来bug free | c*****u
发帖数: 562 | 12 第一题：java.lang.ArrayIndexOutOfBoundsException: -1
T t=flatC.get(currIndex);
用的是楼主提供的testcase
https://dl.dropbox.com/u/7472691/mitbbs/DeepIteratorImplTester.java
也贴个我的第一题吧：
public class DeepIteratorImpl implements Iterator {
private Map> deepIterators;
private Map singleElements;
private int index;
private int maxIndex;
// Constructor
public DeepIteratorImpl(Collection> c) {
if (c == null) {
throw new IllegalArgumentException("Invalid input
Collection of Data");
}
this.deepIterators = new HashMap
>>();
this.singleElements = new HashMap();
int index = 0;
for (Data data : c) {
if (data.isCollection()) {
this.deepIterators.put(index++, new
DeepIteratorImpl(data.getCollection()));
} else {
this.singleElements.put(index++, data.
getElement());
}
}
this.maxIndex = c.size() - 1;
this.index = 0;
}
public T next() {
if (!this.hasNext()) {
return null;
}
if (this.singleElements.containsKey(this.index)) {
return this.singleElements.get(this.index++);
} else {
DeepIteratorImpl iter = this.deepIterators.get(
this.index);
T t = iter.next();
if (!iter.hasNext()) {
this.index++;
}
return t;
}
}
public boolean hasNext() {
if (this.maxIndex < 0 || this.index > this.maxIndex) {
return false;
} else if (this.index == this.maxIndex) {
if (this.deepIterators.containsKey(this.index)) {
return this.deepIterators.get(this.index).
hasNext();
} else {
return true;
}
}
if (this.index < this.maxIndex) {
return true;
}
return false;
}
public void remove() {
throw new IllegalStateException("Not implemented");
}
}
【在 r****i 的大作中提到】
: 试着解第一题：
: import java.util.ArrayList;
: import java.util.Collection;
: import java.util.Iterator;
: public class DeepIteratorImpl implements Iterator {
: //use a flat list to store all elements
: private int currIndex;
: private ArrayList flatC;
: // Constructor
: public DeepIteratorImpl (Collection> c) {
| c*****u
发帖数: 562 | 13 顺着楼上的思路解一题：
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
public class DeepIteratorImpl2 {
private int cursor;
private List elements;
// Constructor
public DeepIteratorImpl2(Collection> c) {
if (c == null) {
throw new IllegalArgumentException("Invalid input
Collection of Data");
}
this.cursor = 0;
this.elements = new ArrayList();
this.getElements(c, this.elements);
}
// get all the elements from the collection
private void getElements(Collection> c, List elements) {
for (Data data : c) {
this.getElements(data, elements);
}
}
// get all the elements from one data
private void getElements(Data data, List elements) {
if (data.isCollection()) {
for (Data itemData : data.getCollection()) {
this.getElements(itemData, elements);
}
} else {
elements.add(data.getElement());
}
}
public T next() {
if (this.hasNext()) {
return this.elements.get(this.cursor++);
}
return null;
}
public boolean hasNext() {
return this.cursor < this.elements.size();
}
}
【在 r****i 的大作中提到】
: 试着解第一题：
: import java.util.ArrayList;
: import java.util.Collection;
: import java.util.Iterator;
: public class DeepIteratorImpl implements Iterator {
: //use a flat list to store all elements
: private int currIndex;
: private ArrayList flatC;
: // Constructor
: public DeepIteratorImpl (Collection> c) {
|
|
