Matrix : Not as complex as movie

1. Given a N x M matrix, print all elements in it in spiral order.

2. Given a N x N matrix, rotate the given matrix by 90 degree.

3. Given a N x M matrix, replace a row and column with 1 if any position in that row or column has 1.

These are three standards questions which are asked regularly in technical interview which do not involve any algorithm as such. Just working around with matrix indices will suffice for solving these problems.

Problem 1:   Given a N x M matrix, print all elements in it in spiral order.

Analysis

Let’s understand what the spiral traversal means. Below diagram explains spiral traversal.

Spiral traversal will be
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25

What we do in that? We traverse first row, then last column, last row and then first column. Once done we move inside and our size of matrix now becomes N-2 and M-2 as we have already traversed two rows and column in first round. Again traverse, second row from second column, till newly adjusted column length. Traverse last column starting between newly adjusted rows, as first and last are already traversed. Go on till we have traversed all elements.
Figure shows how the traversal happens.



Code

Complexity Analysis

Complexity of rotation of matrix code is O(N^2).

Problem 2 : Given a N x N matrix, rotate matrix by 90 degree.

Rotation by 90 means first column of matrix becomes first row of matrix, second column becomes second row and so on. Below diagram shows a original matrix and rotated matrix.

This problem actually extend the problem 1. In this case we need to traverse layer by layer, more we have to swap elements too. If we look closely, we figure out that how elements are exchanged. 

Code

Complexity Analysis

Complexity of spiral printing or traversal of matrix code is again O(N^2).

Problem 3 :Given a N x M matrix, replace a row and column with 1 if any position in that row or column has 1.

Analysis

This problem can be easily solved using two arrays, one for row and one for column. Row array has index set if corresponding row in matrix has any element as 1. Similarly for column array.
Once these two array are filled, go through these arrays and fill ones in rows and columns whose indices are set in row and column array respectively.

Interviewer will ask definitely ask you for space optimization. Here comes the below solution.
have two bool variables. First indicates if there is any one in first row matrix. Second indicates if there 1 present in first column of matrix. 
Once done, reuse first row and column as two arrays in above approach. 

Code

Complexity Analysis

Replacing row and column with 1 with given condition also has complexity of O(N^2).

Strings : Remove duplicate characters from string

Remove duplicates characters from string

Given a string S, remove all the duplicate characters. Only one instance of character should remain in resultant string.
This is very trivial problem asked during interviews. It checks two fundamentals. One ability to work with string and other familiarity with concept of hash.

Analysis

Brute force algorithm to remove duplicates from string would be do scan whole array for the given character and remove all its instances.Once done for all characters, arrange remaining characters in emptied spaces. Complexity of above algorithm will be O(N^2).
How can we identify that we have seen this character before? If we somehow keep track of already visited characters we can do so. What better than having a hash table for characters. Increment the count when character is seen first time (Count will be zero this time). If the character index is not 0, that means we have already seen this character., skip the processing on it.

Above step will remove duplicates but will create whole in the string. Standard way to modify string in such cases is to use two pointers, one as source and other as destination. For detail on this method and its other applications see this  Arrays : Move all zeros at the end of the array

Code to remove duplicate from string

Complexity Analysis

Complexity of above code will be O(N)with constant memory requirement.

Encode a string

Another problem which can be solved with same concept of source and destination pointers in string is following :  Encode a given string such that character is followed by the number of consecutive instances of it in string.  For example “aaaabbbbccccc” is encoded as a4b4c4.

Analysis

We have already seen a problem where we remove consecutive duplicates from an array. This problem is extension of that problem.

Code

Arrays : Problems with rotated array

I have seen many variants of problems where given array is sorted but it is rotated K time. Rotation here means last element of array becomes first and first is moved to second, second to third and second last element to last position. This is K=1 rotation. Fro K=2, same procedure is repeated. 
Look at this example.

Normal sorted array
Rotated sorted array

There are some problems which are based on this which are generally asked during telephonic or online coding rounds. Below is the list:

1. Given a sorted array, rotated K times (K not known), Find K or pivot at which it is rotated. 
Same question can be paraphrase to ask for minimum element in such an array.
2. Given an sorted array rotated K times (K not known), find an element in it.
3. Rotate an array K times (Finally K known)!


Let’s analyse and see solution for each of above problem.

Problem 1: Find minimum element or find K for which array is rotated.

There is simple brute force algorithm with O(N) complexity, that is to scan through array and check for each element for following condition. 
Element which satisfy above condition, is our required element.

Now question is can we do better? 
Idea here is that all the elements on the right side of pivot or minimum element will be greater than it.
We randomly pick any element and check if all elements on the right side are greater. We don’t need to go through each element, compare it with the last element, if last is greater, we are good. (Remember we are working sorted array).

It is necessary condition but is this sufficient condition?
No, as any number after pivot will satisfy that condition. What is unique to pivot then? It is that element just before pivot is greater than pivot.  Combine these conditions and we can find our pivot.
How can we select the element. Well, just take the middle element and if first condition is satisfied and second not, we look in lower part of the array.
If first condition is not satisfied, we look in the upper part of the array.

Code

Complexity Analysis

Complexity of above code is O(log N).

Problem 2: Find an element in a sorted rotated array

Analysis

Again brute force algorithm gives us O(N) complexity solution. Can we do better? Can binary search algorithm be applied here?

How to eliminate sub arrays?

If mid is equal to element we are looking for, return mid.
If not, what are the cases?
Case 1 : If the lower half of the array is sorted. 
         (check if A[mid] >= A[start])
         Check if the element being looked for is greater than A[start]  
           and less than A[mid]
         discard the upper array we have to look in lower array.
         Else look in upper sub array.

Case 2 : If lower array is not sorted.
        If element is greater than A[mid] && less than A[end], look in 
        upper sub array.
         else look in lower sub array.

Code

Queues : Print last N lines of a file

Log file monitoring : Print last N lines of file

After going through many interview experiences at Microsoft on geeksforgeeks.org, I found that one question regularly features in majority of interviews, so I decided to solve it and write a post on it.
Problem statement is such that : given a log, file print last N lines of that file. Another way to ask same problem is to ask how tail -f command is implemented in Unix.

Analysis

There are two parts of given problem, one is related to file operations. We need to open a file, get input from the file stream till End of File and then close the stream.

Second part is to maintain last N lines we have seen till now. In other words, we have to maintain lines which are most recent, those which have come last. That automatically implies that we need to remove lines which have come earlier. Points to first in Fist out kind of scheme. What data structure supports that? Definitely Queue.

Great! We zeroed in on data structure, let see how we can do the needful.

Algorithm to print last N lines of file

  1. Read each line from file.
  2. If size of queue is less than N, we simply enqueue the line in queue.
  3. If size of queue is greater than N, dequeue line from front and enqueue new line at the end.
At any given point of time, queue will contain N last line seen in file.

Word on implementation
We have used fgets to read lines from the file.  fgets() reads characters from current stream pointer to first ‘n’ character (including), or till number of characters read is equal to number provided in argument, whatever is encountered first.
It returns the pointer to string if buffer reading is successful and NULL at end of file.

Code

Arrays : Event Scheduling problem

Any event has two time stamps, it’s start time and end time. When we have to schedule number of events on to particular resource, we need to take care that no two events are no overlapping, that is to say second event cannot be scheduled while first running.

Problem statement

Given a set of jobs S with their start time and end time, find out largest set R such that all events in R are mutually compatible. Two events are compatible if they do not overlap.

Analysis

First thing we get from the problem is we need to maximize the output with a given constraint. Great! What template this problem fit in? It’s greedy algorithm.
We need to select each job which maximizes the output, i.e gives us maximum number of compatible jobs. What should be the selection criteria for the job?
There are three criteria we can think of :
1. We take job with earliest start time first.
2. We take job with earliest end time first.
3. We take job with minimum number of overlapping jobs.
4. Or we take the shortest job first.

Let’s take some examples and see how things work out with each criteria.

1. Earliest  start time first
Earliest Start time first
2. Minimum number of conflicting jobs
Least conflicts
3. Shortest job first.
With shortest event first

So we get from above figures that these three criteria cannot give us optimum output. If we take job with earliest finish time, we can find out the optimal set.

Algorithm

  1. Take the job which has earliest finish time.
  2. Now eliminate all events which have start time less than selected job’s end time.
  3. Add first event to which has start time greater than selected end time set
  4. Repeat Step 2 and 3 till we have considered all jobs.

Word on implementation
Sort all jobs which based on end time and then go for the above algorithm.

Code

Complexity analysis

Complexity of algorithm is dominated by the sorting which is O(N log N).

Reference 

Arrays : Minimum jumps to reach at end

Minimum number of jumps to reach end

Given an array of integers, one can maximum jump a[i] from a given index i. Find minimum number of jumps required to reach at the end of the array.

For example,In following array, minimum number of jumps is 2.

At 2 we can either jump 0, 1 or 2 indices at a time. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4.
However if we jump only one index, next time we will reach at the end of the array

Solution with 3 jumps
minimum jumps to reach at end of array
Solution with 2 jumps

Analysis

While finding minimum jumps to read end we need to minimize something, that is jump. How can we do that? We take longest jump possible from each index. While taking jump we also take care that which among the possible landing indexes can give us maximum jump ahead. So every time we land, we have selected that index because it will give us maximum jump. Just greedy algorithm.
Mathematically,
for index i, scan through all indices e from i+1 till e = i + a[i] and calculate a value v = e +a[e]. Take e with maximum v.

let’s work out an example:
In above example, for i =0, we check e = 1 and v = 1 (e)+3 (a[e]) =4
                                     e = 2 and v = 2 + 1 = 3
So we select e =1.

What will be the complexity of the code? It would be O(N).  Can we solve this using dynamic programming?

What we need to find minimum jumps to reach Nth index. We can reduce this problem like,
If we find minimum number of jumps for 0 and N-1 and can reach from any of them to Nth item, jumps for Nth index would be one more than that. 
If i +a[i] >= N and if Jumps[i] +1 < Jump[N], Jump[N] becomes Jumps[i] +1
For starting index, jumps required would be zero. 

Code to minimum number of jumps algorithm

Complexity Analysis

Complexity of the algorithm would be O(min(k,N) *N) along space complexity of O(N), where K is maximum jump.

Strings : Ransom Note from Magazine

Ransom note from magazine

Kidnapper kidnaps you and writes a ransom note. He does not write it with hand, as handwriting can put him in, so reaches to a magazine at table and creates ransom note. We need to find out given ransom string and magazine string, is it possible to create given ransom note. Kidnapper can use individual characters of words.

Analysis

We need to check if magazine string contains all characters and in equal or greater number, present in ransom note.
How can we keep track which characters are present and how many instances of characters are present in magazine string? Simple standard technique. Create a hash table with 256 values, where key is character, and value as the number of instances it occurs.

Now go through each character in ransom note, and decrement corresponding value in hash table. 
If we try to decrease a value already zero,  we return false. If we reach at the end of ransom note, we return true.

Code ransom note problem

Complexity of code is O(M) where M is length of magazine string.

We can better this. In that method we don’t scan magazine string and ransom note separately but simultaneously. We scan character from ransom note, and check in hash table, if we find good. If not, we scan magazine string till we find the desired character. 
If we reach end of magazine string, return false.
If we reach end of ransom note, return true.

Variation

What if kidnapper cannot use individual characters, but he can use complete words?

Simple again, store all words in magazine in trie with leaf node containing the count which words occurs in it.
Every time we need a word for ransom note, we find word in trie and decrement the count if word is present. If we are trying to decrement a count which is already zero, return false.

I am leaving implementation for now. Basic of trie can be read here. Trie Basics