Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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
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?
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"
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;
}
}
}
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);
}
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]);
}
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;
}
}
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
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;
}
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
}
}
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));
}
}
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;
}
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);
}
#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;
}
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")
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")
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))))
(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")
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;
}
}
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);
}
}
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;
}
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--;
}
}
}
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--;
}
}
}
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;
}
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.
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:
- SK May 05, 2015