## Google Interview Question for Software Engineers

• 3

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

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

@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 = "1";
sarray = "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<>();
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;
}
}
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;

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

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

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;

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);
}
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++);
}``````

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;
int number[]=new int;
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=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;
int number[]=new int;
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=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.

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.