Buffer Overflow

Question: What is a buffer overflow and how do you exploit it?

What is Buffer Overrun?

Buffer Over-run refers to problem where we can make program to use more than allotted ‘buffer’.All buffer overruns cannot be exploited as security vulnerability

What it could lead to?

Buffer overflows can be triggered by inputs that are designed to execute code, or alter the way the program operates. You get an access violation (AV). Your site becomes unstable.The attacker injects code into your application, executes it, and makes everyone an administrator of your site.

Types of Buffer Overrun

• Stack Overruns
• Heap Overruns
• Array Indexing Errors
• Format String
• Unicode and ANSI Buffer size mismatch

A colleague of mine created a  PPT on Buffer Overflow which we deal with here on daily basis. I removed some of the proprietary code and some other useful information.

Buffer OverFlow

View more presentations from Rambabu Duddukuri.

Max Black sub square matrix

Imaging there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Algorithm to Exhibit Did You Mean Feature of Google Search Engine

When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words e.g. In Directly You have Add Space between two such or if are using some data structure , where words would have been inserted , you would have maintained a boolean variable to defined the end of word (eod)
An Example Will be Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?

You can solve this problem using a trie datastructure. Trie data structure implementation can be found here in my previous blog. The rest is just searching the trie

LRU Cache Implementation

Linked List is a palindrome or not

Question: Write a program to check if the given linked list is a palindrome or not

METHOD 1 (using recursion)

METHOD 2 (Using Stack)

• Get the middle of the linked list.
  
  
• Push the elements into the stack till the middle of the linked list
  
  
• Compare the top of the stack and second half.
  

Next bigger number

Q : You have given a positive number. You have to find a number which is immediate bigger than that by using same digits available in the number. use same digits with same number of time, coming in positive integer and if a small number is not possible then we have to return -1.

For example: (1) You have given a number 7585 , your output should be 7855 . (2) 7111, return –1

Algorithm:

Code:

Building Bridges:

Problem: Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a1….an and n cities on the northern bank with x coordinates b1….bn. The cities on each bank are also numbered 1 through n and these numbers do not correspond to the ordering of the x-coordinates. You can only build a bridge from a city on the south bank to a city on the north bank with the same number. No two bridges may cross each other. An example of a valid bridge building is shown in Figure 1. Give an algorithm for finding the maximum number of bridges that can be built.

Solution:
Consider the sequences A = N(a1),……..,N(an) and B = N(b1),…….,N(bn) where N(ai) is the number of the city with x-coordinate ai. The length of the longest common subsequence of A and B is the maximum number of bridges. Since A and B are non-repeating, the length of the LCS for A and B can be calculated in O(n log n) time. Make sure you understand why that is the case!

Proof that length of the LCS is the maximum number of bridges: We show that the maximum number of bridges cannot be more than the length of the LCS and that the maximum number of bridges cannot be less than the length of the LCS.
Firstly, assume the length of the LCS is m. Let c1,…….,cm be a longest common subsequence of A and B, corresponding to cities ai₁……ai_m in A and bj₁,,,,,,,, bj_m in B. Then for 0 < k< = m, we can draw a bridge from ai_k to bi_k . None of these bridges intersect. Therefore, we can draw at least as many bridges as the length of the LCS.

Now assume we can draw at most m bridges from cities CA = ai₁,…..ai_m to cities CB = bj₁,….., bj_m and WLOG assume CA is ordered by increasing x-coordinate. Then N(ai_k ) = N(bj_k ) since we can draw a bridge between them. Moreover, bj_k must have a higher x-coordinate than any of bj₁,…..bj_k-1 and a lower x-coordinate than any of bj_k+1,…..,bj_m so that none of the bridges cross.Therefore CA is a subsequence of A and CB is a subsequence of B and we have found a common subsequence. Thus, the length of the LCS is at least the maximum number of bridges