## Google Interview Question for Backend Developers

• 0

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();
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++;
}
}

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;
freq2--;
if (freq2 != 0) {
}
prevChar = ch2;
}
} else {
freq--;
if (freq != 0) {
}
prevChar = ch;
}
}
}

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

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++) {
}

// 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) {
return !hasSameConsecutiveCharacters(memory);
}

for (int i = 0; i < charList.size(); i++) {
Character c = charList.remove(i);
if (generateAllAnagrams(charList, memory, resultsList)) {
return true;
}
memory.remove(memory.size() - 1);
}
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[]) {
done = false;
permute("aoooaa","");
done = false;
permute("aoooaaa","");
done = false;
permute("aoooa","");
}``````

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.