You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
same tree, Binary tree inorder iterator, inorder & postorder traverse BST, binary tree level order traversal(print指定level的binary tree), tree upside down, add next to every tree node, Convert Sorted Array to BST, binary tree的maxSumPath, reverse linkedlist, linkedlist输出倒数K个node的值, linked list取中值, linked list做减法/加法（反序）, valid BST, linkedlist找merge point, copy linkedlist with random pointer, flatten BST to linkedlist(把BST替换为2Dlinkedlist，本质不变), depth, interseciton of linked list(一个一步一个多步是否可以（复杂度高）) LRUCache, upside down, recover binary tree from inorder and preorder,
word search I, min stack, stock transaction I(buy date is needed) & II, two sum, subset, unique paths II, merge two/k sorted array/linked list, Find kth largest number(quickselect, array partition), sort colors, remove duplicate from a sorted array, search in sorted rotated array(binary search), search for a range and delete it in array, next permutation, find peak element(一个先降后升的数组，怎么在这个数组中找到target值 [先找到最小值，然后分别二分查找]), rotate array, single number(简单版-两个整数数组 所有元素完全相同 但第二个array少了一个数 求少的那个数。array中数字是乱序), valid Parentheses(follow up如果加入" " 和 ' ' 怎么处理？" "中间的视为全部合理，里面的内容可以忽略), Trapping Rain Water, Container With Most Water, merge interval, course schedule II(topological sorting), surrounded region(起点给定，而非四周，通过最后判断是否全X来判断给定的X是否封闭)
palindrome number(先让count一下6位数的palindrome有多少种可能，比如100001，234432这种. 然后让print出所有的), reverse integer(reverse a float, follow up 用 a == reverse(reverse(a)) 来判断overflow行不行), atoi, excel sheet column title/number, power(recursive & iterative), sqrt (指定精度 or返回double - 牛顿迭代), RomanToInteger, IntegerToRoman, 矩阵螺旋(给一个矩阵，从中间开始旋转着一圈一圈把值打印出来。代码写完之后还追问了一下如果要允许用户自定义螺旋的方向要怎么改)
reverse words in a string(1.一开始我想用两次while循环那种解法，边写边念叨思路。然后三哥说不要用这种，换一个一次循环的，函数容器随便用。感觉他确实在干别的事，我就直接把char *的input转成string然后空格分割存进vector再逆序合并2. 去掉一句话中多余的空格。输入“ The sky is beautiful ! " 输出 ”The sky is beautiful!" 他开始给的例子里没有标点符号，我就没考虑到=。= 后来也没让修改了。。), anagram [hashmap,面试官prefer质数], add and search word(给一个string的字典和一个target string，要求找出字典中所有跟target近似的string，带*的匹配), longest palindrome substring, shortest palindrome(从后面添加), strstr()
Binary Tree Upside Down
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example: Given a binary tree {1,2,3,4,5},
return the root of the binary tree [4,5,2,#,#,3,1].
这题有一个重要的限制就是，整个数的任何一个右孩子都不会再生枝节.
public TreeNode UpsideDownBinaryTree(TreeNode root) {
if (root == null)
return null;
TreeNode parent = root, left = root.left, right = root.right;
if (left != null) {
TreeNode ret = UpsideDownBinaryTree(left);
left.left = right;
left.right = parent;
return ret;
}
return root;
}
public TreeNode UpsideDownBinaryTree(TreeNode root) {
TreeNode node = root, parent = null, right = null;
two array A and B, find the max positive difference between element a from A, element b from B, but a and b cannot have the same index. 其实简单到不行啊，就是一个找前两个最大的，一个找前两个最小的。
29. find mode value in an unsorted array. 我的思路是先radix sort，然后从左到右扫了一遍，update之前出现最多次数的count和对应的数。（mode value就是数组里出现的次数最多的element,不一定超过数组数量的一半，所以majority vote 不行）。
2）就是一个字母的matrix和一个字典.要我找到所有这个字母matrix能组成的存在于字典的单词..和某道leetcode挺像.然后又问了不是2D的是3D多D怎么办，什么数据结构好使. 我恍了一下然后说了句adjacent list，只见他眼前一亮,于是我就想到了图, 我说可以构建图然后做BFS，他说那是exactly what I want,
int getNextMin(); } numbers里面的数字是无序的。getNextMin方法返回下一个最小值。问题：用上面给出的类实现下面的新类： Class NewClass { vector<Stream> streams; int getNextMinNumber();
} 要求实现这个 getNextMinNumber 方法。
45.remove 所有有且只有一个child的节点（将child连致parent）。Level order travel + hashmap解决。
46.类似two sum，两个array，unsorted，may have duplicate，里面的数值都是bytes，要求不用hash table，不用额外数组，找到一个pair sum to target value，然后想法是用一个long long的var当成bit vector，对于第一个array里的每个数，那个long long var的对应bit置1。。。[radix排序?]
48. 面试官叙述了一个问题，大致是一个公司有n个小组，招收了m个新人（n>m），培训结束后按打分制度把学员分配入各个小组，每个小组只能招收一个新人。每个新人按照喜欢程度列出最想去的小组，每个小组按照喜欢程度列出想要的新人，如何找到最好的match？比如说小组1最想要A，其次是B，再其次是C； 小组2最想要A， 其次是C， 再其次是B； A最想去小组2，其次是小组1；B最想去小组1，其次是小组3。。。此时应当把A分配进小组, B 分配给小组1。 面试官的想法是： 先根据每个新人的打分询问小组，看该小组是否已招到人，如果没有，加进新人并把状态改为招到人。如果再有新人询问想要进该小组，该小组比较对两个新人的打分情况，留下喜欢程度高的新人，“踢走”另一个新人。如此循环，直到所有新人都找到小组。之后让我把他的想法实现成代码。
51. Given parent - child pairs, reconstruct the tree and return the root node. [用一个hashmap来存已经读到的node，然后再用另一个存所有的child，通过比较两个hashmap的keyset就可以得到root，然后返回就好]
52.input array of number {1,2,3,4,5,6} return number of array {2*3*4*5*6, 1*3*4*5*6,1*2*4*5*6,1*2*3*5*6,1*2*3*4*6,1*2*3*4*5 }, 要求 不允许用除法
1. 100 light bubbles, could be switched to on or off. The initial status is all off. The first round, switch every bubble, the second round, switch every two bubble, ......comes to the 100 round. Question: how to implement this process. Follow up: at the end, what bubbles are on.
9. 4 people cross a bridge, each of them takes 1 min, 2 mins, 5 mins, 10 mins to cross bridge respectively, only one flash, how to use 17 mins to send all of them over to the other side. 然后问有没有一个具体的策略来解决这个问题，如果数值变了。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"Bloomberg L.P. provides financial software tools such as an analytics and equity trading platform, data services and news to financial companies and organizations through the Bloomberg terminal (via its Bloomberg Professional Service), its core money-generating product."
【1】 c, c++, java, why efficiencies c > c++ > java and differences, why c++ is better than c
/***Efficiency:
1.java uses java virtual machine (jvm) to run the code & garbage collection
2. Some C++ constructs impose performance penalties; e.g., Virtual methods generally require indirection through a jump table for every call. Likewise, idiomatic C++ code can produce larger object code than equivalent idiomatic C code, which can make the C++ version not fit in L1/L2 cache where the C code would. Fitting in L1/L2 cache generally leads to huge performance gains since RAM is much slower than on-die storage. 3.On the other hand, C++ Templates allow arbitrary compile-time precomputation, which can vastly improve run-time performance. In the limit, for example, you could write a complete solution to, say, the Eight queens puzzle entirely using templates, meaning that your resulting executable only uses as much run-time as is required to print the answer (which the compiler actually computed ahead of time while compiling your program).
/***c++ vs. c
why c++ better : OOP
Non-OO features that C++ has that C does not:
Templates
Function overloading
References
Namespaces
You can use structs and enums without writing struct or enum before every declaration or using typedefs.
Even if you don't define your own classes, using C++'s string and container classes is still often more convenient and safe to work with than c-style strings and arrays.
Type safety (even though some would call it weak)
Exceptions
Variable declarations in conditionals, C99 only has it in for
/***c++ vs. java
1. java runs in a virtual machine, while c++ runs as native executable machine code.
2.c++: Pointers, references, and pass-by-value are supported for all types (primitive or user-defined). java: All types (primitive types and reference types) are always passed by value
3.c++: Memory management can be done manually through new / delete, automatically by scope, or by smart pointers. java: garbage collection.
4.c++: Operator overloading for most operators. java: not allowed
5.c++: Single and Multiple inheritance of classes, including virtual inheritance. java: Single inheritance of classes. Supports multiple inheritance via the Interfacesconstruct, which is equivalent to a C++ class composed of abstract methods
【2】How do you call C functions from C++, C++ Function in C (Mix C and C++)? extern "C" void foo( ); It will turn o_ "name mangling" for func so that one can link to code compiled by a C compiler. http://www.thegeekstuff.com/2013/01/mix-c-and-cpp/ See detailed answer 【3】memory Allocation/Deallocation
3_1) What is the difference between new/delete and malloc/free("operator new" works like the latter)
Malloc/free do not know about constructors and destructors. New and delete create and destroy objects, while malloc and free allocate and deallocate memory. Malloc returns a pointer to void (void *), and requires a special "typecasting" when it allocates memory for, which isn't type safe. Overridability: new is an operator that can be overridden by a class, while malloc() is not overridable on a per-class basis. check NULL for malloc, unnecessary for new(throw exception: std::bad_alloc)
new的过程：先allocate memory in heap 然后调用constructor
3_2) delete和delete[] 区别，delete[] 怎么知道要delete多少object的 The run-time system stores the number of objects, n, somewhere where it can be retrieved if you only know the pointer, p. There are two popular techniques that do this. Both these techniques are in use by commercial-grade compilers, both have tradeoffs, and neither is perfect. These techniques are: Over-allocate the array and put n just to the left of the first Fred object. Use an associative array with p as the key and n as the value
3_5) Is there any way to specify which part of memory I want to create an object by using new？
void *pData = ....; // memory segment having enough space to store A object
A *pA = new (pData) A;
call destructor explicitly
3_6)memory leak 为什么重要，怎么解决 X
例class A(){}; void xyz(){ A *p = new A; //call some functions //call some library delete p; }. 如果call some library出错了，会memory leak，可以 A p 或者try catch解决
pass by value: call copy constructor, inefficiency
pass by reference is safer than pass by pointer: void* & point to other area(改char * const ptr - 不方便), pointer could be NULL
【6】pointer
6.1) What's the size of a pointer
generally have a fixed size(32bit or 64 bit)
X6.2)smart pointer !@#%^&()_
A smart pointer is a C++ class that mimics a regular pointer in syntax and some semantics,
but it does more. Because smart pointers to different types of objects tend to have a lot of code in common, almost all good-quality smart pointers in existence are templated by the pointee type
auto_ptr: The simplest example of a smart pointer is auto_ptr, which only takes care of Memory leak and does nothing about dangling pointers issue.
template<T> class auto_ptr {
T* ptr;
public:
explicit auto_ptr(T* p = 0) : ptr(p) {}
~auto_ptr() {delete ptr;}
T& operator*() const{return *ptr;}
T* operator->() const {return ptr;}
// ...
};
【7】overload和override的区别
overload: save function name, different parameter
override: derived class override the function of the base class, same function name & parameters
【8】i++, ++i那个更efficient
++i好 i++需要有temporary state （在i为instance，函数++返回时）为什么在for(int i = 0; i < n; ++i)里建议用 ++i而不是i++.
【9】c-string
/****实现strcmp, strcpy, strlen(输入\0, null结果)
/****what does a string look like in c?(array of char terminated at '\0') 字符串指针是啥(point to the first char of a c-string)，c是怎么得到string的长度(遇到'\0'停止)，
/****sizeof vs. strlen char *s : s 的 length 和 size 分别是多少
1. A static local variable inside a function keeps its value between invocations. A static global variable or a function is "seen" only in the file it's declared in. Dynamic global variable can be "extern " used in other files.
2.both initialized at compile time(default 0), release when program ends
/*** class static member varible, class static member function
1. no *this ptr
2. initialized out of the definition of the class (static const可以直接在定义的时候初始化) - c++11可以直接初始化
3.不同子类与基类共享同一个static member variable
【11】const
1.const可以给非const, 反之不行（除非const_cast）
2.指针const int *r 与 int const *r 一致， 表示r指向空间的内容不可改变; int *const r表示r指向的空间不能更换
【14】class :: default function given by compiler - 1.constructor, 2. destructor, 3. copy constructor(pass by value, return by value, construct new object, generate a temporary object), 4.assignment operator.
what is the difference between 3 & 4?
- both swallow copy or call copy constructor/assignment operator of member variable
- 3 is for create a new object, might cause memory problem due to shared memory double deleted.
- 4 is to assign the same value to an existed object, might cause memory problem due to shared memory & memory leak of the previous memory
class A{
int c;
public:
A();
~A();
A(const A &other){c = other.c;} // copy: 必须pass by &, 否则值传递反复调用这个函数直到stack over flow
A& operator =(const A &other){if (this != &other) {c = other.c;} return *this;} //assignment， 返回引用为了可以x = y = z
例：How mang memory (i.e. sizeof(obj) ) will an object of class: class foo { int a; int b; long c; } take? what about adding member function, and adding virtual member function? class bar { int a; int b; long c; void f1(); virtual f2(); }
【18】singleton class
推荐版本：(c++11后为thread-safe)
class Singleton{
public:
static Singleton &Instance() {
static Singleton instance;
return instance;
}
private:
Singleton();
Singleton(const Singleton &t);
Singleton& operator =(const Singleton& rhs);
};
//木有处理delete版本&禁止函数不全
class CSingleton {
private:
CSingleton(){} //构造函数是私有的
static CSingleton *m_pInstance;
public:
static CSingleton * GetInstance() {
if(m_pInstance == NULL) //判断是否第一次调用
m_pInstance = new CSingleton();
return m_pInstance;
}
};
X【19】template
【20】void foo(int a, int b) { cout << a << " " << b << endl; } int main() { int i = 0; foo(++i, i++); return 0; } 求程序输出结果？ 2 0
Bloomberg is looking for a senior full-stack developer with a bias towards back-end to strengthen our R&D Communication Systems team in New York. You'll be a member of the team responsible for designing, implementing, monitoring, scaling, and optimizing the code that powers Bloomberg's Internal Communication services.
Our products are scaling rapidly and this is the team will be impacted the most. Your contributions will have an impact on a rapidly growing and already successful product with high ambitions.
Responsibilities
Design, architect, and develop new back-end software applications, libraries and frameworks, for Bloomberg's next gen communication systems.
Discover and troubleshoot issues with the existing architecture and code.
Leverage your deep understanding of all technologies used in the backend infrastructure. This includes: Python, C++, SOLR, RabbitMQ, Relational DBs.
Qualifications:
3+ years of python experience and asynchronous frameworks, microframeworks like Flask, CherryPy, Bottle, and webpy.
Ability to work well in a fast-paced, dynamic, distributed environment is crucial.
Experience with Infrastructure-as-a-Service.
Experience with designing and implementing APIs for a service-driven architecture.
Obsessive and pragmatic about code cleanliness, and automated unit/integration testing.
Experience with relational databases (preferably SQL Server).
The Company:
Bloomberg, the global business and financial information and news leader, gives influential decision makers a critical edge by connecting them to a dynamic network of information, people and ideas. The company's strength - delivering data, news and analytics through innovative technology, quickly and accurately - is at the core of the Bloomberg Professional service, which provides real time financial information to more than 315,000 subscribers globally. Bloomberg's enterprise solutions build on the company's core strength, leveraging technology to allow customers to access, integrate, distribute and manage data and information across organizations more efficiently and effectively. Through Bloomberg Law, Bloomberg Government, Bloomberg New Energy Finance and Bloomberg BNA, the company provides data, news and analytics to decision makers in industries beyond finance. And Bloomberg News, delivered through the Bloomberg Professional service, television, radio, mobile, the Internet and three
magazines, Bloomberg Businessweek, Bloomberg Markets and Bloomberg Pursuits, covers the world with more than 2,400 news and multimedia professionals at more than 150 bureaus in 73 countries. Headquartered in New York, Bloomberg employs more than 15,000 people in 192 locations around the world.
4 印度人说，我现在心里有一个数，你可以说任意的一个数，我可以回答你大了还是小了。你要用什么的算法思想来猜数。
解法我说了两个，他没有说范围的时候, left window and right window --> right window以（2^n）的速度递增，而left window覆盖上一次的right window，确定了两个window,做binary search。
他说了范围直接用binary search。两个解法都是log(n)时间复杂度。
补充内容 (2015-7-24 20:48):
Add Two Numbers还问了时间复杂度
O(max(m, n))
JoeQi 发表于 2015-4-2 08:51:55
3月中旬onsite，3月低收到拒信。面了四轮，感觉每轮都聊得很好。我能想到可能的原因是专业不太matach吧，没有c++相关的project。
四轮都是白人。
第一轮： 1.给定一个function, double getprice(double stock) ,然后 让写怎么利用给定的function来实现double getstock(double price)。 idea就是binary search. 写了代码 2. find intersection of two linked list. 老掉牙的题目了。 3: find elements in A that is not in B 。 用hashset过了。
第二轮： 1. flaten 2D linked list, 很多人报到过，因为之前看过，所以我思路有，一边讲一边写出了代码。
2. find mode value in an unsorted array. 我的思路是先radix sort，然后从左到右扫了一遍，update之前出现最多次数的count和对应的数。 （mode value就是数组里出现的次数最多的element,不一定超过数组数量的一半，所以majority vote 不行）。 radix sort没写代码，只写了后半部分，我思路有，只是有个人比较rush 应该是刚学做interviewer，因为另一个interviewer几次提醒过这人不要rush。我也是因此学会了rush的这个用法。。
--2nd Round--
亞裔+烙印
三哥很nice 先上了merge two sorted array再來cach(LRU),
寫得差不多就換另一位不苟言笑的出題Top 10 stock price/volume streaming....沒寫code
討論算法hashtable+heap還討論了hashtable實作,time complexity,資料量大的時候怎辦(這不都考古題嗎...).
最後問了一些問題,利用上一輪聊得到的內容再聊個天,亞裔哥終於有說有笑了...
...
lz信心滿滿期待下輪
then 一個漂亮的女孩走進來:seems like you are done for the day. (...fxxk off阿lz不是要妳阿怒丟lunch box..
anyway,想說好吧利用時間去周邊晃晃time square, central park也都在附近阿!!
lz一走出大樓..哇操...下著大雨!!!但這時的lz已經什麼都無所謂了就走近雨中往下一個目標前進了..
感謝bb讓我能夠第一次走在ny街道上,從機場到旅館bb有給專車,旅館的wifi也是免費的,去onsite的各位別擔心,給的$100搭車回機場加吃飯絕對夠的!!
(最後班機delay三小時囧bad bad luck...凌晨抵達感謝接機小夥伴一夜不睡
感謝地裡大大們的面經才讓小的我能夠輕鬆應對就當累積經驗吧!
最後 還沒找到,正在找的各位一起加油吧!!
先提一点，早上一去，就我和一个印度人坐在那里，我就冲他笑了一笑准备聊一聊（当年在Mathworks实习的时候有一个印度前辈对我很好，所以我对印度人很有好感），结果印度大哥上来就是一句you know this position is filled.我当时还没反应过来，他接着说他学校上礼拜来了十几个人都是两轮游。我心里顿时就笑起来了，我擦难道我遇到了传说中的东巴！！！（看过全职猎人都知道我在说什么）当然，做人要实在，我还是假定他不是为了吓唬我而真是这么想的，就顺着他的话聊下去，什么刚过4月1号招人肯定不猛啊之类的，东巴大哥最后脸色也不太好看了... 楼主前几天被fb加面，而且个人觉得面的很好，然后被HR打电话拒了，HR发邮件要给我打电话的时候我人都亢奋了，然后居然是拒绝，不夸张地说瞬间脑子嗡了一下，说不出话来，脸上瞬间全是汗。所以曾经沧海难为水，现在想在心态上影响我基本等于不可能。
