Interview(8)Dictionary and Tree
Dictionary - No Order
public class DictionaryDLNode implements Dictionary {
private List list; //store all items
private EqualityTester tester;
public DictionaryDLNode(){
this(new EqualityTesterDefault());
}
public DictionaryDLNode(EqualityTester t){
list = new ListDLNode(); tester = t;
}
public int getSize() { return list.getSize(); }
public boolean isEmpty() { return list.isEmpty(); }
public Entry find(Object key){
Iterator p = list.positions();
while(p.hasNext()){
Position pos = (Position) p.getNext();
Entry entry = (EntryDefault) pos.getElem();
if(tester.isEqualTo(entry.getKey(), key)){
return entry;
}
}
}
public Iterator findAll(Object key){
List list = new ListDLNode();
Iterator p = l.positions();
while(p.hasNext()){
Position pos = (Position)p.getNext();
Entry entry = (EntryDefault) pos.getElem();
if(tester.isEqualTo(entry.getKey(), key)){
list.insertLast(entry);
}
}
return new IteratorElement(list);
}
public Entry insert(Object key, Object value){
Entry entry = new EntryDefault(key, value); //create new Entry
list.insertFirst(entry);
return entry;
}
public Entry remove(Object key){
Iterator p = list.positions();
while(p.hasNext()){
Position pos = (Position) p.getNext();
Entry entry = (EntryDefault) pos.getElem();
if(tester.isEqualTo(entry.getKey()), key){
Entry oldEntry = entry;
list.remove(pos); //remove item
return oldEntry;
}
}
return null;
}
public Iterator entries() { return new IteratorElement(list); }
}
Dictionary - Order
Binary Search
Method: binSearch(S, low, high, key)
Inputs: search table S, low and high, Key
Outputs: s[low.. high], find the item for key
binSearch(S, 0, n-1, key)
{
if low > high, system can not find it
middle = (low + high) /2;
if key > S[middle].key, binSearch(S, middle+1, high, key);
if key < S[middle].key, binSearch(S, low, middle-1, key);
return middle; //hit the right item
}
Binary Search Tree
left tree should be lower than current parent key, right tree should be higher than current parent key.
AVL Tree
B Tree - TODO
Sorting
References:
分享到:
相关推荐
Tree Serialization, Finding the Top k Elements of Data Streams, MapReduce, Partial Sorting, the Skyline Problem, DFS, BFS and Topological Sorting of Dags, the Alternative Alphabet and the Phone Words...
1. Java语言特性:包括面向对象编程的基本概念,封装、继承、多态的理解与应用,以及Java8及以后的新特性,如Lambda表达式、Stream API等。 2. 数据类型与变量:深入理解基本数据类型与引用数据类型,以及变量的作用...
A collection of Data Science Interview Questions Solved in Python and Spark: BigData and Machine Learning in Python and Spark
从国外网站上下载的Java面试题。可以看看国外公司的Java面试常用题,以及如何用英文回答。
根据提供的文件信息,本文将对其中涉及的C++面试题目进行详细解析,并提供相应的答案,旨在帮助准备参加C++职位面试的求职者更好地理解和掌握相关的技术要点。 ### 1. C++基础知识 #### 1.1 什么是C++?...
150 programming interview questions and solutions Plus: Five proven approaches to solving tough algorithm questions Ten mistakes candidates make -- and how to avoid them Steps to prepare for ...
Learn about Enterprise Architects IT strategy and NFR – this book provides you with methodologies, best practices, and frameworks to ace your interview A holistic view of key architectural skills and...
The book is over 500 pages and includes 150 programming interview questions and answers, as well as other advice. The full list of topics are as follows: The Interview Process This section offers ...
根据提供的文件信息,我们可以从中提炼出三个重要的面试问题及其回答策略。这不仅是对求职者面试技巧的考验,也是展示个人专业素养与职业态度的关键时刻。接下来,我们将详细解析这三个问题及如何给出恰当的回答。...
The Ultimate Reference & Learning Guide for SAP MM/PP Consultants SAP PP Interview Questions, Answers, and Explanations! It's clear that Production Planning is a key specialization for SAP MM ...
"Coding Interview Questions" is a book that presents interview questions in simple and straightforward manner with a clear-cut explanation. This book will provide an introduction to the basics. It ...
The book is over 500 pages and includes 150 programming interview questions and answers, as well as other advice. The full list of topics are as follows: The Interview Process This section offers ...
《Ace the Programming Interview: 160 Questions and Answers for Success》是一本专为编程面试准备的指导书籍,作者为Edward Guiness。本书的目的是帮助读者准备好回答面试中最常见和最相关的问题,从而获得理想的...
CISA Interview Questions and Answers学习文档手册.pdf
8. **条件类型与定价程序(Condition Type and Pricing Procedure)** 9. **使用事务码创建销售人员(Using TransMass to Create Sales Rep)** 10. **序列号(Serial Numbers)** 11. **变体定价(Variant Pricing)** 12. ...
一本介绍面试C程序员时的问题及解答的书籍。
115-Java-Interview-Questions-and-Answers, 115 Java访谈问题和答案- 终极列表 #115-Java-Interview-Questions-and-Answers我们将讨论关于Java面试中可以使用的各种问题,以便雇主在Java和面向对象编程方面测试你的...