## Interview Question for Backend Developers

Team: 3
Country: India

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

Type: Recursion + Loop Problem

Loop on String Length. That is, 1 to MAX(CEILING(N/K), (N-K)) (inclusive)
- Minimum String Length is 1 because non-empty string
- Maximum String Length is a bit tricky
-- K cuts would result in K+1 Strings
-- Case-A: Cuts are equal in size, so max str len is (N/K) (ceiled)
-- Case-B: Cuts are not equal. Max length of (K+1)th string is (N-K) where other K strings are of min len 1

Recursion on String

Psuedo-Code:

``````class StringCutter {
private String str;
private Stack<Pair<int, int>> substrings;
private int numCuts;
private int maxStringSize;
private int maxCutSize;
private int numPalindromes;

public StringCutter(String input) {
this.str = input;
this.maxStringSize = input.Size();
this.substring = new Stack<Pair<int, int>>();
}

public void cut(int cutCount) {
this.substring.clear();
this.numCuts = cutCount;
this.maxCutSize = MAX(CEILING(maxStringSize/numCuts), (maxStringSize-numCuts));
this.numPalindromes = 0;
cutInternal(0);
System.output.printf("Palindrome Count = %d", this.numPalindromes);
}

private void cutInternal(int usedOffset) {
// Did we make enough cuts?
if (substring.size() == this.numCuts) {

// Do cut strings complete the string? if not discard
if (usedOffset < maxStringSize) return;

StringBuilder sb = new StringBuilder();

for (Pair<int, int> p : substrings) {
cutString = str.substring(p.key, p.value);
if (isPalindrome(cutString)) this.numPalindromes++;
sb.append(cutString + "|"));
}

System.output.println(sb.toString());
}

for (int len = 1; len <= maxCutSize; len++) {
substring.push(new Pair<int,int>(usedOffset, len));
cutInternal(usedOffset + len);
substring.pop();
}
}

private boolean isPalindrome(String s) {
// Trivial code to check if 's' is a palindrome
}
}``````

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

This is how I'd go about it,
K will denote the level of the string in the reverse order 0 will be the last
based on the level iterate from end of the previous level to N-level
the rest of the string from current end to the last will be recursively solved
if the current substring is palindrome send 1 (c+1) to the next level
the c will be added to count at the end will have the no of palindromes for the current split

``````static Scanner sc = new Scanner(System.in);
static String input;
static int count = 0;
static int n;

public static void main(String[] args) {
System.out.print("Enter N and K : ");
n = sc.nextInt();
var k = sc.nextInt();
input = sc.nextLine();
System.out.print("Enter the String : ");
input = sc.nextLine();
checkPalin(0, 0, k);
System.out.println("The count of Palindrome in " + input + " = " + count);
}

private static void checkPalin(int c, int start, int lvl) {
if (lvl > 0)
for (int end = start + 1; end <= n - lvl; end++) {
int tmp = 0;
if (isPalin(start, end)) tmp = 1;
checkPalin(c + tmp, end, lvl - 1);
}
if (lvl == 0) {
if (isPalin(start, n)) c += 1;
count += c;
}
}

private static boolean isPalin(int start, int end) {
for (int i = 0; i < (end - start) / 2; i++)
if (input.charAt(start + i) != input.charAt(end - i - 1))
return false;
return true;
}``````

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

We could use dynamic programming. Something like this:

``````def count(s,k):
dp1 = [[0]*(len(s)+1)
for _ in range(k+1)]
dp2 = [[0]*(len(s)+1)
for _ in range(k+1)]
for i in range(len(s)):
for j in range(i+1):
z = s[j:i+1]
p = [0,1][z == z[::-1]]
if j == 0:
dp1[0][i+1] = p
dp2[0][i+1] = 1
for c in range(1, min(k,j)+1):
w = dp1[c-1][j]
y = dp2[c-1][j]
dp1[c][i+1] += w + p*y
dp2[c][i+1] += y
return dp1[k][len(s)]
print count ('aabbc', 2)``````

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

public static void main(String[] args)
{
int cuts = 2;
String str = "aabbc";
String[] cutted = new String[cuts+1];
for(int i=0;i<=cuts;i++)
{
if(i==cuts)
cutted[i] = str.substring(i);
else
cutted[i] = str.substring(i,i+1);
}
cutString(cutted, cuts, cuts, 0);
}

static void cutString(String[] cutted, int cuts, int cp, int palinCount)
{
System.out.println(Arrays.deepToString(cutted) + " : " + (palinCount+=palinCount(cutted)));
if(cutted[cp].length()>1)
{
cutted[cp-1] = cutted[cp-1]+cutted[cp].charAt(0);
cutted[cp] = cutted[cp].substring(1);
cutString(cutted, cuts, cp, palinCount);
}
else
{
cp--;
if(cp>0)
cutString(cutted, cuts, cp, palinCount);
}
}

static int palinCount(String[] strArr)
{
int count=0;
for(String str:strArr)
{
if(checkPali(str)) count++;
}
return count;
}

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

Please Send Me Expected Coding Assesment Questions List With Solutions In Java By Today As I Need An Urgent Help From You. Please Reply My Comment By Today On My Whats App Contact 9557041140 And Email ID jatinbhardwaaj18@gmail.com. Please Reply My Query By Today As I Need An Urgent Help From You For Placement And Internships So Do Me A Favour.

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.