CareerCup

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

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

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

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

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.