Flipkart Question: Find fixed point in array

Problem: Given a sorted array of distinct integers, find index i where arr[i] = i. Note that integers in array can be negative. 

Solution: Use binary search to get the index.

Implementation:

int findIndex(int arr[], int low, int high)
{
if(low <= high)
{
int mid = (low + high) / 2;
if(mid == arr[mid])
return mid;
if(mid < arr[mid])
return findIndex(arr, low, mid - 1);
else
return findIndex(arr, mid + 1, high);
}
else
return - 1;
}

Complexity: O(log n)

[SAP Labs] Move all zeroes to end of array

Problem: Given an array of integers, move all the zero’s in a given array to the end of the array. The order of all other elements should remain same. We need to do it inplace.

Example:

Input: nums = [0,2,0,7,19]
Output: [2,7,19,0,0]

Approach: It's a simple problem to solve using two pointers approach. The only problem here is we need to maintain the order so we can't go with start and end pointers but what we can do is first we move all the nonzero elements in the begining using two pointers and then just fill the rest of the array with 0.

Implementation:

    public void MoveZeroes(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return;

        }

        int j = 0;

        for (int i = 0; i < length; ++i)

        {

            if (nums[i] != 0)

            {

                nums[j++] = nums[i];

            }

        }

        for (; j < length; ++j)

        {

            nums[j] = 0;

        }

    }

Complexity: O(n)

Print permutations of a string

Problem: Print all permutations of a given string

Implementation:

void stringPerm(std::string s, int len, int i = 0)
{
if(i == len)
std::cout<<s<<'\n';
else
{
for(int j = i; j < len; ++j)
{
if(i != j && s[i] == s[j])
continue;
std::swap(s[i], s[j]);
stringPerm(s, len, i + 1);
std::swap(s[i], s[j]);
}
}
}

Complexity: O(n*n!)

Array partition problem

Problem: Determine whether a given array can be partitioned into two arrays such that the sum of elements in both arrays is same.

Solution: 

It can be solved using Subset sum problem. Following are the two main steps to solve this problem using subset sum problem:

1. Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum.
2. If sum of array elements is even, solve subset sum problem for this array with sum equal to sum/2.

Implementation in C#:

        public bool CanPartition(int[] nums)

        {

            int sum = 0;

            foreach(int num in nums)

            {

                sum += num;

            }

            if (sum == 0)

            {

                return true;

            }

            if (sum % 2 != 0)

            {

                return false;

            }

            return this.IsSubsetSum(nums, sum / 2);

        }

Please find the implementation of Subset sum at the following URL:

https://algods-cracker.blogspot.com/2015/04/subset-sum.html

Complexity: O(n²)

Subset Sum

Given an array of non-negative integers and a value determine if there is a subset of the given array with sum equal to given value.

Dynamic Programming Solution:

Maintain a Boolean 2D matrix say table[][] where the value of table[i][j] will be true if there is a subset of array[0..j-1] with sum equal to i, otherwise false. Obviously table[sum][n] will be our answer.

Implementation in C#:

        public bool IsSubsetSum(int[] arr, int sum)

        {

            if (sum == 0)

            {

                return true;

            }

            if (arr?.Length == 0)

            {

                return false;

            }

            bool[,] table = new bool[sum + 1, arr.Length + 1];

            for (int i = 0; i <= arr.Length; ++i)

            {

                table[0, i] = true;

            }

            for (int i = 1; i <= sum; ++i)

            {

                table[i, 0] = false;

            }

            for (int i = 1; i <= sum; ++i)

            {

                for (int j = 1; j <= arr.Length; ++j)

                {

                    table[i, j] = table[i, j - 1];

                    if (i >= arr[j - 1])

                    {

                        table[i, j] = table[i, j] || table[i - arr[j - 1], j - 1];

                    }

                }

            }

            return table[sum, arr.Length];

        }

Complexity: O(n²)

Limitation: You can see that this solution is not feasible if the sum is too big (Too much memory consumption).

Another approach:

Try all the subsets of the given array and check whether sum of the elements in the subset is equal to given sum or not.

Implementation in C++:

bool isSubsetSum(int *arr, int len, int sum)
{
if(sum == 0)
return true;
if(arr == NULL || len == 0)
return false;
if(arr[len-1] > sum)
return isSubsetSum(arr, len - 1, sum);

return isSubsetSum(arr, len - 1, sum) || isSubsetSum(arr, len - 1, sum - arr[len -1]);
}

Complexity: O(2ⁿ)

Longest Palindromic Substring

Problem: Given a string, find the length of the longest palindromic substring in it.

Solution: 

Longest Common Substring can be used to solve this problem. The steps are as follows:

1. Reverse the given string and store the reverse in another string say rev[0..n-1]
2. Longest Common Substring of the given string and rev[] will be the longest palindromic substring.

Implementation:

int LongestPalindromSubString(std::string str)

{

std::string rev = str;

std::reverse(rev.begin(), rev.end());

return LongestCommonSubstring(str, rev);

}

Please find the implementation of Longest Common Substring at the following URL:

http://algods-cracker.blogspot.in/2015/04/longest-common-substring.html

Complexity: O(n²)

Space efficient solution:

We can generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.

1. To generate odd length palindrome, we can fix a center and expand in both directions for longer palindromes.
2. To generate even length palindrome, we can fix two center and expand in both directions for longer palindromes.

We will not be needing any extra space using this approach.

Implementation:

int LongestPalindromSubString(std::string str)

{

int maxLen = 1, len = str.size();

int start = 0; //Can be used to print the substring

for(int i = 1; i < len; ++i)

{

int low = i - 1, high = i; //Even palindromes

while(low >= 0 && high < len && str[low] == str[high])

{

if(high - low + 1 > maxLen)

{

start = low;

maxLen = high - low + 1;

}

--low;

++high;

}

low = i - 1, high = i + 1; //Odd palindromes

while(low >= 0 && high < len && str[low] == str[high])

{

if(high - low + 1 > maxLen)

{

start = low;

maxLen = high - low + 1;

}

--low;

++high;

}

}

//print str[start] to str[start + maxLen - 1]

return maxLen;

}

Complexity: O(n²)

Longest Common Substring

Problem: Given two strings, find the length of the longest common substring.

Solution:

1. Find the length of the longest common suffix for all sub-strings of both strings and store these lengths in a table.
2. The maximum length Longest Common Suffix is the longest common substring.

Implementation:

int LongestCommonSubstring(std::string str1, std::string str2)

{

int len1 = str1.size(), len2 = str2.size(), max = 0;

int **maxLenSubStr = new int* [len1];

for(int i = 0; i < len1; ++i)

maxLenSubStr[i] = new int[len2];

for(int i = 0; i < len1; ++i)

{

for(int j = 0; j < len2; ++j)

{

if(str1[i] != str2[j])

{

maxLenSubStr[i][j] = 0;

}

else

{

if(i == 0 || j == 0)

maxLenSubStr[i][j] = 1;

else

maxLenSubStr[i][j] = 1 + maxLenSubStr[i-1][j-1];

max = max < maxLenSubStr[i][j] ? maxLenSubStr[i][j] : max;

}

}

}

return max;

}

Complexity: O(n²)


Space efficient Solution:

As we can see that only the previous column of the grid storing the dynamic state is ever actually used in computing the next column. Thus, this algorithm can be altered to have only an O(n) storage instead of O(n²). By reassigning array references between two 1D arrays, this can be done without copying the state data from one array to another. Please note that using this method, we will not be able to get the longest common substring. We can only get its length.

Implementation:

int LongestCommonSubstring(std::string str1, std::string str2)

{

int len1 = str1.size(), len2 = str2.size(), max = 0;

int *curr = new int [len2], *prev = new int[len2]; 

for(int i = 0; i < len1; ++i)

{

for(int j = 0; j < len2; ++j)

{

if(str1[i] != str2[j])

{

curr[j] = 0;

}

else

{

if(i == 0 || j == 0)

curr[j] = 1;

else

curr[j] = 1 + prev[j-1];

}

max = max < curr[j] ? curr[j] : max;

}

int *temp = curr;

curr = prev;

prev = temp;

}

delete [] curr;

delete [] prev;

return max;

}

Complexity: O(n²)

[LLD] Design ThreadPool

// Runnable is a base class for Threads
class Runnable
{
public:
Runnable(){ m_bExitRequested = false;}
virtual ~Runnable();
virtual void Run(){}
protected:
virtual bool ExitRequested(){return m_bExitRequested;}
bool m_bExitRequested;
};

// A thread.
class Thread : public Runnable
{
public:
Thread();
virtual ~Thread();
void CreateThread()
{
m_handle = _beginthread( ThreadStartFunction, 0, this );
if ( m_handle == -1 )
{
Error( "Unable to create thread." );
}
}
private:
unsigned long m_handle;
static void* ThreadStartFunction( void* pThis )
{
Thread* pThread = (Thread*)( pThis );
pThread->Run();
delete pThread;
}
};

// A thread that is added to a threadpool.
class PooledThread :
public Thread
{
public:
PooledThread( ThreadPool* pPool ):m_pPool( pPool ), m_pRunnable( NULL ){}
virtual void Run()
{
m_pPool->AddThreadToPool( this );
while ( !ExitRequested() )
{
ThreadPool::PooledRequest request = m_pPool->RemoveRequest();
if ( request.m_command == ThreadPool::PooledRequest::Exit )
break;
if ( request.m_command == ThreadPool::PooledRequest::NoOp )
continue;
if ( request.m_pRunnable != NULL )
request.m_pRunnable->Run();
}
m_pPool->RemoveThreadFromPool( this );
}
protected:
ThreadPool* m_pPool;
CCritSec m_crit;
};


class ThreadPool
{
public:
ThreadPool( int nMaxThreads = 1 ){ ResizeThreadPool(nMaxThreads);}
~ThreadPool();
void ResizeThreadPool( int nMaxThreads )
{
m_crit.Lock();
if ( m_nMaxThreads < nMaxThreads )
{
while ( m_nMaxThreads < nMaxThreads )
{
PooledThread* pThread = new PooledThread( this );
pThread->CreateThread( true );
m_nMaxThreads++;
}
}
else if ( m_nMaxThreads > nMaxThreads )
{
while ( m_nMaxThreads > nMaxThreads )
{
m_requests.push_front( PooledRequest( PooledRequest::Exit, NULL ) );
m_semRequests.Release();
m_nMaxThreads--;
}
}
m_crit.Unlock();
}
void AddRequest( Runnable* pRequest )
{
m_crit.Lock();
m_requests.push_back( PooledRequest( PooledRequest::Run, pRequest ) );
m_semRequests.Release();
m_crit.Unlock();
}
protected:
class PooledRequest
{
public:
enum Command {Exit, NoOp, Run };
Command m_command;
Runnable* m_pRunnable;
PooledRequest( Command command, Runnable* pRunnable ):m_command( command ), m_pRunnable( pRunnable ){}
PooledRequest(): m_command( NoOp ), m_pRunnable( NULL ){}
};
PooledRequest RemoveRequest()
{
m_semRequests.Wait();
m_crit.Lock();
PooledRequest request = m_requests.front();
m_requests.pop_front();
m_crit.Unlock();
return request;
}
virtual void AddThreadToPool( PooledThread* pThread )
{
m_crit.Lock();
m_threads.push_back( pThread );
m_crit.Unlock();
}
virtual void RemoveThreadFromPool( PooledThread* pThread )
{
m_crit.Lock();
m_threads.remove( pThread );
m_crit.Unlock();
}
protected:
CCritSec m_crit;
int m_nMaxThreads;
CSemaphore m_semRequests;
std::list<PooledRequest> m_requests;
std::list<PooledThread*> m_threads;
};

class CCritSec
{
public:
CCritSec(){ InitializeCriticalSection( &m_section ); }
~CCritSec(){ DeleteCriticalSection( &m_section ); }
void Lock() {EnterCriticalSection( &m_section ); }
void Unlock(){LeaveCriticalSection( &m_section ); }
 private:
CRITICAL_SECTION m_section;
};