Interview Question


Country: United States




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

findNthInSeries : N int
	div4 = div7 = div28 = 0
	if N >= 4
		let div4 = N >> 2

	if N >= 7
		let div7 = N / 4

	if N >= 28
		let div28 = N /28

	moveFurther = div4 + div7 - div28
	divTest4 = 5 //00..0011
    
	while moveFurther > 0
		++N
		if N % 28 == 0
			{}
		else if (N % 7 == 0) or (N & divTest == 0)
			++N

	return N

Let me know if i am incorrect somewhere

- aryanmain July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

findNthInSeries : N int
	div4 = div7 = div28 = 0
	if N >= 4
		let div4 = N >> 2

	if N >= 7
		let div7 = N / 4

	if N >= 28
		let div28 = N /28

	moveFurther = div4 + div7 - div28
	divTest4 = 5 //00..0011
    
	while moveFurther > 0
		++N
		if N % 28 == 0
			{}
		else if (N % 7 == 0) or (N & divTest == 0)
			++N
		--moveFurther

	if N % 28 == 0
		{}
	else if (N % 7 == 0) or (N & divTest == 0)
		++N

	return N

- aryanmain July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

2 changes i think:
div7 should be n/7

also divtest4 should be 3 and not 5(you wrote the correct binary equivalent!)

also i don't think its necessary for you to check for numbers being greater than 4,7,28
a check whetehr the number is greater than 0 in the beginning should be enough

- Anonymous July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

A good idea would be to further divide movefurther by 4,7, and 28 and repeat the process till the actual value become 0
because if you have 100
you will iterate in the while loop for around 30 times,
instead you could do some condition checks and 3 operations to find additional movefurther

- Anonymous July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findNthInSeries(int n) {
	int returnNum = 0;

	for (int i = 1; i <= n; ++i) {

		bool multOfFour = (i % 4 == 0);
		bool multOfSeven = (i % 7 == 0);

		if ((multOfFour && !multOfSeven) || (!multOfFour && multOfSeven)) { //XOR
			returnNum += 2;
		} else {
			++returnNum;
		}
	}
	return returnNum;
}

- odormody July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

XOR! Good one! Why did i not think of it before!

- Milind Thombre July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

int findnth(int n)
{
	int number = 1;
    
    	for(int i=0; i < n; i++)
    	{
        	while(number%4 == 0 || number%7 == 0)
        	{
            		number += 1;
        	}
  
       number += 1;     
                
    }

return number-1;
}

- yash bansal July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm pretty sure this solution will skip numbers that are multiples of both 4 and 7.

- odormody July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

int findnth(int n)
{
	int number = 1;
    
    	for(int i=0; i < n; i++)
    	{
        	while((number%4 == 0 && number%7 != 0) || (number%4 != 0 && number%7 == 0))
        	{
            		number += 1;
        	}
  
       number += 1;     
                
    }

return number-1;
}

- yash July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int n = 10;
int nthNum = 1;
for (int i = 1, j = 0; j < n; i++)
{
if ((0 == i % 28) || ((0 != i % 4) && (0 != i % 7)))
{
nthNum = i;
j++;
}
}
cout << n << "th number is" << nthNum << endl;

- gautam chavan July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Algorithm written by shashei kumar*/
package com.carrierCup;

public class gameCollision2 {
public static int numberToReturn(int num)
{
int iterator=1;
int count=0;
int next=1;
while(count!=num)
{

if((iterator%4)==0||(iterator%7)==0)
{
next=iterator+1;

}
else
{
next=iterator;
count++;

}
iterator++;

}
return next;
}
public static void main(String []a)
{
System.out.print(numberToReturn(10));
}

}

- shashi kumar July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is time complexity of your algorithm?
In other words, can it run for, say, n = 10^10;

Below I propose a faster algorithm:

Let sk(n) is the number of numbers that are skipped in range [1, n] by the rule.
sk(n) can be calculated in a constant time (?).

pseudo code:
find_Nth_Number(int n){
	resNum = n;	// init value
	oldNum = n;
	skipt = sk(n);
	while(resNum - sk(resNum) <n){
		oldNum = resNum;	
		resNum += skipt;
		skipt = sk(resNum) - sk(oldNum);	
	};

	return resNum;
};

Time complexity O(log n):
1. The number of skipped numbers in range [1, n] is O(n/k), where k is a constant greater than 1:
e.g., k = 1/ (1/4 + 1/7 - 1/28) = 2.8

2. Thus, the values of the variable "skipt" are decreasing as a geometric progression:
n/k , (n/k)/k, n/k^3, ...
This series converges to 0 after O(log n) times

3. Thus, the while loop is O(log n)
4. sk(n) can be calculated in constant time (?)

- ninhnnsoc July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class a
{
 public static void main(String ...args)
{
 System.out.println(function(10));
}
static int function(int n)
{
 int answer=0;
 int i=1;
 while(i++<=n) {
 answer++;
  if (hasToMoveNumber(answer))
 {
     answer=iterateToNext(answer);
 }
}
 return answer;
}



static boolean hasToMoveNumber(int answer)
{
 boolean divBy4 = answer%4==0 ;
 boolean divBy7 = answer%7==0 ;
 return (divBy4 || divBy7) &&(!(divBy4 && divBy7));
}

static int iterateToNext(int answer)
{
 while(hasToMoveNumber(answer))
 {
  answer++;
 }
 return answer;
}


}

- ioscoder July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python

def nthNumber(N):
    Nlist = []
    for i in range(1,100):
        if i % 4 == 0 and i % 7 == 0:
            Nlist.append(i)
        if i % 4 == 0 or i % 7 == 0:
            next
        else:
            Nlist.append(i)
    print Nlist[len(testlist)-1]

- tchoedak July 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def nthNumber(n):
number =1
for i in xrange(1,n+1):
number = number +1
if((number%4 == 0 or number%7 ==0) and number%28 !=0):
number = number +1
continue
return number

if __name__ == '__main__':
tenth_number = nthNumber(10)
print tenth_number

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

def nthNumber(n):
{number =1}
{for i in xrange(1,n+1):}
{number = number +1}
{if((number%4 == 0 or number%7 ==0) and number%28 !=0):}
{number = number +1}
{continue}
{return number}

{if __name__ == '__main__':}
{tenth_number = nthNumber(10)}
{print tenth_number}

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

int find_nth_no(int n)

{

int div4=0;

int div7=0;

int div28=0;

int nn,mn,t4=1,t7=1,t28=1;

nn=n;

do {

if(div4!=t4){

t4=div4;

div4=nn/4;

t4 =div4 -t4;

} else { t4=0;}

if(div7!=t7) {

t7=div7;

div7=nn/7;

t7 = div7 -t7;

}else { t7=0; }

if(div28 !=t28) {

t28=div28;

div28=nn/28;

t28 = div28 - t28;

}else {t28=0;}

mn= (t4 + t7) - t28;

nn=nn+mn;

t4=nn/4;

t7=nn/7;

t28=nn/28;

if(div4==t4 && div7==t7 && div28==t28)

return nn;

}while (1);
}

- vishal July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int find_nth_no(int n)

{

    int div4=0;

    int div7=0;

    int div28=0;

    int nn,mn,t4=1,t7=1,t28=1;

    nn=n;

    do {

        if(div4!=t4){

            t4=div4;

            div4=nn/4;

            t4 =div4 -t4;

        } else { t4=0;}

        if(div7!=t7) {

            t7=div7;

            div7=nn/7;

            t7 = div7 -t7;

        }else { t7=0; }

        if(div28 !=t28) {

            t28=div28;

            div28=nn/28;

            t28 = div28 - t28;

        }else {t28=0;}

        mn= (t4 + t7) - t28;

        nn=nn+mn;

        t4=nn/4;

        t7=nn/7;

        t28=nn/28;

        if(div4==t4 && div7==t7 && div28==t28)

            return nn;

    }while (1);
}

- Anonymous July 29, 2014 | 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