## Linkedin Interview Question for Site Reliability Engineers

Country: India

Comment hidden because of low score. Click to expand.
4
of 4 vote

Need More Base Conditions

d1[1][0][0][0]=1;
d2[0][1][0][0]=1;
d3[0][0][1][0]=1;
d4[0][0][0][1]=1;

d1[1][0][0][1]=1;
d4[1][0][0][1]=1;

d1[1][1][0][0]=1;
d2[1][1][0][0]=1;

d1[1][0][1][0]=1;
d3[1][0][1][0]=1;

d2[0][1][0][1]=1;
d4[0][1][0][1]=1;

d2[0][1][1][1]=1;
d3[0][1][1][1]=1;

d3[0][0][1][1]=1;
d4[0][0][1][1]=1;

d2[0][1][1][1]=2;
d3[0][1][1][1]=2;
d4[0][1][1][1]=2;

d1[1][0][1][1]=2;
d3[1][0][1][1]=2;
d4[1][0][1][1]=2;

d2[1][1][0][1]=2;
d1[1][1][0][1]=2;
d4[1][1][0][1]=2;

d2[1][1][1][0]=2;
d3[1][1][1][0]=2;
d1[1][1][1][0]=2;

d1[1][1][1][1]=6;
d2[1][1][1][1]=6;
d3[1][1][1][1]=6;
d4[1][1][1][1]=6;

Comment hidden because of low score. Click to expand.
1
of 1 vote

DP approach with O(n1.n2.n3.n4) time and space complexities:

``````C[d][n1][n2][n3][n4] = 	number of sequences that contain n1 1s, n2 2s, n3 3s, n4 4s,
AND have the last digit is d.``````

Recursive formula: (example for d = 2)

``````C[2][n1][n2][n3][n4] = C1(number of sequences that end with '1') + C3(number of sequences that end with '3') + C4(number of sequences that end with '4'); // ignore sequences that end with d = '2', since two adjacent digits must be different.

Where : C4 	= 	number of sequences that end with '4' and have length less by 1 digit;
=	C[4][n1-1][n2][n3][n4] + C[4][n1][n2-1][n3][n4] + C[4][n1][n2][n3-1][n4] + C[4][n1][n2][n3][n4-1]; // with length - 1;``````

Thus the recursive formula will be:

``````C[2][n1][n2][n3][n4] = 		C[1][n1-1][n2][n3][n4] + C[1][n1][n2-1][n3][n4] + C[1][n1][n2][n3-1][n4] + C[1][n1][n2][n3][n4-1]
+	C[3][n1-1][n2][n3][n4] + C[3][n1][n2-1][n3][n4] + C[3][n1][n2][n3-1][n4] + C[3][n1][n2][n3][n4-1]
+	C[4][n1-1][n2][n3][n4] + C[4][n1][n2-1][n3][n4] + C[4][n1][n2][n3-1][n4] + C[4][n1][n2][n3][n4-1]``````

Initial values: DIY! Example:

``````C[2][x][0][y][z] = 0;
C[2][0][1][0][0] = 1;``````

ANS = C1 + C2 + C3 + C4;

(Note: Use module of (10^9+7) in all computational steps)

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````package string;

import java.math.BigInteger;

public static void main(String[] args) {
int[] n = {5, 1, 1, 1};
System.out.println(generate("", n[0] + n[1] + n[2] + n[3], n));
}

public static int generate(String num, int maxLength, int[] n) {
if (num.length() == maxLength) {
return Integer.parseInt(new BigInteger(num).mod(new BigInteger("1000000007")).toString());
}

for (int i = 1; i<=  4; i++) {
if (n[i - 1] > 0 && (num.isEmpty() || num.charAt(num.length() - 1) - '0' != i)) {
n[i - 1]--;
int res = generate(num + i, maxLength, n);
if (res != -1) return res;
n[i - 1]++;
}
}
return -1;
}

}``````

Comment hidden because of low score. Click to expand.
0

This seems to print the first case out that works, or prints out -1 if nothing works, but it doesn't count the number of working cases, it stops when it gets a res that is not -1 Now 5,1,1,1, has only 0 solutions so it returns -1, but 4,1,1,1 has 6 solutions, but this only finds the very first one. 1212134

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string [] arr = new string [] {"1s", "2s", "3s","4s"};
List<int> FinalList = new List<int>();
arr.All(str =>
{
var f = (str.ToArray()[0] - '0');
return true;
});``````

Comment hidden because of low score. Click to expand.
0

please explain the code...im a beginner

Comment hidden because of low score. Click to expand.
0

Hi there !!

Can you explain your code to beginners like me ?

Comment hidden because of low score. Click to expand.
0

This is C#, but the code does not work. In fact, I'm not even sure what the code is trying to do.

Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS definitely works.But is there a explicit formula as solution?

Comment hidden because of low score. Click to expand.
0

How will you apply DFS in this case ? Can you please elaborate ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

use DFS, every node have four int, that is the number of the numbers(s1,s2,s3,s4 )have been used.
class Node{
String name='';
int N1,N2,N3,N4;
}

stack m_stack = new stack();

Comment hidden because of low score. Click to expand.
0

use DFS, every node have four int, that is the number of the numbers(s1,s2,s3,s4 )have been used and a name , traverse all of the possibility
class Node{
String name='';
int N1,N2,N3,N4;
}

stack m_stack = new stack()
if((mstack.pop) only one int is not zero){
return;
}
if((mstack.pop) all int is zero){
print (mstack.peek.name)
return;
}

if(stack.peek.name !='s1'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s1';
mNode.N1++;
}
if(stack.peek.name !='s2'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s2';
mNode.N2++;
}

if(stack.peek.name !='s3'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s3';
mNode.N3++;
}
if(stack.peek.name !='s4'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s4';
mNode.N4++;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

use DFS, every node have four int, that is the number of the numbers(s1,s2,s3,s4 )have been used and a name , traverse all of the possibility
class Node{
String name='';
int N1,N2,N3,N4;
}

stack m_stack = new stack()
if((mstack.pop) only one int is not zero){
return;
}
if((mstack.pop) all int is zero){
print (mstack.peek.name)
return;
}

if(stack.peek.name !='s1'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s1';
mNode.N1++;
}
if(stack.peek.name !='s2'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s2';
mNode.N2++;
}

if(stack.peek.name !='s3'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s3';
mNode.N3++;
}
if(stack.peek.name !='s4'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s4';
mNode.N4++;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe this works. Please look over this and tell me if it seems correct:

``````public int numSeq(int ones, int twos, int threes, int fours){
return numSeqHelper(ones, twos, threes, fours, 0) ;
}

public int numSeqHelper(int ones, int twos, int threes, int fours, int lastDigit){
if(ones ==0 && twos ==0 && threes ==0 && fours ==0)
return 1;

int onesSeq = 0;
int twosSeq = 0;
int threesSeq = 0;

if(last!= 1 && ones != 0)
onesSeq = numSeqHelper(ones-1, twos, threes, fours, 1);
if(last!= 2 && twos != 0)
onesSeq = numSeqHelper(ones, twos-1, threes, fours, 2);
if(last!= 3 && threes != 0)
onesSeq = numSeqHelper(ones, twos, threes-1, fours, 3);
if(last!= 4 && fours != 0)
onesSeq = numSeqHelper(ones, twos, threes, fours-1, 4);

return onesSeq +twosSeq+ threesSeq + foursSeq;
}``````

Comment hidden because of low score. Click to expand.
0

I feel that in the case of:
1 -> 4 times
2 -> 1 time
3 -> 2 times
4 -> 5 times
Your code will generate the sequence: 1 2 1 3 1 3 1 4__ now it stops and am not sure exactly what will happen, i suppose it will return the sum and this is not a valid output.
A possible valid sequence could be:
1 2 3 4 1 4 3 4 1 4 1 4

Please let me know what do you think.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am completely lost when I read this line
"Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will output the number of such sequences using all these numbers. "
Can someone care to explain the question. or give me a hint.

Thanks

Comment hidden because of low score. Click to expand.
0

This might be a version of DFL's code that runs and does what he wants with simple recursion.

``````package simple;

public class DFLSeq {
public int numSeq(int ones, int twos, int threes, int fours){
System.out.println("numSeq " + ones + " " + twos + " " + threes + " " +fours);

return numSeqHelper(ones, twos, threes, fours, 0) ;
}
public static void main(String[] args) {
int[] n = {4, 1, 1, 1};
DFLSeq  d = new DFLSeq();
System.out.println( d.numSeq(n[0],n[1],n[2],n[3]));
}
public int numSeqHelper(int ones, int twos, int threes, int fours, int last){
if(ones ==0 && twos ==0 && threes ==0 && fours ==0)
return 1;
System.out.println("" + ones + " " + twos + " " + threes + " " +fours + " last=" +last);
int onesSeq = 0;
int twosSeq = 0;
int threesSeq = 0;

if(last!= 1 && ones != 0)
onesSeq = numSeqHelper(ones-1, twos, threes, fours, 1);
if(last!= 2 && twos != 0)
twosSeq = numSeqHelper(ones, twos-1, threes, fours, 2);
if(last!= 3 && threes != 0)
threesSeq = numSeqHelper(ones, twos, threes-1, fours, 3);
if(last!= 4 && fours != 0)
foursSeq = numSeqHelper(ones, twos, threes, fours-1, 4);

int res= onesSeq +twosSeq+ threesSeq + foursSeq;
System.out.println("res="+res);
return res;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This seems to be what you are trying to do, which does recursion to try out the cases and counts them.

``````package simple;

public class DFLSeq {
public int numSeq(int ones, int twos, int threes, int fours){
System.out.println("numSeq " + ones + " " + twos + " " + threes + " " +fours);

return numSeqHelper(ones, twos, threes, fours, 0) ;
}
public static void main(String[] args) {
int[] n = {4, 1, 1, 1};
DFLSeq  d = new DFLSeq();
System.out.println( d.numSeq(n[0],n[1],n[2],n[3]));
}
public int numSeqHelper(int ones, int twos, int threes, int fours, int last){
if(ones ==0 && twos ==0 && threes ==0 && fours ==0)
return 1;
System.out.println("" + ones + " " + twos + " " + threes + " " +fours + " last=" +last);
int onesSeq = 0;
int twosSeq = 0;
int threesSeq = 0;

if(last!= 1 && ones != 0)
onesSeq = numSeqHelper(ones-1, twos, threes, fours, 1);
if(last!= 2 && twos != 0)
twosSeq = numSeqHelper(ones, twos-1, threes, fours, 2);
if(last!= 3 && threes != 0)
threesSeq = numSeqHelper(ones, twos, threes-1, fours, 3);
if(last!= 4 && fours != 0)
foursSeq = numSeqHelper(ones, twos, threes, fours-1, 4);

int res= onesSeq +twosSeq+ threesSeq + foursSeq;
System.out.println("res="+res);
return res;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe one of the possible solutions is to find all possible permutations for all given numbers and making sure that while constructing the permutation, we ignore those where same numbers occur consecutively.

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findSequences(ArrayList<Integer> ar,HashSet<Integer> hs, HashMap<Integer,Integer> hm,int prev,int cnt)
{
if(ar.size()==cnt)
{
for(int i: ar)
{
System.out.print(i+" ");
}
System.out.println();
return;
}

for(Integer i : hs)
{
if(i.intValue()==prev)
continue;

if(hm.get(i)==0)
continue;
int val=hm.get(i);
--val;
hm.put(i, val);
findSequences(ar,hs,hm,i.intValue(),cnt);
val=hm.get(i);
++val;
hm.put(i, val);
ar.remove(ar.size()-1);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findSequences(ArrayList<Integer> ar,HashSet<Integer> hs, HashMap<Integer,Integer> hm,int prev,int cnt)
{
if(ar.size()==cnt)
{
for(int i: ar)
{
System.out.print(i+" ");
}
System.out.println();
return;
}

for(Integer i : hs)
{
if(i.intValue()==prev)
continue;

if(hm.get(i)==0)
continue;
int val=hm.get(i);
--val;
hm.put(i, val);
findSequences(ar,hs,hm,i.intValue(),cnt);
val=hm.get(i);
++val;
hm.put(i, val);
ar.remove(ar.size()-1);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class PermutationWays {
public  static int count = 0;

public static void countSequences(int[] values, StringBuilder sb, int totalCount) {
if(sb.length() == totalCount) {
count++;
return;
}
if(values[0] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '1') {
sb.append('1');
values[0]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
values[0]++;
}
}

if(values[1] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '2') {
sb.append('2');
values[1]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
values[1]++;
}
}

if(values[2] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '3') {
sb.append('3');
values[2]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
values[2]++;
}
}

if(values[3] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '4') {
sb.append('4');
values[3]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
}
values[3]++;
}
}

public static void main(String args[]) {
int[] count = {2,2,2,2};
PermutationWays.countSequences(count, new StringBuilder(), 8);
System.out.println(PermutationWays.count);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static long getNumberOfNumbers(int n1, int n2, int n3, int n4, int firstDigit) {

if(n1+n2+n3+n4==1) {
if(n1==1 && firstDigit!=1) {
return 1;
}
else if(n1==1) {
return 0;
}
if(n2==1 && firstDigit!=2) {
return 1;
}
else if(n2==1) {
return 0;
}
if(n3==1 && firstDigit!=3) {
return 1;
}
else if(n3==1) {
return 0;
}
if(n4==1 && firstDigit!=4) {
return 1;
}
else if(n4==1) {
return 0;
}
}

if(cache.containsKey(firstDigit+","+n1+","+n2+","+n3+","+n4))
return cache.get(firstDigit+","+n1+","+n2+","+n3+","+n4);

long retVal = 0;
if(firstDigit!=1 && n1>0)
retVal += getNumberOfNumbers(n1-1, n2, n3, n4, 1);
if(firstDigit!=2 && n2>0)
retVal += getNumberOfNumbers(n1, n2-1, n3, n4, 2);
if(firstDigit!=3 && n3>0)
retVal += getNumberOfNumbers(n1, n2, n3-1, n4, 3);
if(firstDigit!=4 && n4>0)
retVal += getNumberOfNumbers(n1, n2, n3, n4-1, 4);

cache.put(firstDigit+","+n1+","+n2+","+n3+","+n4, retVal);

return retVal;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.