Question
Given an array of strings with R, G & B as characters. Sort the array such that all R comes first, followed by Gs & followed by Bs.
Do it in O(n) time complexity.

For eg. array is:
I/P: G G R B R B B G R B R
O/P: R R R R G G G B B B B

Read Solution:
DNF algorithm

Happy Learning

problem: You are given an array A of size n. You are told that A comprises three consecutive runs – first a run of ’a’s, then a run of ’b’s and finally a run of ’c’s. Moreover, you are provided an index i such that A[i] = b. Design an O(log n) time algorithm to determine the number of ’b’s (i.e.,
length of the second run) in A.


Solution: We will use modified binary search to find the first occurrence of 'b'. In the similar manner we will find the last occurrence of 'b'. The final answer is (last occurrence - first occurrence +1).
Now, to find the first occurrence we have to check that if the current element is 'b' and the element before this current element is 'a'. If yes, then we got our first occurrence else we search on the right segment if the current element is 'a', else we search in the left segment.
Pseudo Code:

first_occurrence(A[],low,high)
   mid=(low+high)/2
   if(A[mid]=='b' && A[mid-1]=='a'):
       return mid
   else if(A[i]=='a'):
       return first_occurrence(A,mid+1,high)
   else:
       return first_occurrence(A,low,mid-1)

In the similar manner we can find the last occurrence. If the current element is 'b' and the next element is 'c' then it is the last occurrence of 'b'. Else we search on the left segment if the current element is 'c'. Otherwise we search the right segment.
Pseudo Code:

last_occurrence(A[],low,high)
  mid=(low+high)/2
  if(A[mid]=='b' && A[mid+1]=='c'):
      return mid
  else if(A[i]=='b'):
      return last_occurrence(A,mid+1,high)
  else:
      return last_occurrence(A,low,mid-1)

Happy Coding!!!

Asked in Microsoft Interview
Count ways to express a number as sum of consecutive numbers

Example
Input :15
Output :3
15 can be represented as:
1+2+3+4+5
4+5+6
7+8

Input :10
Output :1
10 can only be represented as:
1+2+3+4

Read solution:
SOLUTION


Happy Learning

Problem: Give an efficient implementation for a data structure STACK_MAX to support an operation maximum() that reports the current maximum among all elements in the stack. Usual stack operations (createEmpty(), push(), pop()) are also to be supported.




Solution: Instead of an array of integers, we will maintain an array of structure. The structure will comprise of 2 member variables. One that holds current element and the other holds the maximum element uptill now. The prototype is as follows:

struct Stack{
    int cur_element;
    int cur_max;
};

Stack s[MAX_SIZE];

We just need to modify the push() function a little bit.
The pseudo code for push function is as follows:

push(x,top)
    if (top==MAX_SIZE) :
       //Stack is full 
        print("Stack overflow")
    else if(top==-1) :
        //Stack has no elements
        top=0
        s[top].cur_element=x
        s[top].cur_max=x
    else :
        top=top+1
        s[top].cur_element=x
        s[top].cur_max=max(x,s[top-1].cur_max)
    return

The pop() function remains the same. In the maximum() function we just return s[top].cur_max if the stack is not empty. The time complexity for maximum() function is O(1). The overall space complexity is O(n).


Happy Coding!!!

Asked in Google Internship Interview :
Find Median from Data Stream

Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example:
[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Hint and solution :
bit.ly/solution-running-median

Happy Learning

Your are given an array of integers and an integer k of window size, you need to find minimum value in this window.
Ex. A: 1 2 3 4 5 6 and k = 3
Then output will be: 1 2 3 4
This question is similar to Maximum of all subarrays of size k

Read Optimal and Brute force solution
SOLUTION



Happy Learning

Question: A bipartite graph is a (simple) undirected graph G = (V, E) whose vertex set V can be partitioned in two disjoint subsets V1 and V2 such that V = (v1 U V2), no two vertices in V1 are connected by an edge, and no two vertices in V2 are connected by an edge. You are given a connected bipartite graph (V, E), but the sets V1 and V2 are not supplied to you. Design an efficient algorithm to compute V1 and V2. Deduce the running time of your algorithm.


Solution: The given graph is a bipartite graph, we need to figure out all the vertices in the set V1 and V2. We will use bfs ( breadth first search) here. We will maintain a bool variable (let it be named bool_flag) inside every node and then we start to travel the graph. We can choose any vertex as the source vertex here. For simplicity lets choose 1 as the source vertex. We set bool_flag for vertex 1 to 0 and for every adjacent vertex of vertex 1 we set the bool_flag to 1. We then travel all the other nodes and set bool_flag to 1 if its parent's bool_flag is 0 else we set bool_flag to 0 if its parent's bool_flag is 1. Note, since the graph is bipartite hence we will not have any cycle of odd length in the graph, hence if two vertices share an edge then the bool_flag of both of them cannot be the same or in another word, if the bool_flag of one of them is 1 then the other will have 0 as its bool_flag. After the whole process, every vertex will have either bool_flag as 0 or as 1. The vertices having bool_flag as 0 makes up one set and the vertices having bool_flag as 1 makes up another set.
The time complexity for the bfs algorithm is O(V+E).
Note: we can also use dfs for travelling the vertices instead of bfs.



Happy Coding!!!

Sliding Window Maximum (Maximum of all subarrays of size k)

Given an array and an integer K, find the maximum for each and every contiguous subarray of size k.

Examples:
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6

Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90

We have discussed the brute force and optimal solutions in a previous post.
In this post we focus on the O(n) solution and analyse time complexity of the solution.



Explanation:
We create a Deque Q of size k and maintain the following conditions:
1. Q contains only the useful elements of current window.
2. Q contains the elements in descending order.

Now what are useful elements?

Suppose the array is
{10,5,4,3,1,7,6} and k=6

We start traversing input array from index 0 and as we reach index 4 our deque Q contains
{10,5,4,3,1} as all the elements are useful.
Now after we read 7 at index 5 the elements 5,4,3,1 become useless here.
For any window afterwards if it contains 5,it will also contain 7.As 7 is greater than 5 and we are looking for maximum , 5 is useless.Similiarly 4,3,1 are also useless.
So Q contains {10,7}.
Now our window size is 6. For the next element in the array 10 is outside of the window.So We print 10 and pop it from the Q.
Q contains {7,6}.
We process all array elements one by one and maintain Q to contain useful elements of current window and these useful elements are maintained in descending order. The element at front of the Q is the largest of current window.



Pseudocode:
n=size of array
a=array
a=input
Q=deque //We will store the indices of useful elements in the deque
for i=0 to k-1:
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
for i=k to n:
print a[Q.front()]
while(!Q.empty() and Q.front()<=i-k):
Q.pop_front()
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
print a[Q.front()]



Time Complexity:
Suppose 1st k elements of input array are in descending order.So after passing through 1st k elements of input array deque contains k elements.
Let's say each of remaining (n-k) elements will be greater than half of elements present in deque.To insert (k+1)th element we have to make (k/2+1) comparisons and after insertion there will be(k/2) elements in the deque. To insert (k+2)th element we have to make (k/4+1) comparisons and after insertion there will be (k/4) elements in the deque.So to insert all the elements of input array in the deque total number of comparisons will be:
k+((k/2+1)+(k/4+1)+(k/8+1)+......(n-k) terms....)
= (k + k/2 + k/4 + ....(n-k+1) terms.....) +(n-k)
= ( k * (1 - (1/2)^ (n-k+1)) / (1-1/2) ) +(n-k)
= 2 * k * (2 ^ (n-k+1)-1) / (2^(n-k+1)) +(n-k)
≅ 2 * k *(2^(n-k+1)) / (2^(n-k+1)) +(n-k)
≅ 2*k + n - k
≅ n + k
So time complexity of above algorithm is O(n+k) i.e O(n) as (k<=n).



Code:
CODE


For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Range update query
Consider an array A[] of integers and following two types of queries.

update(l, r, x) : l is left index, r is right index and x is value to be added i.e add x to all values from A[l] to A[r] (both inclusive).
printArray() : Prints the current modified array.


Solution:

Using Prefix Array:
Take an array pref of same size as input array.Initialize it with 0.

1.Upadate(l,r,x):
Add x to pref[l] and substract it from pref[r+1]
i.e we do pref[l]+=x , pref[r+1]-=x

2.PrintArray():
Take prefix sum of pref array i.e
for i=1 to n-1
pref[i]=pref[i]+pref[i-1]
Now, for all elements of input array
do A[i]=A[i]+pref[i] and print them

Here update range operation is performed in O(1).
printArray is performed in O(n).


Pseudocode:

n=size of array
A=array
pref=array
initialize pref with 0
A=input

update(l,r,x):
  pref[l]+=x
  if(r+1<n)
    pref[r+1]-=x

printArray():
  for i=1 to n-1
    pref[i]=pref[i]+pref[i-1]
  for i=0 to n-1
    A[i]=A[i]+pref[i]
  for i=0 to n-1
    print A[i]
    print " "
  print "\n"

Code:
CODE



Using Difference Array:
Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0]

1.Upadate(l,r,x):
Add x to D[l] and substract it from D[r+1]
i.e we do D[l]+=x , D[r+1]-=x

2.printArray():
Do A[0] = D[0] and print it.
For rest of the elements, do A[i] = A[i-1] + D[i] and print them.

update range operation is performed in O(1).
printArray is performed in O(n).

Pseudocode:
n=size of array
A=array
D=array
A=input

D[0]=A[0]
for i=1 to n-1
D[i]=A[i]-A[i-1]


update(l,r,x):
D[l]+=x
if(r+1<n)
D[r+1]-=x

printArray():
A[0]=D[0]
for i=1 to n-1
A[i]=A[i-1]+D[i]
for i=0 to n-1
print A[i]
print " "
print "\n"

Code:
CODE


For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Problem: Let A be an unsorted array of n floating numbers. Propose an O(n) time algorithm to compute the (floating-point) number x (not necessarily an element of A) for which max|A[i] - x| is as small as possible for all 1 <= i <= n. (Here |y| means absolute value of y)

Solution: The problem statement can be interpreted as finding a point x such that it's distance from the farthest point is minimized (since, |A[i] - x| is given which is actually distance between two point). Note: we don't need to minimize distance from every point, we just need to minimize the distance of the point which is farthest to it. So we try to put our x as close to the farthest point. But in doing so the point which is near may go far. So the optimal solution is finding the minimum point in the array A (let it be named MN) and finding the maximum point of A (let it be named MX) and the result is the mid-point of these two points, i.e x=(MN+MX)/2. Note: All other point between MN and MX will have distance lesser hence we do not bother it. We could not get more optimal point than this one. Now, MX and MN can be easily determined by travelling once the array. Hence the time complexity is O(n).



Happy Coding!!!

Problem: Hamming distance between two string of same length is the number of positions in which the corresponding character of two string differs. For example the hamming distance between "abc" and "abd" is 1 and between "abcd" and "acdb" is 3. Palindromic distance of a string is hamming distance between the string and it's palindrome. Write a recursive function that will compute the palindromic distance of a given string.

Solution: The solution is very simple and straight-forward. We create a function named pallin_dist(char ch[1...n]). We compare the first character and the last character of the string. If the the character doesn't match then we simply set the ans by 1 else we set the ans as 0. We then call pallin_dist(ch[2...n-2]) on ch[2,......,n-2] and increase the ans by the value returned by this function. We then return the ans. Here is the pseudo-code for the function:

int pallin_dist(char ch[],int start,int end):
    if(end==-1):    //i.e end of string
        return 0
    ans=pallin_dist(ch,start+1,end-1)
    if (ch[start]==ch[end]):
        return ans
    else:
        return ans+1

Happy Coding!!!

Hello Everyone!!

Problem Link: CHEFWAR

Problem:
Bitland declared war on Chefland and sent an army to fight them, but Chefland defended efficiently and Bitland's army has been reduced to N soldiers. They have no chance of winning the war and do not want to surrender, so they are planning to commit group suicide. Josh, the leader of Bitland's remaining soldiers, has different plans — he wants to survive and somehow escape.

The soldiers are numbered 1 through N; Josh is soldier N. The soldiers are going to stand in a circle in the order 1,2,…,P−1,N,P,P+1,…,N−1. Formally, they are standing in the circle in such a way that if Josh's position is P (1≤P≤N), then for each i (1≤i≤N−2, i≠P−1), soldier i+1 is directly to the right of soldier i, soldier P (if P≤N−1) or 1 (if P=N) is directly to the right of Josh and Josh is directly to the right of soldier P−1 (if P≥2) or soldier N−1 (if P=1); if 2≤P≤N−2, soldier 1 is also directly to the right of soldier N−1. For each i (1≤i≤N−1), soldier i has a sword with power Ai. Josh plans to take a shield with sufficiently high defense power D.

First, the soldiers start to commit group suicide according to the following rules:

Initially, soldier 1 is the attacking soldier.
If the attacking soldier is not Josh, this soldier attacks the soldier that is currently to his right.
When Josh is attacked with power a, the current defense power of his shield decreases by a, and if it becomes negative, Josh dies. When a different soldier is attacked, he does not try to defend and dies immediately. The power of the attacking soldier's sword does not change.
Then, the next living soldier to the right of the current attacking soldier becomes the attacking soldier and the process continues until there is only one soldier left.
It is clear that this way, Josh cannot be the last survivor. However, Chefland's general Chef plans to interrupt this process as soon as there are exactly two living soldiers of Bitland left (Josh wants to be one of them) by attacking them with Chefland's full firepower F. Since this attack is unexpected, both attacked soldiers try to defend independently with the weapons they have. Josh survives if the current defense power of his shield is at least F. Any other soldier survives only if the power of his sword is strictly greater than F. Since Chefland does not attack again, if both Josh and another soldier survive, then the other soldier will kill Josh. Therefore, Josh wants to be the only survivor of Chefland's attack.

Your task is to find the minimum possible value of D such that Josh survives if he chooses his position P optimally (or determine that he cannot survive) and the lowest position P such that Josh survives if he takes a shield with this defense power D.

Input:
• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains N−1 space-separated integers A1,A2,…,AN−1.
• The third line contains a single integer F.

Output:
For each test case, first, print a line containing the string "possible" if Josh can survive or "impossible" if he cannot (without quotes). Then, if he can survive, print a second line containing two space-separated integers P and D.

Constraints:
• 1≤T≤1,000
• 2≤N≤1,000,000
• 1≤Ai≤10,000 for each valid i
• 1≤F≤10,000
• the sum of N over all test cases does not exceed 1,000,005

Example Input:
2
5
12 34 45 5
10
5
10 15 43 20
5

Example Output:
possible
4 100
impossible

Explanation:
Example case 1: When Josh is at the position P=4, the soldiers' initial powers in clockwise order around the circle, starting with soldier 1, are [12,34,45,D,5] (D denotes Josh). Then, the following happens:
The soldier with power 12 attacks the soldier with power 34 and kills him.
The soldier with power 45 attacks Josh, who defends. The living soldiers' powers are now [12,45,D−45,5] and Josh is the attacking soldier.
Josh does not attack, so the soldier to his right (with power 5) becomes the attacking soldier. He attacks the soldier with power 12 and kills him.
The soldier with power 45 attacks Josh again and Josh defends again.
The soldier with power 5 attacks the soldier with power 45 and kills him.
Now, two soldiers are left: Josh (with a shield with defense power D−90) and the soldier with a sword with power 5. Each of them is attacked with firepower F=10, so the power of Josh's shield drops to D−100 and the other soldier dies.
If Josh survives, his shield's initial power D should be at least 45+45+10=100. For all other positions P, Josh cannot survive.

Example case 2: Regardless of how large D is and which position Josh chooses, after Chefland's attack, a soldier of Bitland other than Josh will always survive. This soldier will then attack Josh until his shield breaks and he dies.




Solution:
EDITORIAL

Pseudocode:

int Damage(int n, int a[],int p)
  int s = (n-(p+1)) + ceil(p/2)
  int d = 0
  if(p%2 != 0)
    d = d + a[p]
  int last = s
  int step = 2
  while( last != 1)
    if((last-1)%step==0)
      if(last<=(n-(p+1))
        d = d + a[last+p]
      else
        d = d + a[2*(k-n+p)+1]
    else
      last = ((last-1)-(last-1)%step)+1
    step = step*2
  return d

int n,f
n,f=input
n=n-1
int a[n+1]
a[0] = 0;
for i = 1 to n
    a[i]=input
int result[n]

initialize result with -1

for i=0 to n 
    if(a[i]<=f)
        result[i]=damage(n,a,i)
int count=0
for i=0 to n
     if(result[i]!=-1)
         count=count+1
if(count==0)
      print "impossible"
else
      int index=n+1
      int min_damage=INT_MAX
      for i = n to 0
           if(result[i] != -1 && result[i]<=min_damage)
                 index=i
                 min_damage=result[i]
      print "possible\n"
      print index+1
      print min_damage+f

Code:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Problem 1: What will be the output of the following C code:

int fun(char *x){
char *ptr=x;
while(*ptr!=0)ptr++;
return (ptr-x);
}
int main(){
char str[30]="This is PDS test";
printf("%d",fun(str));
}

(a) 4 (b) 16
(c) 17 (d) 30



Problem 2: What will the following code print:

int main(){
int array[4]={20,18,16,14};
int *ptr=array;
printf("%d,%d",*ptr+2,*(ptr+2));
}

(a) 16,16 (b) 20,16
(c) 22,16 (d) 22,22



Problem 3: Which of the following line will give an error if we declare array A, B, C as:

int *A,*B,C[10];

(a) A=B;. (b) B=A+10;
(c) B=C+20; (d) C=B+30;


Problem 4: What will be the output of the following C code:

int main(){
int arr[3]={1,2};
int i;
for(i=0;i<3;i++){
printf("%d ");
}
}

(a) compilation error
(b) 1 2 0
(c) runtime error
(d) 1 2 garbage-value
(e) 1 2 3


Solution 1: (b) 16

Solution 2: (c) 22,16

Solution 3: (d) C=B+30;

Solution 4: (b) 1 2 0



Additional task for viewers:
Try to figure out why the outputs were so.






Happy Coding!!!

Problem:
We have an array arr[0 . . . n-1]. We should be able to
(1) Find the sum of elements from index l to r where 0 <= l <= r <= n-1

(2) Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

Solution:
We can solve this problem using different datastructures. The main purpose of this problem is to introduce some datastructures which are useful to find optimized solutions in many cases.

Prefix Array:
Given an array arr[] of size n, its prefix sum array is another array prefixSum[] of same size such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] … arr[i].

void precompute(int prefixSum[])
prefixSum[0]=arr[0]

for i=1 to n-1 prefixSum[i]=prefixSum[i-1]+arr[i]

int rangesum(int l,int r,int prefixSum[])
if(l=0)
return prefixSum[r]
else
return prefixSum[r]-prefixSum[l-1]

void update(int i,int x,int prefixSum [],int arr[])
int diff = x-arr[i]
for j=i to n-1
prefixSum[j]=prefixSum[j]+diff
arr[i] = arr[i] + diff

Time complexity of range sum query is O(1)
and update query is O(n)

Binary Indexed Tree:
DETAILS
Binary Indexed tree or Fenwick tree takes O(logn) complexity for both range sum operation and update operation.
Compared with segment tree , binary indexed tree requires less space and is easier to implement.

Segment Tree:
DETAILS
Segment tree also performs both range sum operation and update operation in O(logn) time.

Square Root Decomposition:
DETAILS
The key concept of this technique is to decompose given array into small chunks specifically of size sqrt(n).
The time complexity of range sum query is O(sqrt(n)) in worst case.
The time complexity of update query operation is O(1).

Solve different problems using these datastructures to become proficient in applying them in various competitive programming problems.

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Jump Game

Difficulty level : Medium


Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Hint / Solution Link :
SOLUTION

Microsoft Interview Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.


Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]


Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?


Solution:
SOLUTION

"What are the algorithms required to solve all problems (using C++) in any competitive coding contest?"
Answered by Mostafa Saad Ibrahim, ACM ICPC World Finalist, Problem Setter

Here is my helper list. It lists most of needed algorithms/concepts.Some elements are not algorithms (e.g. Fake, States/Concerns) and little repetitions.

But 1 final advice: Initially, Given great attention to thinking skills rather than the knowledge. This is helpful for both competitions and your future. To do so, make sure you are so good in adhocks, where no algorithms are required, just pure thinking.

Asked in Amazon Interview

Find Longest Palindrome in a String : Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

NOTE: Required Time Complexity O(n^2).

Example:
Input:
1
aaaabbaa

Output:
aabbaa

Solution:
https://www.linkedin.com/feed/update/urn:li:activity:6594490601763364864

Problem : Merge Intervals
Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.


Solution:
SOLUTION

Elevator Problem

A building has floors numbered 0 through n≤10^18. There is a single elevator with four buttons: "go to floor 0", "+a floors", "+b floors", and "+c floors". We have a,b,c≤ 10^6. Compute the number of unreachable floors.


Solution:

This feels like a number theory problem, but trying to solve it by GCDs and casework will not lead to success. Instead, treat it as a graph theory problem. First, note that if you can reach floor x, you can reach all floors of the form x+k*a. Hence, for each remainder modulo a all we need is the smallest reachable x with this remainder. These can be found by using Dijkstra’s shortest path algorithm on a graph with a nodes. The nodes are the remainder classes, and from each node there are two edges, corresponding to +b and +c.

The stunning thing about this problem is the asymmetry of the solution: you are treating one button differently from the other two.

Credits : Michal Forišek on Quora, scientist, competitive programmer