T******g
发帖数: 790 | 1 不自己写Node->LinkedList了，直接import java.util.*;?
可以不可以？比如这个切割链表的代码:package chapter2;
import java.util.*;
public class CC2_4{
public static LinkedList partition(LinkedList list,int k){
if(list==null)
return null;
LinkedList less=new LinkedList();
LinkedList noLess=new LinkedList();
for(int i=0;i
if(list.get(i)
less.add(list.get(i));
}else{
noLess.add(list.get(i));
}
}
less.addAll(noLess);
return less;
}
public static void mai... 阅读全帖 |
|
h*****g
发帖数: 944 | 2 执行的时候总说segmentation fault,
谢谢大家指点
===================================
#include
using namespace std;
template< class T>
class ListNode{
public:
T data;
ListNode(T v);
ListNode< T > *next;
};
template ListNode < T >::ListNode(T v)
{
}
template
class LinkedList{
ListNode *head;
public:
LinkedList(){}
~LinkedList(){
while(head){
ListNode* next = head->next;
delete head;
... 阅读全帖 |
|
z***e
发帖数: 5393 | 3 【 以下文字转载自 Java 讨论区 】
发信人: zlike (最终幻想), 信区: Java
标 题: 在java里面无法创建7M个Long type的LinkedList？
发信站: BBS 未名空间站 (Tue May 3 00:14:29 2011, 美东)
我设了
set MAVEN_OPTS=-Xmx4096m
(windows下)
然后在maven里面跑了这么一个test程序：
int N = 100000000;
try {
LinkedList buffer = new LinkedList ();
for(int i=0;i
buffer.add((long)i);
if (i % 1000000 == 0) {
System.out.println("added " + i);... 阅读全帖 |
|
|
B********4
发帖数: 7156 | 5 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？ |
|
|
F****n
发帖数: 3271 | 7 List is a general interface implemented by LinkedList, ArrayList, and Vector.
LinkedList is fast to insert and delete, while ArrayList is fast to access
through index. Evaluate your the major future burden on your List before
choose between the two. Vector is not java1.1 stuff, and it implements List
for back compatibility reason. Java2 programming should avoid Vector as much
as possible. If you want a synchronized List, use
Collections.sychronizedList(List) to pack one. |
|
l***i
发帖数: 168 | 8 如果是很大的object，加入一个ArrayList，是不是在随便什么地方allocate足够的内
存建立这个object，然后把object的一个pointer加入ArrayList。只有当这个pointer
的ArrayList所在的内存不够的时候才会另外找更大的地方，并把整个ArrayList复制过
去再延长。
如果是同样的object，使用LinkedList，是不是不用对这个object额外建立一个
pointer。也是在随便什么地方allocate足够的内存建立这个object，然后把
LinkedList上一个element的next指向这个object就行了。
谢谢。 |
|
d*****o
发帖数: 28 | 9
The head did not initialized in LinkedList class.
the head is null, if you add a node to it like head->next = ...
it will have segment fault error |
|
I*****8
发帖数: 37 | 10 I think circular linked-list is common, just like a single linkedlist, but
the end node's next is not null but head.
For Question 1, My answer is:
First loop from head to next time meeting head, maintain a max and the
references of the start, end points of the sequence.
Then starts from the ending point,loop the linked-list again,maintain two
max value, heading sequence(ending with the start point),tailing sequence(
starting with end point), then use the new sum of three values, and new
start, e... 阅读全帖 |
|
c********t
发帖数: 5706 | 11 最初的解法，travel linkedlist,把每个node都存到hashmap里，如果走到已经放入了
的，则有循环。
这个解法有问题吗？除了空间O(n)比两个指针差外？ |
|
x******a
发帖数: 6336 | 12 只看到定义了linked element的class
linkedlist是不是要另外定义？
template
class ListElement {
public:
ListElement( const T& value):next(NULL), data(value){}
~ListElement(){}
ListElement *getNext() const{ return next;}
const T& value() const (return data;}
//... more member functions
private:
ListElement *next;
T data;
} |
|
s*****n
发帖数: 5488 | 13 写个递归程序或者loop
1. foreach node p
comp value
p->next = p->prev;
if there is a cycle in the ll, you will reach the head node eventually when
there is no search result found.
2. start from here, reverse eveything again to restore the linkedlist. |
|
o******e
发帖数: 1001 | 14 我有一堆数据，比如1，2，3，4，...,10. 我想把这些数据用linkedlist来储存，我该
怎么implement？ |
|
z*******3
发帖数: 13709 | 15 你要做啥？
java把一些基本的数据结构都封装了
你再做这些其实就是背个api的事
linkedlist是双链表，比如reverse这些很容易做
如果对方只是考察你基本功的话
你最好问问，一般不太可能让你用
这就是为啥java程序员面试一般不会问atoi这种东西
直接Integer.parseInt就搞定了 |
|
z*******3
发帖数: 13709 | 16 学会用ide
比如eclipse
然后学会用.这种查方法的方式
这样工作效率会大幅增加
这是工作
如果你想对付面试
楼上说了
看这种实现类的interface
这里就是List有啥方法
然后背List常用的方法就好了
以后不管遇到LinkedList还是ArrayList，接口方法是一致的
可以通用，然后你再记住各个不同的impl里面方法的复杂度
差不多可以了 |
|
y**********a
发帖数: 824 | 17
){
你这复杂度太高，O(n^2)了。 LinkedList 不应该用 get.
要用 iterator 或 listiterator |
|
B********4
发帖数: 7156 | 18 LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n). |
|
B********4
发帖数: 7156 | 19
需要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面
的所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o
(n).
这么解释就说的通。我的新问题是为啥并不包括找到这个点? 在Java里
LinkedList.remove(int index)
要实现这个方法需要两步，第一步找到这个节点，第二步修改前后节点的指针。 |
|
v****p
发帖数: 53 | 20 LinkedList.java was supposed to implement List interface which has 2 methods:
1. listIterator(int index)
2. listIterator()
I checked the source code from Sun, it only has the first method implemented
. How could this happen? |
|
p*****2
发帖数: 21240 | 21 感觉java的linkedlist就是个joke，难用的很。 |
|
B***r
发帖数: 79 | 22 ArrayList doesn't provide push and pop methods for stack as LinkedList |
|
n******1
发帖数: 3756 | 23 java里面的LinkedList应该FIFO？所以addFirst是插到第一个被插入的元素的前面，而
add默认是addLast,iterator也是这个结果
我的问题作为data structure，Linked list本身有规定一定是FIFO或者LIFO吗？ 因为
如果没有明确定义，实现上似乎比较混乱，我在其他的书上是LIFO的，搞的我有点混乱 |
|
w**z
发帖数: 8232 | 24 FIFO是queue, FILO是stack， linkedlist 只有头。 |
|
|
w**z
发帖数: 8232 | 26 double linkedlist has head and tail. can traverse both ways. |
|
f*******n
发帖数: 12623 | 27 Yeah LinkedList is a doubly-linked list. |
|
G****A
发帖数: 4160 | 28 Write a function that moves the largest item on a given linkedlist to be
the final node on the list.
要求head node非dummy node. 怎样写最简单? |
|
g*****g
发帖数: 34805 | 29 Iterator.remove() is an O(1) operation for LinkedList. If you have the
element and you want O(1) operation, you need to write your own double
linked list, which should be trivial enough. |
|
x******a
发帖数: 6336 | 30 ／／main（）
#include
#include
#include "linkedlist.h"
int main()
{
LinkedList myList(5, "luke");
Iterator myIterator=myList.begin();
myList.insert(myIterator, "leia");
myIterator.forward();
myList.erase(myIterator);
myList.insert(myIterator, "chewbca"); 《＝＝＝＝＝＝出问题。
myList[2]="han";
for (int i=0; i
std::cout<
}
myList.insert(myIterator, "chewbca"); 《＝＝＝＝＝＝出问题。
这一句运行起来ta... 阅读全帖 |
|
D***0
发帖数: 138 | 31 网上申请的，回复的挺快，安排了code challenge，一道题，不限时，半个小时写完了
，发过去，第二天收到了thank you but 88.不知道哪里的问题。
* Write a function that takes two parameters:
* (1) a String representing a text document and
* (2) an integer providing the number of items to return.
* Implement the function such that it returns a list of Strings ordered by
word frequency,
* the most frequently occurring word first.
* Use your best judgement to decide how words are separated.
* Your solution should run in O(n) time where n is the number of cha... 阅读全帖 |
|
p*****2
发帖数: 21240 | 32 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 33 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
d**e
发帖数: 6098 | 34 ☆─────────────────────────────────────☆
gezwenti (gezwenti) 于 (Sun Feb 28 12:23:17 2010, 美东) 提到:
( 版主能给几个包子吗？ 我从没得过包子， 说的也都是个人真实体验）
真的。 本人在墙街做IT已经六年多了， 拿的也是很普通的薪水， 我现在的Total是135K + 10-25% Bonus （奖金时好时坏， 大致在10% 到 25% 之间）
我只会Java/J2EE。 不会C++, 一点都不会。
现在的Project是做Post-Trading的Changing P&L, Position Calulation.整个
Department是Support Equity Trading的， 公司也是大家都知道的大投行。
我以前的面试经验， 包括我周围IT朋友的面试经验 从来没被问过本版这么难的问题，
1) B-Tree, Graph 这些都太难了， 从没被问过。 最多就问个Binary Tree, 遍历二叉
树。 红黑树都没问道过， 面试官自己都不知道。
2) 数据结构， 最多就问问... 阅读全帖 |
|
n*******w
发帖数: 687 | 35 bless！
1.写一段程序比较两棵树是否一样。
常见题。
2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
的节点。问如何实现clone函数。
最近版上刚讨论过。先creat big linkedlist然后split。
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
经典算法。两个stack，一个操作数，一个操作符。写代码其实不简单，要定义操作符
的优先级。
4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
经典题。允许O(n)空间，hashtable。否则先sort，一前一后两个指针往中间找。
5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
版上最近刚讨论过。递归或者iterative都有。
6.如何求一个树的mirror（将所有节点的children节点反序排列）.
跟遍历similar。
7.下面这道题目是吃饭的时候问的... 阅读全帖 |
|
i*******6
发帖数: 107 | 36 #5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
扩展了这道题，写成可以自己设置每几个数reverse一下。
思路大概是这样,一个原始链表为
0->1->2->3->4->5->6
如果每3个数反转一下的话，那么先把5指向0,6指向3,2指向null （换言之则是把第kn
个节点指向(k-2)*n+1个节点，再把第n个节点指向null），可以得到
6->3->4->5->0->1->2
然后把整个链表反转就是我们要的结果：
2->1->0->5->4->3->6
附上java代码和数据结构，以及测试用例，在netbeans5.5测试通过：
class ListElement{
public ListElement next;
public int data;
public ListElement(){
}
public ListElement(int data){
th... 阅读全帖 |
|
G******i
发帖数: 5226 | 37 ☆─────────────────────────────────────☆
ctozlm (ctozlm) 于 (Sun Dec 18 00:08:10 2011, 美东) 提到:
电面第二天通知onsite.先说一下对b家的印象。我觉得他家还挺厚道的，hr比较nice，
酒店不错。办公楼和其他大it公司比，小福利一般，但是装修要fancy得多。
深夜两点钟才到宾馆时差没怎么倒就起来去面试了，hr还把时间搞错了。。。就是传说
中的俩小兵。一个三哥，一个白人。说话都很清楚。
btw，之前看他家一般都要考brain teaser.所以特地去quant版准备了一下，然后去
careercup上做他家的brain t。发现他家稍微难点的题都是经典题，其他的基本现想就
能知道答案的。难度在brain t里并不算高，可惜电面和onsite一个都没问。
面试官上来先问了why bloomberg热身？然后就是简历谈research。枉费我讲了大半天
，小印问你这个能用在哪。我给他解释了一下，发现他对kinect的理解还停留在
windows画图的层次就知道白讲了。有说了不同的项目，他俩... 阅读全帖 |
|
z*******3
发帖数: 13709 | 38 这是新的代码
建 route 的时候，不从字典里面找，而是挨个替换字符串的char，换成其他char，组
建成新字符串，然后再去看字典里有没有，有的话，放到set里去，再把set放到map里
，每个pair表示从key string出发，能够转换的点的集合
然后从start开始找，用linkedlist，不用queue，queue是二叉树，效率低，用
linkedlist快，bfs都用linkedlist，先进先出，linkedlist的pollfirst效率高
然后建立一个类，node，这个node记录当前的string，以及上一个string，还有当前
路径长度
然后方法主体，每次把当前string对应的点取出来，然后看能走到那些点，挨个对比这
些点，看是不是end string，如果是，则表示找到，那就记录当前长度，因为还有可能
有相同长度的解，然后继续，如果不是end string，则查找visitedmap，看是否访问过
，如果访问过，比较当前路径长度跟上次访问的长度，如果上次访问的长度更短，则把
set里面这个node给移除，要不然会产生死循环，这里还要避开并发修改的问题，... 阅读全帖 |
|
I*******x
发帖数: 69 | 39 来两个Queue和一个List
一个queue里面装了当前Level的node，从左往右放好的，再一个一个取出来，将他们的
值放进List，
另外一个queue放下一level的node，将当前level取出来的node的left和right放进去，
直到当前level的queue为空，然后将currentQueue ＝ nextQueue;nextQueue ＝ new
LinkedLIst(); list放进最终的List> 里面的第一个。
直接上code：
public List> levelOrderBottom(TreeNode root) {
List> result = new ArrayList>();
if(root == null) return result;
LinkedList cq = new LinkedList();
LinkedList阅读全帖 |
|
y*********e
发帖数: 518 | 40 BST to Doubly Linked List:
public LinkedList convert(BTree tree) {
LinkedList list = new LinkedList();
convert(tree, list);
return list;
}
private void convert(BTree tree, LinkedList list) {
if (tree != null) {
convert(tree.getLeftChild(), list);
LinkedListNode node = new LinkedListNode(tree.getValue());
list.add(node); // append to tail
convert(tree.getRightChild(), list);
}
}
看起来很眼熟把？就是in-order的tree traverse而已。
至于LinkedList的实现。。
public cl |
|
y*********e
发帖数: 518 | 41 Doubly Linked List to Balanced BST:
取LinkedList的中间Node，那就是BST的Root。LinkedList的前半部分，就是BST的Left
Child；后半部分，就是BST的
Right Child。用递归。
public BTree convert(LinkedList list) {
if (list.size() > 0) {
// partition it into three parts: left, middle, right
Partition parts = partition(list);
LinkedList leftList = parts.getLeftSubList();
LinkedList rightList = parts.getRightSubList();
LinkedListNode middle = parts.getMiddle();
BTree root = new BTree( |
|
l*********c
发帖数: 29 | 42 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
福。
1.写一段程序比较两棵树是否一样。
2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
的节点。问如何实现clone函数。
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
6.如何求一个树的mirror（将所有节点的children节点反序排列）.
7.下面这道题目是吃饭的时候问的，题目比较长，大概的意思是,现在亚马逊希望通过
facebook寻找拥有共同爱好的用户，并推荐那些用户所购买的商品给这个用户。如果这
个新用户刚刚通过facebook连接到am... 阅读全帖 |
|
r**d
发帖数: 90 | 43 来自主题: JobHunting版 - 贡献一道题 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
static private bool isWord(string s)
{
switch (s)
{
case "this":
case "is":
case "a":
case "all":
case "some":
case "allsome":
return true;
}
return fal... 阅读全帖 |
|
y**x
发帖数: 67 | 44 official offer 出来了，实在一般。可能我的级别很低吧,entry level，“associate
” SE。有牛人指点一下怎么negotiate啊，是不是太少了？78k + 6280/year bonus +
1000share/4years。不知道这种转正式的software engineer要多久呢？好了，以下面
经，反正也没签什么NDA，我一股脑全贡献出来啦：
第一次onsite screen。不知为何没有phone screen，可能因为我住的近，他们直接叫
我过去了。一个小时一个白哥。问了how to delete a node from binary search tree
。CLRS上直接有解法。白哥答案要求的很笼统，写个psuedo code就pass了。连找
successor node的具体实现都不用写出来。后来又问不用mutex怎么实现share data
between threads。我说GPU里面有一个东西叫thread synchronizer （我master学位做
了些CUDA编程），白哥没理解，说他会用个queue把thread都qu... 阅读全帖 |
|
j**7
发帖数: 143 | 45 public String window(String S, String P) {
HashMap> indexMap = new HashMap<
Character, LinkedList>();
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
LinkedList list = indexMap.get(c);
if (list == null) {
list = new LinkedList();
list.add(i);
indexMap.put(c, list);
} else {
list.add(i);
}... 阅读全帖 |
|
m*******o
发帖数: 264 | 46 Consider the following C++ program declarations for a linked-list class:
class Node {
friend class LinkedList;
int value;
Node* next;
Node() {next = 0;}
}
class LinkedList {
Node* head;
Public:
LinkedList() { head = 0; }
bool addElement(Node * newElement);
...
}
An instance of class LinkedList is to be used to maintain a sorted list.
Write function LinkedList::addElement(Node * newElement) which inserts
newElement into the linked list at the appropriate location and returns
false |
|
z*j
发帖数: 42 | 47 Amazon:
First round:
1. C++ and OO questions
2. Write a linkedlist support append at tail
3. Given a linkedlist, find duplicate elements
4. Given a linkedlist, group by different elements
Second round:
1. C++ and OO questions
2. Reservoir sampling
3. A brain teaser
4. design pattern
Onsite:
OO and C++ questions
Recursion and non-recursion version code. like reverse linkedlist, post-
order traverse a tree, permutation. (I found Amazon likes recursion a
lot. Almost each interviewer asked me about |
|
c********t
发帖数: 5706 | 48 似乎可行，写了个recursion。等牛人写个iteration吧
public LinkedList longestPath(Node root) {
if (root == null)
return new LinkedList();
LinkedList leftPath = longestPath(root.left);
LinkedList rightPath = longestPath(root.right);
if (leftPath.size() >= rightPath.size()) {
leftPath.push(root);
return leftPath;
} else {
rightPath.push(root);
return rightPath;
}
} |
|
c********t
发帖数: 5706 | 49 好像不太行
比如 1,2,3,4,2 这样的循环，结果应该是2,3,4 你用set怎么能把1去掉呢？
我觉得用 linkedlist + hashmap比较好，trace the references into linkedlist,
当current reference已经在hashmap里，把current之前的node都从linkedlist里删掉
就是结果。
不过怎么能去掉duplicate呢？例子中的2,3,4 和 3,4,2是重复的。我觉得还要一个2维
visted flag数组，凡是visited的string就不处理了。
当然最终结果也是多个，返回ArrayList>
be |
|
f*******t
发帖数: 7549 | 50 层序遍历+hashmap解法。动手写+test大概25分钟
public static boolean compareTrees(TreeNode tree1, TreeNode tree2) {
if (tree1 == null && tree2 == null)
return true;
else if (tree1 == null || tree2 == null)
return false;
HashMap map = new HashMap();
LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();
list1.add(tree1);
list2.add(tree2)... 阅读全帖 |
|
