CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

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;
}

- losmi April 17, 2017 | Flag Reply
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;
}

- respectmyauthoritah April 18, 2017 | Flag Reply
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...

- krbchd April 16, 2017 | Flag Reply
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++);
		 
	 }

- jerry April 17, 2017 | Flag Reply
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;

}

- A July 05, 2017 | Flag Reply
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;

}

- A July 05, 2017 | Flag Reply
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;

}

- Anonymous July 05, 2017 | Flag Reply
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;

}

- A July 05, 2017 | Flag Reply
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;

}

- AA July 05, 2017 | Flag Reply


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