Interviewstreet Challenge: Even Tree

Problem

https://www.interviewstreet.com/challenges/dashboard/#problem/4fffc24df25cd

You are given a tree (a simple connected graph with no cycles).You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest contains even number of vertices

Your task is to calculate the number of removed edges in such a forest.

Input:
The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. 2 <= N <= 100.
Next M lines contains two integers u_i and v_i which specifies an edge of the tree. (1-based index)

Output:
Print a single integer which is the answer

Sample Input 

10 9

2 1

3 1

4 3

5 2

6 1

7 2

8 6

9 8

10 8

Sample Output :

2

Explanation : On removing the edges (1, 3) and (1, 6), we can get the desired result.

Original tree:


Decomposed tree:

Note: The tree in the input will be such that it can always be decomposed into components containing even number of nodes. 

Analysis

All Java Solutions on the InterviewStreet needs to run in 5 seconds with 256 MB maximum RAM available. So that means our solution can never be "Brute-Force" or O(n^2). Same applies to the space complexity.

Well this is an interesting problem. Initially it appears to be a problem of n-ary trees. But to build a tree and perform the decomposition on the trees, it is time consuming. So I approached it with a Map approach. And well all my 10 testcases took around 1 sec only.
Create a map with parent as key and list of all its children. Now once this map is created, then take the root. Get each of its children from the list. So we have 1 as the node and 2, 3, 6 as children. So take 2. Check if the total number of nodes under it are even or odd (I am using a recursive call here to get the count.) In this case we have only two nodes - 7 and 5 (even number of nodes). So we cannot remove the link 1-3. Since that leaves with a subtree with 3-nodes (2, 7 and 5) which is not even number. So do not increment the count. However remove 2 from the list of 1's children and add 7 and 5 to the list. 
Now take 6, it has 3 children (8, 9 and 10). So the link 1-6 can be removed. Increment counter, remove 6, add 8, 9 and 10 to the list.
The next entries 7, 5, and 4 have no children. Continue to 8. It has 2 children, hence cannot remove.

Now take the next element in the list - it is 3. It has only 1 child (odd number). So that means we can break 1-3 link. Increase the counter, remove 3 and add 4 to the list.

Solution

5 Solutions for Search

Search has been a favorite topic of today and there are a lots of algorithms around it. Its all due to the rise in the data generated by systems and the increase in storage capacity. So we would need more faster and efficient algorithms to search. Today we will discuss Search in-depth, and look at multiple algorithms. I am limiting the solution to 5, but there are tons of other solutions not discussed here.

Types of Search

1. Fixed Text Base and Variable Pattern - In this type of search, we have a more or less fixed data set on which we repeatedly search. But each time we search for a different pattern. This is more or less like a web search. Lets take Google as an example. There are huge number of documents that has to be searched. So the crawlers index the web and build a data structure. So the data set is fixed now. Our search operates on this data set.
2. Variable Text Base and Fixed Pattern - In this type of search, we have the data set changing regularly. But we search for the same pattern every time. This is employed in censoring applications, e.g. News Feed. The feed comes in continuous fashion. On this we search if it contains any abusive words. 
3. Variable Text Base and Variable Pattern - In this pattern, the data keeps changing and so also our queries. This is a common one. 

Solution:1 - Naive or Brute-Force approach

This is one of the simplest solutions and least effective one. In this we are given a string "S" of length "n". And we are given a pattern "P" of length "m". We need to scan through S and find where all we find the pattern P. Print all the indexes in increasing order. This is some what like saying  print all s.indexOf(p). 

e.g. S:   thisishiscar

      P:   hiscar

In this approach, we keep two variables i and j initialized to 0. If the characters at i and j are same, save the position i in another variable k. Increase i and j by till the two characters match. In our case, they match till below.

thisishiscar

hiscar

After this position it does not match. So we have to reset j to 0 and set i to (k+1). This is because we found that the position k does not match, so we have to restart from the next position. 

Definitely this approach is not suggested. Lets derive the time-complexity for this algorithm (for people who are not familiar with Big-O). Here in worst case we compare each character of pattern 'P' to each character of String 'S'. So we have m*n comparisons. Hence the time-complexity is O(m*n). So what it means is if 1 comparison takes say 1 ms, then to search for a pattern of length 5 in a string of length 100, we take 500 ms.  

CODE

Alternate Solution:- To address the problem of comparing every character of pattern with every character of text, we have KMP Algorithm. But then again the problem with this algorithm is we need to calculate the fault functions for each pattern.

Solution:2 - Java List Approach

Now lets increase the system behavior slightly. So lets say we are given a list of names where each name contains FirstName and LastName. We have to search for a name (either firstname or lastname). The program should print all names where it matches.
I have used a text file available on the web consisting of 1,51,671 names. Its available at http://stavi.sh/downloads/names.txt. Download this text file to your local system. I have stored it in "C:\\Apps" folder. We will use this file for the remaining approaches.
In this approach, store all the names in an ArrayList. When the user searches for a name "xyz" - go through the entire list. Search if the value in the list starts with "xyz " (notice the space here at end) or ends with " xyz" (notice the space here at the beginning). This is because we want to do exact search.
So what is the time complexity of this approach? Its again same as approach 1. We are checking the entire list and comparing the pattern against each entry. So if we have N words and the length of the longest word is "K". And if the pattern length is "M", then the complexity is O(N*M*K). This is because for each word in the word list we are comparing the pattern O(K*M) and we are doing it for 'N' words.

The program loaded the 151671 words in 77 ms and searched in 94 ms.

CODE

Solution:3 - Java List and Map Approach

So how can we increase the processing time of approach 2? Lets say all the names contains only the 26 English alphabets. So instead of keeping one list we will keep a list of size 26. So any first name or last name starting with 'A' will goto list entry 0. And one starting with 'B' goto entry 1. At each entry we will maintain a LinkedHashMap. This map will contain the firstname/surname and the index of the name in the text file. So if we have a name "Anand Chari" at position 4 of the text file then we will store ("Anand", 4) in list entry 0 and ("Chari", 4) in list entry 2. Once this data structure is built, to search we can get the first character of the search key and goto the appropriate list entry. We will search only in this entry and not the other 25 entries.

So we have made the search 25 times faster?? Well yes, but the map factor adds to the cost. And still we are going through all the names which have the specific first character. So the order is O(N*M*K/(d-1)) where d is the character set size. In this case its 26.


The program loaded the 151671 words in 769 ms and searched in 3 ms.

CODE

Solution:4 - TRIE

We will introduce TRIE data structure. The basic structure of the TRIE is as shown below

There are 2 ways of implementing a TRIE - as a character array or linked list. In case of character array TRIE we have each node storing a value and a marker indicating if its an end node (double-circle). Along with this it stores children. The children here are again TRIE nodes. The number of children is 'd', which is the character set size. So we could have 26 for english or 256 for unicode character set. So this wastes a lot of space.
To overcome this, we can use the Linked List TRIE. In this the children are not 'd' but only the ones that are used. So we can avoid the additional space requirements. But we have to pay for the lost indexing capability, we have to do sequential access in linked list. We can maintain the linked list sorted for faster access.
In this approach, we will store the firstname/lastname and the occurrence of the name in the file.
Search is very simple, we will have to do a depth first search. For instance to search for "acd", we goto node    "a" and from there we go down to "b". From here we goto "c". Then we go down to "d". So we only searched 4 nodes. Then what is the time-complexity of this algorithm? O(m*d). This is because in worst-case we might have to traverse d-nodes for each character of the pattern. This we do for each of the 'm' characters.


The program loaded the 151671 words in 1 sec and searched in 0 ms. As you notice, the build-time is increased but the search time is really fast.

CODE

Solution:5 - PATRICIA TRIE (RADIX TRIE)
The problem with TRIES is the space requirement. It stores characters at each node. So the number of nodes is (d*N), even with linked list approach. That means we would need 151671*26 nodes just for English alphabets. To address this we have PATRICIA (Practical Algorithm to Retrieve Information Coded in Alphanumeric) TRIE. Here if we have N keys the total nodes would be (2*N - 1) always.
Its a difficult algorithm to explain, but I will try my best to attempt. It uses the binary representation of string.
Ascii value of 'A' is 65 which is represented in binary as "0100 0001".
So if we have a String s = "AC", we can represent it as below
0100 0001 0100 0011

Lets say we want to add 3 strings "THAT", "THEM" and "THEY" to the tree.

THAT     0101 0100 0100 1000 0100 0001 0101 0100
THEM    0101 0100 0100 1000 0100 0101 0100 1101
THEY     0101 0100 0100 1000 0100 0101 0101 1001

So the words THAT and THEM differ at position 21 (left to right). Similarly, THEM and THEY differ at position 27. So we make a binary tree like this

Notice that to store 3 keys we have used 5 nodes (2*3 - 1).

In "THAT" the 21st bit is 0 that is why it is on the left. For "THEM" and "THEY" the bit is 1 and thats why they they are on right. The words "THEM" and "THEY" differ at bit 27. THEM has 0 at the position and THEY has 1.





So we build a tree like this and the search is very simple in this case. There are several other reasons for choosing this data structure. We can do lot more things like proximity search, approximate search, regex search, substring search, and so on.


The program loaded the 151671 words in 2 sec and searched in 1 ms. The increase in build time is due to the fact that we are using string manipulation functions to convert String to Binary. I haven't optimized it yet.

So what did we gain in this?? A lot less memory requirement and very fast search. 

CODE

Solution for Probability using Tree

Probability is one area that's most often ignored by many. However there are very interesting problems on it. One such thing is tossing coins or picking up a ball, etc. Why do people ask such questions in interviews? Well, if we observe carefully tossing a coin is Head/Tail, that means binary. So the solution for these can be solved using binary algorithms. We will discuss how to achieve using a special type of Complete Binary Search Tree called "Probability Tree".
Lets say i toss a coin 'n' times and i get the following sequence - HTHTHHTTTHHHTHTH
Here H denotes Head and T denotes Tail. Now with this data, can you predict the probability for a series of 1, 2 or 3 coin tosses? Example, what is the probability that my first toss results in H? Or what is the probability of getting Head first time and Tail second time? Or what is the probability of getting HHT? All these can be solved using probability tree.
For our consideration we will take a maximum of 3-coin toss series problems. Treat H as '0' and T as '1'. Take the input and read all 3 series starting from the left. Since there are 16 tosses in total, we can make 3 series of 14 inputs. They are

HTH
THT
HTH
THH
HHT
HTT
TTT
TTH
THH
HHH
HHT
HTH
THT
HTH

What we have done is, we have read 3 at a time and removed the first. So (1,2,3), (2,3,4), (3,4,5) etc..

Now prepare a 3 level Complete Binary Search Tree and assume left nodes denote 'T' and right nodes denote 'H'. Initialize the count of all nodes to 0. Take the above 14 inputs one by one. First we start with HTH. So we go right, left, and right.  As we traverse we increase the count of the node by 1. Likewise do it for all the 14 inputs. Now we are done with counts. Now at level-1 the left node has count 6 and right node has 8. So the total for the 2 nodes is 14. The probability for left node is 6/14 and for right is 8/14. Store it and move on to calculate next levels. For each node just consider its two children and set their probabilities. Thats all we are done!!

Now to find the probability of an event lets say "H". We can directly goto right node and get its probability. So it is nearly 0.57.
Lets say we want to find the probability of "TT". Its 0.43*0.33.
Probability of "TTH" is 0.43*0.33*0.5.

Note that the total probability is the probability for all leaf nodes and it is equal to 1.

Solution:

Spell Check - Minimum Distance Calculation

Wherever there is a manual user input, there is a possibility of a typo error. As per research its been found that possibility of the first letter being typed wrongly is very remote.
Errors are classified into the following types

1. Extra character : "inpuut" instead of "input"
2. Missing character: "publsh" instead of "publish"
3. Wrong character: "prebiew" instead of "preview"

We call each of the above errors as 1 distance.  Now given 2 strings, its possible to calculate the distance.
For eg. "Apple" and "Applets" distance is 2 as it is 2 missing characters.
"Apple" and "Tablet" distance is 4 as it is 3 Wrong characters (A instead of T, p instead of a, p instead of b),   and 1 missing character (t missing).

There is an algorithm to calculate this distance, found by a Russian mathematician Levenshtein. This algorithm is named according to him. So if the length of string1 is 'n' and length of string2 is 'm' then the algorithm runs in O(n*m). First we plot the string1 and string2 characters in a matrix format and then start filling up the values.

Calculation starts from (1,1) and the result is stored at the right bottom (red).

at (1,1) we have 't' and 'a'. they do not match so consider the values (0,0), (0,1) and (1,0) and take the minimum value and add 1. So the numbers are 0, 1, and 1. The minimum is 0 add 1 to it. We get 1.

at (2,1) we have 'a' and 'a'. they match so take the value at (1,0) which is the diagonally above the current element.

The minimum distance is stored at (6,5) which is 4


The same algorithm can be extended to check multiple strings. It can be applied to find all matching words in a dictionary. Some of the spell checkers that we see day-today use this to find the nearest matching word in a given dictionary. While doing so, the average distance they would check against is 2 (as per research).
But if they have to prepare this matrix for each string and compare it in O(n*m) its a time consuming thing. So there is a revised algorithm which runs in O(n log n + m log m). I am planning to put up this algorithm in the next sessions where I will be posting on the algorithm behind Google Docs.

Solution

Perfect Hashing - Collision Free HashMap

The HashMap is a reliable Key-Value store in Java which works on the principles of Hashing. The structure of the HashMap class is as below -

Buckets are array of Linked Lists.
Initial size of Buckets is 11.

Each key/value pair is stored in the linked list
Key's hashCode is used to find the Bucket.

Due to Hash-Collision multiple Key-Value
pairs hash to same bucket.




For Instance consider the below code
map.put( new Integer(33), "ThirtyThree");
map.put( new Integer(11), "Eleven");
map.put( new Integer(25), "TwentyFive");

The Keys here are Integers and the default implementation of hashCode for Integer class is the intValue.
So for the first put for 33, the hashCode of the key is 33. Now this value is converted to Bucket Index-
index = hashCode % capacity
index = 33 % 11 = 0
So the key/value pair is inserted at bucket 0.
Next, for 11 as well the bucket index is 0. This is a hash-Collision. This increases the length of the Linked-List. More the conflicts, worse the performance would be. As the linked list has to be traversed.

How do we ensure that there are no conflicts at all??
The answer is Perfect Hashing. There are various techniques available. We will look at "Cuckoo Hashing". This is a type of hashing which ensures zero-conflicts.

Image Source Wikipedia

In this hashing we maintain 2 set of buckets(or tables). We use 2 hashing functions h(k) and h'(k).

h(k) = key % 11 
h'(k) =(key/11) % 11

Here 11 is the capacity and its changed at run-time based on the capacity of the table.

So to populate key 20, first h(k) is calculated.
20%11 = 9

The first preference is table1. The algorithm checks if the index 9 of table 1 is free. If it is, store the key ( key-value pair infact) at the index 9. Hence you don't need to calculate h'(k).
Next key is 50. For this h(k) is 6. Again table1 index 6 is free and the key is inserted.
Next key is 53. For this h(k) is 9. But at that index we already have key 20. So calculate h'(k). It is (53/11)%11 = 4%11 = 4. Check if the index 4 of table2 is free. It is, so insert it in table2.

When inserting 67, h(k) = 1 and h'(k) = 6. And you notice that table1 index 1 is not empty and so also table2 index 6. Now apply greedy-method.Steal the index of table1 index 1 and store 67 at that position. So the old-key in that position, 100 is pushed out. Now 100 has to find a new place. Since it originated from table1, now it seeks its position in table2 using h'(k). For 100, h'(k) is 9 and table2 index 9 is free. Hence it is stored there.
Similarly, follow the path for 39. For 39, h(k) is 6 and h'(k) is 3. Both are occupied. So force out 105 from table1 index 6. For 105, h'(k) is 9. Store 105 at table2 position 9 by forcing out 100. For 100 h(k) is 1. Store it in table1 index 1 by forcing out 67. For 67, h'(k) is 6. So store it at table2 position 6 by forcing out 75. For 75, h(k) is 9 hence force out 53. and so on...

If we proceed like this, will we not end up with infinite-loop? YES.
So this algorithm works by ensuring that anytime the table's loadfactor is not exceeding 0.5. That means the number of buckets occupied should not be more than 50%. For people who are not aware of load-factor it is (size/capacity). This way we can ensure that the possibility of an infinite-loop is remote. And if that happens we can apply a different hashing.

The code below implements Cuckoo Hashing. To simulate the infinite loop, test by adding 6 (comment out the portion mentioned in the code)

Finally, why the name Cuckoo?? Its a technique used by Cuckoo bird :)

Solution

Convert a Binary Tree to Linked List

Given a binary tree (or Binary Search Tree), convert it to a doubly-linked list. Can you do it inline?

Input:
                    60
           50             70
      40       55   65      75

Output:
      60 -> 50 -> 70 ->40 -> 55 -> 65 -> 75

Approach
The structure of a Binary Tree Node is similar to Linked List Node. Binary Tree node has left and right. A linked list has prev and next.
Do a Bread-First-Search (BFS) and adjust the pointers as the nodes are read.

Solution

Print prime numbers from 1 to 10 Million

Print all prime numbers from 1 to 10 million.

Approach
Prime number is one which is divisible by 1 and itself. So to find if a number 'X' is prime, we need to divide each and every number with 'X'. However this can be optimized. Instead of checking for all the numbers, check upto square-root of 'X'.
Further to this, Sieve has proposed an optimized solution to calculating primes.
If a number is prime then any multiple of it is not a prime

With this approach, I was able to print all prime numbers from 1 to 10 million, in 4 seconds on my laptop.

Solution

Find the next smallest number for a given number

In an unsorted array, given a number 'x',
find the next smallest number.
The number 'x' does exist in the array.
Array {62,50,91,32,60,63,17,36,55,61}
Num = 62
Result = 61

Num = 50
Result = 36

Approach:

Sorting is not a solution, since it will be O(N^2) or atleast O(N log N). 

Create a Binary Search Tree and find the number 'X'. Once found, fetch the right most node of its left subtree. Thats the required element.

Solution

Find the number or next smallest number

 In a sorted array, find if a given number 'X' is found.
 If found, print it
 If not found, print the next smallest number lesser than the given number
 Eg. {17,32,58,60,63,91}
 Num = 35
 Answer = 32

Approach
As the numbers are already sorted, we can use a modified version of binary search. The twist here is, when the middle number is less than 'X' then check if the next number is greater than 'X'.

Alternatively, what if the numbers were not sorted??
Use a min-heap and get the minimum till finding a number greater than 'X'.

Solution

Two non-repeating numbers in an unsorted array

Design an algorithm to find two non-repeating numbers in an array where other numbers are repeated.
for eg.
input array: {2, 8, 6, 8, 3, 9, 2, 9}
result: 3,6

Approach:-

XOR all the numbers. This gives a value x. 

2^2, 8^8, and 9^9 all become 0. So the remaining is 6^3.

0110

0011

------

0101

------

So x in this case is 5. Take the last set bit, in this case is 1 (that is the unit place). So in the result, one number has 1 in position 1 and the other number has 0 in position 1. That is the reason we have 1 in the result.

Next scan the input array again, but as the numbers are inspected check if the number has 0 or 1 in the position 1. Make 2 XOR groups - one group of numbers with 1 in position 1 and the other group having 0.

The result is the 2 numbers.

Solution

First occurrence of a number in a sorted array

Given a sorted array of numbers where each number is repeated multiple times,  design an algorithm to find the first occurrence of a given number.
for e.g.
input array: {2,2,2,3,4,5,5,5,6,6,6,7,7,7,7,12,12,15,19}
number: 6
Here number 6 is found in position 8,9 and 10 (0-indexed). However, 8 is the first index.

Approach:- Using binary search locate the block of numbers containing the list of target number.
Once the list is found, apply binary search on the block again.

Solution

Single non-repeating number

Given an array of numbers where every number except one is repeated, efficiently find the number.
for e.g. {9, 1, 8, 7, 8, 1, 9}
Answer: 7

Approach
Sorting and finding each number with the next number - this is not an ideal approach as it takes O(N^2).
Instead use bit manipulation. XOR all numbers and the left out number is the result

Solution

Sum of Digits until it becomes a single digit

You are given a huge number and the task is to add the number till it becomes a single digit.
E.g.
Number = 9580658690133945975556610984511994659
 9+5+8+0+6+5+8+6+9+0+1+3+3+9+4+5+9+7+5+5+5+6+6+1+0+9+8+4+5+1+1+9+9+4+6+5+9     =195
  1+9+5 =  15
  1+5 = 6
  Result = 6
 
  Wait!! Can I do it in one pass?? Yes O(N) solution
  Add the values. If sum is divisible by 9, result is 9.
  Else result is (sum mod 9). In the above case, after the first pass the result is 195. Hence 195%9 = 6, the   desired answer.

Solution

Count number of 1's in a Number

Count the number of 1's in a number's representation.
E.g. Number 23 is 0001 0111
So there are 4 One's

Approach
Left Shift a number (equivalent to dividing by 2). Then if divided number is a double of original number, ignore. Else increment count (the original number is odd).
23 >> 1   gives 11
11 >> 1   gives 5
5  >> 1    gives 2
2 >> 1     gives 1

Solution

In place merge sort 2 sorted arrays

Given two sorted arrays A and B of size (m+n) and m respectively, design an algorithm to merge A and B in-place.

e.g.  A = {8, 12, 15, 20, 22, 0, 0, 0, 0}
        B = {6, 13, 18, 19}
 Result= {6, 8, 12, 13, 15, 18, 19, 20, 22}

Approach
Apply 2-way merge. Advantage of this method is - it can be extended for any number of arrays (k-way merge). Take the last elements of arrays (22 and 19), put the highest element to the end of Array A. Next take 20 and the previous smaller element (19). Compare and put 20 in the last but one position. so on..

Solution

Interviewstreet Amazon India - Meeting Schedule

Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes.

Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes
An event time slot is of form [Start Time, End Time ) . Which means it inclusive at start time but doesn’t include the end time.

Sample Input:                                                       Sample Output:

5 120                                                                    00 00 09 00

16 00 17 00                                                          17 00 20 45

10 30 15 30

20 45 22 15

10 00 13 25

09 00 11 00

Approach

The time is expressed as hh mm, and we have 1440 minutes in a day. So we can create a integer array of size 1440, with elements initialized to 0. Now read each value of the busy-time and set the corresponding slot in the integer array to 1s. For instance 01:28 is at array position 88. Since its 1 hour and 28 minutes. 

Once all the busy-time slots are mapped to the integer array, then you can find the free slot of given duration. So to find a free slot, start from integer array position 0 and search for consecutive 0s of length atleast 'duration'. All such durations are the free durations. 

Solution

Interview Street - pairs of numbers that have a difference of K

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:3

Solution
This problem can be solved with hashing or by sorting.I have taken the sorting approach.
Sort the contents of the array in (n log n) time. Then for each number in the array, do a binary search to see if the num+k exists in the array.

In hashing approach, maintain a hashtable. As you iterate each number X, check if X+k exists in the hashtable with 1 value. If its there then you have a pair. Else put the key (X+k) and value '0'. 

Interview Street - Indian Startup - Matrix Multiplication

Mr. Evan has given to his students an assignment where they need to multiply two boolean matrices and write the resultant matrix. Boolean matrix multiplication is done in the same way as standard matrix multiplication except for in the resultant matrix any entry which is not zero is treated as one.

Mr. Evan is tired of checking the correctness of their results, so he has asked you for help.

Given three N X N boolean matrices A, B and C, you need to write a code to determine whether A x B = C.

NOTE: There need not be a deterministic algorithm so you need to come up with a better probabilistic algorithm to get accepted.

Matrix A

0 0 0 0 0

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 0 1

Matrix B 

1 0 0 0 0

0 0 0 0 0

0 1 0 0 0

1 0 0 0 0

0 0 0 0 0

Matrix C 

0 0 0 0 0

1 0 0 0 0

0 0 0 0 0

0 1 0 0 0

0 0 0 0 0

Approach-

Here we don't need to do actual multiplication. We can identify all matrix A elements having 1's and matrix B elements having 1's. So in the above - A has 1 in (4, 3) and B in (3, 2). Here A col and B row are same (3). So the resultant matrix C would have 1 in (4, 2). 

Solution

InterviewStreet Puzzle for Startups India

This question was posted in the InterviewStreet for India Startups. InterviewStreet regularly runs contests were the topics are related to coding, algorithms and puzzles. The toppers of the contest get a chance to apply for a job with the startups. This question is taken from the Indian startups round.

Alice and Bob are playing a game. This game starts with two piles of n1 and n2 chips. They play alternatively and Alice starts first.
In his/her turn a person has to remove one of the piles and split the other pile into two piles, these two new piles need not be of same size. The person who cannot make a move in his turn loses.
Write a program which given n1 and n2 finds the winner. Assume both the players play optimally.

Approach

Visualizing this kind of a puzzle is easy with Mathematical Induction. So take a smaller value and gradually build up. 

Example 1:-

Start with (2, 1).

Alice keeps 1, and splits the 2.

Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.

Example 2:-

Start with (2, 2)

Alice keeps 2, and splits the other 2.

Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.

Example 3:-

Start with (3, 2)

Alice keeps 3, and splits the 2.
Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.

Example 4:-

Start with (3, 3)

Alice keeps 3, and splits the other 3.
Bob gets (2,1). Bob keeps 1 and splits 2.
Alice gets (1,1) she looses.

Example 5:-
Start with (8, 1)
Alice keeps 1, and splits the 8
Bob gets (5, 3). He cannot keep 5 and split 3, since in that case he will have to provide (2, 1) in which case he will loose immediately. So he splits 5. To split 5, he cannot split it to (3, 2) as Alice will keep 3 and split the 2 as (1,1). In this case again Bob will loose. So to keep the game going he will split 5 as (4,1).
Alice gets (4,1). She keeps 1 and splits 4. There are 2 options (2, 2) and (3,1). But if she gives (2,2), in the next move Bob will provide her (1,1) and she will loose. So she splits (3,1).
Bob gets (3,1). He keeps 1 and has to split (2,1). So again he looses.

In example 5, instead of Alice splitting (5, 3), what if she split (4,4) or (6, 2). Well (6,2) is not possible, as she will loose immediately. Assume she splits (4, 4)
Bob gets (4, 4). He can split as (2, 2) which he won't do. So he will split (3, 1).
Alice gets (3,1). She keeps 1 and splits ( 2, 1). She will loose.

So splitting 8 as (5, 3) was a better move.

Example 6:-
Start with (10, 1).
Bob (5, 5)
Alice ( 4, 1)
Bob (3, 1)
Alice ( 2, 1) and wins

Start with (10, 1)
Bob (6, 4)
Alice (3, 1)
Bob (2, 1) and wins

Start with (10, 1)
Bob (6, 4)
Alice (3, 3)
Bob (2, 1) and wins

Solution:-
I have provided a solution which ensures the highest chances for Alice to win. Alice winning chances are when she gets atleast one input as even. For instance (10, 1) here 10 was even. She will split it into 2 odds - 5 and 5. This way she can ensure her winning. If she got (8, 1) then she can split (5, 3). If she got (8, 12) still she can split (5, 3). This way she can ensure the game is finished early.
If she gets (13, 1) that is the only option available is an odd, then Bob stands a winning chance. Still she can keep the game on by splitting into (12, 1).
The program prints the most optimized path favoring Alice.

Facebook Question - Find the longest increasing subsequence

Problem
You are given an unsorted array of integers. In that array, find the longest increasing subsequence.
For eg. {1, 5, 3, 4, 6, 1, 2, 4, 8, 5 }
In the above, there are multiple increasing sequences:
{1,5}
{3,4}
{3,4,6}
{1,2}
{1,2,4}
{1,2,4,8}
Of the above, last one is the longest sequence.
Write a program to solve the above. It should be linear O(N) time.

Approach
Initialize an array of same length as input. Call it current array. Read the first element and store it in this array. Keep navigating the input array and if the current element is greater than the last element in the current array, then put the value into the current array. If the value is less than the last current array element, then we need to start again. So we need to reset the current array. But hold on, the current array that we have might be the  longest subsequence. So before resetting the array check if the current length of current array is the biggest we found ever. If so copy the array elements into the result array.

current array: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}
length: 1
maxlength:1

i=1, a[1] = 5 (increasing)
current array: {1, 5, 0, 0, 0, 0, 0, 0, 0, 0}
length: 2
maxlength: 2

i=2, a[2] = 3 (decreasing)
current array: {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}
result: {1, 5}
length: 1
maxlength: 2

i=3, a[3] = 4 (increasing)
current array: {3,4, 0, 0, 0, 0, 0, 0, 0, 0}
result:{1,5}
length: 2
maxlength:2

Solution