First-Round interview: 1 hour online-test
This is my second interview. I check online before staring the test. There are some useful reviews on glass door. I went through them and make up knowledge. The test cares a lot about the storage and locks which I think is related to Pure storage technique.
Multiple choices questions are tough for me since they talks a lot about the mutual exclusion. I have learned it from wiki but not into really detail. What they are asking about needs you to be familiar with the fundamental knowledge within this area. That's not easy to cover all in just two days.
All the way, I enjoyed the process but hope I could be better and made a better time control. For us, international students, understanding long questions actually takes longer time.
Questions
Check the correctness of a binary search
Find the least common ancestor in binary tree
Check the valid of locks, whether acquired just once or leased in order.
1. Which number can be represented as two decimal?
The floating binary point representation of decimals:Decimals can be represented exactly if there's enough space, just not by floating binary point numbers. There are some decimals cannot be represented exactly because of recurring. Some floating decimal point types have a fixed size, which is "arbitrarily" large. It will face problems when the storage is not large enough.
Answers from StackOverFlow :
http://stackoverflow.com/questions/1089018/why-cant-decimal-numbers-be-represented-exactly-in-binary
"The problem is that 3 is a prime number which isn't a factor of 10. That's not an issue when you want to multiply a number by 3: you can always multiply by an integer without running into problems. But when you divide by a number which is prime and isn't a factor of your base, you can run into trouble (and will do so if you try to divide 1 by that number).Although 0.1 is usually used as the simplest example of an exact decimal number which can't be represented exactly in binary floating point, arguably 0.2 is a simpler example as it's 1/5 - and 5 is the prime that causes problems between decimal and binary. So if you have 23 bits for the significand, you can only represent about 8.3 million distinct values."
2. How to implement mutex using spinlocks and flags.
Mutex: mutual exclusion
"In computer science, mutual exclusion refers to the requirement of ensuring that no two concurrent processes[a] are in theircritical section at the same time; it is a basic requirement in concurrency control, to prevent race conditions. Here, a critical section refers to a period when the process accesses a shared resource, such as shared memory." -WikiSpin Lock
"In software engineering, a spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not performing a useful task, the use of such a lock is a kind of busy waiting. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread being waited on (that which holds the lock) blocks, or "goes to sleep". "-Wiki
Simple:
typedef struct _lock_t{
int flag;
}lock_t;
void init ( lock_t *lock ){
// 0-indicates that the lock is available, 1-indicate the lock is busy
lock->flag = 0;
}
void lock( lock_t *lock ){
while( TestAndSet( &lock->flag, 1 ) == 1 );//spin-wait ( do nothing)
}
void unlock( lock_t *lock ){
lock->flag = 0;
}
3. How virtual functions work
Virtual function:
Call member functions of difference classes with the same name. By using virtual functions, which function will be called is depend upon the content of pointer.
e.g. code b->display( ) will call the display( ) of the derived class.
Pure Function: if you do not want to implement the function in base class
virtual float area() = 0;
Virtual Table:
Virtual function works base on virtual tables. Each class which has at least one virtual function will have a hidden pointer pointing to its virtual table. Virtual table stores the address of all virtual functions.
Check out a good article about this mechanism.
4. What is the memory layout for a given class.
The memory layout of a class including: class members( not function), base class, virtual table pointers. Static function is the same as common functions, do not need a class instance. Simple functions need a class instance, by calling hidden this pointer.
5. Gave three requirements for a data structure like size of the data is unknown etc.choose the best data structure for those requirements .
6. remove all elements from a linkedlist that has the same value as the given value
7. Given an multi-threaded implementation of a stack, find the bugs in the code and complete the code for the pop operation.
8.The code for the programming challenge can be compiled and executed on the test website itself and one can figure out whether one's solution is correct.
- Study about synchronization mechanisms and how it is implemented. View Answers (3)
- Read about C++ objects and virtual functions.
- 9. classic pure interview problems: draw a circle and bitmap
- 10.Before you talk with them, make sure you know what stocks means.
11. Then on site, Draw a circle, multi-threading.
12. is there inherent rounding error
13. Tricky problem relating to figuring out the value of a counter in the presence of race conditions.
14. Given two base classes and a class derived from them how might one layout class instance memory so that polymorphism will work correctly. Problem was simplified in that one could assume memory was a series of same-sized slots and methods and attributes took up one slot each.
