## Google Interview Question for Software Engineers

• 3
of 5 votes

Country: United States
Interview Type: Phone Interview

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

The pattern is that starting from index 2, each pair acts as a compression of terms in the last element. For index 2, it indicates that there was one 1 in the last element. For index 3, it indicates that there was one 2 and one 1 in the last element. In index 3, it indicates that there was one 1, one 2, and two 1s in the last element. So on and so forth. Code below:

``````public String getSequence(int n) {

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

current = analyzeInt(current);
}

return current;
}

public String analyzeInt(String x) {

if (x.length() == 1) {

return 1+""+x;
}

int currentCount = 1;
String output = "";

int i = 0;

for (i = 1; i <= x.length(); i++) {

currentCount = 1;
while (i < x.length() && x.charAt(i - 1) == x.charAt(i)) {
i++;
currentCount++;
//System.out.println(currentCount);
}

output += currentCount+""+x.charAt(i - 1)+"";
}

return output;
}``````

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

Number at any index is showing the count of numbers at previous index. eg. for index 2 value is 11 which implies that at index 1 there is 1(count) of number 1. similarly value at index 4 is 1211 --> that at index 3 there is 1(count) of number 2 and 1(count) of number 1

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

How about for i = 6: you have 312211 according to your logic it would sum up to:
3*1 + 2*2 + 1*1 = 3 + 4 + 1 = 8 ? Shouldn't it sum up to 5?

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

nope... its not sum....you got it wrong, what i mean to say that value at any index represent the number of occurence of particular digit in previous index value.
so 1211 represent that there is 1 occurence of number 2 and 1 occurance of number 1 in prev value i.e 21. Dont look at these numbers as integers.. look at them as strings which represents as "no of occurances+value of that digit"

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

@varun got it! Now it makes sense

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

``````public class CountOfPreviousValue {

public static void main(String[] args) {
int n = 7;
System.out.println(findNthInSeries(n));
}

private static String findNthInSeries(int n) {
String curr = "1";
for (int i = 1; i <n ; i++) {
curr = generateSeq(curr);
}
return curr;
}

private static String generateSeq(String curr) {

String out="";
if(curr.equals("1")){
return "11";
}
else{

for (int i = 1; i <=curr.length() ; i++) {
int count=1;
while(i<curr.length() &&(curr.charAt(i-1)==curr.charAt(i))){
count++;
i++;
}
out = out+count+curr.charAt(i-1);
}
return out;
}

}
}``````

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

``````public static void main(String[] args) {
recursionNum(4);
}

/* This function is called 'n' times */
public static void recursionNum(int index)
{
int num = 1;
for(int i=0; i < index - 1; i++)
{
num = calcRept(num);
}
System.out.println(num);

}

/* Function to compute next Number */
public static int calcRept(int num)
{
char[] myCharArr = String.valueOf(num).toCharArray();
String finalString = "";
int simCharCount = 1;
for(int i=0;i< myCharArr.length  ; i++)
{
if((i != myCharArr.length -1) && (myCharArr[i] == myCharArr[i+1]))
{
simCharCount++;
}
else
{
finalString += String.valueOf(simCharCount) + String.valueOf(myCharArr[i]);
simCharCount = 1;
}
}
return Integer.parseInt(finalString);
}``````

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

Here is a non-recursive solution.

``````public static void printNthSquence(int n){
String[] sarray = new String[n];
sarray[0] = "1";
sarray[1] = "11";

int i = 2;
while(i < n){
String s = sarray[i-1];
int index = 0;
int count = 0;
char c;
String nextSequence = "";
while(index<s.length()){
c = s.charAt(index);
if(index+1<s.length() && s.charAt(index+1) == c){
count++;
}else{
nextSequence = nextSequence.concat(String.valueOf(count+1)+String.valueOf(c));
count=0;
}
index++;
}
sarray[i] = nextSequence;
i++;
}
System.out.println(sarray[n-1]);
}``````

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

import java.util.ArrayList;

public class Career {

/**
* @param args
*/
public static void main(String[] args) {

System.out.println(getValue(28));

}

private static String getValue(int n) {

ArrayList<String> raga = new ArrayList<>();
raga.add("1");
String res = "";
for(int i = 1 ; i < n; i++) {
res = "";
String prev = raga.get(i-1);
int j = prev.length() - 1;
while(j >= 0) {
res = prev.charAt(j) + res;
char rep = prev.charAt(j);
int count = 1;
while( j!= 0 && prev.charAt(j-1) == rep) {
count++;
j--;
}
j--;
res = count + res;
}
raga.add(res);
}
return res;
}

}

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

``````public static void main(String[] args) {
solveSeries();
}

public static void solveSeries() {
for (int i = 1; i <= 6; i++) {
System.out.println(findSeries(i));
}
}

public static String findSeries(int n) {
String s = "1";

if (n == 1) {
return s;
}

for (int i = 2; i <= n; i++) {
s = buildOnPrevious(s);
}
return s;
}

public static String buildOnPrevious(String s) {
char[] c = s.toCharArray();
StringBuilder sb = new StringBuilder();
int cnt = 1;
char ci = c[0];

for (int i = 1; i < c.length; i++) {
if (c[i] == ci) {
cnt++;
} else {
sb.append(cnt + "" + ci);
cnt = 1;
ci = c[i];
}
}

sb.append(cnt + "" + ci);
return sb.toString();
}``````

// output:
1
11
21
1211
111221
312211

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

count and say！

``````#include <bits/stdc++.h>
using namespace std;

string getNext(string s) {
string res;
int cnt = 1;
for (int i = 1; i <= s.length(); ++i) {
if (i < s.length() && s[i] == s[i-1]) {
++cnt;
} else {
res += to_string(cnt) + s[i-1];
cnt = 1;
}
}
return res;
}

string say(int n) {
string res = "1";
for (int i = 1; i < n; ++i) {
res = getNext(res);
}
return res;
}

int main() {
int n;
while (cin >> n) {
cout << say(n) << endl;
}
return 0;``````

}

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

Awsome... Eason

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

This can be resolved recursively very easily. All what you need to do is to implement this pattern which generally say:
1. Count all similar numbers.
2. If you find another number then append the previous character count + number to the output string.
3. If you reach the end of the string then finally append the final character count + number to the output string.

``````public class PatternResolver {

public static String resolvePuzzle(String currentState, int start, int end) {

if (start >= end) {
return currentState;
}

currentState = resolveNextStep(currentState);

return resolvePuzzle(currentState, start + 1, end);
}

private static String resolveNextStep(String currentState) {
char[] currentStateChars = currentState.toCharArray();

int localCount = 0;
String output = "";
Character currentChar = null;

for (int i = 0; i < currentStateChars.length; ++i) {
++localCount;

if (currentChar == null) {
currentChar = currentStateChars[i];
} else {
if (currentStateChars[i] != currentChar) {
output += (localCount - 1) + "" + currentChar;

localCount = 1;
currentChar = currentStateChars[i];
}
}
}

if (localCount != 0) {
output += localCount + "" + currentChar;
}

return output;
}

public static void main(String[] args) {
System.out.println(resolvePuzzle("1", 1, 2)); // will output 11
System.out.println(resolvePuzzle("1", 1, 6)); // will output 312211
}
}``````

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

This pattern is count and say. How it works is starting from 1, next number in series will

"1" -> "One 1" i.e "11"
"11" -> "Two 1" i.e "21"
"21" -> "One 2 One 1" i.e "1211"
"1211" -> "One 1 One 2 Two 1" i.e 111221
.....

``````class GetCountAndSay {
public String solution(int n) {
if(n == 0) {
return "";
}
String out = "1";
int count = 1;
while (count != n) {
int c = 0;
String in = out;
out = "";
for(int i = 0; i < in.length()-1; i++) {
if(in.charAt(i) == in.charAt(i+1)) {
c++;
} else {
c++;
out = out+("" + c) + in.charAt(i);
c=0;
}
}
c++;
out = out+("" + c) + in.charAt(in.length()-1);
count++;
}
return out;
}
}

public class GoogleGetCountAndSay {
public static void main(String[] args) {
GetCountAndSay mSol = new GetCountAndSay();
System.out.println(mSol.solution(1));
System.out.println(mSol.solution(2));
System.out.println(mSol.solution(3));
System.out.println(mSol.solution(4));
System.out.println(mSol.solution(5));
System.out.println(mSol.solution(6));
System.out.println(mSol.solution(7));
System.out.println(mSol.solution(8));
System.out.println(mSol.solution(9));
System.out.println(mSol.solution(10));
System.out.println(mSol.solution(11));
System.out.println(mSol.solution(12));
}
}``````

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

Can some one please explain how 111221 is derived from 1211?

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

count from left. e.g 1211 then it is one one, one two and two one. and so 111221

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

C++11 version

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

using std::cout;
using std::endl;
using std::string;
using std::to_string;

string find_next_pattern(string prev);
string find_nth_pattern(int n);

int main() {

cout << find_nth_pattern(1) << endl;

return 0;
}

string find_nth_pattern(int n) {
if (n <= 0) {
return "Error, please give positive number..";
}
string nth_ptn = "1";
for (int i = 1; i < n; i ++) {
nth_ptn = find_next_pattern(nth_ptn);
}
return nth_ptn;
}

string find_next_pattern(string prev) {
string next = "";
int counter = 1;
char compare = prev[0];

for (int i = 1; i < prev.length(); i++) {
if (prev[i] == compare) {
counter++;
}
else {
next.append(to_string(counter) + compare);
counter = 1;
compare = prev[i];
}
}
next.append(to_string(counter) + compare);

return next;``````

}

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

All of the solutions I see here are great. But based on the discussion I had with my interviewer, she was looking for a double recursive solution. Obviously I failed to answer it in the interview, but I have the answer now. The code becomes very small with double recursive solution:

``````String get(int n){
if (n==1)
return "1";
String last= get(n-1);
return readAndSay(last,0);
}
private String readAndSay(String input, int index){
if(index>=input.length())
return "";
int next;
for(next=index;next<input.length() && input.charAt(index)==input.charAt(next); next++);
return (next-index)+""+input.charAt(index)+ readAndSay(input,next);
}``````

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

``````#include <list>
using namespace std;

list<int> generateNextLayer(const list<int>& l)
{
list<int> ret_val;
list<int>::const_iterator pos = l.begin();
int curr_val = *pos;
int curr_val_count = 1;
pos++;

while(pos != l.end())
{
if(*pos != curr_val)
{
ret_val.push_back(curr_val_count);
ret_val.push_back(curr_val);
curr_val = *pos;
curr_val_count = 1;
}
else
{
curr_val_count++;
}
pos++;
}

ret_val.push_back(curr_val_count);
ret_val.push_back(curr_val);

return ret_val;
}

void print(const list<int> &l)
{
for(auto b = l.begin(); b != l.end(); ++b)
{
std::cout << *b;
}
std::cout << std::endl;

}

int main()
{
list<int> l;
l.push_back(1);

int n;
cin >> n;

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

print(l);
return 0;
}``````

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

In clojure

``````defn num-counter [x]
(let [[st ch count] (reduce (fn [acc element]
(let [r (acc 0) ;result until now
l (acc 1) ;last element
c (acc 2)] ;number of times last element has been seen until now
(cond (nil? l) [r element 1]
(= l element) [r l (+ c 1)]
:else (if (nil? r) [(format "%s%s" c l) element 1] [(format "%s%s%s" r c l) element 1]))))
[nil nil 0] ;reduce function start value
(into [] (.toCharArray x)))] ;convert given string to char vector
(if (nil? st) (format "%s%s" count ch) (format "%s%s%s" st count ch))))

(defn get-nth [n x]
(last (take n (iterate num-counter x))))``````

Test with (get-nth 10 "1")

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

In clojure, you would

``````defn num-counter [x]
(let [[st ch count] (reduce (fn [acc element]
(let [r (acc 0) ;result until now
l (acc 1) ;last element
c (acc 2)] ;number of times last element has been seen until now
(cond (nil? l) [r element 1]
(= l element) [r l (+ c 1)]
:else (if (nil? r) [(format "%s%s" c l) element 1] [(format "%s%s%s" r c l) element 1]))))
[nil nil 0] ;reduce function start value
(into [] (.toCharArray x)))] ;convert given string to char vector
(if (nil? st) (format "%s%s" count ch) (format "%s%s%s" st count ch))))

(defn get-nth [n x]
(last (take n (iterate num-counter x))))``````

To test, (get-nth 10 "1")

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

in clojure,

``````(defn num-counter [x]
(let [[st ch count] (reduce (fn [acc element]
(let [r (acc 0) ;result until now
l (acc 1) ;last element
c (acc 2)] ;number of times last element has been seen until now
(cond (nil? l) [r element 1]
(= l element) [r l (+ c 1)]
:else (if (nil? r) [(format "%s%s" c l) element 1] [(format "%s%s%s" r c l) element 1]))))
[nil nil 0] ;reduce function start value
(into [] (.toCharArray x)))] ;convert given string to char vector
(if (nil? st) (format "%s%s" count ch) (format "%s%s%s" st count ch))))

(defn get-nth [n x]
(last (take n (iterate num-counter x))))``````

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

``````(defn num-counter [x]
(let [[st ch count] (reduce (fn [acc element]
(let [r (acc 0) ;result until now
l (acc 1) ;last element
c (acc 2)] ;number of times last element has been seen until now
(cond (nil? l) [r element 1]
(= l element) [r l (+ c 1)]
:else (if (nil? r) [(format "%s%s" c l) element 1] [(format "%s%s%s" r c l) element 1]))))
[nil nil 0] ;reduce function start value
(into [] (.toCharArray x)))] ;convert given string to char vector
(if (nil? st) (format "%s%s" count ch) (format "%s%s%s" st count ch))))

(defn get-nth [n x]
(last (take n (iterate num-counter x))))``````

To test, try (get-nth 10 "1")

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

This prints:
1
11
21
1211
111221
312211
13112221

``````public static void main(String[] args){
int n = 7;
String str = "1";

while(n-->0){
System.out.println(str);
String tmp ="";
for(int i =0; i<str.length();)
{
int count =0;
char ch = str.charAt(i);
int j = i;
while(j<str.length() &&  str.charAt(j++)== ch)count++;
tmp = tmp+count+ch;
i= i +count;
}
str=tmp;
}``````

}

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

``````public class HelloWorld{

public static void main(String []args){
System.out.println(f(7));
}

public static int f(int n){
if(n==1){
return 1;
}

int temp= f(n-1);
String str= new Integer(temp).toString();
String out= "";
int i=0;
int len= str.length();
while(i<len){
int count= 1;
while((i+1)<len && (str.charAt(i)==str.charAt(i+1))){
count++;
i++;
}
out+=count+""+str.charAt(i);
i++;
}
return Integer.parseInt(out);
}
}``````

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

A recursive approach based on SK's solution

``````public static String getNthSequence(int n) {

if(n==1) {
return 1 + "";
}

String prevRes = "";
String output = "";

prevRes = getNthSequence(n-1);

for(int i=1; i <= prevRes.length(); i++) {
int count = 1;
while(i < prevRes.length() && (prevRes.charAt(i) == prevRes.charAt(i-1))) {
count ++;
i++;
}

output += count + "" + prevRes.charAt(i-1) + "";
}
return output;
}``````

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

``````package javaapplication20;

import java.util.Scanner;

public class JavaApplication20 {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int term,n=1,j,count=0,b,m,t=0;
int S[] = new int[100];
int number[]=new int[100];
Scanner in=new Scanner(System.in);
System.out.println("enter the limit");
m=in.nextInt();
m=m-1;
if(m<0)
System.exit(0);
term=1;
System.out.print(term);
System.out.print(" , ");
S[0]=1;
if(m<0)
System.exit(0);

while(m!=0)
{
t=0;
for(int k=0;k<n;k++)
{
b=S[k];
for(j=0;j<n;j++)
{
if(b==S[j]&&b!=0)
{

count++;
S[j]=0;

}
}

if(count!=0)
{
number[t]=count;
number[t+1]=b;
t=t+2;
}
count=0;
}
for(int i=0;i<t;i++)
{
System.out.print(number[i]);
S[i]=number[i];
n=t;
}
System.out.print(" , " );
m--;
}
}
}``````

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

use this code
package javaapplication20;

import java.util.Scanner;

public class JavaApplication20 {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int term,n=1,j,count=0,b,m,t=0;
int S[] = new int[100];
int number[]=new int[100];
Scanner in=new Scanner(System.in);
System.out.println("enter the limit");
m=in.nextInt();
m=m-1;
if(m<0)
System.exit(0);
term=1;
System.out.print(term);
System.out.print(" , ");
S[0]=1;
if(m<0)
System.exit(0);

while(m!=0)
{
t=0;
for(int k=0;k<n;k++)
{
b=S[k];
for(j=0;j<n;j++)
{
if(b==S[j]&&b!=0)
{

count++;
S[j]=0;

}
}

if(count!=0)
{
number[t]=count;
number[t+1]=b;
t=t+2;
}
count=0;
}
for(int i=0;i<t;i++)
{
System.out.print(number[i]);
S[i]=number[i];
n=t;
}
System.out.print(" , " );
m--;
}
}
}

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

``````static string Nth(int n)
{
string prev = "1";
StringBuilder cur = new StringBuilder();

for (int i = 0; i < n - 1; i++)
{
int count = 1;
for (int j = 1; j < prev.Length; j++)
{
if (prev[j] != prev[j - 1])
{
cur.Append(count.ToString() + prev[j - 1].ToString());
count = 1;
}
else
{
count++;
}
}
cur.Append(count.ToString() + prev[prev.Length - 1].ToString());
prev = cur.ToString();
cur.Clear();
}

return prev;
}``````

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

I'm not sure if I understanding it right, why can't we just pre-process the string by creating a array (if provided the element doesn't exceed 2^64 for a 64 bit machine) or else create a array of pointers pointing to the location of the element within the string or to object with pointer to the location of the element in string and a variable indicating the length of the element.

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