peroooo's blog

By peroooo, history, 3 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.

Full text and comments »

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

By peroooo, 3 years ago, In English

Question 1:- You are given a string of numbers, You have to return a partitioned String Array in which substring (i-1)th +(i-2)th = ith substring. If not possible return an empty string array. For example: Input: Output: "111122335" ------> {"1","11","12","23","35"}
Input: Output: "112233" -------> {"11","22","33"} Input: Output: "11314" -------> {"11","3","14"} or {"1","13","14"} Input: Output: "13234113" -------->{}

Link:- https://www.geeksforgeeks.org/partition-given-string-manner-ith-substring-sum-1th-2th-substring/

So I gave a Backtracking solution(same as the given link) for the first question. but he asked me to improve the time complexity for the solution is there any better approach to solve this problem really can't think of anything else than backtracking.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By peroooo, history, 4 years ago, In English

There are N RED balls and M BLACK balls output should be the total number to arrangements with atmost K balls can be together.

ex: Input: n = 3 m = 2 k =1 Output: 1 explantion: RBRBR

input: n = 2 n = 2 k =1 output: 2 explantion: RBRB BRBR

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it