CareerCup

Follow up:

f(n) = f(n-1)+f(n-2)+f(n-3)+g(n-2)+2g(n-3)
g(n)=g(n-1)+g(n-2)+g(n-3)

f(n) all possible ways;
g(n) all possible ways without Absent.

For a record to be rewardable, 'A' cannot show up more than once.
So we ignore 'A' at the place and consider only the combination and arrangement for 'O' and 'L'.
We create a 2D array arr[i][j] where arr[i][0] is the number of strings with length i and ending letter 'O'; arr[i][1] is the number of strings with length i and ending letter 'L'

int count(int n) {

        int[][] arr = new int[n+1][2];
        arr[0] = new int[]{0, 1};
        arr[1] = new int[]{1, 1};

        for (int i = 2; i <= n; i++) {
            arr[i % 2][0] = arr[(i-1) % 2][0] + arr[(i-1) % 2][1];  // the ith letter is O
            arr[i % 2][1] = arr[(i-1) % 2][0] + arr[(i-2) % 2][0];  // the ith letter is L
        }

        int opt = arr[n][0] + arr[n][1];   // case when there is no "A"



        for (int i = 0; i < n; i++) {      // consider all the cases with one A, there are i letters to the left of A and n-i-1 letter to the right of A
            opt += ( arr[i][0] + arr[i][1] ) * ( arr[n-i-1][0] + arr[n-i-1][1] );
        }   

        return opt;
    }

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

public boolean studentReward(String studentRec) {

		studentRec = "OOLLAOOLLOO";

		if (studentRec.indexOf("A") != studentRec.lastIndexOf("A")) {
			// absent more than 1s
			return false;
		}

		// LLA ALL LAL
		// no consecutive late/Absent 3 times
		if (studentRec.matches(".*(A|L){3}.*")) {
			return false;
		}

		return true;
	}

public boolean studentReward(String studentRec) {

		studentRec = "OOLLAOOLLOO";

		if (studentRec.indexOf("A") != studentRec.lastIndexOf("A")) {
			// absent more than 1s
			return false;
		}

		// LLA ALL LAL
		// no consecutive late/Absent 3 times
		if (studentRec.matches(".*(A|L){3}.*")) {
			return false;
		}

		return true;
	}

public class StudentReward {

public enum reward{
LLL,LLA,AAL
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "OLLAOOOLLO";
boolean flag = true;
for(reward r :reward.values()){
if(str.contains(r.toString())){
flag = false;
}
}
System.out.println(flag);
}

}

public class StudentReward {public enum reward{ LLL,LLA,AAL} public static void main(String[] args) { String str = "OLLAOOOLLO"; boolean flag = true; for(reward r :reward.values()){if(str.contains(r.toString())){ flag = false;}}System.out.println(flag);}}

#Python

s = input("Enter the pattren:")

def studentattend(strr):

    if "LLL" in strr or "LLA" in strr or "LAL" in strr or "ALL" in strr:
        return(False)
    elif "AA" in ''.join(sorted(strr)):
        return(False)
    else:
        return(True)

b = studentattend(s)

if b == False:
    print("Student not eligible for reward")
else:
    print("Student is eligible for reward")

How did LLA become late thrice? He becomes late twice and absent once...or absent is counted as being late too?

#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
char ch[20],mask1=0,mask2=0,i=0;
cin>>ch;
while(ch[i])
{
if(ch[i]=='A')
{
mask1++;
}
if(strlen(ch)>(i+2)){
if((ch[i]=='A'||ch[i]=='L')&&(ch[i+1]=='A'||ch[i+1]=='L')&&(ch[i+2]=='A'||ch[i+2]=='L'))
return 0;
}

if(mask1==2)
{
return 0;
}
i++;
}
return 1;

}

#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
char ch[20],mask1=0,mask2=0,i=0;
cin>>ch;
while(ch[i])
{
if(ch[i]=='A')
{
mask1++;
}
if(strlen(ch)>(i+2)){
if((ch[i]=='A'||ch[i]=='L')&&(ch[i+1]=='A'||ch[i+1]=='L')&&(ch[i+2]=='A'||ch[i+2]=='L'))
return 0;
}

if(mask1==2)
{
return 0;
}
i++;
}
return 1;

}

bool IsRewarded(const char* sStr)
{
   return !strchr(sStr, 'A') && !strstr(sStr, "LLL");
}

We can figure out this by keeping two variable one is WasAbsent and ContinousLateCount, and if WasAbsent is true when we found a new Absent, return false, or if ContinousLateCount is 2 when he/she is Late, return false.
Here is how we will write the code

public static boolean ShouldbeRewarded(string attendance)
{
	if(String.IsNullOrWhiteSpace(attendance))
	{
		return true;
	}
	boolean wasAbsent = false;
	int continousLateCount = 0;
	boolean WasLateLastDate = false;
	for(int i = 0 ; i < attendance.Length;i++)
	{
		if(attendance[i] == 'A')
		{
			if(wasAbsent || continousLateCount >= 2)
			{
				return false;
			}
			wasAbsent = true;
			continousLateCount++;
		}
		else if(attendance[i] == 'L')
		{
			if(continousLateCount >= 2)
			{
				return false;
			}
			continousLateCount++;
		}
		else
		{
			continousLateCount = 0;
		}
	}
	return true;
}

O(n) time and space.

#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

uint64_t Count(int n, unordered_map<uint64_t, uint64_t>& memo, bool absense = false, int late_in_row = 0)
{
    if (n < 0)
    {
        return 0;
    }
    if (n == 0)
    {
        return 1;
    }

    uint64_t memo_key = (static_cast<uint64_t>(n) << 32) | (late_in_row << 1) | absense;
    auto it = memo.find(memo_key);
    if (it != memo.end())
    {
        return it->second;
    }

    uint64_t count = 0;
    if (!absense && late_in_row < 2)
    {
        count += Count(n - 1, memo, true, late_in_row + 1);
    }
    if (late_in_row < 2)
    {
        count += Count(n - 1, memo, absense, late_in_row + 1);
    }
    count += Count(n - 1, memo, absense, 0);

    memo[memo_key] = count;
    return count;
}


int main()
{
    unordered_map<uint64_t, uint64_t> memo;
    cout << Count(128, memo) << "\n";
    return 0;
}

public class AbsentReward {

	public static void main(String[] args) {
		String input = "OLLOAOLLO";
		
		System.out.println(reward(input));
	}
	
	public static boolean reward(String input){
		char[] inputCh = input.toCharArray();
		
		int lateCount= 0;
		int absentNum = 0;
		char previous='L';
		boolean check = true;
		for(char value : inputCh){
			if(value=='L' || value=='A'){
				if(previous!='O'){
					lateCount++;
				}
			}
			if(value=='A'){
				absentNum++;
			}
			
			if(lateCount>=3 || absentNum>=2){
				check = false;
			}
			previous = value;
		}
		return check;
	}
}