Bobek's blog

By Bobek, history, 7 years ago, In English

I know that a number of valid parantheses is nth catalan number. The same is for number of binary search trees. Is there any way to convert valid parantheses sequence to binary search tree with keys 1-n?

Full text and comments »

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

By Bobek, history, 7 years ago, In English

I have array with N numbers and I'm allowed to add (),+-* between to generate max sum. Unary operator is not allowed. I know the solution for only positive numbers but I don't know how to handle negatives. Could you please give me any hints or solution?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Bobek, history, 7 years ago, In English

I read some articles about ternary search and it seems that it's very similar to binary search, but we divide interval on three rarther than two parts. Is there any problem that can be solved using ternary search and can't be solved using (or at least much harder) binary search ? When should I use ternary search over binary search ?

Full text and comments »

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

By Bobek, history, 8 years ago, In English

I know how to find Binomial coefficient usign dynamic programming , but in this case I have to store many others binomial coefficients. Could somebody provide me code how to calculate Binomial coefficient using factorization? I know that I have to factorize n! , k! and (n-k)! and the try to reduce it but I don't know how to compute it efficiently

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Bobek, history, 9 years ago, In English

Could somebody give me a hint to the following question ?

Given balanced BST find the biggest subtree that is duplicated in that tree.

I've just came up with this problem and I don't know anything better than checking all pairs of nodes and setting them as roots. Then having those roots I can check what's the biggest duplicated subtree. Complexity will be O(n^3) . Is it possible to solve it more efficient ?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Bobek, history, 9 years ago, In English

I am trying to solve this problem http://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/ There is a solution, but in my opinion it's actually O(n^2) , because rotate function also is O(n). Am I right ? Is there a way to solve it in O(n) time and O(1) space ?

Full text and comments »

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

By Bobek, history, 9 years ago, In English

Maybe it's not the best place to ask this question, but I believe I'll get an answer here. How long have you waited for a contact from Google/Palantir/Facebook after applying online ( not by passing your CV to your friend or recruiter directly). Thank you in advance.

Full text and comments »

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