Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя peroooo

De Shaw SDE Interview question
Автор peroooo, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 4   Проголосовать: нравится -12 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится 
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.
→ Ответить