Interview Question

Interview

1. JAVA vs C++

Java: write once, run anywhere
C++: write once,Write once, compile anywhere
1. C++ supports both procedural progamming and OOP. Java is pure OOP, everything is an object in Java(Java.lang.Object).
2. Java is platform independent language but c++ is depends upon operating system.
- Java uses compiler and interpreter both and in c++ their is only compiler
- Compiler will convert the source code to byte code, JVM(interpretor) will interpertor the byte code to machine code.
- C++ run and compile using compiler which converts source code into machine level languages so c++ is plate from dependents
3. Manual memory management by default in C++, Automatic memory management through a garbage collector.
4. C++ supports pointers, whereas Java does not. But Java has restricted pointers.
5. Thread support is built-in Java but not in C++.
https://www.quora.com/What-are-major-differences-between-C++-and-Java
https://www.quora.com/What-are-major-differences-between-C++-and-Java

2. abstract class vs interface

Abstract class must have one or more abstract methods. A method is declared abstract when it has a method heading, but no body – which means that an abstract method has no implementation code inside. Abstract classes are meant to be inherited from.

An interface differs from an abstract class because an interface is not a class. An interface is essentially a type that can be satisfied by any class that implements the interface.

Any class that implements an interface must satisfy 2 conditions:
It must have the phrase "implements Interface_Name" at the beginning of the class definiton.
It must implement all of the method headings listed in the interface definition.

Interfaces are a good substitute for multiple inheritance. Java does not allow multiple inheritance.

Abstract classes can have some implementation code. An abstract class may provide some methods with definitions – so an abstract class can have non-abstract methods with actual implementation details.

3. Polymorphism

The word polymorphism means having many forms.
The pointers or references of base class can point or refer to sub-class object. And when you call the member function, it will cause a diffirent function depending on the type of the object. (dynamic binding) //基类的指针，引用可以指向派生类, 但是指针和引用只能访问基类方法.

4. Override vs Overload

Override重写覆盖:
- in the same scope(in a same class)相同的范围（在同一个类中）
- same function name函数名一样
- diffirent arguments参数不同
Overload重载：
- diffirent scope(base class and sub-class)不同的范围
- same function name函数名相同
- same arguments参数相同
- the base function must have virtual key word基类必须有virtual关键字

5. Stack, heap, static

• stack: a contiguous memory space. The space is very limited. Local varibles, function arguments and etc, maintain by the compiler, works like a stack. From higher address to lower address.
• heap: discontiguous memory space, dynamically alocate by the progammer(new - delete, malloc - free). It works like a linked list. Higher address to lower.
• static: global variables, static variables.

6. C++ 11

• Lambda expression

[] (int x) {return x > 3;};  //只有一条返回语句 就可以自动判断返回值
[] (int a, int b)->int {int sum = a + b; return sum;};  //多条语句 就要用后置返回值
auto sum = [] (int a, int b)->int {return a + b;};  //还可以给定一个名字 但是必须是auto类型

• nullptr
• Multi thread library
• Initialization in the class
• Smart pointer

7. Big O

• O(1) Constant
  
  -
• O(log n) Logarithmic, not as good as constant, but still pretty good
  
  • binary search
• O(n) Linear, The larger the data set, the time taken growns proportionately.
  
  • search a number in a unsorted array.
• O(nLogn)
  
  • quick sort
• O(n^2) Quadratic
  insert sort, bubble sort
• O(2^n) Exponential
  
  • DP travelling salesman problem
• O(n!) Factorial
  
  • brute-force travelling salesman problem

8. Sorting Alogrithm

• Comparison sort: bubble sort, selection sort, insert sort, mergesort, quick sort, heapsort.
• Non-Comparison sort: bucket sort, count sort, radix sort.
  
  参考连接

9. Common Operations

参考连接

10. STL

• Sequence container:
  
  • vector, list, deque, array
• Associative containers(Red-Black Tree, self-balancing binary search tree):
  
  • set, map, multiset, multimap
  • access, insert, search, delete: average:log(n), worst: log(n);
• Unordered associative containers(hash table):
  
  • unordered_set, unordered_map, unordered_multiset, unordered_multimap
  • access, insert, search, delete: average:O(1), worst: O(n);

1.vector

Vector通过一个连续的数组存放元素in heap，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素。重新分配内存后迭代器失效。

vector<int> nums;           //nums.capacity() == 0;
vector<int> nums(10, 1);    //nums.capacity() = 10;

push_back()就直接在后面插入。

insert()通过迭代器在任何一个位置插入，把后面的元素向后拷贝移动。

删除元素：删除和新增差不多，也分两种，删除最后一个元素pop_back和通过迭代器删除任意一个元素erase(iter)。通过迭代器删除还是先找到要删除元素的位置，即int index=iter-begin();这个位置后面的每个元素都想前移动一个元素的位置。同时我们知道erase不释放内存只初始化成默认值。

删除全部元素clear：只是循环调用了erase，所以删除全部元素的时候，不释放内存。内存是在析构函数中释放的。

vector vs array
std::vector vs std::array

arrays:
- a builtin language construct;
- provide just a contiguous, indexable sequence of - elements; no bells and whistles;
- are of fixed size;
- their size must be a compile-time constant unless they are allocated dynamically;
- if dynamically allocated, you must explicitly deallocate them;
- if they are dynamically allocated, you just get a pointer, and you can't determine their size; otherwise, you can use sizeof (hence the common idiom sizeof(arr)/sizeof(*arr);
- can't be returned from a function;
- can't be copied/assigned directly;

std::vector:
- is a template class;
- is implemented as a dynamic array;
- grows and shrinks dynamically;
- automatically manage their memory, which is freed on destruction;
- can be passed to/returned from functions (by value);
- can be copied/assigned (this performs a deep copy of all the stored elements);
- always brings along with the internal dynamic array its size (how many elements are currently stored) and capacity (how many elements can be stored in the currently allocated block);
- less efficient than "regular" arrays for small, short-lived, local arrays;
when reallocating, the objects are copied (moved, in C++11);
- does not require a default constructor for the objects being stored;

2. set, map

Red-Black Tree;
access, insert, search, delete: average:log(n), worst: log(n);

3. unordered_set, unordered_map

Hash table;
access, insert, search, delete: average:log(1), worst: log(n);

4. forward_list(singly-linked lists)

- = 没有[], 不能随机访问
- 没有size(), 但是有resize();
- push_front(), pop_front() //不能再后面push pop,也没有back(),
- insert_after(), erase_after() //在后面insert, 返回的iterator指向插入的最后一个节点
- erase_after() //***返回的it 指向删除节点的后面一个***
- remove(x) //***删除值等于x的节点***
- mylist.sort() //升序(小的在前面)
- mylist.sort(std::greater<int>()); //降序

5. list(doubly-linked lists)

- push_back(), push_front(), pop_back(), pop_front(), size()
- insert(), //返回的it指向插入的第一个元素 与vector一样
- erase();  //返回的it指向删除的元素的后面一个 与vector一样
- remove();
- sort() //和�上面一样

6. queue

- front(), back(), push(), pop(), size(), empty(), swap(), emplace()

7. priority_queue

- 默认是max_heap
- top(), push(), pop(), size(), empty(), swap(), emplace() //相对于queue少了back(), front(), 多了top();

8. deque(double ended queue)

- [], =
- push_back(), push_front(), pop_back(), pop_front(), insert(), erase(), size()

9. stack

- top(), push(), pop(), size(), empty(), swap(), emplace()

10. heap

- 二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。如果存储数组的下标基于0，那么下标为i的节点的子节点是2i + 1与2i + 2；其父节点的下标是⌊(i − 1) ∕ 2⌋。
- ***insert, deleteMin, remove复杂度是log(n), findMin复杂度O(1)***

- 插入节点: 在数组的最末尾插入新节点。然后自下而上调整子节点与父节点（称作up-heap或bubble-up, percolate-up, sift-up, trickle up, heapify-up, cascade-up操作）：比较当前节点与父节点，不满足堆性质则交换。从而使得当前子树满足二叉堆的性质。时间复杂度为O(log n)。

- 删除节点: 删除根节点用于堆排序。对于最大堆，删除根节点就是删除最大值；对于最小堆，是删除最小值。然后，把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点：对于最大堆，父节点如果小于具有最大值的子节点，则交换二者。这一操作称作down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max等。直至当前节点与它的子节点满足堆性质为止。

11. Trie Tree

Wiki
Leedcode: implement Trie Tree

12. Segment Tree

Wiki

11.