## Google Interview Question for SDE1s

Country: United States

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

This problem is known as Collatz conjecture (check Wikipedia). Brute-force method was proposed by Jerry. Such solution would waste a lot of time because it would recalculate for many number. For each number there is only one way to reach 1, so no need to recalculate. Solution for this problem - dynamic programming, i.e. caching!
We cannot use an array/vector because the numbers do not always necessarily decrease (consider 9999) and thus we cannot know how large it should be and even if we resize we would waste lots of space. Solution for this - hash map!

Here is a working C++11 solution for an arbitrary number of elements. It is hard to define complexity because it depends on how the sequence goes.

``````#include <iostream>
#include <unordered_map>

int collatz(std::unordered_map<int, int>* cache_ptr, int n) {
std::unordered_map<int, int>& cache = *cache_ptr;
const auto& calculated = cache.find(n);

if(calculated != cache.end()) // value already calculated (including 1), return the value
return calculated->second;

if(n%2) { // odd
cache[n] = collatz(cache_ptr, 3*n+1) + 1;
} else { // even
cache[n] = collatz(cache_ptr, n/2) + 1;
}
return cache[n];
}

int collatz(int max) {
std::unordered_map<int, int> cache;
int longest_path = 0;
int longest_start = 1;
cache.insert({1, 0});

for(int i = 2; i < max; ++i) {
int collatz_path = collatz(&cache, i);
if(collatz_path > longest_path) {
longest_path = collatz_path;
longest_start = i;
}
}
return longest_start;
}

int main() {
std::cout << collatz(10000) << std::endl;

return 0;
}``````

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

``````public int getLongest(int[] dp, int n){
if(dp[n]>0) return dp[n];
if(n%2==0) dp[n] = getLongest(dp, n/2) + 1;
else dp[n] = getLongest(dp,3*n + 1) + 1;
return dp[n];
}
public int collatzConjecture(){
int[] dp = new int[100000000];
dp[2] = 1;
int max = 0, maxNum = 1;
for(int i=2;i<=10000;i++){
if(getLongest(dp,i)>max){
max = getLongest(dp,i);
maxNum = i;
}
}
return maxNum;
}``````

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

Variant of BFS,

Start from 1,
* mark level as 1
* then next level include all numbers from which you can reach one. Add those numbers in queue, store level for these numbers as 2(that is if you have these numbers , the chain would be of length 2)
* Similarly for any number i, add i*2 and (i-1)/3(if valid integer between [1, 10000] and for (i-1)/3 it has to be odd, i*2 has to be even and the number != 1) into queue , with those numbers level = level of i + 1;
* Continue till queue is empty, keep track of the highest level . And then return highest level
.
You will never see a duplicate, so no point tracking those.

For example

l1 - 1
l2 - 2
l3 - 4
l4 - 8
l5 - 16
l6 - 32,5
and so on...

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

Well, is the question not just about counting how many steps it takes to reach the 1 from the number given by following the sequence

``````public static int getlongestCollapsesequence(int n, int count){
System.out.print(n + " ");
if(n==1)
return count;
if(n%2 == 0)
return getlongestCollapsesequence(n/2, count++);
else
return getlongestCollapsesequence(3*n+1, count++);

}``````

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

My answer in C++

I got 261 as a result...not sure if it's correct

#include <iostream>
#include <unordered_map>

using namespace std;
unordered_map<int, int> col;
unordered_map<int, int> path_length;

int F(int n)
{
if (col.count(n) != 0)
return col[n];

if (n % 2 == 0)
col.insert({ n, n / 2 });
else
col.insert({ n, (3 * n + 1) });

return col[n];
}

int FindPathLength(int num )
{
if (path_length.count(num) != 0)
return path_length[num];

int f = F(num);
if (f == 1)
{
path_length.insert({ num, 0 });
return 1;
}

int r = FindPathLength(f);
path_length.insert({ f, r });

return (1 + r);

}

int GetLongestCollapseSequence(int n)
{
int max = INT_MIN;

for (int i = 1; i < n; ++i)
{
//cout << i << endl;
int curr = FindPathLength(i);
if (curr > max)
{
max = curr;
//cout << "max is now " << max << " for i " << i << endl;
}
}

return max;
}

void main_collapse_seq(void)
{
cout << GetLongestCollapseSequence(10000)<< endl;

}

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

I got 261 for the answer. I'm not sure if it's correct.

Here is my C++ code:

``````#include <iostream>
#include <unordered_map>

using namespace std;
unordered_map<int, int> col;
unordered_map<int, int> path_length;

int F(int n)
{
if (col.count(n) != 0)
return col[n];

if (n % 2 == 0)
col.insert({ n, n / 2 });
else
col.insert({ n, (3 * n + 1) });

return col[n];
}

int FindPathLength(int num )
{
if (path_length.count(num) != 0)
return path_length[num];

int f = F(num);
if (f == 1)
{
path_length.insert({ num, 0 });
return 1;
}

int r = FindPathLength(f);
path_length.insert({ f, r });

return (1 + r);

}

int GetLongestCollapseSequence(int n)
{
int max = INT_MIN;

for (int i = 1; i < n; ++i)
{
//cout << i << endl;
int curr = FindPathLength(i);
if (curr > max)
{
max = curr;
//cout << "max is now " << max << " for i " << i << endl;
}
}

return max;
}

void main_collapse_seq(void)
{
cout << GetLongestCollapseSequence(10000)<< endl;

}``````

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

My solution in C++

I got 261, I'm not sure whether it's the correct answer for 1000

``````#include <iostream>
#include <unordered_map>

using namespace std;
unordered_map<int, int> col;
unordered_map<int, int> path_length;

int F(int n)
{
if (col.count(n) != 0)
return col[n];

if (n % 2 == 0)
col.insert({ n, n / 2 });
else
col.insert({ n, (3 * n + 1) });

return col[n];
}

int FindPathLength(int num )
{
if (path_length.count(num) != 0)
return path_length[num];

int f = F(num);
if (f == 1)
{
path_length.insert({ num, 0 });
return 1;
}

int r = FindPathLength(f);
path_length.insert({ f, r });

return (1 + r);

}

int GetLongestCollapseSequence(int n)
{
int max = INT_MIN;

for (int i = 1; i < n; ++i)
{
//cout << i << endl;
int curr = FindPathLength(i);
if (curr > max)
{
max = curr;
//cout << "max is now " << max << " for i " << i << endl;
}
}

return max;
}

void main_collapse_seq(void)
{
cout << GetLongestCollapseSequence(10000)<< endl;

}``````

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

``````#include <iostream>
#include <unordered_map>

using namespace std;
unordered_map<int, int> col;
unordered_map<int, int> path_length;

int F(int n)
{
if (col.count(n) != 0)
return col[n];

if (n % 2 == 0)
col.insert({ n, n / 2 });
else
col.insert({ n, (3 * n + 1) });

return col[n];
}

int FindPathLength(int num )
{
if (path_length.count(num) != 0)
return path_length[num];

int f = F(num);
if (f == 1)
{
path_length.insert({ num, 0 });
return 1;
}

int r = FindPathLength(f);
path_length.insert({ f, r });

return (1 + r);

}

int GetLongestCollapseSequence(int n)
{
int max = INT_MIN;

for (int i = 1; i < n; ++i)
{
//cout << i << endl;
int curr = FindPathLength(i);
if (curr > max)
{
max = curr;
//cout << "max is now " << max << " for i " << i << endl;
}
}

return max;
}

void main_collapse_seq(void)
{
cout << GetLongestCollapseSequence(10000)<< endl;

}``````

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

``````#include <iostream>
#include <unordered_map>

using namespace std;
unordered_map<int, int> col;
unordered_map<int, int> path_length;

int F(int n)
{
if (col.count(n) != 0)
return col[n];

if (n % 2 == 0)
col.insert({ n, n / 2 });
else
col.insert({ n, (3 * n + 1) });

return col[n];
}

int FindPathLength(int num )
{
if (path_length.count(num) != 0)
return path_length[num];

int f = F(num);
if (f == 1)
{
path_length.insert({ num, 0 });
return 1;
}

int r = FindPathLength(f);
path_length.insert({ f, r });

return (1 + r);

}

int GetLongestCollapseSequence(int n)
{
int max = INT_MIN;

for (int i = 1; i < n; ++i)
{
//cout << i << endl;
int curr = FindPathLength(i);
if (curr > max)
{
max = curr;
//cout << "max is now " << max << " for i " << i << endl;
}
}

return max;
}

void main_collapse_seq(void)
{
cout << GetLongestCollapseSequence(10000)<< endl;

}``````

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.