Facebook Interview Experience


Online Coding Round on InterviewStreet

The given problem boils down to : Given a undirected graph, source and destination, write the code to find the total number of distinct nodes visited, considering all possible paths.

4 of us were shortlisted for Personal Interviews in Delhi.

Personal Interview Problems:

  1. Given two “ids” and a function getFriends(id) to get the list of friends of that person id, you need to write a function that returns the list of mutual friends.
  2. Given an “id” and a function getFriends(id) to get the list of friends of that person id, you need to write a function that returns the list of “friends of friends” in the order of decreasing number of mutual friends, as in friend recommendations.
  3. Given a number of time slots – start time and end time,“a b”, find any specific time with the maximum number of overlapping.
  4. Given an array of Integers, find the Longest sub-array whose elements are in Increasing Order.
  5. Given an array of Integers, find the length of Longest Increasing Subsequence and print the sequence.
  6. Given a Sorted Array which has been rotated, write the code to find a given Integer.
  7. You have a number of incoming Integers, all of which cannot be stored into memory. We need to print largest K numbers at the end of input.
  8. Implement LRU Cache.

The Interview Process was pretty impressive and well-organised. A fully sponsored trip to Delhi comes to an end, with me having a full-time Offer as a Software Engineer at Facebook. \m/

Codeforces Round #105 ( Problem: Bag Of Mice )


This is a problem from the recently held Codeforces Round #105 (Div 2).

Problem Statement: The dragon and the princess are arguing about what to do on the New Year’s Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, while the princess thinks they should just go to bed early. They are desperate to come to an amicable agreement, so they decide to leave this up to chance.

They take turns drawing a mouse from a bag which initially contains w white and b black mice. The person who is the first to draw a white mouse wins. After each mouse drawn by the dragon the rest of mice in the bag panic, and one of them jumps out of the bag itself (the princess draws her mice carefully and doesn’t scare other mice). Princess draws first. What is the probability of the princess winning?

If there are no more mice in the bag and nobody has drawn a white mouse, the dragon wins. Mice which jump out of the bag themselves are not considered to be drawn (do not define the winner). Once a mouse has left the bag, it never returns to it. Every mouse is drawn from the bag with the same probability as every other one and every mouse jumps out of the bag with the same probability as every other one.

Input

The only line of input data contains two integers w and b (0 ≤ w, b ≤ 1000).

Output

Output the probability of the princess winning. The answer is considered to be correct if its absolute or relative error does not exceed10 - 9.

Sample test(s)

Input

1 3

Output

0.500000000

Input

5 5

Output

0.658730159

Here’s my accepted solution:


using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

double arr[1010][1010],temp,temp1,temp2;
int main()
{
     int i,j,w,b;
     scanf("%d %d",&w,&b);

     for(i=0;i<=w;i++) arr[i][0]=1;
     for(i=0;i<=b;i++) arr[0][i]=0;

     for(i=1;i<=w;i++)
     {
          for(j=1;j<=b;j++)
          {
               arr[i][j]=(double)i/( (double)i+(double)j );

               temp=(1-arr[i][j]);
               temp*=(double)(j-1)/( (double)i+(double)j-1.0 );

               temp1=0.0;
               if(i+j>2 && j>2) temp1=temp*((double)(j-2.0)/( (double)i+(double)j-2 ));
               if(j>=3) temp1*=arr[i][j-3];

               temp2=0.0;
               if(i+j>2) temp2=temp*((double)(i)/( (double)i+(double)j-2 ));
               if(j>=2) temp2*=arr[i-1][j-2];

               arr[i][j]+=temp1+temp2;
          }
     }
     printf("%.9lf\n",arr[w][b]);
     return 0;
}

ACM-ICPC Kanpur Site Online Prelims ’11


Finally, ACM-ICPC Asia-Kanpur Site First Round Online Contest has come to an end…..Must say, it was real fun!!!!!

Lets have a look at the contest problems and their optimal solutions. Some of the solutions are from those teams which managed a good rank at the end of the contest. Congratulations to them!!!! :D

My team Gibberish managed an AIR of 26 and 1st in BIT Mersa. But unless and until the results are declared I won’t be at peace. :P

Problem 1: Arithmancy

Hermione Granger, the most talented witch of her generation, likes to solve various types of mathematical problems in the Arithmancy class. Today, the professor has given her the following task:

Find the number of fractions a/b such that-

1. gcd(a, b) = 1
2. 0 < a/b < 1
3. a * b = (n!) ^ (n!)

Where “n!” denotes the factorial of n and “^” denotes power, i.e. (2!) ^ (2!) = 4.

She is quite confident that she can solve it for n <= 10,000,000 (i.e. 10^7), but then she remembers that she has to study some case history so that she can help Hagrid to win the case of Buckbeak. So, she wants your help to solve the problem.

Input

There will be one line for each test case containing the number n (1 <= n <= 10,000,000). Input will be terminated by EOF. There will be around 20,000 test cases.

Output

For each case, print the number of fractions in a separate line. This number may be very large, so print the answer modulo 10,007.

Example

Input:

1
2

Output:

0
1

Time limit: 5s
Source limit: 50000

Solution by Team Gibberish

using namespace std;
#include <iostream>
#include <cstdio>
#include <vector>

# define MAX 10000001
# define MOD 10007
vector<bool> prime(MAX,true);
int sum[MAX];

void sieve()
{
     int i,j,p;
     prime[1]=false;

     for(i=3;(i*i)<MAX;i+=2)
     {
          if(!prime[i]) continue;
          for(j=i*i;j<MAX;j+=(i<<1))
          prime[j]=false;
     }

     sum[0]=sum[1]=0;sum[2]=1;
     p=1;

     for(i=3;i<MAX;i++)
     {
          if(!(i&1))
          {
               sum[i]=p;
               continue;
          }
          if(prime[i])
          {
               p++;
               sum[i]=p;
          }
          else sum[i]=p;
     }
}
int sq(int x)
{
     return (x*x)%MOD;
}
int pow(int x)
{
     if(!x) return 1;
     if(x&1) return (2*pow(x-1))%MOD;
     return sq(pow(x/2));
}
int main()
{
     sieve();
     int num,cnt,i;
     while(scanf("%d",&num)!=EOF)
     {
          cnt=sum[num];
          if(cnt!=0) cnt=pow(cnt-1);

          printf("%d\n",cnt);
     }
     return 0;
}

Problem 2: Calender

We know that there are so many calendar systems. For example, Bangla, Christ, Arabic, Chinese etc. This problem is about Decimal calendar. There are 3 months in this calendar. First month is “Hundreds”. There are 300 days in this month. Second month is “Tens”. There are 60 days in this month. And this followed by the last month “Ones” having 5 or 6 days depending on whether this is leap year or not. A Decimal year spans a full Christ calendar. That is 1st Hundreds in Decimal Calendar is 1st January in Christi Calendar. Similarly, 31st December of Christ Calendar is 5th or 6th day of Decimal calendar (depending on whether it is leap year or not).

A year in Decimal calendar is leap year if the corresponding Christ year is leap year. For example, the Decimal year corresponding to 2000 Christ year is leap year but 2001 is not, and again 1900 is not leap year too. A year in Christ calendar is leap year if the year is divisible by 400 or divisible by 4 but not by 100.

You are given a day in Christ calendar in DD-MMM-YYYY format (DD stands for day, MMM stands for first three letters (in CAPS) of the month and YYYY stands for the year). You are to give the date in Decimal Calendar format.

Input

First line contains number of test case. Every test case consists of a date in Christ Calendar format in each line.

Output

You are to output the case number and the date in Decimal Calendar format. Output the date and the month in the Decimal Calendar.

Example

Input:

3
01-JAN-1900
10-JAN-1900
16-DEC-1900

Output:

Case 1: 1 Hundreds
Case 2: 10 Hundreds
Case 3: 50 Tens

Note

First three letters for the months are:
JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC.

Time limit: 5s
Source limit: 50000

Solution By Team Gibberish

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;

int main()
{
     int n,k=1,day,year,mon,l,date;
     string s,month;
     cin>>n;
     int cal[][12]={ {0,31,59,90,120,151,181,212,243,273,304,334},
                     {0,31,60,91,121,152,182,213,244,274,305,335} };
     while(n--)
     {
          cin>>s;
          month="";
          day=(s[0]-'0')*10 + (s[1]-'0');
          month= month + s[3]+s[4]+s[5];
          year=(s[7]-'0')*1000 + (s[8]-'0')*100 + (s[9]-'0')*10 + (s[10]-'0');

          if(month=="JAN") mon=1;
          else if(month=="FEB" ) mon=2;
          else if(month=="MAR" ) mon=3;
          else if(month=="APR") mon=4;
          else if(month=="MAY" ) mon=5;
          else if(month=="JUN" ) mon=6;
          else if(month=="JUL" ) mon=7;
          else if(month=="AUG" ) mon=8;
          else if(month=="SEP" ) mon=9;
          else if(month=="OCT" )mon=10;
          else if(month=="NOV" ) mon=11;
          else if(month=="DEC") mon=12;

          l=0;
          if(year%25==0)
          {
               if(year%16==0)
                    l=1;
               else
                    l=0;
          }
          else if(year%4==0)
               l=1;
          else
               l=0;

          date = day+cal[l][mon-1];
          if(date<=300)
               cout<<"Case "<<k++<<": "<<date<<" "<<"Hundreds\n" ;
          else
          {
               date-=300;
               if(date<=60)
                    cout<<"Case "<<k++<<": "<<date<<" "<<"Tens\n";
               else
               {
                    date-=60;
                    cout<<"Case "<<k++<<": "<<date<<" "<<"Ones\n";
               }
          }
     }
     return 0;
}

Problem 3: CricInfo

I guess the most visited site of the past 3 months is www.cricinfo.com. First World Cup Cricket, then Australia tour to Bangladesh and now IPL T20. I believe there are lots of cricket fans among you. So I do not need to describe the game rule. But for the purpose of this problem here is short description of scoring. Any rule out of this problem description is not applicable for this problem.

For this problem we will use only the following outcomes in a ball:

Possible Outcome in a Ball Runs Is the Ball valid?
. (dot) 0 Yes
1 1 Yes
2 2 Yes
3 3 Yes
4 4 Yes
6 6 Yes
Wd 1 No
1Wd 2 No
2Wd 3 No
4Wd 5 No
Nb 1 No
1Nb 2 No
4Nb 5 No
6Nb 7 No
W 0 Yes

(Wd stands for Wide, Nb for No Ball and W for Wicket)

In cricinfo we always watch the score card. In cricket an over consists of 6 valid balls. A score card of an over may look like below:

1 . W . Wd Nb . 6

In this over there were 1 wicket and 9 runs. In the last over of second innings of a match, a team requires N runs to win. You are to output number of ways of the outcome of the over. Note that, as you are watching second innings of the match, so it may be possible that he can score N runs in first 4 balls and win the match. That means, it is not necessary to play an entire over to score N runs. Also suppose you do not know how many wickets are already gone. So it may also be possible that after a few wicket falls they are all out. Also note that, if a team scores greater or equal to N runs the team wins and does not play any ball.

Input

First line contains number of test case T (T <= 10000). For each test a line contains N (1 <= N <= 10000).

Output

For every test case, output the case number and number of ways of outcome of the last over where the team needs N runs to win. As the answer can be very big, so output in mod 10000007.

Example

Input:

1
1

Output:

Case 1: 946

Time limit: 5s
Source limit: 50000

Solution by Team XCoders

# include<stdio.h>

int run[15]={0,1,2,3,4,6,1,2,3,5,1,2,5,7,0};
int ball[15]={1,1,1,1,1,1,0,0,0,0,0,0,0,0,1};

long count,n;
long a[10000][7]={0};

void fun(long rnew,int bnew)
{
     long nb,nr,i,bn,rn,c;
     c=0;

     for(i=0;i<15;i++)
     {
          bn=bnew-ball[i];
          rn=rnew-run[i];
          if(bn>=0)
          {
               if(i==14) c++;
               if(rn<=0) c++;
               else
               {
                    if(bn>0) c=c+a[rn][bn];
                    else c++;
               }
          }
     }
     a[rnew][bnew]=c%10000007;
}

int main()
{
     int i,j,t,b,r;
     scanf("%d",&t);

     for(i=1;i<10001;i++)
     {
          for(j=1;j<7;j++)
               fun(i,j);
     }

     for(i=0;i<t;i++)
     {
          scanf("%ld",&n);
          printf("Case %d: %ld\n",i+1,a[n][6]);
     }
     return 0;
}

Problem 4: Mr and Mrs Ant

Mr. and Mrs. Ant are very hungry. So, they want to collect food as much as they can. They can search for foods simultaneously. To do so, they start from their house and collect all foods together and meet in some place (not necessarily their house). Finally, they eat together.

The world of Mr. and Mrs. Ant is a two dimensional grid. Each cell is either the home, or free, or blocked, or contains a food. Two cells are adjacent if they share an edge. In each second, they can move from one cell to another cell simultaneously. One can decide to not to move in some step, while other may move. One cell can be visited many times. Both of them can move into the same cell also.

In this problem, the grid is given by an R x C matrix represented by following characters:

Character Meaning Remarks

H Home of Mr. and Mrs. Ant Occurs exactly once
F A food item Occurs at least once, at most 8 times
. (dot) Free (passable) cell -
# (hash) Blocked Cell -

Given the grid information, give the minimum amount of time that must be needed for them to collect all the foods and then meet.

Input

The first line of input will contain T (T <= 30) denoting the number of cases. Each case starts with two integers R and C (2 <= R, C <= 12). Then, R lines follow giving the grid.

Output

For each case, print the case number, the minimum amount of time (in seconds) that must be needed for them to collect all the foods and meet. If it is impossible to collect all the food items, output -1 (negative one) instead.

Example

Input:

2
2 3
H#.
.#F
2 6
F#F..#
..H#.F

Output:

Case 1: -1
Case 2: 8

Time limit: 5s
Source limit: 50000

Solution by Team Pandoras Box

# include <cstdio>
# include <algorithm>
using namespace std;

char maze[12][13];
int dist[12][12][12][12];
int neigh[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int arr[8];
int coord[9][2];

int main()
{
     int T;
     scanf("%d",&T);
     for(int t=0;t<T;t++)
     {
          int R,C;
          scanf("%d%d",&R,&C);

          for(int i=0;i<R;i++)
          scanf("%s",maze[i]);
          int cnt=1;

          for(int i=0;i<R;i++)
               for(int j=0;j<C;j++)
               {
                    for(int k=0;k<R;k++)
                         for(int l=0;l<C;l++)
                              dist[i][j][k][l]=1000000;
                    if(maze[i][j]!='#')  dist[i][j][i][j]=0;
                    if(maze[i][j]=='H')  {coord[0][0]=i;coord[0][1]=j;}
                    else if(maze[i][j]=='F')  {coord[cnt][0]=i;coord[cnt++][1]=j;}
               }

         for(int chaathu=0;chaathu<144;chaathu++)
              for(int i=0;i<R;i++)
                   for(int j=0;j<C;j++)
                   {
                        for(int q=0;q<4;q++)
                        {
                             int k=i+neigh[q][0],l=j+neigh[q][1];
                             if(k>=0&&k<R&&l>=0&&l<C&&maze[k][l]!='#')
                                  for(int m=0;m<R;m++)
                                       for(int n=0;n<C;n++)
                                            if(dist[m][n][k][l]>dist[m][n][i][j])
                                                 dist[m][n][k][l]=dist[m][n][i][j]+1;
                        }
                   }
          cnt--;

          for(int i=0;i<cnt;i++)
               arr[i]=i+1;
          int mindist=1000000;

          do
          {
               int start=0,disttot=0;

               for(int i=0;i<cnt;start=arr[i++])
                    disttot+=dist[coord[start][0]][coord[start][1]][coord[arr[i]][0]][coord[arr[i]][1]];

               disttot+=dist[coord[start][0]][coord[start][1]][coord[0][0]][coord[0][1]];
               disttot>>=1;

               if(mindist>disttot)mindist=disttot;
          }while(next_permutation(arr,arr+cnt));

          printf("Case %d: %d\n",t+1,mindist>10000?-1:mindist);
     }
     return 0;
}

Interview Questions #1


This problem was asked to a friend of mine in his final round of interview for internship at Microsoft.

Given an unsorted array of non-negative integers and a non-negative integer ‘K’, find any one pair of integer in the given array such that their sum is equal to K. ‘n’ is the number of elements in the array.

  • Brute-Force O(n^2) solution.
using namespace std;
#include <cstdio>
#include <iostream>

int arr[10000];
int main()
{
     int n,sum,i,j;
     while(scanf("%d",&sum)!=EOF)
     {
          scanf("%d",&n);
          for(i=1;i<=n;i++)  scanf("%d",&arr[i]);

          for(i=1;i<=n;i++)
          {
               for(j=i+1;j<=n;j++)
               {
                    if( (arr[i]+arr[j])==sum )
                    {
                         printf("%d %d\n",arr[i],arr[j]);
                         break;
                    }
               }
               if(j<=n) break;
          }
          if(i>n) printf("NO\n");
     }
     return 0;
}

It’s pretty simple to design the O(n^2) algorithm. So we betta have a look at an O(n) algorithm.

  • Optimised O(n) solution
using namespace std;
#include <cstdio>
#include <iostream>

int arr[10000],ans[10000];
int main()
{
     int n,sum,i,val;
     while(scanf("%d",&sum)!=EOF)
     {
          scanf("%d",&n);
          for(i=1;i<=n;i++)  scanf("%d",&arr[i]);

          for(i=0;i<=sum;i++) ans[i]=0;

          for(i=1;i<=n;i++)
          {
               val=sum-arr[i];
               if(val<0) continue;

               if(ans[val]==1) {printf("%d %d\n",val,arr[i]);break;}

               ans[arr[i]]=1;
          }
          if(i>n) printf("NO\n");
     }
     return 0;
}

Microsoft Internship Selection


Finally Microsoft visited our campus!!

Only those with a minimum CGPA of 7.00 were allowed to sit for the written test. The written test comprised of two sections. The first one had 10 multiple choice questions with +3 for every right answer and -1 for every wrong answer. Questions were pretty simple mainly from topics like pointers, recursion, memory, and the C programming language. The other section had two questions of 10 marks each: one was a coding problem and for the other we had to design test cases.

Coding Problem: Write a function to shrink a given string. For example: Input String is “aaabbbaaccc”, and then the output string should be “a3b3a2c3”. You are passed a character array. Make changes in that string (do not create a new string) and return it.

Well I don’t remember the other one… :(

After waiting for more than 3 weeks, the results were announced. 16 students made it to the list, and I was one of them. Now 6 of us were supposed to have a Group Activity. In that each one of us were given two coding problems.

Coding Problem 1: We have a sorted circular linked list. You are being passed a pointer to one of the node and an integer. Write a function to insert a node in that linked list, with the given value such that the linked list thus formed is also sorted.

Coding Problem 2: Write a function to find the number of set bits in an unsigned integer.

Now comes the Personal Interview.

Interview  #1 (Technical) :

  1. You are given two sorted arrays. Write a function to find the median of the two merged arrays. No extra space is to be used (Only variables are allowed).
  2. Write a function to find the depth of a Binary Tree.

And I was asked a few questions on the difference between Arrays and Linked List and the advantage of one over the other. Same goes for Iteration and Recursion.

Interview  #2 (Technical) :

You are given a binary tree where each node has 3 pointers: left, right and cousin. All the cousin pointers are initialized to NULL. Write a function to connect the nodes at the same level such that the cousin pointer of a node points to a node at its immediate right, on the same level.

And at the end I got to hear those words which actually left me numb for a moment,

“Congratulations, you have made it through to MICROSOFT”. :)

Negative Base Number System


Here’s a C++ code to convert a number from decimal base to any negative base number system.

using namespace std;
#include<iostream>
#include<cstdio>

void convert(int n,int b)
{
     int rem;
     if(n==0) return;
     rem=n%b;
     n/=b;
     if(rem<0) {
          n++;
          rem+=(b*-1);
     }
     convert(n,b);
     printf("%d ",rem);
}
int main()
{
     int n,b;
     while(scanf("%d %d",&n,&b)!=EOF)
     {
          if(n==0) {printf("0\n");continue;}
          convert(n,b);
          printf("\n");
     }
     return 0;
}

Multiply Using Shift Operators


Recently came across this Russian Multiplication Algorithm, also known as Ethiopian Multiplication to multiply two numbers without using * operator.
Here’s the Algorithm to multiply a and b:

1.If a is odd, add b to the Result.
2.If a is zero, break and print the Result.
3.Divide a by 2, Multiply b by 2 and goto step 1.

Here’s the C++ code…..

# include<cstdio>

int main()  {
     int a,b,ans;
     while(scanf("%d%d",&a,&b)!=EOF)  {
          ans=0;
          while(a!=0)  {
               if(a&1) ans+=b;
               a>>=1;
               b<<=1;
          }
          printf("%d\n",ans);
     }
     return 0;
}

Interesting, huh! :D

For more details on the topic, refer to Russian Peasant Multiplication.

Follow

Get every new post delivered to your Inbox.

Join 34 other followers

%d bloggers like this: