## Google Interview Question for Backend Developers

• 0
of 0 votes

Country: United States

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

This code will check if such a string can be formed, if no then it will return null, otherwise it will return a possible string.

``````private static String generateOne(String str) {
if (str == null || str.length() == 0) return null;
int length = str.length();
StringBuilder answer = new StringBuilder();
PriorityQueue<Pair> pq = new PriorityQueue<>();
char[] array = str.toCharArray();
Arrays.sort(array);
for (int i = 0; i < length; ) {
char ch = array[i];
int freq = 1;
i++;
while (i < length && (array[i] == ch)) {
freq++;
i++;
}
pq.add(new Pair(freq, ch));
}

char prevChar = ' ';
while (pq.isEmpty() == false) {
Pair p = pq.poll();
char ch = p.ch;
int freq = p.freq;
if (ch == prevChar) {
if (pq.size() == 0) {
return null;
} else {
Pair q = pq.poll();
char ch2 = q.ch;
int freq2 = q.freq;
answer.append(ch2);
freq2--;
if (freq2 != 0) {
pq.add(new Pair(freq2, ch2));
}
prevChar = ch2;
pq.add(p);
}
} else {
answer.append(ch);
freq--;
if (freq != 0) {
pq.add(new Pair(freq, ch));
}
prevChar = ch;
}
}
return answer.toString();
}

static class Pair implements Comparable<Pair>{
int freq;
char ch;
Pair (int f, char c) {
freq = f;
ch = c;
}
public int compareTo(Pair p) {
if (freq > p.freq) return -1;
if (freq < p.freq) return 1;
return 0;
}
}``````

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

This is a real Google question. I suggest people work on it.

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

@11.9.95.shubham

The question is about validation, not generation.

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

``````// Logic: if the highest frequency character count is lesser or equal
// to the sum of all other frequencies + 1, it is possible to find a
// permutation in which no two repeated characters exist
static String stringIntercalation(String str) {
if (str == null || str.length() <= 1) {
return str;
}

// Frequency count
HashMap<Character, Integer> freq = new HashMap<>();
int maxFreq = 0;
for (int i = 0; i < str.length(); i++) {
Character c = str.charAt(i);
if (!freq.containsKey(str.charAt(i))) {
freq.put(c, 1);
if (maxFreq == 0) {
maxFreq = 1;
}
} else {
freq.put(c, freq.get(c) + 1);
if (maxFreq < freq.get(c)) {
maxFreq = freq.get(c);
}
}
}

// Check if such an array exists
Integer total = 0;
Character maxFreqChar = '\0';
for (Character c : freq.keySet()) {
if (maxFreq == freq.get(c)) {
maxFreqChar = c;
}
total += freq.get(c);
}
total = total - maxFreq;
if (maxFreq > total + 1) {
return "";
}

// Get one possibility for this array
StringBuilder sb = new StringBuilder();
freq.remove(maxFreqChar);
while (!freq.isEmpty()) {
// Iterator required to modify Collection while iterating through it
Iterator<Character> iter = freq.keySet().iterator();
while (iter.hasNext()) {
Character c = iter.next();
sb.append(c);
if (maxFreq > 0) {
sb.append(maxFreqChar);
maxFreq--;
}
if (freq.get(c) > 1) {
freq.put(c, freq.get(c) - 1);
} else {
iter.remove();
}
}
}
if (maxFreq > 0) {
sb.insert(0, maxFreqChar);
}
return sb.toString();
}``````

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

dsdsadsada

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

``````// C++ program to rearrange characters in a string
// so that no two adjacent characters are same.
#include<bits/stdc++.h>
#include <iostream>
using namespace std;

const int MAX_CHAR = 26;

struct Key
{
int freq; // store frequency of character
char ch;

// function for priority_queue to store Key
// according to freq
bool operator<(const Key &k) const
{
return freq < k.freq;
}
public:
friend ostream &operator<<(ostream& out, Key n);
};
ostream &operator<<(ostream& out, Key n)
{
return out<<"("<<n.ch<<", "<<n.freq<<")";
}
void show( priority_queue<Key> pq)
{
cout<<"{ ";
while (!pq.empty())
{
cout << pq.top();
pq.pop();
}
cout<<"}"<<endl;
}
// Function to rearrange character of a string
// so that no char repeat twice
void rearrangeString(string str)
{
int n = str.length();

// Store frequencies of all characters in string
int count[MAX_CHAR] = {0};
for (int i = 0 ; i < n ; i++)
count[str[i]-'a']++;

// Insert all characters with their frequencies
// into a priority_queue
priority_queue< Key > pq;
for (char c = 'a' ; c <= 'z' ; c++)
if (count[c-'a'])
pq.push( Key { count[c-'a'], c} );

// 'str' that will store resultant value
str = "" ;

// work as the previous visited element
// initial previous element be. ( '#' and
// it's frequency '-1' )
Key prev {-1, '#'} ;

// traverse queue
while (!pq.empty())
{
// pop top element from queue and add it
// to string.
show(pq);
Key k = pq.top();
pq.pop();
str = str + k.ch;
cout<<str<<endl;
// IF frequency of previous character is less
// than zero that means it is useless, we
// need not to push it
if (prev.freq > 0)
pq.push(prev);

// make current character as the previous 'char'
// decrease frequency by 'one'
(k.freq)--;
prev = k;
}

// If length of the resultant string and original
// string is not same then string is not valid
if (n != str.length())
cout << " Not valid String " << endl;

else // valid string
cout << str << endl;
}

// Driver program to test above function
int main()
{
string str = "bbbaacc" ;
rearrangeString(str);

return 0;
}``````

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

I think just need to count the frequency of each char and find maximum one, say x, as long as x<=(n+1)/2, it can be formed.

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

My Algo is

boolean find(String s){
Map<String, Integer> map = new HashMap<String, Integer>();
int maxRepeat = 0, noofChar = 0;

for(char c: s.toCharArray()){
if(map.containsKey(c)){
int i = map.getVal(c);
map.put(c, ++i);
} else {
map.put(c, 1);
}
}

for(Map.EntrySet<String, Integer> entry: map.entrySet()){
if(maxRepeat < entry.getValue()) maxRepeat = entry.getValue();
noofChar++;
}

return ((noofChar / maxRepeat) > 1) ? true : false);
}

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

``````// Graph coloring problem variation so it's NP-Complete.
// There's no polynomial complexity algorithm for it.
static String possibleIntercalation(String str) {
if (str == null || str.length() <= 1) {
return str;
}

// Convert String to ArrayList of Chars
ArrayList<Character> charList = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
charList.add(str.charAt(i));
}

// Will hold all different results of the problem
HashSet<ArrayList<Character>> resultsList = new HashSet<>();

// Used as an auxiliary memory element between recursive calls
ArrayList<Character> memory = new ArrayList<>();

if (generateAllAnagrams(charList, memory, resultsList)) {
System.out.println(memory.toString());
}

return "";
}

private static boolean generateAllAnagrams(ArrayList<Character> charList,
ArrayList<Character> memory,
HashSet<ArrayList<Character>> resultsList) {
if (charList.size() == 0) {
resultsList.add(new ArrayList<Character>(memory));
return !hasSameConsecutiveCharacters(memory);
}

for (int i = 0; i < charList.size(); i++) {
Character c = charList.remove(i);
memory.add(c);
if (generateAllAnagrams(charList, memory, resultsList)) {
return true;
}
memory.remove(memory.size() - 1);
charList.add(i, c);
}
return false;
}

private static boolean hasSameConsecutiveCharacters(ArrayList<Character> list) {
if (list == null || list.size() == 1) {
return false;
}

boolean sameConsecutive = false;
Character prev = '\0';
for (Character c : list) {
if (c == prev) {
sameConsecutive = true;
break;
} else {
prev = c;
}
}
return sameConsecutive;
}``````

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

``````static boolean done = false;
private static void permute(String rest, String sofar) {
if (rest.length() == 0) {
done = true;
System.out.println(sofar);
return;
}
for (int i=0; i<rest.length(); ++i) {
if (!done) {
if (sofar.length() == 0 || sofar.charAt(sofar.length()-1) != rest.charAt(i)) {
permute(rest.substring(0,i)+rest.substring(i+1),sofar+rest.charAt(i));
}
}
}
}

public static void main(String args[]) {
permute("google", "");
done = false;
permute("aoooaa","");
done = false;
permute("aoooaaa","");
done = false;
permute("aoooa","");
}``````

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More