Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
You're given number n and your task is to return nth look-and-say sequence.
Wiki:
In mathematics, the look-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... (sequence A005150 in OEIS).
To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit. For example:
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
1211 is read off as "one 1, then one 2, then two 1s" or 111221.
111221 is read off as "three 1s, then two 2s, then one 1" or 312211.
int main()
{
std::vector<int> tmp;
std::vector<int> result;
tmp.push_back(1);
for (uint32_t i = 0; i < 5; i++) {
result.clear();
while (!tmp.empty()) {
std::vector<int>::iterator it = tmp.begin();
int c = 0;
int num = *it;
while ((num == *it) && !tmp.empty()) {
it = tmp.erase(it);
c++;
}
result.push_back(c);
result.push_back(num);
}
tmp = result;
}
std::vector<int>::iterator it;
for (it = result.begin(); it != result.end(); it++) {
printf("%d", *it);
}
return 0;
}
int main()
{
std::vector<int> tmp;
std::vector<int> result;
tmp.push_back(1);
for (uint32_t i = 0; i < 5; i++) {
result.clear();
while (!tmp.empty()) {
std::vector<int>::iterator it = tmp.begin();
int c = 0;
int num = *it;
while ((num == *it) && !tmp.empty()) {
it = tmp.erase(it);
c++;
}
result.push_back(c);
result.push_back(num);
}
tmp = result;
}
std::vector<int>::iterator it;
for (it = result.begin(); it != result.end(); it++) {
printf("%d", *it);
}
return 0;
}
public String pattern(int input){
return patternUtil(input, "1");
}
public String patternUtil(int input, String result)
{
if(input == 0) {
return result;
}
char curChar = result.charAt(0);
String newResult = "";
int counter = 0;
for(int i = 0; i< result.length(); i++) {
char character = result.charAt(i);
if(character != curChar) {
newResult = newResult + counter;
newResult = newResult + curChar;
counter = 0;
curChar = character;
}
counter ++;
}
newResult = newResult + counter;
newResult = newResult + curChar;
return patternUtil(input -1 , newResult);
}
It's just run length encoding, create a table of length n+1 and fill it up. The algorithm is as follows:
import java.util.*;
public class LookAndSay {
public static void main (String[] args) {
String num = "1";
for (int i = 1; i<=4; i++) {
System.out.println(num);
num = lookAndSay(num);
}
}
public static String lookAndSay (String num) {
StringBuilder sb = new StringBuilder();
char first = num.charAt(0);
int count = 1;
if (num.length() == 1) {
sb.append(count);
sb.append(first);
return sb.toString();
}
for (int i = 1; i < num.length(); i++) {
if (first == num.charAt(i)) {
count++;
}
else {
sb.append(count);
sb.append(first);
first = num.charAt(i);
count = 1;
}
if (i == num.length() - 1) {
sb.append(count);
sb.append(first);
}
}
return sb.toString();
}
}
I considered the number as a String, but we can also modify this for num as an Integer.
Solution in C++. I read the string from right to left, but produce the new string from left to right, and reverse it in the end of the iteration.
using std::string;
string pattern(int input)
{
int current;
string output = "1";
for (current = 0; current < input; ++current) {
string new_output;
unsigned len = output.length();
int i = len-1;
int counter = 0;
int current_digit = 1;
int digit;
while (i >= 0) {
digit = output[i] - '0';
// Reset count
if (digit != current_digit) {
new_output.push_back(current_digit + '0');
string counter_str = std::to_string(counter);
std::reverse(counter_str.begin(), counter_str.end());
new_output.append(counter_str);
current_digit = digit;
counter = 1;
}
else {
++counter;
}
--i;
}
// Append last segment of the string
new_output.push_back(digit + '0');
string counter_str = std::to_string(counter);
std::reverse(counter_str.begin(), counter_str.end());
new_output.append(counter_str);
std::reverse(new_output.begin(), new_output.end());
std::cout << new_output << "\n";
output = new_output;
}
return output;
}
Here's a simpler, shorter and more efficient code in c++ using iterators and find_if:
#include <algorithm>
#include <sstream>
string LookAndSaySequence(unsigned int _n)
{
string sequence("1");
for (unsigned int i = 0; i < _n; ++i)
{
auto iter = sequence.begin();
std::stringstream sSrtream;
while (iter != sequence.end())
{
auto c = *iter;
auto sequenceEndedIter = std::find_if(iter + 1, sequence.end(), [c](char _c) { return c != _c; });
auto count = sequenceEndedIter - iter;
sSrtream << count << c;
iter = sequenceEndedIter;
}
sequence = sSrtream.str();
}
return sequence;
}
def __count(seq):
count = 0
first_char = seq[0]
for i in seq:
if i == first_char:
count += 1
else:
break
return seq[count:], str(count), first_char
def lsseq(n,__cache=['1']):
if len(__cache) > n:
return __cache[n]
while len(__cache) <= n:
last_seq = __cache[-1]
new_last_seq = ''
while last_seq:
last_seq, x, y = __count(last_seq)
new_last_seq = ''.join([new_last_seq, x, y])
__cache.append(new_last_seq)
return __cache[n]
def __count(seq):
count = 0
for i in seq:
if i == seq[0]:
count += 1
else:
break
return seq[count:], str(count), seq[0]
def lsseq(n,__cache=['1']):
if len(__cache) > n:
return __cache[n]
while len(__cache) <= n:
last_seq = __cache[-1]
new_last_seq = ''
while last_seq:
last_seq, count, num= __count(last_seq)
new_last_seq = ''.join([new_last_seq, count, num])
__cache.append(new_last_seq)
return __cache[n]
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
int getpattern(int n)
{
int i=0;
int count=0,j=-1,k=0;
int output;
char prev[20],c;
prev[0]='1';
prev[1]='\0';
while(k<n-1)
{
output=0;
while(prev[i]!='\0')
{
if(i!=0&&c!=prev[i])
{ j++;
output=output*10+count;
j++;
output=output*10+(c-'0');
count=0;
}
c=prev[i];
count++;
i++;
}
if(count!=0)
{
j++;
output=output*10;
output+=count;
j++;
output=output*10+(c-'0');
count=0;
}
itoa(output,prev,10);
count=0;
j=-1;
i=0;
k++;
}
return output;
}
void main()
{
int r=getpattern(7);
printf("%d",r);
getch();
}
public static String pattern(final int input) {
if (input == 0) return "1";
final String ans = pattern(input - 1);
final StringBuilder resultStr = new StringBuilder();
int count = 0;
char curr = 0;
for (final char c : ans.toCharArray()) {
if (count == 0) {
curr = c;
count = 1;
} else if (curr == c) {
count++;
} else {
resultStr.append(String.valueOf(count))
.append(String.valueOf(curr));
curr = c;
count = 1;
}
}
resultStr.append(String.valueOf(count))
.append(String.valueOf(curr));
return resultStr.toString();
}
#include<iostream>
#include<vector>
#include<string>
using namespace std;
string* GetPattern(int input)
{
if(input<0)
{
return NULL;
}
string *str=new string[input+1];
str[0]="1";
for(int i=1;i<=input;i++)
{
string currentStr=str[i-1];
int currentLength=currentStr.length();
string nextStr="";
int tmpIndex=0;
int charLength=0;
while (tmpIndex<currentLength)
{
int k=tmpIndex+1;
char buffer[10];
if(k>=currentLength)
{
charLength=k-tmpIndex;
sprintf_s(buffer,"%d%c",charLength,currentStr[tmpIndex]);
nextStr+=(string)buffer;
tmpIndex=k;
break;
}
for(;k<currentLength;k++)
{
if(currentStr[k]!=currentStr[tmpIndex])
{
break;
}
}
charLength=k-tmpIndex;
sprintf_s(buffer,"%d%c",charLength,currentStr[tmpIndex]);
nextStr+=buffer;
tmpIndex=k;
}
str[i]=nextStr;
}
return str;
}
int main()
{
int patternNumber=30;
string * result=GetPattern(patternNumber);
if(result!=NULL)
{
for(int i=0;i<=patternNumber;i++)
{
cout<<result[i]<<endl;
}
}
return 0;
}
public String pattern(int input){
if (input == 0) {
return "1";
}
String value = "1";
for (int i = 1 ; i <= input ;++i) {
value = count(value);
}
return value;
}
public String count (String s){
StringBuilder sb = new StringBuilder ();
int count = 1;
for (int i = 1 ; i < s .length() ;++i) {
if (s.charAt(i) == s.charAt(i-1)) {
count++;
}else{
sb.append(count);
sb.append(s.charAt(i-1));
count = 1;
}
}
sb.append(count);
sb.append(s.charAt(s.length() -1));
return sb.toString();
}
-(NSString*)lookAndSay:(NSInteger)num
{
NSArray* arr = @[@1];
for (int i = 0; i < num; i++)
{
arr = [self lookAndSayForArray:arr];
}
return [arr componentsJoinedByString:@""];
}
-(NSArray*)lookAndSayForArray:(NSArray*)arr
{
NSMutableArray* resultArr = [NSMutableArray new];
NSInteger currentCount = 1;
for (int i = 0; i < [arr count]; i++)
{
if(i == [arr count] - 1 || ![arr[i] isEqualToNumber:arr[i+1]])
{
[resultArr addObject:@(currentCount)];
[resultArr addObject:arr[i]];
currentCount = 1;
}
else
{
currentCount++;
}
}
return resultArr;
}
Python 3
from itertools import groupby
def pattern(num):
patt = '1'
for n in range(num):
patt = (''.join([str(x.count(x[0])) + x[0] for x in
[list(g) for k, g in groupby(patt)]]))
return patt
print([pattern(x) for x in range(6)])
# ['1', '11', '21', '1211', '111221', '312211']
public static string NumberToReadString(int number)
{
string input = "1";
string tempResult = null;
if (number < 0)
{
throw new ArgumentException("Invalid Argument");
}
for (int i = 0; i < number; i++)
{
tempResult = ReadString(input);
input = tempResult;
}
return input;
}
public static string ReadString(string str)
{
if (String.IsNullOrEmpty(str) || String.IsNullOrWhiteSpace(str))
{
throw new ArgumentException("Invalid Argument");
}
int index = 0, count = 1;
StringBuilder result = new StringBuilder();
char curr, next;
for (index = 0; index < str.Length - 1; index++)
{
curr = str[index];
next = str[index + 1];
if (curr != next)
{
result.AppendFormat("{0}{1}", count, curr);
count = 1;
}
else
{
count++;
}
}
result.AppendFormat("{0}{1}", count, str[index]);
return result.ToString();
}
A simple c# solution
public static void Main(String[] args)
{
PrintLookAndSayPattern(5);
}
public static void PrintLookAndSayPattern(int n)
{
string prevElem = "1";
for (int i = 1; i<= n; i++)
{
Console.WriteLine(prevElem);
prevElem = LookAndSay(prevElem);
}
}
public static string LookAndSay(string lookupValue)
{
int charCount = 0;
char prevChar = '-';
string stringToSay = string.Empty;
foreach (char c in lookupValue.ToCharArray())
{
if (prevChar == '-')
{
prevChar = c;
charCount = 1;
}
else if (prevChar == c)
{
charCount++;
}
else
{
stringToSay += charCount;
stringToSay += prevChar;
prevChar = c;
charCount = 1;
}
}
stringToSay += charCount;
stringToSay += (int)Char.GetNumericValue(prevChar);
return stringToSay;
}
Fun easy one.
public static List<int> CalculatePattern(int level)
{
if(level < 0)
throw new ArgumentException("level");
List<int> result = new List<int>() { 1 };
for(int i = 1; i <= level; i++)
{
List<int> temp = new List<int>();
int number = result[0];
int count = 0;
foreach(int r in result)
{
if(r == number)
{
count++;
}
else
{
temp.Add(count);
temp.Add(number);
number = r;
count = 1;
}
}
temp.Add(count);
temp.Add(number);
result = temp;
}
return result;
}
public class Patterns {
static int n = 5;
static String p = null;
static int i = 0;
static void rep(String result) {
System.out.println(result);
i++;
if (i <= n) {
char c[] = result.toCharArray();
Deque<Character> stack = new ArrayDeque<Character>();
int tempcount = 0;
String nres="";
for (int i = 0; i < c.length; i++) {
if(result.length()==1)
{
stack.push(c[i]);
rep("1"+c[i]);
}
else
{
if(stack.isEmpty()==false){
if(stack.peek()==c[i]){
tempcount+=1;
stack.push(c[i]);
if(c.length-i==1){
nres=nres+""+tempcount+""+c[i];
}
}
else
{
nres=nres+""+tempcount+""+c[i-1];
tempcount=1;
stack.push(c[i]);
if(c.length-i==1){
nres=nres+""+tempcount+""+c[i];
}
}
}
else
{
stack.push(c[i]);
tempcount+=1;
}
}
}
rep(nres);
}
}
public static void main(String args[]) {
rep("1");
}
}
#include <string>
using namespace std;
string pattern(int index)
{
string last("1"), cur;
int i = 0;
while (++i <= index)
{
cur.clear();
char c = last[0];
int j = 0, count = 1;
while (++j < last.length())
{
if (last[j] == c)
{
++count;
}
else
{
cur += (count + '0');
cur += c;
c = last[j];
count = 1;
}
}
cur += (count + '0');
cur += c;
last = cur;
}
return cur;
}
<?php
$n = (int)$argv[1];
function pattern($num) {
$seq = '1';
for ($i = 1; $i <= $num; $i++) {
$seq = get_next_seq($seq);
}
return $seq;
}
function get_next_seq($prev) {
$n = strlen($prev);
$next = '';
for($i = 0; $i < $n; $i++) {
$len = get_len($i, $prev);
$next = $next . $len . $prev[$i];
$i += $len - 1;
}
return $next;
}
function get_len($pos, $prev) {
$elem = $prev[$pos];
$len = 0;
$i = $pos;
while ($elem == $prev[$i]) {
$i++;
$len++;
}
return $len;
}
$p = pattern($n);
var_dump($p);
public static void main(String args[]){
System.out.println(patternUtil(4));
}
public static String patternUtil(int input)
{
String result = "1";
while(input> 0){
input--;
char currentCharacter = result.charAt(0);
String newResult = "";
int countRipetitionChar = 0;
for(int i = 0; i< result.length(); i++) {
char nextCharacter = result.charAt(i);
if(nextCharacter != currentCharacter) {
newResult = newResult + countRipetitionChar + currentCharacter;
countRipetitionChar = 0;
currentCharacter = nextCharacter;
}
countRipetitionChar ++;
}
result = newResult + countRipetitionChar + currentCharacter;
}
return result;
}
public static void main (String[] args) {
System.out.println(pattern(10));
}
static String countSay(String pattern) {
StringBuilder sb = new StringBuilder();
int count = 0;
char c = pattern.charAt(0);
for (int i = 0; i < pattern.length(); i++) {
char curChar = pattern.charAt(i);
if (curChar == c) count++;
else {
sb.append(count).append(c);
c = curChar;
count = 1;
}
}
sb.append(count).append(c);
return sb.toString();
}
static String pattern(int input) {
if (input == 0) return "1";
return countSay(pattern(input - 1));
}
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class RecursionTest {
public RecursionTest() {
}
int[] compute(int n){
int[] res = null;
if(n == 0){
res = new int[1];
res[0] = 1;
}
// recursion
if(n>0){
int[] prevRes = compute(n-1);
List<Integer> resList = new LinkedList<Integer>();
int prevVal = prevRes[0], freq = 1;
for(int i = 1; i < prevRes.length; i++){
int x = prevRes[i];
if(x == prevVal){
freq++;
} else {
resList.add(freq);
resList.add(prevVal);
prevVal = x;
freq = 1;
}
}
resList.add(freq);
resList.add(prevVal);
res = new int[resList.size()];
for(int i = 0; i < resList.size(); i++){
res[i] = resList.get(i);
}
}
return res;
}
public static void main(String[] args){
RecursionTest wrapper = new RecursionTest();
for(int i = 0; i < 7; i++){
int[] res = wrapper.compute(i);
System.out.print(i + "\t");
System.out.println(Arrays.toString(res));
}
}
}
I believe this is an elegant recursive solution which doesn't use Strings.
static int findPattern(int i) {
if(i == 0)
return 1;
return countOf(findPattern(i-1),0);
}
static int countOf(int pattern, int level) {
int count = 1;
int num = pattern % 10;
int temp = num;
while(temp == num && temp != 0) {
pattern = pattern / 10;
temp = pattern % 10;
if(temp == num)
count++;
}
int pat = (int) ((count*10 + num) * Math.pow(10,level));
if(temp == 0)
return pat;
else {
return countOf(pattern, level+2) + pat;
}
}
Simple and clean working example.
std::string findPatternImp(std::string in)
{
std::string res;
int numOfCurrChar = 0;
char prevChar = in[0];
for (int i = 0; i < in.length(); ++i)
{
if (in[i] == prevChar)
{
++numOfCurrChar;
}
else
{
res.append(std::to_string(numOfCurrChar));
res += prevChar;
numOfCurrChar = 1;
}
prevChar = in[i];
if (in.length() == i + 1){
res.append(std::to_string(numOfCurrChar));
res += prevChar;
}
}
return res;
}
std::string findPattern(const int num)
{
std::string result = "1";
for (size_t i = 0; i < num-1; i++)
{
cout << i << ": " << result << endl;
result = findPatternImp(result);
}
return result;
}
This is called "The Conway Sequence"
My approach in Java:
public static void main(String[] args) {
conwaySequence(5);
}
private static void conwaySequence(int num) {
if(num < 1)
return;
System.out.println("1");
String output = "1";
String new_output = "";
int current_count = 0;
char current_char;
for(int i = 1; i < num; i++){
current_char = output.charAt(0);
for(int j = 0; j < output.length(); j++){
if(output.charAt(j) == current_char)
current_count++;
else{
new_output += Integer.toString(current_count) + current_char;
current_char = output.charAt(j);
current_count = 1;
}
}
output = new_output + Integer.toString(current_count) + current_char;
new_output = "";
current_count = 0;
System.out.println(output);
}
}
int main()
{
std::vector<int> tmp;
std::vector<int> result;
tmp.push_back(1);
for (uint32_t i = 0; i < 5; i++) {
result.clear();
while (!tmp.empty()) {
std::vector<int>::iterator it = tmp.begin();
int c = 0;
int num = *it;
while ((num == *it) && !tmp.empty()) {
it = tmp.erase(it);
c++;
}
result.push_back(c);
result.push_back(num);
}
tmp = result;
}
std::vector<int>::iterator it;
for (it = result.begin(); it != result.end(); it++) {
printf("%d", *it);
}
return 0;
}
int main()
{
std::vector<int> tmp;
std::vector<int> result;
tmp.push_back(1);
for (uint32_t i = 0; i < 5; i++) {
result.clear();
while (!tmp.empty()) {
std::vector<int>::iterator it = tmp.begin();
int c = 0;
int num = *it;
while ((num == *it) && !tmp.empty()) {
it = tmp.erase(it);
c++;
}
result.push_back(c);
result.push_back(num);
}
tmp = result;
}
std::vector<int>::iterator it;
for (it = result.begin(); it != result.end(); it++) {
printf("%d", *it);
}
return 0;
}
int main()
{
std::vector<int> tmp;
std::vector<int> result;
tmp.push_back(1);
for (uint32_t i = 0; i < 5; i++) {
result.clear();
while (!tmp.empty()) {
std::vector<int>::iterator it = tmp.begin();
int c = 0;
int num = *it;
while ((num == *it) && !tmp.empty()) {
it = tmp.erase(it);
c++;
}
result.push_back(c);
result.push_back(num);
}
tmp = result;
}
std::vector<int>::iterator it;
for (it = result.begin(); it != result.end(); it++) {
printf("%d", *it);
}
return 0;
}
int main()
{
std::vector<int> tmp;
std::vector<int> result;
tmp.push_back(1);
for (uint32_t i = 0; i < 5; i++) {
result.clear();
while (!tmp.empty()) {
std::vector<int>::iterator it = tmp.begin();
int c = 0;
int num = *it;
while ((num == *it) && !tmp.empty()) {
it = tmp.erase(it);
c++;
}
result.push_back(c);
result.push_back(num);
}
tmp = result;
}
std::vector<int>::iterator it;
for (it = result.begin(); it != result.end(); it++) {
printf("%d", *it);
}
return 0;
}
Here is C++ version of solution.
#include<string>
#include<iostream>
using namespace std;
string pattern(int input)
{
string result = "1";
char prev=' ';
char cur;
for (int i = 1; i<= input; i++)
{
string next;
int count = 0;
for (int j = 0; j < result.length(); j++)
{
cur = result[j];
if (j > 0 && prev != cur)
{
next.push_back('0'+count);
next.push_back(prev);
count =1;
} else {
count++;
}
prev = cur;
if (j == result.length()-1)
{
next.push_back('0'+count);
next.push_back(cur);
}
}
result = next;
}
return result;
}
int main ()
{
cout <<"pattern = " << pattern(4)<<endl;
cout <<"pattern = " << pattern(5)<<endl;
return 1;
}
private static void pattern(int nb, String str, int offset)
{
if (offset == nb)
return;
System.out.print(offset + ":" + str);
int occurence = 1;
int number = Integer.valueOf(str.charAt(0)) - '0';
StringBuilder result = new StringBuilder();
for (int j = 1; j < str.length(); j++)
{
int current = Integer.valueOf(str.charAt(j)) - '0';
if (current == number)
occurence++;
else
{
result.append(occurence + "" + number);
number = current;
occurence = 1;
}
}
result.append(occurence + "" + number);
System.out.println();
pattern(nb, result.toString(), offset + 1);
}
public static void init()
{
pattern(6, "1", 0);
}
Can please any one explain the question
- Anonymous November 21, 2014