Serge Aktanorovich
BAN USER
Comments (5)
Reputation 20
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Hello. Can you provide some constraints on problem input?
- Serge Aktanorovich October 28, 2015Comment hidden because of low score. Click to expand.
1
of 1 vote
Hello. Did you look at Bin Packing Problem? I think the best answer is to use branch and bound method or implement some kind of heuristic or probabilistic algorithm.
- Serge Aktanorovich October 27, 2015Comment hidden because of low score. Click to expand.
0
of 0 vote
Hello. Did you try to iterate from the last element to the first and keep track elements in stack?
- Serge Aktanorovich October 27, 2015Comment hidden because of low score. Click to expand.
0
of 0 vote
Hello. In order to solve this problem we can use a queue implemented on two stacks with additional operation getMax() defined both on queue and stack. In that case amortized query time will be O(1).
- Serge Aktanorovich October 27, 2015Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Hello. This problem can be solved in at least three different ways with the same approach. Assume L is sequence's length (in our case 10M). The main idea is to build data structure with two operations defined: 1) flip(start_index, end_index) -- flip bits from start_index to end_index; 2) query(index) -- get hexadecimal number corresponding to bits on positions [index, index+3]. The first approach is related to provided answer. The main issue is that the flip operation takes O(L) time in the worst case. The second idea is to divide our sequence on Sqrt(L) blocks and perform flip operation on blocks instead of on each element. In this case flip operation takes(O(Sqrt(L)) time in the worst case. The third approach is to build segment tree and implement each operation with complexity O(log(L)).
- Serge Aktanorovich October 28, 2015