peroooo's blog

De Shaw SDE Interview question
By peroooo, history, 4 years ago, In English

Question: Given an encoded String eg "a2bb3k11" that can be expended after decode "aabbbbbbkkkkkkkkkkk" and you have performe given range queries and find the length of the expended string;

input : a2bb3k11
3
0,3 = "a2bb"
2,5 = "bb3k"
2,6 = "bb3k1"
output: 2 = "aa"
6 = "bbbbbb"
7 = "bbbbbbk"

brute force will give (n*q) or (n^2) solution is there any way to optimize the queries to log(n) time.

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
← Rev. 4   Vote: I like it -12 Vote: I do not like it

This can be done simply using a dp,where $$$dp_i= length\ of\ prefix\ ending\ at\ i$$$. Your anser will be $$$dp_r-dp_{l-1}$$$.

Edit: This solution is wrong.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    thanks for the help i thought maybe this problem requires a segment tree I got stuck on that

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    How can we answer for query 3,4?? As dp[4]=8 and dp[2]=3 so ans would be (8-3=5) but real ans would be b3 i.e. bbb 3.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In that case, what would be the answer of the query $$$(1,2)$$$ $$$substring\ ="2b"$$$? $$$1\ or\ 2$$$ ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Zero.As there is no expansion of any string.I think u misunderstood the problem.see sample case again ith query (2,5).We don't have to cout whole string length.We need to find expanded string length.If a character is not in expansion then it will be excluded.

        → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You can do this using prefix sums, like store the answer for each integers, eg s = "a2bb3k11": P[1] = 2, P[4] = 6, P[7] = 11, then just do prefix sum.

Now suppose queries are symmetrical, that means in [l, r], l: begins after integer ends, and r: ends at the integer. Ex: [0, 1], [0, 4], [0, 7], [2, 7] etc.. answer for these queries can be easily calculated by prefix sums.

Now only the main part is non-symmetrical queries, to solve those, you just need to calculate the answer manually for endpoints (l and r), inside part of this range is symmetrical so we can give the answer using prefix sum. The calculation for endpoints is not that difficult.

If there is some bug in this solution let me know:D

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it 
if a query is given as [l,r] we would find Nearest_left_Integer[r] which would give us some index <= r such that it is an integer.So our real range would reduce to [l,r'](r'<=r A[r'] is an integer.
For further reduction wwe would find Nearest_right_Integer array.

we would find l'>=l such that A[l'] is an integer.
Now our range reduces to [l'+1,r'] for which ans can be calculated using standard prefix sum(Dp[r']-Dp[l']).

For remaining range [l,l'] and [r',r].For [r',r] ans would be zero as there would be expansion in that area.

For [l,l'] we would count number of character cnt=l'-l.and multiply it with A[l'] which is an integer.
so final ans would be cnt*A[l']+(Dp[r']-Dp[l']).

Now there are some implementation issues as there would be  number with more than 1 digits.So you must care fully calculate nearest left integer and right integer.


Everything can be done in O(n).
I hope it helps.
→ Reply