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)

Google Question: Reverse linked list without using recursion.

Problem: Reverse the linked list without using recursion.

Solution: It is straight forward, can be easily understood by implementation.

Implementation:

        public void Reverse()

        {

            LinkedListNode prev = null, curr = this.Head;

            while (curr != null)

            {

                var next = curr.Next;

                curr.Next = prev;

                prev = curr;

                curr = next;

            }

            this.Head = prev;

        }

Complexity: O(n)

Amazon Question: Flatten a multilevel linked list

Problem: Given a linked list where in addition to the next pointer, each node has a child pointer, which may or may not point to a separate list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. You are given the head of the first level of the list. Flatten the list so that all the nodes appear in a single-level linked list. Flatten the list in way that all nodes at first level should come first, then nodes of second level, and so on.

Solution:

Follow the following steps:

1. Take "curr" pointer pointing to head of the list.
2. Take "tail" pointer pointing to end of the first level of the list
3. Repeat the following steps until curr != tail
1. if curr has child then:
• Append this child to the tail
• Make the tail points to the end of this child's list.
2. Assign curr->next to curr.

Implementation:

//Structure of the node

struct Node

{

Node *next;

Node *child;

int data;

Node(int d, Node* n = 0, Node* c = 0):data(d), next(n), child(c){} 

};

void ListWithChild::flattenList()

{

if(!head)

return;

Node *tail = head;

while(tail->next)

tail = tail->next;

Node *curr = head;

while(curr != tail)

{

if(curr->child)

{

tail->next = curr->child;

while(tail->next)

tail = tail->next;

}

curr = curr->next;

}

}

Complexity: O(n)

Carwale Question: Find a triplet in an array that sum to given value

Problem: Given an array and a value, find if there is a triplet in array whose sum is equal to the given value.

Solution: Use sorting.

Implementation:

void findTriplet(int arr[], int len, int sum)
{
if(len < 3)
{
std::cout<<"Length is less than three\n";
return;
}
std::sort(arr, arr + len);

for(int i = 0; i < len - 2; ++i)
{
int left = i + 1, right = len - 1;
while(left < right)
{
int currSum = arr[i] + arr[left] + arr[right];
if(currSum == sum)
{
std::cout<<"Found Triplet:: "<<arr[i]<<' '<<arr[left]<<' '<<arr[right]<<'\n';
return;
}
else if(currSum < sum)
++left;
else
--right;
}
}

std::cout<<"Triplet not found\n";
}

Complexity: O(n²)

Equilibrium point of an array

Problem: Equilibrium point of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

Solution: Get total sum of array first. Then Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get right sum by subtracting the elements one by one. 

Compare left and right sum, if they are equal then current index is the equilibrium point.

Implementation:

int equilibriumPoint(int arr[], int len)

{

if(len == 0)

return -1;

int sum = 0;

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

sum += arr[i];

int leftSum = 0;

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

{

sum -= arr[i];

if(leftSum == sum)

return i;

leftSum += arr[i];

}

return -1;

}

Complexity: O(n)