Yahoo Interview Question
Applications DevelopersCountry: United States
Interview Type: Written Test
private static String removeAdjacentDuplicates(String str){
if ( 0 == str.length() )return "-1";
char lastchar = str.charAt(0);
int position = 0;
int i =1;
for ( i = 1; i < str.length();i++){
if ( lastchar == str.charAt(i)){
position++;
continue;
}else{
lastchar = str.charAt(i);
}
if ( position > 0){
break;
}
}
if ( position == 0){
return str;
}else{
return removeAdjacentDuplicates(
str.substring(0,i-(position+1)) + str.substring(i,str.length()));
}
}
guys in order to solve this u just need to remove all i mean all the even length palindromes from the string.
for eg:- in above case ABCCBCBA remove BCCB as it is even length paliondrome.
for eg:-ABBBBADD need to remove ABBBA and then DD and return -1
may be your algorithm fails here..
Eg: ABBBBB
the even length palindrome here is BBBB, removing this gives you AB.
finding all palindromic substring is nonlinear order. We don't need that for solving this problem. Here I have an efficient recursive solution:
removeAdjacentDuplicate("ABCCBCBA", 0)
public static void removeAdjacentDuplicate(String in, int cur)
{
if(in.length() == 0 || cur<0 || cur>= in.length())
return;
int len = 1;
while(cur+len<in.length() && in.charAt(cur) == in.charAt(cur+len))
len++;
StringBuilder sb = new StringBuilder(in);
sb = sb.delete(cur, cur+len);
removeAdjacentDuplicate(sb.toString(), curr--);
}
recursive solution
public static void removeString_rec(char [] chs , int len ,int current, int next){
if (chs.length == next){
if (len == 0){
System.out.println(-1);
} else {
for (int i = 0 ; i < len ; ++i){
System.out.print(chs[i]);
}
}
} else {
if (chs [current] == chs [next]){
len -= 2;
if (current != 0){
current-- ;
}
} else{
current++ ;
chs[current] = chs [next] ;
}
removeString_rec(chs, len, current, next + 1);
}
}
The recursive solution can be written as follows:
The inputString is a StringBuilder representation of String to leverage its mutability. Initially start and end are set to 0 and 1 respectively.
private static void removeDuplicate(StringBuilder inputString, int start,
int end) {
// If input String of length 0
if (inputString.length() == 0) {
System.out.println(-1);
return;
}
// If the end has reached
if (end >= inputString.length()) {
System.out.println(inputString);
return;
}
// If start character equals the end character; remove the two
if (inputString.charAt(start) == inputString.charAt(end)) {
// removes the start character
inputString.deleteCharAt(start--);
// As a character is removed; decrement the end counter as well
end--;
// removes the end character
inputString.deleteCharAt(end--);
// decrements the start character; can be skipped as in the next
// step we are setting it to 0 to restart the whole process from
// first character so as to incorporate the scenarios where deletion
// of some characters have NOW made two consecutive characters to be
// same
start--;
start = 0;
end = 1;
// calls recursively
removeDuplicate(inputString, start, end);
} else {
// if no duplicate characters are found then increment the counters
removeDuplicate(inputString, start + 1, end + 1);
}
}
recursive solution using C++
#include<iostream>
#include<string>
using namespace std;
bool hasRemoved = false;
bool recursive_remove(string& str, int pos){
//pos cannot be greater than the length of str.
if(pos >= str.length()){
return hasRemoved;
}
//judge how many identical characters have appeared
int index = pos;
while(index < str.length() && str[index] == str[pos]){
++index;
}
//if duplication exists
if(index - pos > 1){
hasRemoved = true;
str.erase(pos, index - pos);
recursive_remove(str, max(pos - 1, 0));//max(pos-1, 0) means if it's like AAAB, after erasing AAA, we start from 0, if it is like ADBBC, we start from the first index of B - 1.
}else{
recursive_remove(str, pos + 1);
}
return hasRemoved;
}
int main(){
//string str = "ABCCBCBA";
string str = "AA";
if(recursive_remove(str, 0)){
if(str.length() > 0)
cout<<str<<endl;
else
cout<<"-1"<<endl;
}
return 0;
}
I'm assuming that char '$' will not be in the string
string str = "CBAABC";
RemoveChars(-1,0,'$',str);
void RemoveChars(int uniqueIndex, int currIndex, char lastChar, string& str){
if( currIndex == str.length()){
if( uniqueIndex == -1)
cout<<-1<<endl;
else{
for(int i = 0 ; i <= uniqueIndex ; i++)
cout<<str[i];
}
}
else{
if( lastChar == str[currIndex] ){
uniqueIndex--;
return RemoveChars(uniqueIndex, currIndex+1, (uniqueIndex == -1)?'$':str[uniqueIndex], str);
}
else{
uniqueIndex++;
str[uniqueIndex] = str[currIndex];
return RemoveChars(uniqueIndex, currIndex+1, str[uniqueIndex], str);
}
}
}
recursive C# solution using read/write index to rewrite char[]
protected static void FilterDuplicates3(ref char[] chars)
{
int writeIndex = 0;
for (int readIndex = 0; readIndex < chars.Length; readIndex++)
{
// Should write the character if neither preceding or succeeding char matches
if (!((readIndex > 0 && chars[readIndex] == chars[readIndex - 1]) ||
(readIndex < chars.Length - 1 && chars[readIndex] == chars[readIndex + 1])))
chars[writeIndex++] = chars[readIndex];
}
// Need to terminate the char array if we removed any duplicates
if (writeIndex < chars.Length - 1)
{
chars[writeIndex] = '\0';
Debug.Write(new String(chars));
Debug.Write("-->");
FilterDuplicates(ref chars);
}
}
Here is another recursive solution to this problem. I tested it using C++
#include<iostream>
#include<string>
using namespace std;
void remove_duplicate(string& input_str, int start_pos, int current_pos){
if(current_pos == input_str.length() || input_str.length() == 1){
if(current_pos - start_pos > 1){
input_str = input_str.substr(0, start_pos) + input_str.substr(current_pos);
}
return;
}
if(input_str[start_pos] == input_str[current_pos]){
remove_duplicate(input_str, start_pos, current_pos + 1);
}else{
//duplication exists
if(current_pos - start_pos > 1){
//remove duplicate
input_str = input_str.substr(0, start_pos) + input_str.substr(current_pos);
remove_duplicate(input_str, max(start_pos - 1, 0), start_pos);//max(start_pos - 1, 0) means the index cannot be less than 0
}else{
remove_duplicate(input_str, current_pos, current_pos + 1);
}
}
}
int main(){
string input_str = string("AAAAAB");
remove_duplicate(input_str, 0, 1);
if(input_str.length() > 0){
cout<<input_str<<endl;
}else{
cout<<"-1"<<endl;
}
return 0;
}
public class RemoveAdjacentDuplicates {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(removeDup("ABCCBCBBA"));
}
public static String removeDup(String s){
String finalRes = s;
//if(s.equals(f));
String f="";
for(int i=0; i<=s.length()-2;i++){
if(s.charAt(i) == s.charAt(i+1)){
String temp = s.substring(0, i);
f = temp+s.substring(i+2, s.length());
System.out.println("fin "+f);
}
/*else{
finalRes = finalRes+s.charAt(i);
}*/
}
while(!finalRes.equals(f))
{removeDup(f);
}
return finalRes;
}
}
public class RemoveAdjacentDuplicates {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(removeDup("ABCCBCBBA"));
}
public static String removeDup(String s){
String finalRes = s;
//if(s.equals(f));
String f="";
for(int i=0; i<=s.length()-2;i++){
if(s.charAt(i) == s.charAt(i+1)){
String temp = s.substring(0, i);
f = temp+s.substring(i+2, s.length());
System.out.println("fin "+f);
}
/*else{
finalRes = finalRes+s.charAt(i);
}*/
}
while(!finalRes.equals(f))
{removeDup(f);
}
return finalRes;
}
}
public class RemoveDups {
public static String removeDuplicate(String input, int startAt)
{
System.out.println("input:" + input + ", startAt:" + startAt);
if (input.length() == 0)
return "-1";
if (input.length() ==1)
return input;
int i, len = input.length(); // must have at least two
if (len == startAt)
return input.toString();
StringBuffer buildIt = new StringBuffer();
char c = input.charAt(startAt); // check for it
boolean revoked = false;
boolean haveDup = false;
for(i = startAt; i < len-1; i++)
{
if (input.charAt(i) == input.charAt(i+1))
{
c = input.charAt(i);
revoked = haveDup = true;
continue;
}
else if (revoked)
{
c = input.charAt(i+1);
revoked = false;
}
else
{
buildIt.append(input.charAt(i));
System.out.println("buildIt:" + buildIt);
if (haveDup)
{
i++;
break;
}
}
}
if (!revoked)
buildIt.append(input.substring(i, len)); // last char
input = buildIt.toString();
return haveDup ? removeDuplicate(input, 0) : input;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//StringBuffer buildIt = new StringBuffer();
String input = "DSTUUCCTSD"; // if ABCCBCBA, then ACBA
// if ABCC, then AB
// if CC, then -1
// if C, then C
// if CCDB, then DB
// if DSTUUCCTDB, then DSDB
// if DSTUUCCTSD, then -1
String result = removeDuplicate(input, 0);
System.out.println("Result from " + input + ", is " + result);
}
}
public class RemoveDups {
public static String removeDuplicate(String input, int startAt)
{
System.out.println("input:" + input + ", startAt:" + startAt);
if (input.length() == 0)
return "-1";
if (input.length() ==1)
return input;
int i, len = input.length(); // must have at least two
if (len == startAt)
return input.toString();
StringBuffer buildIt = new StringBuffer();
char c = input.charAt(startAt); // check for it
boolean revoked = false;
boolean haveDup = false;
for(i = startAt; i < len-1; i++)
{
if (input.charAt(i) == input.charAt(i+1))
{
c = input.charAt(i);
revoked = haveDup = true;
continue;
}
else if (revoked)
{
c = input.charAt(i+1);
revoked = false;
}
else
{
buildIt.append(input.charAt(i));
System.out.println("buildIt:" + buildIt);
if (haveDup)
{
i++;
break;
}
}
}
if (!revoked)
buildIt.append(input.substring(i, len)); // last char
input = buildIt.toString();
return haveDup ? removeDuplicate(input, 0) : input;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//StringBuffer buildIt = new StringBuffer();
String input = "DSTUUCCTSD"; // if ABCCBCBA, then ACBA
// if ABCC, then AB
// if CC, then -1
// if C, then C
// if CCDB, then DB
// if DSTUUCCTDB, then DSDB
// if DSTUUCCTSD, then -1
String result = removeDuplicate(input, 0);
System.out.println("Result from " + input + ", is " + result);
}
}
function removeDuplicates(string1) {
if(string1 empty)
return -1;
push all to a stack stack1
x = stack1.pop()
output ostring =""
while stack1 not empty
if x == stack1.top
stack1.pop()
x = stack.pop()
else
ostring = ostring + stack.pop
end while
if(string1 != ostring)
return removeDuplicates(ostring)
end function
How about start pushing characters into the stack from the right of the string. Whenever pushing a character, check if it's equal to the top of the stack. If it is, keep popping the top until the top is not equal to the character under consideration and then discard the given character. When the string is exhausted, just print the stack in popping order.
solution using recursive call..
{
import java.util.ArrayList;
public class SolutionDup
{
static String remDup(String str){
String inputString = str;
char[] charray=inputString.toCharArray();
ArrayList<Character> list = new ArrayList<Character>();
boolean isAdded = false;
for(char ch:charray){
if(list.size()> 0 && !isAdded && list.get(list.size()- 1).equals(ch)){
list.remove(list.size()- 1);
isAdded = true;
}
else{
list.add(ch);
}
}
if(list.size()==0){
return "-1";
}
if(!isAdded){
return inputString;
}
inputString = "";
for(char ch:list){
inputString = inputString +ch;
}
System.out.println("inputstring="+inputString);
return remDup(inputString);
}
public static void main(String[] args)
{
System.out.println("input=ABCCBCBA \n result ="+ remDup("ABCCBCBA"));
System.out.println("input=AA \n result ="+ remDup("AA"));
}
}
}
Main program
public class YahooInterview {
public String removeAdjacentDuplicates(char[] duplicates, List<Integer> dupRemoval, int index) {
if (index == duplicates.length - 1) {
return String.format("%c", duplicates[index]);
}
if (duplicates[index] == duplicates[index + 1]) {
dupRemoval.set(0, dupRemoval.get(0) + 1);
return removeAdjacentDuplicates(duplicates, dupRemoval, index + 2);
} else {
return String.format("%c%s", duplicates[index], removeAdjacentDuplicates(duplicates, dupRemoval, index + 1));
}
}
}
Driver Method
public void testRemoveAdjacentDuplicates() throws Exception {
YahooInterview yahooInterview = new YahooInterview();
String test = "ABCCBCBA";
List<Integer> intlist = new ArrayList<Integer>(1);
intlist.add(0, 0);
String output = yahooInterview.removeAdjacentDuplicates(test.toCharArray(), intlist, 0);
while (intlist.get(0) != 0) {
intlist.set(0, 0);
output = yahooInterview.removeAdjacentDuplicates(output.toCharArray(), intlist, 0);
}
}
The approach:
Find duplicates and remove them in the remove_duplicate method
Keep a track of duplicates removed if > 0 then call the method again till duplicates removed!=0
if duplicates removed = 0 that means we have cleared all the duplicates in the string.
public static boolean changed = true;
public static void main(String[] args) {
//System.out.println(remove("ABCCBCBA"));
String str = "AA";
//String str = "ABCCBCBA";
while(changed) {
changed = false;
str = remove(str);
if(str.length() < 1) {
str= "-1";
break;
}
}
System.out.println(str);
}
public static String remove(String s) {
StringBuilder str = new StringBuilder();
for(int i =0 ; i < s.length(); i++) {
if(i+1 < s.length() && s.charAt(i) == s.charAt(i+1)) {
changed = true;
while(i+1 < s.length() && s.charAt(i) == s.charAt(i+1))
i++;
}
else
str.append(s.charAt(i));
}
return str.toString();
}
/*
Given a string, complete the given function to recursively remove the adjacent duplicate characters and return the resultant string. If there are no characters left in the resultant string, return "-1" (without quotes).
Sample Test Cases
Sample Input: ABCCBCBA
Output: ACBA
*/
#include <iostream>
#include <string>
using namespace std;
void remove_duplicate(string &in){
bool is_duplicate=false;
for(int i=0;i<in.length()-1;i++)
{
if(in[i]==in[i+1]){
is_duplicate=true;
//cout << in << " is Duplicate" <<endl;
}
}
if(!is_duplicate)
return;
for(int curr=0;curr<in.length();)
{
int len=1;
while(curr+len<in.length() && in[curr]==in[curr+len])
{
len++;
//cout <<"Found repeated char " <<endl;
}
if(len>1)
in.erase(curr, len);
curr += 1;
}
remove_duplicate(in);
}
int main()
{
cout<<"Enter input string " <<endl;
string in;
cin>>in;
remove_duplicate(in);
cout <<"out put is "<<in <<endl;
return 0;
}
public static String removeAdjacentDuplicate(String in) {
if (in == null || in.trim().length() < 2) {
return in;
}
Stack<String> stack = new Stack<String>();
boolean shouldPop = false;
for (int i = 0; i < in.length(); i++) {
String nextChar = String.valueOf(in.charAt(i));
if (!stack.isEmpty()) {
if (stack.peek().equals(nextChar)) {
shouldPop = true;
} else {
if (shouldPop) {
stack.pop();
shouldPop = false;
i--;
} else {
stack.push(nextChar);
}
}
} else {
stack.push(nextChar);
}
}
if (shouldPop) {
stack.pop();
}
StringBuilder output = new StringBuilder();
while (!stack.isEmpty()) {
output = output.append(stack.pop());
}
String reverse = output.reverse().toString();
return reverse.equals("") ? "-1" : reverse;
}
Here is my solution. Feel free to comment.
public static String removeAdjacentPairs(String str, StringBuilder sb, int index){
if(index > str.length()-1){
if(sb.length() < 1){
return "-1";
}else{
return sb.toString();
}
}else{
char c = str.charAt(index);
if(sb.length() == 0 || c != sb.charAt(sb.length()-1)){
sb.append(c);
} else {
sb.deleteCharAt(sb.length()-1);
}
return removeAdjacentPairs(str, sb, ++index);
}
}
Solution w/o recursion
int remove_adjacent_duplicate(string &str) {
if(str.size() == 0)
return -1;
int cur = 0;
bool adj = false;
do {
adj = false;
cur = 0;
while(cur < str.size() - 1) {
int len = 1;
while((cur+len < str.size()) && (str[cur] == str[cur+len])) {
len++;
}
if(len != 1) {
adj = true;
str.erase(cur, len);
}
cur = cur + len;
}
}while(adj);
return 1;
}
int main() {
for(int i = 0; i < 26; ++i) {
code[i] = nth_prime(i+1);
}
string str = "abccbcba";
if(remove_adjacent_duplicate(str)) {
cout<<str;
}
}
Output:
acba
#include <iostream>
using namespace std;
void recFunc( char src[] ){
char * read = src;
char * write = src;
int cnt_res = 0;
while( *read!='\0' ){
int cnt = 0;
while( *(read) == *(read+1) && *(read+1)!='\0'){
cnt++;
read++;
cnt_res++;
}
if(cnt!=0)
read++;
if( cnt == 0 ){
*write = *read;
read++;
write++;
}
}
*write = '\0';
if( cnt_res != 0 )
recFunc( src );
}
int main() {
char src[] = "abccbcba";
recFunc( src );
return 0;
}
public class RemoveAdjacentDuplicates {
public static void main(String[] args) {
String str = "AAA";
System.out.println("String before: " + str);
System.out.println("String after: " + removeDuplStr(str));
}
public static String removeDuplStr(String s)
{
int i=0;
if(s.length() == 0)
return "-1";
while(i < s.length()-1)
{
int m = i;
int count=0;
while( m < s.length()-1)
{
if(s.charAt(m) == s.charAt(m+1))
{
count++;
m++;
}
}
i++;
if(count>0) {
s = s.substring(0, i-1) + s.substring(m+1, s.length());
i=0;
}
}
return s.equals("") ? "-1" : s;
}
}
#include <iostream>
#include <string>
#include<algorithm>
#include<typeinfo>
#include<cstring>
using namespace std;
char* removeAdjacent(char *str){
string s(str);
for(auto i=s.begin();i!=s.end();i++){
if(*i==*(i+1)){
rotate(i,i+2,s.end());
s.resize(s.size()-2);
strcpy(str,s.c_str());
removeAdjacent(str);
return str;
}
}
strcpy(str,s.c_str());
return str;
}
int main()
{
char str[]="abccbcba";
cout<<removeAdjacent(str);
}
#include <iostream>
#include <string>
#include<algorithm>
#include<typeinfo>
#include<cstring>
using namespace std;
char* removeAdjacent(char *str){
string s(str);
for(auto i=s.begin();i!=s.end();i++){
if(*i==*(i+1)){
rotate(i,i+2,s.end());
s.resize(s.size()-2);
strcpy(str,s.c_str());
removeAdjacent(str);
return str;
}
}
strcpy(str,s.c_str());
return str;
}
int main()
{
char str[]="abccbcba";
cout<<removeAdjacent(str);
}
Hey guys, this works. But it gives only the first solution --> turns ABCCBCBA to ABBCBA. How to run it till we get ACBA?
#include <stdio.h>
#include <string.h>
int main(void) {
char str[100];
int len,i,j=0;
scanf("%s",str);
len=strlen(str);
for(i=1;i<=len;i++)
{
if(str[i]==str[j] && j>=0)
{
i++;
j--;
}
str[++j]=str[i];
}
printf("%s",str);
return 0;
}
class Main {
public static void main(String[] args) {
System.out.println();
System.out.println(removeAdjacentDuplicate("AAAABBBB"));
}
private static String removeAdjacentDuplicate(String str){
char prev = str.charAt(0);
StringBuilder sb = new StringBuilder();
sb.append(str.charAt(0));
for(int i=1; i<str.length();i++){
System.out.println(sb.toString());
if(prev != str.charAt(i)){
sb.append(str.charAt(i));
prev = str.charAt(i);
}else{
if(sb.length() >= 1)
sb.deleteCharAt(sb.length()-1);
if(sb.length() >= 1)
prev = sb.charAt(sb.length()-1);
else
prev = ' ';
}
}
return sb.length() == 0 ? "-1" : sb.toString();
}
}
class Main {
public static void main(String[] args) {
System.out.println();
System.out.println(removeAdjacentDuplicate("AAAABBBB"));
}
private static String removeAdjacentDuplicate(String str){
char prev = str.charAt(0);
StringBuilder sb = new StringBuilder();
sb.append(str.charAt(0));
for(int i=1; i<str.length();i++){
System.out.println(sb.toString());
if(prev != str.charAt(i)){
sb.append(str.charAt(i));
prev = str.charAt(i);
}else{
if(sb.length() >= 1)
sb.deleteCharAt(sb.length()-1);
if(sb.length() >= 1)
prev = sb.charAt(sb.length()-1);
else
prev = ' ';
}
}
return sb.length() == 0 ? "-1" : sb.toString();
}
}
class Main {
public static void main(String[] args) {
System.out.println();
System.out.println(removeAdjacentDuplicate("AAAABBBB"));
}
private static String removeAdjacentDuplicate(String str){
char prev = str.charAt(0);
StringBuilder sb = new StringBuilder();
sb.append(str.charAt(0));
for(int i=1; i<str.length();i++){
System.out.println(sb.toString());
if(prev != str.charAt(i)){
sb.append(str.charAt(i));
prev = str.charAt(i);
}else{
if(sb.length() >= 1)
sb.deleteCharAt(sb.length()-1);
if(sb.length() >= 1)
prev = sb.charAt(sb.length()-1);
else
prev = ' ';
}
}
return sb.length() == 0 ? "-1" : sb.toString();
}
}
recursive solution
public static void removeString_rec(char [] chs , int len ,int current, int next){
if (chs.length == next){
if (len == 0){
System.out.println(-1);
} else {
for (int i = 0 ; i < len ; ++i){
System.out.print(chs[i]);
}
}
} else {
if (chs [current] == chs [next]){
len -= 2;
if (current != 0){
current-- ;
}
} else{
current++ ;
chs[current] = chs [next] ;
}
removeString_rec(chs, len, current, next + 1);
}
}
This is backtracking problem.
Start from the second from last character and compare it with the last character.
If they are the same remove both characters. And recursively repeat the process every time comparing chars[i] with chars[i+1].
Code:
public static String removeDups(String s) {
return removeDups(new StringBuilder(s), 0).toString();
}
public static StringBuilder removeDups(StringBuilder sb, int pos) {
if(pos == sb.length()-1) {
return sb;
}
sb = removeDups(sb, pos+1);
if(sb.charAt(pos) == sb.charAt(pos+1)) {
sb.deleteCharAt(pos+1);
sb.deleteCharAt(pos);
}
return sb.length() == 0 ? new StringBuilder("-1") : sb;
}
I've just realized that @Nasser Ghazali was right and the current implementation is not working correctly although he removed his comment. The general idea didn't changed though. This is still backtracking problem.
1) Start iterating from the end of the string.
2) Count duplicated characters.
3) Once you find a point at which characters are not the same remove the following duplicated characters.
4) Recursively repeat the process
Fixed implementation:
public static String removeDups(String s) {
StringBuilder sb = new StringBuilder(s);
int numOfSameChars = removeDups(sb, 0);
if (numOfSameChars != 0) {
sb.delete(0, numOfSameChars);
}
return sb.length() == 0 ? "-1" : sb.toString();
}
public static int removeDups(StringBuilder sb, int pos) {
if (pos == sb.length() - 1) {
return 0;
}
int numOfSameChars = removeDups(sb, pos + 1);
if (sb.charAt(pos) == sb.charAt(pos + 1)) {
return numOfSameChars != 0 ? numOfSameChars + 1 : 2;
} else if (numOfSameChars > 0) {
sb.delete(pos + 1, pos + 1 + numOfSameChars);
if (pos != sb.length() - 1 && sb.charAt(pos) == sb.charAt(pos + 1)) {
return 2;
}
}
return 0;
}
@Nasser Ghazali thanks for pointing it out.
finding all palindromic substring is nonlinear order. We don't need that for solving this problem. Here I have an efficient recursive solution:
- zahidbuet106 May 04, 2014