Google Interview Question for Backend Developers


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;
        }
    }

- 11.9.95.shubham January 12, 2018 | Flag Reply
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.

- Johnb January 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@11.9.95.shubham

The question is about validation, not generation.

- Johnb January 12, 2018 | Flag Reply
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();
  }

- amid.salaad January 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dsdsadsada

- Anonymous January 15, 2018 | Flag Reply
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;
}

- Mehdi January 16, 2018 | Flag Reply
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.

- charlie January 18, 2018 | Flag Reply
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);
}

- hprem991 January 12, 2018 | Flag Reply
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;
  }

- Anonymous January 12, 2018 | Flag Reply
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","");
    }

- pugal January 14, 2018 | Flag Reply


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