Nearest smaller numbers on left side

Problem: Given an array of integers, find the nearest smaller number for every integer on its left side.

Solution: Use stack.

Implementation:

void printNearestSmaller(int arr[], int len)
{
if(len <= 0)
return;

std::stack<int> st;
for(int i = 0; i < len; ++i)
{
while(!st.empty() && st.top() >= arr[i])
st.pop();

if(st.empty())
std::cout<<"-\t";
else
std::cout<<st.top()<<'\t';
st.push(arr[i]);
}
std::cout<<std::endl;
}

Complexity: O(n)

Microsoft Question: Sort an array such that all odd numbers are in left side and sorted in increasing order where all even numbers are sorted in decreasing order and come after the odd numbers.

Problem: Sort an array such that all odd numbers are in left side and sorted in increasing order where all even numbers are sorted in decreasing order and come after the odd numbers.

Solution: Segregate the odd number and even numbers and then sort these sub arrays separately in ascending and descending order.

Implementation:

void sortOddEven(int arr[], int len)

{

int i = 0, j = len - 1;

while(i < j)

{

while((arr[i] % 2 != 0) && (i < j))

++i;

while((arr[j] % 2 == 0) && (i < j))

--j;

if(i < j)

{

std::swap(arr[i], arr[j]);

++i;

--j;

}

}

std::sort(arr, arr + i);

if(i < len)

std::sort(arr + i, arr + len, std::greater<int>());

}

Complexity: O(nlogn)

Amazon Question: Best time buy sell stock

Problem: Given an array in which its i^th element is the price of the stock on day i, design an algorithm to maximize the profit than can be made by buying and selling the stock on these days.

Note that you can not engage in multiple transaction at the same time i.e. you must sell the stock before you buy again. 

Solution: Take the following steps:

1. Start from the start and go until prices[i + 1]  > prices[i].
2. i + 1 is the day for buying the stock.
3. Now again traverse the array and go until prices[i] < prices[i - 1].
4. i - 1 is the day for selling the stock.
5. Push these days to result.
6. Repeat the above steps until you reach the end of the given array of stock prices.

Implementation:

void stockBuySell(std::vector<int>& prices)

{

int len = prices.size();

if(len <= 1)

return;

int i = 0;

std::vector<StockBuySellPrices> result;

while(i < len - 1)

{

while((i < len - 1) && (prices[i+1] <= prices[i]))

++i;

if(i == len - 1)

break;

StockBuySellPrices price(prices[i++]);

while((i < len) && (prices[i] >= prices[i-1]))

++i;

if(price.buy < prices[i - 1])

{

price.sell = prices[i-1];

result.push_back(price);

}

}

len = result.size();

int totalProfit = 0;

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

{

std::cout<<i<<": Buy at price: "<<result[i].buy<<" and Sell at price: "<<result[i].sell<<'\n';

totalProfit += (result[i].sell - result[i].buy);

}

std::cout<<"Total Profit: "<<totalProfit<<std::endl;

}

Complexity: O(n)

Synopsys Question: Sort array which contains only 0 and 1.

Problem: Sort a given array which contains only 0 and 1.

Solution: Take two pointers; one from start and one from end. Move them towards each other until start is pointing to 1 and end is pointing to 0. In this case swap the elements.

Implementation:

void sortArray(int arr[], int len)
{
int l = 0; int r = len - 1;

while(l < r)
{
while(arr[l] == 0 && l < r)
++l;
while(arr[r] == 1 && l < r)
--r;
if(l < r)
{
std::swap(arr[l], arr[r]);
++l;
--r;
}
}
}

Complexity: O(n)

Paytm Question: Coin change problem

Problem: Find the number of ways of making changes for a given amount of Rupees/Cents etc.

Solution: Following are the steps to achieve the desired result -

1. Construct a table of size value + 1 where table[i] will tell the number of changes available using given coins.
2. Base case is 0 where table[0] = 1 as there is only one way to get the change of 0 i.e. leaving all coins.
3. Fill the table in bottom up manner by picking all coins one by one and update the table[j] where coins[i] <= j <= value.
4. table[n] contains the desired result.

Implementation:

int countChange(int coins[], int numOfCoins, int value)

{

int *table = new int[value + 1];

table[0] = 1;

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

table[i] = 0;

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

{

for(int j = coins[i]; j <= value; ++j)

table[j] += table[j - coins[i]];

}

return table[value];

}

Complexity: O(mn)

Paytm Question: Minimum distance between two numbers in an array

Problem: Given an unsorted array and two numbers num1 and num2, find the minimum distance between num1 and num2 in the given array.

Solution:

1. Traverse array from start and once either num1 or num2 are found, store the index of this occurrrence in a variable prevIndex.
2. Going ahead if the number at current index matches with either num1 or num2 then check if it is different from element at prevIndex. If yes, then update the minimum distance if needed. Make prevIndex = current index.

Implementation:

int minDistance(int arr[], int len, int num1, int num2)

{

int minDist = INT_MAX;

int prevIndex = -1;

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

{

if(arr[i] == num1 || arr[i] == num2)

{

if(prevIndex == -1)

prevIndex = i;

else

{

if(arr[i] != arr[prevIndex] && (i - prevIndex) < minDist)

minDist = i - prevIndex;

prevIndex = i;

}

}

}

return minDist;

}

Complexity: O(n)

Reverse a Linked List in groups of given size

Problem: Given a linked list, write a function to reverse every k nodes.

Solution: Tweak the reverse method to get the desired result.

Implementation:

//Public interface
void List::reverseK(int k)
{
if(!head || k == 0)
return;

head = reverseK(head, k);
}

//Actual Implementation
List::ListNode* List::reverseK(List::ListNode *node, int k)
{
ListNode *curr = node;
ListNode *next = 0, *prev = 0;
int count = 1;
while(curr && count <= k)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
++count;
}

if(next)
node->next = reverseK(next, k);
return prev;
}

Complexity: O(n)