Linkedin Interview Question Site Reliability Engineers
Country: India
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;
Final answer:
ANS = C1 + C2 + C3 + C4;
(Note: Use module of (10^9+7) in all computational steps)
package string;
import java.math.BigInteger;
public class NonAdjacentBigInteger {
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;
}
}
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
string [] arr = new string [] {"1s", "2s", "3s","4s"};
List<int> FinalList = new List<int>();
arr.All(str =>
{
var f = (str.ToArray()[0] - '0');
FinalList.AddRange(Enumerable.Repeat(f, f).ToArray());
return true;
});
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();
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()
public void add(stack mstack){
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++;
add(stack);
}
if(stack.peek.name !='s2'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s2';
mNode.N2++;
add(stack);
}
if(stack.peek.name !='s3'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s3';
mNode.N3++;
add(stack);
}
if(stack.peek.name !='s4'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s4';
mNode.N4++;
add(stack);
}
}
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()
public void add(stack mstack){
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++;
stack.add(mNode);
add(stack);
}
if(stack.peek.name !='s2'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s2';
mNode.N2++;
stack.add(mNode);
add(stack);
}
if(stack.peek.name !='s3'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s3';
mNode.N3++;
stack.add(mNode);
add(stack);
}
if(stack.peek.name !='s4'){
Node mNode = new Node();
mNode.name =stack.peek.name +'s4';
mNode.N4++;
stack.add(mNode);
add(stack);
}
}
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;
int foursSeq = 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;
}
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.
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
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;
int foursSeq = 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;
}
}
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;
int foursSeq = 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;
}
}
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;
ar.add(i);
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);
}
}
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;
ar.add(i);
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);
}
}
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);
}
}
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;
}
Need More Base Conditions
- TheCodester October 19, 2014d1[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;