## Amazon Interview Question for SDE1s

Team: Software Development
Country: United States
Interview Type: Phone Interview

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

c++, implementation

``````struct Node {
int val;
Node* next;
Node(int v) : next(NULL) {
val = v;
}
};

bool isFibonacci(int n) {
int k, r;

k = n * n * 5 - 4;
r = sqrt((double)k);
if (r * r == k) return true;

k = n * n * 5 + 4;
r = sqrt((double)k);
if (r * r == k) return true;

return false;
}

void divideLinkedList(Node* node, Node** fRoot, Node** oRoot) {
Node* fNode = NULL;
Node* oNode = NULL;

while (node) {
if (isFibonacci(node->val) == true) {
if (fNode == NULL) {
*fRoot = node;
fNode = *fRoot;
} else {
fNode->next = node;
fNode = fNode->next;
}
} else {
if (oNode == NULL) {
*oRoot = node;
oNode = *oRoot;
} else {
oNode->next = node;
oNode = oNode->next;
}
}
node = node->next;
}
if (fNode) fNode->next = NULL;
if (oNode) oNode->next = NULL;
}``````

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

``````import java.util.Iterator;

public class AMZ_Fibonacci {

public static void main(String args[]) {
isFibonacci(10);

}

if (llist == null) {
return;
}

Iterator<Integer> ll = llist.iterator();
int num = -1;
while (ll.hasNext()) {
num = ll.next();
if (isFibonacci(num)) {
} else {
}
}

System.out.println(fibSeriesList);
System.out.println(noSeriesList);
}

public static boolean isFibonacci(int num) {

int num1 = 5 * num * num - 4;
int num2 = 5 * num * num + 4;
boolean result = isPerfectSqr(num1) || isPerfectSqr(num2);
System.out.println("Run Fibonacci Test > " + num + " | Result > " + result);
return result;

}

public static boolean isPerfectSqr(int num) {

int sqrt = (int) Math.sqrt(num);
return sqrt * sqrt == num;
}
}``````

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

``````public class FibonacciNumbers {

if (numbers == null || numbers.isEmpty()) {
return Collections.emptyList();
}

List<Integer> fibonacciNumbers = new ArrayList<>();
Iterator<Integer> iterator = numbers.iterator();

// add first number & remove it
iterator.remove();

int prevFibIndex = 1;
int nextFibIndex = 2;
int currentIndex = 2;

while (iterator.hasNext() && nextFibIndex > 0) {
Integer number = iterator.next();
if (currentIndex == nextFibIndex) {
// remove number from first list & add it to second list
iterator.remove();
// calculate next fibonacci index number
int tmp = nextFibIndex;
nextFibIndex = prevFibIndex + nextFibIndex;
prevFibIndex = tmp;
}

currentIndex++;
}

return fibonacciNumbers;
}

public static void main(String[] args) {
FibonacciNumbers test = new FibonacciNumbers();
List<Integer> output = test.filterByIndex(input);
System.out.println("Fibonacci: " + output);
System.out.println("Filtered: " + input);
}
}``````

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

I was testing the Java code for Fibonacci and saw that 15 is coming under Fibonacci series.

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

Implement a linked list split function which is to take a predicate. Use latest std::function feature from C++11. See code on cpluspluslearning-petert.blogspot.co.uk/2015/11/linkedlist-split-linked-list-into.html

Test

``````bool IsFibonaciNumber(int val)
{
int temp = 5 * val*val;
int root = static_cast<int>(sqrt(temp - 4));
if (root*root == (temp - 4)) {
return true;
}

root = static_cast<int>(sqrt(temp + 4));
if (root*root == (temp + 4)) {
return true;
}

return false;
}

void TestSplitLLAgainstFibonaci()
{
{

assert(fibonaciNodes == nullptr);
assert(nonFibonaciNodes == nullptr);
}

{
std::vector<int> testArr = { 0, 1, 1, 2, 3, 5, 8 };

assert(fibonaciNodes != nullptr);
assert(nonFibonaciNodes == nullptr);

std::vector<int> result;
LL_CopyDataToStdVector(fibonaciNodes, result);
assert(testArr == result);

LL_Delete(&fibonaciNodes);
}

{
std::vector<int> testArr = { 4, 6, 7, 9, 10 };

assert(fibonaciNodes == nullptr);
assert(nonFibonaciNodes != nullptr);

std::vector<int> result;
LL_CopyDataToStdVector(nonFibonaciNodes, result);
assert(testArr == result);

LL_Delete(&nonFibonaciNodes);
}

{
std::vector<int> testArr = { 0, 4, 1, 6, 1, 7, 2, 9, 3, 10, 5, 8 };
std::vector<int> fibonaciArr = { 0, 1, 1, 2, 3, 5, 8 };
std::vector<int> nonFibonaciArr = { 4, 6, 7, 9, 10 };

assert(fibonaciNodes != nullptr);
assert(nonFibonaciNodes != nullptr);

std::vector<int> fibonaciResult;
LL_CopyDataToStdVector(fibonaciNodes, fibonaciResult);
assert(fibonaciArr == fibonaciResult);

std::vector<int> nonFibonaciResult;
LL_CopyDataToStdVector(nonFibonaciNodes, nonFibonaciResult);
assert(nonFibonaciArr == nonFibonaciResult);

LL_Delete(&fibonaciNodes);
LL_Delete(&nonFibonaciNodes);
}
}``````

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

``````pair<ListNode*, ListNode*> partitionList(ListNode *head){

int fib = 1, fib2 = 1;
int count = 0;

fibhead = fp = new ListNode(0);

nfibhead = nfp = new ListNode(0);

if(count == fib){
fp = fp->next;
// calculate the next Fibonacci number
fib = fib + fib2;
fib2 = fib - fib2;
}
else{
nfp = nfp->next;
}

count++;

}

return {fp, nfp};
}``````

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

``````import java.util.Iterator;

public static void main(String args[])
{

}

{
int number ;

if(list == null)
{
return;
}

Iterator<Integer> iter = list.iterator();

while(iter.hasNext())
{
number = iter.next();

if(isFibannoci(number))
else
}

}

private static boolean isFibannoci(int number) {

int a=0,b=1,c=0;

if(number < 0)
throw new IllegalArgumentException();

while(c<number)
{
c=a+b;
a=b;
b=c;
}

if(c==number)
return true;
else
return false;

}
}``````

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

``````import java.util.Iterator;

public static void main(String args[])
{

}

{
int number ;

if(list == null)
{
return;
}

Iterator<Integer> iter = list.iterator();

while(iter.hasNext())
{
number = iter.next();

if(isFibannoci(number))
else
}

}

private static boolean isFibannoci(int number) {

int a=0,b=1,c=0;

if(number < 0)
throw new IllegalArgumentException();

while(c<number)
{
c=a+b;
a=b;
b=c;
}

if(c==number)
return true;
else
return false;

}
}``````

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

#include<iostream>
using namespace std;
struct node
{
int data;
struct node* next;
};

void pop_list(struct node* start)
{
int x = 13, i=0;
while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}
x = 12;
while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}

void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}

bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;

while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}
if(f == n)
return true;
else
return false;
}

int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}

cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}

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

// Given a linked list, convert into 2 linked lists such that one contains fibonacci numbers other non fibonacci numbers

#include<iostream>
#include<string>

using namespace std;

struct node
{
int data;
struct node* next;
};

void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}

void pop_list(struct node* start)
{
int x = 13, i=0;

while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}

x = 12;

while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}

bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;

while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}

if(f == n)
return true;
else
return false;
}

int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
//cout << " Number belongs to fibonacci series " << endl;
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
//cout << " Number DOESNOT belongs to fibonacci series " << endl;
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}

cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}

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

// Given a linked list, convert into 2 linked lists such that one contains fibonacci numbers other non fibonacci numbers

``````#include<iostream>
#include<string>

using namespace std;

struct node
{
int data;
struct node* next;
};

void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}

void pop_list(struct node* start)
{
int x = 13, i=0;

while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}

x = 12;

while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}

bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;

while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}

if(f == n)
return true;
else
return false;
}

int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
//cout << " Number belongs to fibonacci series " << endl;
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
//cout << " Number DOESNOT belongs to fibonacci series " << endl;
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}

cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}``````

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

``````// Given a linked list, convert into 2 linked lists such that one contains fibonacci numbers other non fibonacci numbers

#include<iostream>
#include<string>

using namespace std;

struct node
{
int data;
struct node* next;
};

void print_list(struct node* start)
{
while(start)
{
cout << start->data << " ";
start=start->next;
}
cout << endl;
}

void pop_list(struct node* start)
{
int x = 13, i=0;

while(i++<20)
{
start->data = x;
start->next = new node;
start = start->next;
x = x + 1;
}

x = 12;

while(i++<30)
{
start->data = x;
start->next = new node;
start = start->next;
x = x - 1;
}
start->data=2;
start->next=NULL;
}

bool if_fibonicci(int n)
{
int f1=1,f2=1,f=1;

while(f<n)
{
f=f1+f2;
f1=f2;
f2=f;
}

if(f == n)
return true;
else
return false;
}

int main()
{
struct node* start = new node,*temp,*fibo_series=NULL, *non_fibo_series=NULL;
pop_list(start);
print_list(start);
temp=start;
while(temp)
{
if(if_fibonicci(temp->data))
{
//cout << " Number belongs to fibonacci series " << endl;
if(!fibo_series)
{
fibo_series = new node;
fibo_series->data = temp->data;
fibo_series->next = NULL;
}
else
{
struct node* t = fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
else
{
//cout << " Number DOESNOT belongs to fibonacci series " << endl;
if(!non_fibo_series)
{
non_fibo_series = new node;
non_fibo_series->data = temp->data;
non_fibo_series->next = NULL;
}
else
{
struct node* t = non_fibo_series;
while(t->next)
t=t->next;
t->next = new node;
t->next->data = temp->data;
t->next->next = NULL;
}
}
temp=temp->next;
}

cout << " fibonacci series " << endl;
print_list(fibo_series);
cout << " NON fibonacci series " << endl;
print_list(non_fibo_series);
return 0;
}``````

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

In this case I did not remember how compute if number is Fibonacci so what I do is:
- get max element in the list
- compute fibonacci numbers up to that element and store in set
- go through the list. if element is in the set add it to fibnacci list otherwise add it to non-fibonacci list:

``````#include <iostream>
#include <list>
#include <set>

using namespace std;

int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}

set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}

int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}``````

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

In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise

``#include <iostream>``

#include <list>
#include <set>

using namespace std;

int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}

set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}

int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}

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

In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise

``#include <iostream>``

#include <list>
#include <set>

using namespace std;

int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}

set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}

int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}

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

In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise

``#include <iostream>``

#include <list>
#include <set>

using namespace std;

int getMaxValue(const list<int> &l) {
int max = 0;
for (list<int>::const_iterator it=l.begin();it!=l.end();++it)
if ((*it) > max)
max = *it;
return max;
}

set<int> getFibonacciNumbers(int limit) {
set<int> fibonacci;
int result = 0;
int number1 = 0;
int number2 = 1;
while(result < limit) {
result = number1 + number2;
number2 = number1;
number1 = result;
fibonacci.insert(result);
}
return fibonacci;
}

int main() {
list<int>isFibonacci;
list<int>isNotFibonacci;
list<int>mylist;
mylist.push_back(1);
mylist.push_back(5);
mylist.push_back(20);
mylist.push_back(7);
mylist.push_back(13);
mylist.push_back(56);
set<int> fibonacciNumbers = getFibonacciNumbers(getMaxValue(mylist));
for (list<int>::iterator it=mylist.begin();it!=mylist.end();++it)
if(fibonacciNumbers.find(*it) != fibonacciNumbers.end())
isFibonacci.push_back(*it);
else
isNotFibonacci.push_back(*it);
cout << "Fibonacci numbers: " << endl;
for (list<int>::iterator it=isFibonacci.begin();it!=isFibonacci.end();++it)
cout << *it << " ";
cout << endl;
cout << "No Fibonacci numbers: " << endl;
for (list<int>::iterator it=isNotFibonacci.begin();it!=isNotFibonacci.end();++it)
cout << *it << " ";
return 0;
}

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

In my case I did not remember how to calculate if number is fibonacci so I have used different algorithm:
- Get max element in the list
- Compute fibonacci sequence up to that max element and store it in set
- Go through the list and check if each element is in the set, if it is add it to fibonacci list, add it to non-fibonacci list otherwise

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.

### 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.