PROGRAMMING INTERVIEWS

Question: You are given 2 number streams. You need to find whether they will create the same BST or not.

Example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True

Array1:10 5 20 15 30
Array2:10 15 30 20 5
Result: False (see corresponding trees below)

Answer:

Method of building a BST from an incoming stream is like below:

1. Make first element as root.
2. If current element is smaller then root -> insert in left subtree.
3. If current element is greater then root -> insert in right subtree.
4. If current element is equal to root -> skip (or as pre-decided)
5. While inserting in left and right subtree, follow above steps recursively.

So in above question, we have to check top-down if all the subtrees are identical or not. For that, we should follow below steps:

1. Check if stream is finished if yes -> return false
2. Check if both the stream has same number of elements, if not -> return false
3. Check if root is same, if not -> return false
4. leftsubtree arrays = constructed from smaller elements than root
5. rightsubtree arrays = constructed from greater elements than root
6. if leftsubtree == rightsubtree -> return true
7. For finding result in step 6, follow above steps recursively

Code: While writing code, I am skipping the element equal to root.

Ruby:

def checkidenticaltree(a, b)
   return false if a.length != b.length
   return false if a[0] != b[0]
   return true if a.length <= 1

   a_left  = a.select {|v| v < a[0]}
   a_right = a.select {|v| v > a[0]}
   b_left  = b.select {|v| v < b[0]}
   b_right = b.select {|v| v > b[0]}

   return checkidenticaltree(a_right, b_right) && checkidenticaltree(a_left, b_left)   
end

Python:

def checkidenticaltree(a, b):
   if len(a) != len(b):
       return False
   if a[0] != b[0]:
       return False
   if len(a) <= 1:
       return True

   a_left  = []
   a_right = []
   for x in a:
       if x < a[0]:
           a_left.append(x)
       elif x > a[0]:
           a_right.append(x)

   b_left  = []
   b_right = []
   for x in b:
       if x < b[0]:
           b_left.append(x)
       elif x > b[0]:
           b_right.append(x)
    
   return checkidenticaltree(a_right, b_right) and checkidenticaltree(a_left, b_left)

PS: This is not a very efficient approach as we have to segment stream on each recursion. It will be great, if we can find some bottom-up approach. Any suggestions?

I had to convert ttf fonts in Base64 encoding and save them in CSS while doing some more complex stuff. I wrote a python script for it using inbuild base64 library, which worked pretty fine.

I did the same in ruby (with inbuild Base64 library) and my code ran without any error. So far so good! But when I saw the results in browser, I was surprised to see that it replaced the actual glyphs with random glyphs. Since python script output was doing good job, I was surprised, what I did wrong.

When I run the base64 encoding on a shorter string, I noticed the difference in results.

Ruby Run:

irb(main):010:0* require 'base64'
=> false
irb(main):011:0> str="Akash is testing Base64 Encoding between python and ruby"
=> "Akash Agrawal is testing Base64 Encoding between python and ruby"
irb(main):012:0> Base64.encode64(str)
=> "QWthc2ggaXMgdGVzdGluZyBCYXNlNjQgRW5jb2RpbmcgYmV0
     d2VlbiBweXRo\nb24gYW5kIHJ1Ynk=\n"

>>> import base64
>>> str="Akash is testing Base64 Encoding between python and ruby"
>>> base64.b64encode(str)
'QWthc2ggaXMgdGVzdGluZyBCYXNlNjQgRW5jb2RpbmcgYmV0
   d2VlbiBweXRob24gYW5kIHJ1Ynk='

irb(main):018:0> Base64.encode64(str).gsub("\n", '')

I am using pdftk to burst pdf in different pages. This utility ("pdftk <pdf filename> burst") produces single page pdf for every page of input pdf. Name of out pdf is like pg_{x}.pdf. where {x} is page number with leading zeros to make total length as 4 (if it is less than 4).

Example:

>> pdftk test.pdf burst
>> ls
pg_0001.pdf pg_0002.pdf pg_0003.pdf pg_0004.pdf