VoiceNotes : Dictate Your Notes and Reminders

 One of the common things that people do regularly is taking notes and reminders

Recently I launched Voicenotes app for android.

https://play.google.com/store/apps/details?id=com.yogpatri.app.voicenotes

For the bare minimum I want the app to do the following

- Add notes and reminders quickly and efficiently

- No intrusive full screen especially no irritating video ads with full sound

- 400+ languages and accents for dictation

- Voice commands like next line, next paragraph etc

Add notes and Reminders Quickly and efficiently

In the best case just click the add reminder button, speak your reminder, choose today/tomorrow and time from 8 am, 1 pm, 5 pm and 9 pm and its done.

Non intrusive ads

I personally don't like full screen ads especially the video ones which start playing at full sound.

I understand that developers have to earn and these ads pay the most but as a user I hate it if my screen is getting covered every 30 seconds. So I will be using simple banner like ads which won't get in the way of user's work.

400+ languages and accents for Dictation

I speak hindi and I want to dictate my reminders in hindi only most times. Even when I am dictating in english. I prefer Indian English above US english.

So I have given a list with 400+ languages and accents so you can dictate in language of your choice. Now android's speech to text may not be high quality for some of these languages but whatever. I have also given a filter so that you can simply filter and don't have to scroll the whole list

Voice Commands

I have added Voice commands like new line, next line, next paragraph, delete etc.

Delete will delete the last word. deleting one character at a time was too slow for me, so I tried to experiment with deleting one word at a time rather than deleting a single character.

I am looking forward to you using the app and if you do please given me opinions on what you didn't like and what needs to be improved or added at contact@yogpatri.com

https://play.google.com/store/apps/details?id=com.yogpatri.app.voicenotes

Following is the list of languages (with various accents) that VoiceNotes Supports:

Afrikaans, Aghem, Akan, Albanian, Amharic, Arabic, Armenian, Assamese, Asu, Azerbaijani,
Bafia, Bambara, Basaa, Basque, Belarusian, Bemba, Bena, Bengali, Bodo, Bosnian, Breton, Bulgarian, Burmese
Catalan, Central Atlas Tamazight, Cherokee, Chiga, Chinese, Congo Swahili, Cornish, Croatian, Czech
Danish, Duala, Dutch, Dzongkha
Embu, English, Esperanto, Estonian, Ewe, Ewondo
Faroese, Filipino, Finnish, French, Fulah,
Galician, Ganda, German, Greek, Gujarati, Gusii
Hausa, Hawaiian, Hebrew, Hindi, Hungarian
Icelandic, Igbo, Indonesian, Irish, Italian
Japanese, Jola-Fonyi
Kako, Kalaallisut, Kalenjin, Kannada, Kashmiri, Kazakh, Khmer, Kinyarwanda, Konkani, Korean, Koyraboro Senni, Kwasio, Kyrgyz
Lakota, Langi, Lao, Latvian, Lingala, Lithuanian, Luba-Katanga, Luo, Luyia
Macedonian, Makhuwa-Meetto, Malagasy, Malay, Malayalam, Maltese, Manx, Marathi, Masai, Meru, Meta, Mongolian, Morisyen, Mundang
Nama, Nepali, Ngiemboon, Ngomba, North Ndebele, Norwegian Bokmål, Norwegian Nynorsk, Nuer, Nyankole
Oriya, Oromo
Pashto, Persian, Polish, Portuguese, Punjabi
Romanian, Romansh, Rombo, Rundi, Russian, Rwa
Samburu, Sango, Sangu, Sena, Serbian, Shambala, Shona, Sichuan Yi, Sinhala, Slovak, Slovenian, Soga, Somali, Spanish, Standard Moroccan Tamazight, Swahili, Swedish, Swiss German
Tachelhit, Taita, Tamil, Tasawaq, Telugu, Teso, Thai, Tibetan, Tigrinya, Tongan, Turkish
Ukrainian, Urdu, Uyghur, Uzbek
Vai, Vietnamese, Vunjo
Welsh
Yangben, Yoruba
Zarma, Zulu

Preparing for Software Engineer Interview in Two weeks

This post is about how to prepare for a job in companies like Microsoft, Amazon , Adobe etc on a short notice say 2 weeks.

Mostly I am giving out a set of coding question if one does , he/she will be ready to crack software engineering interviews at these companies.

For now I am only giving a list of algorithmic problems. Object oriented design and system design problems will be a part of a separate blog.

This list is my personal choice and I have built and used it in the last few years preparing for interviews with success.

There is not much of an advice here , just that go ahead and try the problems , if you have any questions ping me on facebook https://www.facebook.com/prashant.priyadarshi.35  .

So lets begin.

List of data structures to code :

1. ArrayList, LinkedList , Stack, HashMap, LinkedHashMap, ConcurrentHashMap , HashSet, TreeSet , Heap , Trie.

 And verify your code with that of java library code.

• You should know when to use  linked list over arraylist and vice versa see: https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist
• Also You should know how a HashMap works internally and should be able to code it.You will be asked to code hashmap directly or either use it with a doubly linked list in an LRU cache https://www.interviewbit.com/problems/lru-cache/
• For testing heaps this question can be asked: https://leetcode.com/problems/find-median-from-data-stream/description/

Now We have a topic wise list of questions.

Array:

• https://www.interviewbit.com/problems/hotel-bookings-possible/
• https://www.interviewbit.com/problems/maximum-unsorted-subarray/
• https://www.interviewbit.com/problems/merge-overlapping-intervals/
• https://www.interviewbit.com/problems/find-permutation/
• https://www.interviewbit.com/problems/next-permutation/
• https://www.interviewbit.com/problems/n3-repeat-number/
• https://www.interviewbit.com/problems/flip/

Linked Lists:

• https://www.interviewbit.com/problems/reorder-list/
• https://www.interviewbit.com/problems/reverse-link-list-ii/ (many details to handle)
• https://www.interviewbit.com/problems/sort-list/ 
• https://www.interviewbit.com/problems/k-reverse-linked-list/ (frequently asked)

Stacks and Queues:

• https://www.interviewbit.com/problems/nearest-smaller-element/
• https://www.interviewbit.com/problems/largest-rectangle-in-histogram/ (this problem uses trick in above problem (nearest-smaller-element)
• https://www.interviewbit.com/problems/rain-water-trapped/

Tree:

• https://www.interviewbit.com/problems/populate-next-right-pointers-tree/
• https://www.interviewbit.com/problems/order-of-people-heights/ ( you need segment tree to do it in nlogn)
• https://www.interviewbit.com/problems/2sum-binary-tree/   (use tree iterator here)
• https://www.interviewbit.com/problems/construct-binary-tree-from-inorder-and-postorder/
• https://www.interviewbit.com/problems/postorder-traversal/
• https://www.interviewbit.com/problems/recover-binary-search-tree/

BitWise Operator:

• https://www.interviewbit.com/problems/different-bits-sum-pairwise/
• https://www.interviewbit.com/problems/min-xor-value/

Greedy:

• https://www.interviewbit.com/problems/distribute-candy/
• https://www.interviewbit.com/problems/majority-element/

Binary Search:

• https://www.interviewbit.com/problems/median-of-array/
• https://www.interviewbit.com/problems/rotated-sorted-array-search/
• https://www.interviewbit.com/problems/allocate-books/
• https://www.interviewbit.com/problems/matrix-median/

Dynamic Programming

• https://www.interviewbit.com/problems/regular-expression-ii/
• https://www.interviewbit.com/problems/rod-cutting/
• https://www.interviewbit.com/problems/shortest-common-superstring/

Graph Theory :

• https://www.interviewbit.com/problems/clone-graph/
• https://www.interviewbit.com/problems/word-ladder-ii/
• https://www.interviewbit.com/problems/largest-distance-between-nodes-of-a-tree/

Others:

• http://www.geeksforgeeks.org/date-after-adding-given-number-of-days-to-the-given-date/
• http://www.geeksforgeeks.org/find-number-of-days-between-two-given-dates/ 

If you want to get a look and feel of the process I recommend you reading these:

• http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html 
• http://www.crackingthecodinginterview.com/

ConnectingCars SRM 645 div 2 500 , Topcoder

               ConnectingCars SRM 645 div 2 500

Problem statement :

Janusz works in roller coaster maintenance. The station of the roller coaster is a long straight segment of railroad tracks. There are some cars on those tracks. The cars are currently not attached to each other, and there may be gaps between some of them. Janusz has to push them all together and connect them into a train.

You are given the int[]s positions and lengths. For each valid i, there is a car that is lengths[i] meters long and starts positions[i] meters from the beginning of the station. (In other words, the coordinates currently occupied by this car are in the interval from positions[i] to positions[i]+lengths[i].)

Moving a single car one meter in either direction costs Janusz one unit of energy. Compute the smallest total amount of energy sufficient to push all cars together. In the final configuration the cars must be located one after another with no gaps between them.

(Note that there is no restriction on the movement of cars or on the final position of the train. Janusz may push the cars in any order, and he may even push some cars by a non-integer number of meters if he wants to.)

0)          

              

{1, 3, 10, 20}

{2, 2, 5, 3}

Returns: 15

There are four cars. The intervals currently occupied by the cars are (1,3), (3,5), (10,15), and (20,23). In one optimal solution Janusz would move each of the first two cars three meters to the right, the third car two meters to the left, and the fourth car seven meters to the left. At the end, the cars occupy the intervals (4,6), (6,8), (8,13), and (13,16). Total energy spent: 3+3+2+7 = 15.

Solution :

See the ranges of position and lengths of cars are very large . 

It is intuitive to sort the cars based on their position in increasing order. 

Initially I was looking to find the first point which will be the starting point for the train of cars and find the cost to push all cars to meet the train starting at this point. But as one can guess there can be upto 10^9 such positions, so its a bad idea.

When I saw a few passed solutions they had the following strategy :

 If we keep position of a car fixed, what will be the cost incurred to push the cars before it and after it such that no gap is left between any two cars. Our answer will be the minimum of all the cost of each car.

Below is my code to do this:

import java.util.*;import java.math.*;

import static java.lang.Math.*;

public class ConnectingCars {

public long minimizeCost(int[] pos, int[] len)

 { int l=pos.length; 

for(int i=0;i<l;i++)for(int j=i+1;j<l;j++)if(pos[i]>pos[j]) 

{ swap(i,j,pos); swap(i,j,len); } 

long ans=1L<<55;  

for(int i=0;i<l;i++) {  

long lt=pos[i],rt=pos[i]+(long)len[i],temp=0;  

for(int j=i-1;j>=0;lt-=len[j],j--)temp+=lt-(pos[j]+len[j]);

for(int j=i+1;j<l;rt+=len[j],j++)temp+=pos[j]-rt;  

ans=min(ans,temp);  

} 

return ans; 

}

long get(long mid,int pos[],long sum[])

{ long temp=abs(pos[0]-mid); 

for(int i=1;i<pos.length;i++)temp+=abs(pos[i]-(mid+sum[i-1])); 

return temp;

} 

void swap(int i,int j,int a[]) 

{  

int t=a[i]; a[i]=a[j]; a[j]=t;

}

}

Now why is this solution correct . I just tried to see what happens if out fixed point is between two cars instead of position of a car. See the figure below

 In the above figure there are 5 cars numbered 1,2,3,4, and 5 respectively.

distance between 1 and 2 = a

distance between 2 and 3 = b

distance between 3 and 4 = c

distance between 4 and 5 = d

now our cost if we fix car 3 will be :

  a+b ( for car 1)   +   b  (for car 2)   + 0 (for car 3)  + c  (for car 4)  + c+d  ( for car 5)

total --> a+2b+2c+d

Now what if we fix a point at a distance dx from left of car 3 :

Out cost in this case will be :

a+b -dx( for car 1)   +   b-dx  (for car 2)   + dx (for car 3)  + c +dx (for car 4)  + c+dx+d  ( for car 5)

total -->  a+2d+2c+d+dx

so we see that in this case our total increases by dx for this configuration.

SRM 581 div 1 level 2 TreeUnion

Problem statement 

I counted all the possible number of k cycles . Now since we are connecting two trees so when will a cycle form ? it will form when two nodes connected in tree1 are connected to two nodes of tree2 which have a path between them.

e.g suppose tree1 : aà bà cà d      tree2 : pàqàràs

suppose we connect  a  to  q  and  c  to  s ,  so it will be cycle of length 6  aàbàcàsàràqàa

similarly if  we connect  b to p and d to q it will be a cycle of length 5, bàcàdà qàp

length of  cycle =sum of  number of nodes b/w first node to second node  in tree1 or dis1[node1][node2]+1  and number of nodes b/w first node to second node of tree2 dis2[node1][node2].

We can find the distance between each pair of nodes in respective node using floyad warshall ,since maximum number of nodes is only 300.

Since cycle length is exactly k, so our expected value =  total number of cycles of length k divided by total number of permutation which is n! .

For tree1 and tree2 we keep cnt1[][] and cnt2[][]

For each node I in tree1 cnt1[i][j] is number of nodes which is at a distance j from i

Similarly cnt2[i][j] is filled.

Now basically the idea is to match 2 nodes in tree1 at distance d1 to 2 nodes in tree2 at distance d2 such that d1+d2+2=k

 -----------------------------------------------------------------------------------------------------------------------------

  import java.util.*;

   import static java.lang.Math.*;

public class TreeUnion {

                public double expectedCycles(String[] tree1, String[] tree2, int K) {

        int cnt1[][]=fill(tree1);

        int cnt2[][]=fill(tree2);

        int n=cnt1.length;

        double mul=1.0/(n*(n-1)),ans=0;

        for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=1;k<K-2;k++)ans+=2*mul*cnt1[i][k]*cnt2[j][K-2-k];

                                return ans;

                }

    int[][] fill(String tree1[])

    {

        StringBuilder sb=new StringBuilder();

        for(String s:tree1)  sb.append(s);

        String s[]=sb.toString().split(" ");

        int n=s.length,inf=1<<25;

        int dis1[][]=new int[n+1][n+1];

        for(int i[]:dis1)Arrays.fill(i,inf);

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

        {

            int p=Integer.parseInt(s[i]);

            dis1[i+1][p]=dis1[p][i+1]=1;

        }

        for(int k=0;k<=n;k++)for(int i=0;i<=n;i++)for(int j=0;j<=n;j++) 

        dis1[i][j]=min(dis1[i][j],dis1[i][k]+dis1[k][j]);

        int cnt[][]=new int[n+1][6];

        for(int i=0;i<=n;i++)for(int j=i+1;j<=n;j++)if(dis1[i][j]<6)cnt[i][dis1[i][j]]++;

        return cnt;

    }

}