Google Interview Question for Software Engineer / Developers


Country: India




Comment hidden because of low score. Click to expand.
5
of 5 vote

I believe it's not a exact Motzkin number. Can get the value through recursion.

Cal(n){
  if (n is Odd) return 0;
  if (n==2) return 1;
  else
    for i from 2 to n{
      sum += (Cal(i-2) * Cal(n-i);
    }
  return sum;
}

- daidongLY February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

These are just the Catalan numbers. It has a simpler and more efficient one-term recurrence (look it up on Wikipedia) which you can use to compute the nth number in O(n) time.

- psykotic February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes,It's Catelan numbner.Thx.

- daidongLY February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes,It's Catelan numbner.Thx.

- daidongLY February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

missed one base case:

if (n == 0) return 1;

- db March 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

iterative version

public int chords(int n)
        {
                if(n == 0) return 1;
                int[] table = new int[n + 1];
                table[0] = 1;
                table[1] = 1;
                for(int i = 2; i <= n; i++) {
                        for(int j = 0; j < i; j++) {
                                table[i] += table[j] * table[i - 1 - j];
                        }
                }
                return table[n];
        }

- dgbfs December 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont think you can use the one-term recurrence as the odd terms has Cn = 0

- AJK November 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
5
of 11 vote

Catalon number is the Solution
2 points 1
4 points 2
6 points 5
8 points 14

Catalon number values C1 = 1, C2 = 2, C3= 5, C4 = 14


Cn= (2nCn)/(n+1)

- FIGHTER May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would be the application of Motzkin Number.

- Ran May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How did u get 2 for 4 points and 5 for 6 points?
if two chords can share a point the it will be 5 for 4 points and if they cannot, answer will always be two if 2n>=4

- cancer16789 May 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, it wont be always two i that case also....take 6 points 1,2,3,4,5,6
chords can be...
(1,2)(3.4)(5,6)
(2,3)(4,5)(6,1)
(1,4)(2,3)(5,6)

- Puneet August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Only the parallel chords is not the answer. For instance, with 6 points, we can draw a hexagon and select any group of alternate edges, thus drawing 3 non-intersecting chords.
The number can be found using the following recursion I think:

T(n) = 2n x T(n-1)

The logic behind above recursion is that we can choose any two adjacent points, then any non-intersecting set of (n-1) chords on rest 2n-2 points, will form set of n non-intersecting chords with a chord using these two point, hence on 2n points.

The above recursion can be solved to give T(n) = 2^(n-1) x n!

- gimli February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

for 2 points : 1
4 points: 5
6 points: 9

so it is 4N - 3

- Rahul May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How did you arrive at 5 for 4 points.

I guess you have joined all points to form a Quadrilateral and then made diagonal.
I am not sure if you can have 2 chords starting from the same point.

So for the case of 4 points there can only be 2 chords possible.

- Avimonk May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How did you arrive at 5 for 4 points.

I guess you have joined all points to form a Quadrilateral and then made diagonal.
I am not sure if you can have 2 chords starting from the same point.

So for the case of 4 points there can only be 2 chords possible.

- Avimonk May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For 4 points i think you have joined the vertices to form a quadrilateral and then joined a diagonal.

If its not intersecting then i think you cannot have 2 chords fro the same point.
Hence for 4 points only 2 chords are possible

- Avimonk May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If two chords cannot share a point, then this problem is not at all interesting. Answer will always be 2 if 2n>=4

- cancer16789 May 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

neen not...
let say there are six points numbered- 1,2,3,4,5,6
one possible way is 1-2,3-4,5-6 or 2-3,4-5,6-1
other can be 1-4,2-3,5-6 and its variations

- season August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In order to draw non-intersecting chords, you have draw triangles in the circle with all the triangles sharing one vertex.

Ex: If n = 5, then there are 10 points on the circle.

Start from P0, and draw chords to all other points, P1 - P9.
This will give you 9 lines or (2 * n - 1).

Then join all the points from P1 - P9 to their neighbors. This will give you 7 lines or (2 * (n - 1)).

Adding the two, you will get (4 * n - 3).

- Prash September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How large is N? I remember a coding competition where you had to answer a similar problem even for very large N (e.g. 10^9). So clearly there exists some very fast method. However, this can probably be solved using dynamic programming and the like for somewhat smaller N.

- eugene.yarovoi February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is based on Motzkin_number. Search the same on Wiki.

- iictarpit February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n vs 2n, then the problem can be viewed as represent n as the sum of some integer.

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if n=3 then 2n = 6 then number of chords passing through 3 nodes is

4*6
3*6
2*6
1*6 = 60
can someone confirm this one or give an example how to calculate?

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are chords originating from same point deemed as intersecting?

- gimli February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, chords from the same point are deemed as intersecting.

- Joel Parker Henderson February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

but the question says that the number of ways to draw n chords .... that means we have to draw n chords at a time and keeping that in mind

No. of Ways = n

- ravi February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

but the question says that the number of ways to draw n chords .... that means we have to draw n chords at a time and keeping that in mind

No. of Ways = n

- ravi February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I agree with ravi. Since it is a requirement to draw n chords and chords originating or terminating at a point are intersecting, the problem seems to reduce to drawing n parallel chords on 2n points on a circle, which is n.

- jay February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I agree with ravi. Since it is a requirement to draw n chords and chords originating or terminating at a point are intersecting, the problem seems to reduce to drawing n parallel chords on 2n points on a circle, which is n.

- jay February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int motzkin(int n)
{
if(n%2==1)
return 0;
else if(n==2) return 1;
else
{
int sum=0;
for(int i=2;i<=n;i++)
sum+=motzkin(i-2)+motzkin(n-i);
return sum;
}
}

main()
{
int n;
cout<<"Enter the number of points(n) : ";
cin>>n;
cout<<motzkin(2*n)<<endl;
}

- Azazle February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not exactly it is motzkin number....and we can improve it by stepping up i by 2......

- Azazle February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a shot at a different way to see this problem. If you connect any two points, the circle is partitioned into two arcs, each arc has a certain number of points. For the remaining points, you could only connect those that are on the same arc, otherwise, lines will intersect. Take ten points {1,2, …, 10} for an example. For point 1, you could connect it to 9 other points. However, only 5 of them are valid, i.e., points 2, 4, 6, 8, , and 10. If you connect point 1 to 3, then, you are left with two groups of odd number of points, {2} and {4,5,6,7,8, 9,10}, which are invalid. Let f(n) denote the number of ways to draw n non intersecting chords. For n = 10:

f(10) = f(0)*f(8)+f(2)*f(6)+f(4)*f(4)+f(6)*f(2)+f(8)*f(0)

From here, we could derive a recurrence relationship as the one by daidongLY (adding f(0) = 1 as a base case). I included daidongLY's code as follows with minor modifications.

int Cal(int n){
if (n % 2 == 1) return 0;
if (n == 0) return 1;
if (n==2) return 1;
int sum = 0;
for (int i = 0; i < n; i = i+2)
{
sum += Cal(i) * Cal(n-i-2);
}
return sum;
}

Here is my DP code

int countChords(int n)
{
if (n < 0 || n % 2 != 0)
return 0;
int len = n / 2 + 1;
int ways[len];
ways[0] = ways[1] = 1;
for (int i = 2; i < len; ++i)
{
int w = 0;
int cur_len = i*2;
for (int j = 0; j < cur_len; j = j + 2)
w += ways[j/2] * ways[(cur_len-2-j)/2];
ways[i] = w;
}
return ways[len-1];
}

Tested both code and they output the same results.

- db March 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cleaned up my code. tested.

long countChords(int n)
{
    if (n < 0 || n % 2 != 0)
        return 0;
    int len = n / 2 + 1;
    long c[len];
    c[0] = c[1] = 1;
    for (int i = 2; i < len; ++i)
    {
        int sum = 0;
        for (int j = 0; j < i; j++)
            sum += c[j] * c[i-1-j];
        c[i] = sum;
    }
    return c[len-1];
}

- - db March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a basic fibonacci sequence, you have 4 different solutions possible... you can use recursion, iterative, golden ratio, or matrix method.

here's my iterative solution:

int current = 1;
    int previous = 0;
    int total;
    
    for (int i = 2; i <= N; i+=2) {
        total = previous + current;
        previous = current;
        current = total;
    }

    return current;

- rdo April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

so the answer will be the same for N=2 & N=3, which is not the case.

- Daru April 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the problem stated for 2n points... I was assuming N=2,4,6,8...

- rdo April 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

even for n=2,4 etc
this solution is wrong.
it gives current=3 when n=6 which is wrong because for n=6, it should give 5. solution is catalon number.

- prakhargoyal May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you for pointing that out, i was unsure what the correct number should be, I was working off OP's expected numbers

- rdo May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 2 points : 1
4 points: 5
6 points: 9

so it is 4N - 3 where 2N is 2 ,4 ,6, ...

- Rahul May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 2 points : 1
4 points: 5
6 points: 9

so it is 4N - 3 where 2N is 2 ,4 ,6, ...

- Rahul May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a Catalan number question
When n =6 we have 5 solutions

- Qiang May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 2 pts: 1
for 4 pts: 2(clockwise and anti)
for 6 pts: 2+1+1(including diagonals)
for 8 pts: 2+4+4+4
for 10 pts:2+12+12+12+12....and so on

- Riz May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int j; i=1; sum=0;
int ways(int n)
{
if(n==2)
return 1;
if(n==4)
return 2;

n=n-2;
j=n/2;
for(i=1;(n-2-2i)!=0;i++)
{
sum=j*(ways(2i)*ways(n-2-2i));
return (sum+2);
}
}

Please verify code.

- Riz May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 2 pts: 1
for 4 pts: 2(clockwise and anti)
for 6 pts: 2+1+1(including diagonals)
for 8 pts: 2+4+4+4
for 10 pts:2+12+12+12+12....and so on

- Riz May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 2 pts: 1
for 4 pts: 2(clockwise and anti)
for 6 pts: 2+1+1(including diagonals)
for 8 pts: 2+4+4+4
for 10 pts:2+12+12+12+12....and so on

- Riz May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@All


there should be exactly N chords and all are non intersecting
if you take diagonal points they will intersect each other

- NaiveCoder May 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

These are the two cases besides the clock and anti clock:
(considered diagonal above)
....@@@@
..@......./.../..@
@......../.../..../.@
@......./.../.../..@
..@..../.../.../..@
.....@@@@

....@@@@
..@...\....\.....@
@..\...\....\.......@
@...\...\....\.....@
..@..\...\....\...@
.....@@@@

- I_think May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

on second thot u r right!
3 it is.
(As they both are same)

- I_think May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ans: 2n-3

justification :

we have n points so between every adjacent points we can draw a chord (n chords).
now select any one point form n points nc1 and we can draw n-1 chords to other n-1 points but the two nodes adjacent to that point are already counted so total chords = n-3(n-1 - 2)

total number of chords = n + n-3 = 2n - 3

- krishna May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ans: 2n-3

justification :

we have n points so between every adjacent points we can draw a chord (n chords).
now select any one point form n points nc1 and we can draw n-1 chords to other n-1 points but the two nodes adjacent to that point are already counted so total chords = n-3(n-1 - 2)

total number of chords = n + n-3 = 2n - 3

- krishna May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

T(0)=1, T(2)=1
T(2n) = T0*T(2n-2)+T2*T(2n-4)+T4*T(2n-6)+... = Sum T(2i)*T(2n-2-2i) for i=0 to n-1

- Fang May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's a recursion problem, but using a table to store the value will make it more efficiently

int dp[100]={0};
int chord(int p)
{

	if (p%2==1) return 0;  //cant draw chord using all points in this case
	else if (p==0) return 1;   //return "1", it's still a possible case
	else if (p==2) return 1;
	else if (dp[p]!=0) return dp[p];
	int sum=0;
	for (int i=2;i<=p;++i)   
	{
		sum+=(chord(i-2)*chord(p-i));
	}
	dp[p]=sum;
	return sum;
}

- Anonymous May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you have 2N points, divide them with an imaginary line such that N points lie on one side of the line and N on another (say left half and right half)

a) you have N chords joining N points on left half and right half
b) you have N - 1 cords joining points on left half
c) you have N - 1 cords joining points on right half
d) you have N - 1 cords joining one point on left half and one point on right half that is immediately below the chord you drew in a)

So answer is a) + b) + c) + d)
N + N - 1 + N - 1 + N - 1 = 4N - 3

- Victor May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Problem statement implies that every point is used in the solution.

remember[n+1] = {0};  // solutions for smaller circles with 2n points
remember[1] = 1; 
remember[2] = 2;

int HowMany(int n) {
 if (remember[n]) return remember[n]; // efficiency
 int i = 0; // i is the distance between the endpoints of our chord
  // now test every chord and subdivide
  for (i=1; i<2n-1; i+=2) { // cannot connect an even number of points away
   inside = i-1;  // number of points on one side of the chord 
 outside = 2n -2 -inside;
 count += HowMany (inside/2) + HowMany(outside/2);
 }
return count; 
}

- wealthychef June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

f(N = 1) => 2 node => 1 line
f(N = 2) => 4 node => 2 line
f(N = 3) => 6 node => 5 line
f(N = 4) => 8 node => 13 line
....
f(N = n) => 2n node => (3 * f(n - 1) - f(n - 2)) line

proof:
consider following tree states:
1- node(i) is connected to node(i + 1) => remaining nodes will form a circle with (2n - 2) => f(n - 1)
2- node(i) is connected to node(i - 1) => same as (1). => f(n - 1). there is no intersection between (1) and (2) as.
3- node(i+1) is connected to node(i + 2) => same as (1) => f(n -1) => this state has no intersection with (1), but has intersection with (3) => some duplicate states in which both of the following are true
3-1 node(i) is connected to node(i - 1)
3- 2 node(i+1) is connected to node(i + 2)
=> the remaining nodes will form a circle with (2n - 4) node => number of duplicates = f(n - 2)

Total = f(n-1) + f(n-1) + f(n-1) - f(n-2) = 3f(n - 1) - f(n - 2)

- Atefeh June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Typo: Three states

- Atefeh June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the answer is 2N + C(2N, 2) = 2N^2

Basically you can connect 2 consecutive points to create a convex polygon with 2N sides.
Then you can create triangles in C(2N,2) every alternative points.

- Anonymous June 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n = 1, chord # = 1
n = 2, chord # = 5
n > 2, chord # = 3n

- Anonymous June 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

refer catalan number from wiki page

- Arya June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(2n - 1) + (2n -2)

m=2n;
printf("Number of chords = %u\n",(m-1)+(m-2));

- okaysh June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(2n-1)+(2n-2)

- okaysh June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(2n-1)+(2n-2)

- okaysh June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hxxp://en.wikipedia.org/wiki/Motzkin_number#CITEREFDonagheyShapiro1977

- zingo August 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ways : (2n!)/( n! * (n+1)!)
O(1) solution

- amitp49 September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Video Explanation for DP Approach with intuition : " youtu.be/zx6_ypjbstk "

- Vishesh July 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Video Explanation for DP Approach with intuition : " youtu.be/ zx6_ypjbstk "

- Anonymous July 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Video Explanation for DP Approach with intuition : " hxxps://youtu.be/zx6_ypjbstk "

- Vishesh July 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Video Explanation for DP Approach with intuition : " htps://youtu.be/zx6_ypjbstk "

- Vishesh July 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It is given by Motzkin number
check the en.wikipedia.org/wiki/Motzkin_number
use DP

- googlybhai February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So how do we calculate Motzkin Number?

- Andy2000 September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@All Please note that chords are non intersecting ....

for Eg :

for n=2 ans is 1

for n=4 ans is 2
for n=6 ans is 3
for n=8 ans is 5
for n=10 ans is 8

i think u got the pattern :)



and so on.... so finally i thought it's very simple


int T(int n)
{
if (n==2)
return 1;
if(n==4)
return 2;

else
return ( T(n-2) + T(n-4));
}

- NaiveCoder April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for n=6, ways = 5
for n=8, ways = 14....

hence your solution is wrong........

- ravigupta May 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I think it will be simply N for 2N points.

- Daru April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, with 6 points in the circle, there are 4 ways

- wealthychef June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

N is correct answer and can be proved by mathematical induction

- Sean Chen June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL -- we are both wrong, because I can show you five ways to do it with 6 nodes.
1: 0-1, 2-3, 4-5
2: 0-5, 1-2, 3-4
3: 0-1, 2-5, 3-4
4: 0-5, 1-4, 2-3
5: 1-2, 0-3, 4-5

- wealthychef June 12, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More