swordx's blog

By swordx, history, 5 months ago, In English,

Hello Guys,

Can you share your thoughts on the following question:

Given a string, we have to find the longest non-overlapping repeating subsequence. For example, If we have a string like "abdead", then here the answer is "ad" because longest repeating subsequence is "ad" which is non-overlapping.

My initial thought on this question is that we can use the concept of longest common subsequence but we need to manage the non-overlapping part.

Thanks in advance!

Read more »

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

By swordx, history, 9 months ago, In English,

Hello all,

Can you please share your thoughts on the following question:

Given an array of integers and some queries, you have to tell the length of the longest increasing subsequence for each query. The query is in the form such that you have to change the value at a given index to given value. Each query is independent of others. So the array gets backs to its original state after each query.

Example: Arr[]={1,6,2,4};

query: 1 4 : means: arr[1]=4, Now calculate the length of LIS.

Thanks in advance.

Read more »

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

By swordx, history, 21 month(s) ago, In English,

Hello all,

Could someone share their thoughts on the problem mentioned below:

Given an array of sorted integers, find the number of unique triplets such that (a[i]*a[k])+a[j]=target and i<j<k.

Ex: A={1,3,3,5,5} and target=18 o/p should be {[3,3,5]} . Explanation a[1]*a[3]+a[2].

I know we can solve it in O(n^2) time.

Ques-1: Can we solve it in less than O(n^2) time. If yes, how?

Quest-2: What if the given array is not sorted? What will be the time complexity in this case?

Thanks in advance.

Read more »

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

By swordx, history, 21 month(s) ago, In English,

Hello all,

Can someone share their thoughts on the following question :

Given a array of n elements. You have to find the median of difference of pairs. For Example: Lets say the elements are {1,2,4,5}. So the pairs will be {(1,2),(1,4),(1,5),(2,4),(2,5),(4,5)}. The array formed by those pairs are {1,3,4,2,3,1}. So you have to find the median of this new array generated by the difference of pairs.

I know it can be easily done in O(n^2). Could anyone share their approach to solve it in less than O(n^2) time.

Thanks in advance.

Read more »

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

By swordx, history, 2 years ago, In English,

Hi All,

Can someone share their ideas on how to do the following problem in O(n): http://www.geeksforgeeks.org/lexicographically-smallest-rotated-sequence-set-2/

I have found on wikipedia that it can be done in O(n). I am not able to understand the booth's algorithm given on wikipedia.

Can someone share their approach to solve this problem in O(n).

Thanks in advance

Read more »

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

By swordx, history, 4 years ago, In English,

Can anybody tell me the solution of k tree problem using 1d dp link: http://codeforces.com/contest/431/problem/C

How to eliminate those paths which doesnot contain an edge of weight d?

Read more »

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