Brain Teasers – WikiSree

Find the biggest black square from an N*N matrix of black or white squares

Question:

Find the biggest black square from an N*N matrix of squares. 1 means it’s black, 0 means it’s white. Output should be the list of squares which forms the largest black square.

Input : ‘{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}’

Output : {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Find the biggest black square from an N*N matrix of squares. 1 means it's black, 0 means it's white
    #                         Input     : '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
    #                         Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}
    

#!/usr/bin/python

def largestSquareAt(sq, i, j, k=1):
    if not ( i+k<len(sq) and="" j+k<len(sq[i])="" ):=""   =""    =""  return="" 0=""  for="" x="" in="" range(0,k):=""  if="" sq[i+x][j+k-1]="='0':" y="" sq[i+k-1][j+y]="='0':" 1="" +="" largestsquareat(sq,="" i,="" j,="" k+1)  =""  ="" def="" biggestsquare(input1):="" len(input1)="=0" or="" not="" (="" input1.count('{')="=input1.count('}')" )="" :="" ''=""  i="str(input1)"  j="i" for="" j]=""  resx="-1"  rexy="-1"  ressize="-1"  res="[]" range(0,len(j)):=""  res.append([])="" range(0,len(j[x])):=""  res[x].append(largestsquareat(j,="" x,="" y))="" ressize<res[x][y]:=""  resy="y"  resstring="" ressize="">0:                                
        resstring = "{"
        for x in range(resx,resx+ressize):
            if x>resx:
                resstring += ","
            resstring += "("
            for y in range(resy,resy+ressize):
                if y>resy:
                    resstring += ","
                resstring += (str(x)+"#"+str(y))
            resstring += ")"    
        resstring += "}"
    
    return resstring  

input = '{0#1#1#0,0#1#1#1,0#1#1#1,1#1#1#1}'
input1 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input2 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input3= '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,0#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input4 = '{0#0#0#0,0#0#0#0,0#0#0#0,0#0#0#0}'
print biggestSquare('')    
print biggestSquare(input1)    
print biggestSquare(input2)        
print biggestSquare(input3)        
print biggestSquare(input4)

Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Question:

Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Input : ({}[((({{}})[{()}]))])

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Given a string of length N, output "Correct" if brackets close in correct order else output "Incorrect"
    #                         Input     : ({}[((({{}})[{()}]))])
    #                         

#!/usr/bin/python
def validString(input1):
    stk = []
    flag = True
    for x in input1:
        if x in ['{', '(', '[']:
            stk.append(x)
        else:
            if  len(stk)==0:
                flag = False
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            elif x == ')' and not stk[len(stk)-1]=='(' :
                flag = False 
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            if not flag:
                return "Incorrect"
            else:
                stk.pop()
    return "Correct"
 

input1 = '({}[((({{}})[{()}]))])'
input2 = '({}((({{}})[{()}]))])'
print validString(input1)    
print validString(input2)

Algorithm Puzzles

You are a given a unimodal array of n distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element that runs in O(log n) time.

Ans. Divide and Conquer

Algorithm Puzzles

You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index i such that A[i] = i. Design the fastest algorithm that you can for solving this problem.

Ans.

Input: Array a[0..n-1] of n elements

pseudocode:

func(a, i, k) {
j = (i + k)/2
if      (a[j]==j)    return True
else if (a[j]<j)   =”” return=”” <span=”” class=”hiddenSpellError” pre=”return ” data-mce-bogus=”1″>func(a, j, k)       // since all numbers are distinct, a[x]
else                 return func(a, i, j)        // since all numbers are distinct, a[x]>x for all x > j
}

C++ Brain Teaser : Virtual Destructor

Hi All,

This time I plan to explain to you a C++ brain teaser I came across. With no further adieu, let me get directly to the question:

What is the problem with this code, if any?

(Assurance from me: this code will compile and execute fine. ie. no compilation error)

Hope you have put enough thought on it. Some might have already cracked it. For the rest of the folks, let me reveal it.

Yes, this code has some serious problem at run-time. If not compilation-error, what is it?

You are right; the worst nightmare, memory leak! But where is it leaking?

Let pause that question for a few minutes to discuss something in C++ language.

In a scenario where a Child class inherits a Parent class, when a Child object is created, first the Parent-Constructor is invoked and then the Child-Constructor and when the Child object is destroyed, first the Child-Destructor is invoked and then the Parent-Destructor is executed.

In our above program, we use a variable of type “Parent” to point to a “Child” object. Lets use below program to check if the order of invocation of constructor and destructor is followed in this case.

Output of the above program is:

As you can see, here the child destructor is not invoked, which means, whatever we coded in the Destructor method of Child class is not executed. In our main program, we allocate an array of memory in the Constructor of Child and delete the same in its Destructor. So our main program successfully allocates an array of memory but don’t delete it, which will result in Memory Leak.

So we have answered our question. Now lets see how we can avoid it.

Here is where Virtual-Destructor comes for help. Make the destructor of “Parent” class virtual and this issue is solved.

New implementation of “Parent”:

New output:

To put it straight, virtual destructor forces the parent class to check for child class destructors and executes it.

Use a virtual destructor if you ever expect a derived class to be destroyed through a pointer to the base class to ensure that the destructor of the most derived classes gets called.

It’s a good practice to make the destructors of all interface classes, ie. any class with at-least one virtual method, as virtual.

Rate this:

Rate this:

Rate this:

Rate this:

Rate this: