Itcecsa
BAN USER- 1of 1 vote
AnswersDesign a service that keeps track of mobile users as they check in at different locations. This service will get informed of each check-in in real time (a user/location pair) and must be able to answer the following queries in real time:
- Itcecsa in United States
1. Where is user U right now?
2. What users are at location L right now?
The following requirements apply:
1. A user can only be at one location at a time. If user U checks in at location X and then at location Y, they are no longer at location X.
2. A check-in only valid for at most 2 hours. If user U checks in at location X and then does nothing for 2 hours, they are no longer at location X.
The service should have durable enough storage that you can restart it without losing all of your data It should not store everything in memory.
what kind of DB will you use and how data will be organized and any indexes. If storage is spread out over multiple databases(locations), how is that done?
scalability/availability consideration, how will be distribute multiple servers. what happens when the traffic goes 10x all of sudden. What happens if one of the server goes down.| Report Duplicate | Flag | PURGE
AppNexus Software Engineer System Design - 0of 0 votes
Answersin a Hadoop-like system, how do we manage multiple nodes collaborating together without having a master node?
- Itcecsa in United States
my answer was running a back end job to randomly select a node to be a master node; and whenever the master node goes down, the backend job select a new node.| Report Duplicate | Flag | PURGE
Bloomberg LP Senior Software Development Engineer System Design - 0of 0 votes
AnswersGiven the following structure Record and we have million of records on disk.
- Itcecsa in United States
struct Record
{
char[257] name;
int startTime;
char[257] description;
}
Now we want to keep a in-memory cache which is represented in class ManageRecords to perform 2 methods GetDesriptions and GetRecords. Given that we have very big memory and we can use any data structure so that the 2 methods can be performed really quick. Here are the questions:
1. what should be the return type for method GetDesriptions
2. what should be the return type for method GetRecords
3. what data structure should we use in the private part as commented out below
class ManageRecords
{
public:
ManageRecords();
? GetDesriptions(char[] name);
? GetRecords(int begin, int end); //do a range search based on startTime of structure Record
private:
// what data strcture should we use here?
}| Report Duplicate | Flag | PURGE
Bloomberg LP Senior Software Development Engineer Algorithm - -1of 1 vote
Answersmulticast VS broadcast
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Networking / Web / Internet - 0of 0 votes
Answersimplement a deque
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Algorithm - 0of 0 votes
Answerswrite atoi() function
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer C - 0of 0 votes
Answerswhat is bus error? common causes of bus errors?
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Linux Kernel - 0of 0 votes
Answersdifference between preemptive and cooperative multithreading
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Operating System - 0of 0 votes
Answerspipe VS message queue
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Operating System - 0of 0 votes
Answershared mmy VS mmy mapped file
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Operating System - 0of 0 votes
Answersimplement a deque
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Front-end Software Engineer Algorithm - 0of 0 votes
Answersfind the 2nd largest # in int array
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Front-end Software Engineer Algorithm - 0of 0 votes
Answershow do you get the average value from a large data stream?
- Itcecsa in United States
I used long long for calculating the sum and int for counting the total number, then divide the sum by total number, if the total sum overflows, have a class present a very large integer.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answersgiven an string with space and an dictionary for all words in the string, how do you find words in the string?
- Itcecsa in United States
I used prefix tree to store all the words in the dictionary, and query works in the prefix tree takes O(n) time.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answera tree is either:
- a branch with a list of child trees
- or a leaf with a value@ / | \ / | \ @ D @ / | \ | | | | | A B C E
1) write a struct to represent it.
2) write a function f() to print out leaf values in in-order travesal
- Itcecsa in United Statesclass InvalidTree { }; template <class T> struct tree { vector<tree> child; T* value; // no empty tree is allowed tree(vector<tree>& _tree, T* _t) { if( !_t && _tree.empty() ) throw InvalidTree(); } bool IsLeaf() const { return branch.empty(); } T* GetValue() const { return value; } const vector<tree>& GetChild() const { return child; } }; template <class T> void f(tree<T>* root) { if(root->IsLeaf() ) { cout << root->GetValue(); return; } vector<tree> childs = root->GetChild(); for(vector<tree>::const_iterator iter = childs.begin(); iter != childs.end(); ++iter) { f(iter); } }
| Report Duplicate | Flag | PURGE
Jane Street Software Engineer / Developer Data Structures - 0of 0 votes
Answershow does Java do Garbage Collection?
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Morgan Stanley Financial Software Developer Java - 0of 0 votes
Answersimplement shared_ptr in C++
- Itcecsa in United Statestemplate <class T> class shared_ptr { private: T* _t; int *count; public: shared_ptr(T* t){ _t = t; count = new int(1); } template <class D> shared_ptr(shared_ptr<D>& d){ _t = d.Get(); count = d.GetCount(); *count = (*count)+1; } ~shared_ptr() { *count = (*count)-1; if(*count == 0) delete _t; } template <class D> shared_ptr<T>& operator= (shared_ptr<D>& d) { if( this->Get() != d.Get() ) { *count = (*count)-1; if( *count == 0) delete _t; _t = d.Get(); count = d.GetCount(); *count = *count + 1; } return *this; } T* Get() { return _t; } int* GetCount() { return count; } };
| Report Duplicate | Flag | PURGE
Morgan Stanley Financial Software Developer C++ - 0of 0 votes
Answerswhat are the different forms of IPC in UNIX?
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Operating System - 0of 0 votes
Answerswhat is better(why and how): multi processes OR single process with multiple threads?
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Operating System - 0of 0 votes
Answerswhat happens if the parent process ends before the child process?
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Operating System - 0of 0 votes
Answershow do applications communicate with kernel?
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Operating System - 0of 0 votes
Answerswrite a function
- Itcecsa in United States
int dominator(const vector<int> &A);
that, given a zero-indexed array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return -1 if array A does not have a dominator.
Assume that:
N is an integer within the range [0..1,000,000];
each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].
For example, given array A such that
A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3
the function may return 0, 2, 4, 6 or 7, as explained above.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given a positive integer A. The goal is to construct the shortest possible sequence of integers ending with A, using the following rules:
- Itcecsa in United States
the first element of the sequence is 1,
each of the successive elements is the sum of any two preceding elements (adding a single element to itself is also permissible),
each element is larger than all the preceding elements; that is, the sequence is increasing.
For example, for A = 42, a possible solutions is [1, 2, 3, 6, 12, 24, 30, 42]. Another possible solution is [1, 2, 4, 5, 8, 16, 21, 42].| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given a positive integer A. The goal is to construct the shortest possible sequence of integers ending with A, using the following rules:
- Itcecsa in United States
the first element of the sequence is 1,
each of the successive elements is the sum of any two preceding elements (adding a single element to itself is also permissible),
each element is larger than all the preceding elements; that is, the sequence is increasing.
For example, for A = 42, a possible solutions is [1, 2, 3, 6, 12, 24, 30, 42]. Another possible solution is [1, 2, 4, 5, 8, 16, 21, 42].| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answerssupport we have an input file while contains integers in the following format
- Itcecsa in United States
3
8 5
2 3 1
0 7 4 2
basically line N has N integers. starting from line 1, find the adjacent numbers in the following line and get the max total from top to bottom. in the above case, the sum is 3+8+2+7=20| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
Answerswrite a method to solve a maze. there should be 3 inputs for the method, start point, end point and maze itself. how to represent the maze itself?
- Itcecsa in United States
X is the start point, Y is the end point, and find the path in the maze
X
| |
| |________
|__________Y| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven the following structure in memory
- Itcecsa in United States
Name State City Street
David CT Stamford main st
Cindy MA Boston huntington ave
Grace NY New York kissena blvd
Ted FL Miami lexington ave
give an data structure and algorithm for providing queries:
given any "State" or "State + City" or "State + City + Street" and return all names
give any "Name" and return all "State + City + Street"
make sure the algorithm is efficient for millions of such records| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - -1of 1 vote
Answershave 1 million product id, get the top 10 in the past 1 hour
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Large Scale Computing - 0of 0 votes
Answersdesign a library for borrowing books and renewing
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design - 0of 0 votes
Answersdesign a zoo with different types of animals and cages(type, size), some of them cannot be in same cage.
- Itcecsa in United States
how to represent relationship? what if lion eat 1 million different animals?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design - 0of 0 votes
AnswerDesign DVD renting system, database table, class and interface
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design - 0of 0 votes
Answersnext permutation of a given number
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answerspower set of a set
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answersrebuild binary tree with pre-order and in-order sequence
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSerialization & Deserialization of Binary Tree
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersConsider this string representation for binary trees. Each node is of the form (lr), where l represents the left child and r represents the right child. If l is the character 0, then there is no left child. Similarly, if r is the character 0, then there is no right child. Otherwise, the child can be a node of the form (lr), and the representation continues recursively.
- Itcecsa in United States
For example: (00) is a tree that consists of one node. ((00)0) is a two-node tree in which the root has a left child, and the left child is a leaf. And ((00)(00)) is a three-node tree, with a root, a left and a right child.
Write a function that takes as input such a string, and returns -1 if the string is malformed, and the depth of the tree if the string is well-formed.
For instance:
find_depth('(00)') -> 0
find_depth('((00)0)') -> 1
find_depth('((00)(00))') -> 1
find_depth('((00)(0(00)))') -> 2
find_depth('((00)(0(0(00))))') -> 3
find_depth('x') -> -1
find_depth('0') -> -1
find_depth('()') -> -1
find_depth('(0)') -> -1
find_depth('(00)x') -> -1
find_depth('(0p)') -> -1| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - 0of 0 votes
Answerswhile reading a binary file with over 1 billion unsigned integers, how can you optimize the following code to make it perform better?
- Itcecsa in United States
int i=0;
long sum=0;
ifstream file("binary.dat", ios::in|ios::binary);
if(file.is_open())
{
while(!file.eof()) {
file.read(reinterpret_cast<char*>(&i), sizeof(unsigned int));
sum += i;
i = 0;
}
}
file.close();| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer C++ - 0of 0 votes
Answerswhy do we need weak_ptr? give an example by code!
- Itcecsa in United States
I didn't answer the question well.
I am really confused about weak_ptr. weak_ptr is an observer of shared_ptr, meaning that we always need shared_ptr in order to use weak_ptr. but in cyclic case, we don't use shared_ptr for one of the object, then in this case how can we use weak_ptr without shared_ptr to break cycle?| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer C++ - 0of 0 votes
AnswersGiven an file which consists thousands of lines. each line consists of a string and several integers.
- Itcecsa in United States
design an algorithm which take input of several integers and print out the string of the line that have most matches.
input file
----------
aa 3 4 10 2
bb 9 14 15 21 3
cc 12 1024 200 3 9 4
----------
examples:
input: 3 4 10
output: aa
input: 12 3 4
output: cc
input: 3 9
output: bb
input: 3 9
output: cc
input: 3 4 12
output: cc
Thanks!| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answerwhat's the signature of [ ] in std::map? why not const?
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer C++ - 0of 0 votes
Answersgive an algorithm to generate random numbers between 1 and 2.
- Itcecsa in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answerswhen i++ is better than ++i?
- Itcecsa| Report Duplicate | Flag | PURGE
Baidu Software Engineer / Developer C - 0of 0 votes
AnswersWrite a C++ program that would find and print the first longest ascending or descending contiguous subsequence for a vector of integers. For example, given a vector with
- Itcecsa
4, 2, 1, 2, 3, 4, 3, 5, 1, 2, 4, 6, 5
the program would find the underlined subsequence and print it.| Report Duplicate | Flag | PURGE
Interactive Brokers Software Engineer / Developer - 0of 0 votes
Answersis STL map thread-safe? why?
- Itcecsa| Report Duplicate | Flag | PURGE
Citigroup Software Engineer / Developer C++
Trie should be good for implementing a dictionary.
I do have question about trie:
1. the wiki says that lookuping keys with m length takes m operations, but what about each operation inside notes, how complicated it is? let's say we are looking up "zzz" in a Trie, while searching for 'z' in root node, it might take up to 26 comparisons given all nodes only contains English letters. if this is true, I will say Trie is not efficient
2. how do we generate the value for each leaf node?
thanks!
in the copy constructor, how to implement the reference count? I used an integer for counting the reference, incrementing by 1 when constructing a new shared pointer, decreased by 1 when destructing a shared pointer. but the problem here is how to share the reference count for all shared pointers. obvious i can't use static variable.
- Itcecsa June 06, 2011
actually the string doesn't have space within it.
- Itcecsa June 12, 2012