Facebook Interview Question Software Engineer / Developers
public class Solution {
public String countAndSay(int n) {
String ans = "1";
for(int i=2;i<=n;i++)
{
ans = GetSay(ans);
}
return ans;
}
public String GetSay(String inp){
int len = inp.length();
String ans = "";
char last = inp.charAt(0);
int count = 1;
for(int i=1;i<len;i++)
{
char ch = inp.charAt(i);
if(ch == last)
{
count++;
}
else
{
ans+=count+""+last;
count = 1;
last = ch;
}
}
ans+=count+""+last;
return ans;
}
}
Please check below working java solution O(MN) time complexity and O(1) space complexity.
public class Solution {
public String countAndSay(int n) {
String ans = "1";
for(int i=2;i<=n;i++)
{
ans = GetSay(ans);
}
return ans;
}
public String GetSay(String inp){
int len = inp.length();
String ans = "";
char last = inp.charAt(0);
int count = 1;
for(int i=1;i<len;i++)
{
char ch = inp.charAt(i);
if(ch == last)
{
count++;
}
else
{
ans+=count+""+last;
count = 1;
last = ch;
}
}
ans+=count+""+last;
return ans;
}
}
<pre lang="java" line="1" title="CodeMonkey23143" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(countAndSay(3));
}
private static String countAndSay(int n)
{
StringBuilder prev = new StringBuilder("1");
StringBuilder curr = new StringBuilder();
while (n-- > 0)
{
curr.delete(0, curr.length());
for (int i = 0; i < prev.length(); i++)
{
char c = prev.charAt(i);
int count = 1;
int j = i + 1;
for (; j < prev.length() && prev.charAt(j) == c; j++, count++)
;
i = j - 1;
curr.append(count);
curr.append(c);
}
StringBuilder t = prev;
prev = curr;
curr = t;
}
return prev.toString();
}
}
</pre><pre title="CodeMonkey23143" input="yes">
</pre>
public void countAndSay(int n) {
String current = "0 1";
String previous = "";
int count=0;
do {
System.out.println(current);
previous = current;
++count;
StringBuilder sb = new StringBuilder();
String [] str = previous.split(" ");
int [] A = new int[str.length];
for (int i=0; i<A.length; i++) {
A[i] = Integer.parseInt(str[i]);
}
sb.append(count + " ");
int i = 1;
while (i<A.length) {
int c = A[i];
int cnt = 0;
while ((i < A.length) && A[i] == c) {
++cnt;
i=i+1;
}
sb.append(cnt + " ");
sb.append(c + " ");
}
current = sb.toString();
}while (n-- > 0);
}
function a = test(n)
a = 1;
if (n == 0)
return
end
while (n > 0)
old = a;
len = columns(old);
undercheck = old(1);
count = 0;
pt = 0;
for i=1:len
if (old(i) == undercheck)
count += 1;
else
a(pt+1) = undercheck;
a(pt+2) = count;
undercheck = old(i);
count = 1;
pt += 2;
end
end
a(pt+1) = undercheck;
a(pt+2) = count;
n -= 1;
end
end
<pre lang="java" line="1" title="CodeMonkey12320" class="run-this">% octave code
%
function a = test(n)
a = 1;
if (n == 0)
return
end
while (n > 0)
old = a;
len = columns(old);
undercheck = old(1);
count = 0;
pt = 0;
for i=1:len
if (old(i) == undercheck)
count += 1;
else
a(pt+1) = undercheck;
a(pt+2) = count;
undercheck = old(i);
count = 1;
pt += 2;
end
end
a(pt+1) = undercheck;
a(pt+2) = count;
n -= 1;
end
end</pre><pre title="CodeMonkey12320" input="yes">
</pre>
<pre lang="java" line="1" title="CodeMonkey22935" class="run-this">#!/usr/bin/env python
def countSay(n):
code = [1]
if n==0:
return code
while n>0:
old = code
size = len(code)
code = []
undercheck = old[0]
count = 0
for i in range(size):
if old[i]==undercheck:
count += 1
else:
code.append(undercheck)
code.append(count)
undercheck = old[i]
count = 1
code.append(undercheck)
code.append(count)
n -= 1
return code
</pre><pre title="CodeMonkey22935" input="yes">
</pre>
How about using a queue?
Queue<int> q = new Queue<int>();
q.Enqueue(1);
int length = 1;
for (int i = 1; i < n; i++)
{
int nextLength = 0;
int next = q.Peek();
int count = 0;
for (int j = 0; j < length; j++)
{
if (next == q.Peek())
{
count++;
q.Dequeue();
}
else
{
q.Enqueue(count);
q.Enqueue(next);
nextLength += 2;
next = q.Dequeue();
count = 1;
}
}
q.Enqueue(count);
q.Enqueue(next);
nextLength += 2;
length = nextLength;
}
#include<stdio.h>
#include<iostream>
using namespace std;
int b[100] ;
int a[100];
int ct ;
int func()
{
int i = 1 ;
int j = 0 ;
int ctr = 1 ;
while(1)
{
if(i == ct)
break ;
if(a[i] == a[i-1])
ctr++;
else
{
b[j++] = ctr ;
b[j++] = a[i-1] ;
ctr = 1 ;
}
i++;
}
b[j++] = ctr ;
b[j++] = a[i-1] ;
ct = j ;
}
int main()
{
int n ;
int i ;
int j ;
cin >> n ;
ct = 1 ;
a[0] = 1 ;
printf("0 1\n");
for(i = 1 ; i < n; i++)
{
printf("%d ",i);
func();
for(j = 0 ; j < ct ; j++)
{
printf("%d ",b[j]);
a[j] = b[j] ;
}
printf("\n");
}
return 0;
}
public static void csp(int n) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
for (int i = 1; i <= n; ++i) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
System.out.println();
for (int j : list) {
System.out.print(j + " ");
int count = 1;
if (map.containsKey(j)) {
count = map.get(j);
count++;
}
map.put(j, count);
}
list = new ArrayList<Integer>();
for (Integer k : map.keySet()) {
list.add(map.get(k));
list.add(k);
}
}
}
public static void csp(int n) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
for (int i = 1; i <= n; ++i) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
System.out.println();
for (int j : list) {
System.out.print(j + " ");
int count = 1;
if (map.containsKey(j)) {
count = map.get(j);
count++;
}
map.put(j, count);
}
list = new ArrayList<Integer>();
for (Integer k : map.keySet()) {
list.add(map.get(k));
list.add(k);
}
}
}
#import<stdio.h>
#import<string.h>
void countAndSay(char* string)
{
int i = 0;
int currentCharCount = 1;
char currentChar = string[i];
i++;
while(string[i] != '\0')
{
if(string[i] == currentChar)
{
currentCharCount++;
i++;
}
else
{
printf("%d %c ", currentCharCount, currentChar);
currentChar = string[i];
currentCharCount = 1;
i++;
}
}
printf("%d %c ", currentCharCount, currentChar);
}
int main()
{
char str[] = "1211";
countAndSay(str);
}
#include<iostream>
#include <sstream>
using namespace std;
void str_print(strint str);
int main()
{
int N;
string str="";
string temp="";
cin>>N;
int i=0;
int count=0;
while(i<=N)
{
if(i==0)
{cout<<"0"<<" 1"<<endl;str="1";}
else
{
temp="";
int start=0;
string te1="";
while(start<str.size())
{
count=0;
if(te1=="")
{
while(str[start]!=' ' && str[start]!='\0')
{
te1=te1+str[start];
start++;
}
}
string te2;
do{
te2="";
count++;
if(str[start]=='\0')
break;
start++;
while(str[start]!=' ' && str[start]!='\0')
{
te2=te2+str[start];
start++;
}
}while(te2==te1);
ostringstream convert;
convert << count;
if(temp!="")
temp=temp+" "+convert.str()+" "+te1;
else
temp=convert.str()+" "+te1;
string kl=te1;
if(te2!="" && te2!=te1)
te1=te2;
if(start>=str.size() && kl!=te1)
temp=temp+" 1 "+te1;
}
str=temp;
cout<<i<<" "<<str<<endl;
}
i++;
}
return 0;
}
public class Solution {
public String countAndSay(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
StringBuffer prev = new StringBuffer();
StringBuffer curr = new StringBuffer();
int count=1;
char temp='1';
if(n==1)
return "1";
for(int i=0;i<n;i++){
curr.setLength(0);
if(i == 0){
curr.append("1");
}
else{
for(int j=0;j<prev.length();j++){
if(j==0){
temp=prev.charAt(j);
count = 1;
}
else{
if(temp == prev.charAt(j)){
count ++;
}else{
curr.append(""+count);
curr.append(temp);
temp=prev.charAt(j);
count = 1;
}
}
}
curr.append(""+count);
curr.append(temp);
}
prev.setLength(0);
prev.append(curr);
}
return curr.toString();
}
}
public class Solution {
public String countAndSay(int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
StringBuffer prev = new StringBuffer();
StringBuffer curr = new StringBuffer();
int count=1;
char temp='1';
if(n==1)
return "1";
for(int i=0;i<n;i++){
curr.setLength(0);
if(i == 0){
curr.append("1");
}
else{
for(int j=0;j<prev.length();j++){
if(j==0){
temp=prev.charAt(j);
count = 1;
}
else{
if(temp == prev.charAt(j)){
count ++;
}else{
curr.append(""+count);
curr.append(temp);
temp=prev.charAt(j);
count = 1;
}
}
}
curr.append(""+count);
curr.append(temp);
}
prev.setLength(0);
prev.append(curr);
}
return curr.toString();
}
}
import java.util.ArrayList;
public class CountSay {
public CountSay() {
}
public static ArrayList<Integer> getNStr(int n) {
if (n == 0) {
ArrayList<Integer> o = new ArrayList<Integer>();
o.add(1);
return o;
}
ArrayList<Integer> out = getNStr(n-1);
int cnt = 0;
int prev = out.get(0);
ArrayList<Integer> out2 = new ArrayList<Integer>();
for (int i = 0; i <= out.size(); i++) {
if (i != out.size()) {
if ((int)(out.get(i)) == prev) {
cnt++;
prev = (int)(out.get(i));
} else {
out2.add(cnt);
out2.add(prev);
cnt = 1;
prev = out.get(i);
}
} else {
out2.add(cnt);
out2.add(prev);
}
}
return out2;
}
public static void printArray(ArrayList<Integer> a) {
System.out.println("length = " + a.size());
for(Integer i : a) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main (String[] args) {
int n = Integer.parseInt(args[0]); // n >= 1
ArrayList<Integer> out = getNStr(n);
printArray(out);
}
}
import java.util.LinkedHashMap;
import java.util.Map;
public class Solution {
public String countAndSay(int n) {
Map<Character,Integer> map=new LinkedHashMap<Character,Integer>();
StringBuilder sb=new StringBuilder();
String s=String.valueOf(n);
int c=1;
if(s.equals("1"))
return "1";
for(int i=0;i<s.length();i++)
{
if(map.containsKey(s.charAt(i)))
{
c++;
map.put(s.charAt(i),c);
}
else
{
map.put(s.charAt(i),c);
}
}
for(Map.Entry<Character,Integer> entry:map.entrySet())
{
sb=sb.append(entry.getValue()).append(entry.getKey());
}
// int x=Integer.parseInt(sb.toString());
return sb.toString();
}
}
Please check below working java solution O(MN) time complexity and O(1) space complexity.
public class Solution {
public String countAndSay(int n) {
String ans = "1";
for(int i=2;i<=n;i++)
{
ans = GetSay(ans);
}
return ans;
}
public String GetSay(String inp){
int len = inp.length();
String ans = "";
char last = inp.charAt(0);
int count = 1;
for(int i=1;i<len;i++)
{
char ch = inp.charAt(i);
if(ch == last)
{
count++;
}
else
{
ans+=count+""+last;
count = 1;
last = ch;
}
}
ans+=count+""+last;
return ans;
}
}
we have N
we can do :-
- Aditya October 20, 2010string s1="" , s2""; s1 = "1"; i=1; int tmp,cnt; if( N==0 ) print 0 and s1; while( i<=N ) { s2.clear(); for( j=0; j<strlen(s1); ) tmp = s1[j]; cnt = 0; while( s1[j] == tmp && j<strlen(s1) ) cnt++; j++; s2 += cnt+'0'; s2 += tmp + '0'; print i and s2; s1.clear(); s1 = s2; i++; }