Microsoft Interview Question
SDE-2sTeam: Office
Country: India
Interview Type: In-Person
#include <stdio.h>
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
bool isSimTogether(char *a, int size){
for (int i = 0; i < size; i++){
if (a[i] == a[i + 1])
return true;
}
return false;
}
void permute(char *a, int l, int r)
{
int i;
if (l == r && !isSimTogether(a,r)){
printf("%s\n", a);
}
else
{
for (i = l; i <= r; i++)
{
if (l == i) continue;
swap((a + l), (a + i));
permute(a, l + 1, r);
swap((a + l), (a + i));
}
}
}
int main()
{
char str[] = "AABC";
int n = sizeof(str) / sizeof(str[0]) - 1;
permute(str, 0, n - 1);
return 0;
}
ABCA
ACAB
BACA
1. Store the chanracters in Hashtable against the count
2. Iterate the hashtable one by one.
3. Append the result array after checking the character for the quality check.
4. if found to be equal , swap between the current position and the two character behind the current character.
5. Once the character count in the Hashtable is 0 , remove the entry.
6. Traverse till the Hashtable is empty.
1.Fill in HashTable with characters against its count
2. Iterate the HashTable
3. After every Iteration , deduct the count of the character.
4. Remove the entry if the character count is 0
5. If the character placed is equal to the existing current character, then swap with the character at two positions behind.
Repeat this , till the HashTable is empty.
Try your algorithm with AAAAABBBC. It doesn't work, although the string can be reconstructed to ABABABACA .
1.Fill in HashTable with characters against its count
2. Iterate the HashTable
3. After every Iteration , deduct the count of the character.
4. Remove the entry if the character count is 0
5. If the character placed is equal to the existing current character, then swap with the character at two positions behind.
Repeat this , till the HashTable is empty.
Create a doubly liked list of characters.
Now start moving from start.
If you find a duplicate.
Remove that node.
Find a place for it where it fits in a linked list.
So , every time you find a duplicate , just repeat it.
If no place is found for a duplicate, return false bcz we cannot solve it.
void ScrambleString( string &inputString, int iter = 4 )
{
if( iter == 0 )
return;
cout << "Iteration : " << iter << endl;
size_t strLen = inputString.size();
for( int i = 1; i < strLen; i++ )
{
if( inputString[i-1] == inputString[i] )
{
for( int k = i+1; k < strLen; k++ )
{
if( inputString[i] == inputString[k] )
continue;
char temp = inputString[i];
inputString[i] = inputString[k];
inputString[k] = temp;
break;
}
}
}
iter--;
bool iterateFlag = false;
for( int i = 1; i < strLen; i++ )
{
if( inputString[i-1] == inputString[i] )
{
iterateFlag = true;
break;
}
}
if( iterateFlag )
{
std::reverse(inputString.begin(), inputString.end());
ScrambleString(inputString, iter );
}
return;
}
public List<String> shuffleString(String str) {
List<String> ans = new ArrayList<>();
shuffleStringHelper(str, ans, new StringBuffer(), new boolean[str.length()]);
return ans;
}
private void shuffleStringHelper(String str, List<String> ans, StringBuffer curr, boolean[] visited) {
if (curr.length() >= str.length()) {
ans.add(curr.toString());
return;
}
for (int i = 0; i < visited.length; i++) {
if (visited[i] || curr.length() > 0 && curr.charAt(curr.length() - 1) == str.charAt(i)
|| i > 0 && str.charAt(i) == str.charAt(i - 1) && !visited[i - 1]) {
continue;
}
visited[i] = true;
curr.append(str.charAt(i));
shuffleStringHelper(str, ans, curr, visited);
curr.deleteCharAt(curr.length() - 1);
visited[i] = false;
}
}
void continueShuffle(std::vector<char> &shuffeRes,
std::unordered_map<char, int> &charsCountMap,
size_t total){
if(total == shuffeRes.size()){
std::cout << "found one solution: ";
for(char ch:shuffeRes){
std::cout << ch;
}
std::cout << std::endl;
return;
}
char neiborChar = '\0';
if(shuffeRes.size() > 0){
neiborChar = shuffeRes.back();
}
std::unordered_map<char, int>::iterator it = charsCountMap.begin();
while (it != charsCountMap.end()){
if(it->first != neiborChar && it->second != 0){
it->second--;
shuffeRes.push_back(it->first);
continueShuffle(shuffeRes, charsCountMap, total);
shuffeRes.pop_back();
it->second++;
}
++it;
}
}
void shuffleChar(std::string chars){
std::unordered_map<char, int> charsCount;
std::vector<char> shuffeRes;
for(char ch : chars){
charsCount[ch]++;
}
continueShuffle(shuffeRes, charsCount, chars.size());
}
void continueShuffle(std::vector<char> &shuffeRes,
std::unordered_map<char, int> &charsCountMap,
size_t total){
if(total == shuffeRes.size()){
std::cout << "found one solution: ";
for(char ch:shuffeRes){
std::cout << ch;
}
std::cout << std::endl;
return;
}
char neiborChar = '\0';
if(shuffeRes.size() > 0){
neiborChar = shuffeRes.back();
}
std::unordered_map<char, int>::iterator it = charsCountMap.begin();
while (it != charsCountMap.end()){
if(it->first != neiborChar && it->second != 0){
it->second--;
shuffeRes.push_back(it->first);
continueShuffle(shuffeRes, charsCountMap, total);
shuffeRes.pop_back();
it->second++;
}
++it;
}
}
void shuffleChar(std::string chars){
std::unordered_map<char, int> charsCount;
std::vector<char> shuffeRes;
for(char ch : chars){
charsCount[ch]++;
}
continueShuffle(shuffeRes, charsCount, chars.size());
}
namespace Practice1
{
public class Program
{
public static void Main(string[] args)
{
Console.WriteLine("Enter a String");
String userInput = Console.ReadLine();
String answer = "";
bool stillSimilar = true;
char[] inputArray = userInput.ToArray();
while (stillSimilar)
{
for (int i = 0; i < inputArray.Length - 1; i++)
{
if (inputArray[i] == inputArray[i + 1])
{
char tmp = inputArray[i + 1];
inputArray[i + 1] = inputArray[(i + 2) % inputArray.Length];
inputArray[i + 2] = tmp;
}
}
stillSimilar = isSimilar(inputArray);
}
for (int i = 0; i < inputArray.Length; i++)
{
answer += inputArray[i];
}
Console.WriteLine(answer);
Console.ReadLine();
}
public static bool isSimilar(char[] input)
{
for (int i = 0; i < input.Length - 1; i++)
{
if (input[i] == input[i + 1]) {
return true;
}
}
return false;
}
}
}
{
void swap(char &a, char &b)
{
char temp;
temp = a;
a = b;
b = temp;
}
void shuffle()
{
int curr = 0, next = 1;
char str[] = {'A', 'A', 'A', 'A', 'B', 'B', 'C', 'C', 'D', 'C', 'A', 'D', '\0'};
while (str[curr] != '\0')
{
if(str[curr] == str[next])
{
next++;
continue;
}
else
{
swap(str[curr+1], str[next]);
curr++;
}
}
cout << str << endl;
}
void swap(char &a, char &b)
{
char temp;
temp = a;
a = b;
b = temp;
}
void shuffle)
{
int curr = 0, next = 1;
char str[] = {'A', 'A', 'A', 'A', 'B', 'B', 'C', 'C', 'D', 'C', 'A', 'D', '\0'};
while (str[curr] != '\0')
{
if(str[curr] == str[next])
{
next++;
continue;
}
else
{
swap(str[curr+1], str[next]);
curr++;
}
}
cout << str << endl;
}
public class HashTb
{
public static void main(String[] args)
{
LinkedHashMap<Character,Integer> hm=new LinkedHashMap<Character, Integer>();
StringBuilder strnew=new StringBuilder("");
String str="AAAACCCCBB";
int k=0;
for(int i=0;i<str.length();i++)
{
if(hm.isEmpty())
{
hm.put(str.charAt(i), 1);
}
else
{
boolean val=hm.containsKey(str.charAt(i));
if(val==false)
{
hm.put(str.charAt(i), 1);
}
else
{
hm.put(str.charAt(i), hm.get(str.charAt(i))+1);
}
}
}
Set<Character> set = hm.keySet();
Iterator<Character> itr = set.iterator();
int flag=1;
while(true)
{
flag=1;
itr = set.iterator();
while (itr.hasNext())
{
Character ch = itr.next();
int val= hm.get(ch);
if(val!=0)
{
strnew.insert(k,ch);
if(k>0)
{
if(strnew.charAt(k)==strnew.charAt(k-1))
{
strnew.setCharAt(k, strnew.charAt(k-3));
strnew.setCharAt(k-3, ch);
}
}
k++;
hm.put(ch,val-1);
}
if((val-1)>0)
{
flag=0;
}
}
if(flag==1)
break;
}
System.out.println("New String:- "+strnew);
}
}
Put the number of each character into a hash table as <character, count>. Then iterate through the hash table printing out each consecutive character to ensure non of the same are next to each other and decrement each characters count. When count reaches 0, remove the key-value pair. Loop until the hash table is empty again.
import java.util.Hashtable;
import java.util.Set;
public class ScrambleString {
static Hashtable<Character, Integer> hash = new Hashtable<Character, Integer>();
static String testInput = "AAAAABBABAAAACCCDEF";
static Set<Character> myKeys;
public static void main(String[] args) {
// Create hash table
Integer num;
for (int i = 0; i < testInput.length(); i++) {
num = hash.get(testInput.charAt(i));
if (num == null) {
num = 1;
} else {
num++;
}
hash.put(testInput.charAt(i), num);
}
// Print out new string
int index = 0;
while (!hash.isEmpty()) {
myKeys = hash.keySet(); // set of unique characters remaining
Object[] myArray = myKeys.toArray(); // convert to array for easy access
Character key = (Character) myArray[index++ % myArray.length]; // get next character
Integer i = hash.get(key); // get count
System.out.print(key); // print character
hash.put(key, --i); // decrement count
if (i == 0) {
hash.remove(key); // remove if printed out all counts of character
}
}
}
}
public static string Shuffle(string str)
{
var strArr = str.ToCharArray();
Random rm = new Random();
var l = strArr.Length;
while (l > 1)
{
l--;
int k = rm.Next(l);
var temp = strArr[k];
strArr[k] = strArr[l];
strArr[l] = temp;
if (CheckValidation(strArr))
break;
}
return new string(strArr);
}
private static bool CheckValidation(char[] arr)
{
if (arr.Length > 1)
{
for (int i = 0; i < arr.Length-1; i++)
{
if (arr[i] == arr[i + 1])
return false;
}
}
return true;
}
o=[]
t=[]
def shuffle_string(a):
for i in a:
if len(o) == 0:
o.append(i)
elif o[-1]!=i:
o.append(i)
j = len(t)
while j != 0:
if o[-1] != t[j-1]:
o.append(t.pop())
j-=1
else:
t.append(i)
for j in t:
for i in xrange(len(o)):
if i == 0 and o[i]!= j:
o.insert(i,j)
elif o[i]!=j and o[i+1]!=j:
o.insert(i+1,j)
print o
shuffle_string("ABCCCc")
A working Python solution.
def shuffle(string):
counter = {}
# one character count > n/2 then can't suffle
n = len(string)
for char in string:
if char in counter:
counter[char] += 1
if counter[char] > (n+1)/2:
return None
else:
counter[char] = 1
sorted_string = sorted(string)
shuffled_string = ""
previous_char = ""
queue = []
# AAABBCCDD
# result: ABCD
# queue: DCBAA
for char in string:
if char == previous_char:
queue.insert(0,char)
for queue_char in char:
if queue_char != previous_char:
shuffled_string += queue_char
previous_char = queue_char
else:
shuffled_string += char
previous_char = char
if len(queue) > 0:
for queue_char in queue:
previous_char = ""
for i,char in enumerate(shuffled_string):
if queue_char != previous_char and queue_char != char:
shuffled_string = shuffled_string[:i] + queue_char + shuffled_string[i:]
break
previous_char = char
return shuffled_string
print shuffle('ABCDAABCD')
print shuffle('aaaabbbca')
print shuffle('aaaabbbcaa')
print shuffle('')
print shuffle('a')
Try this:
//Not possible scenario:
//When count of max occuring character is more than all other characters plus one then its not possible.
//Solution: get an array of length equal to string length.
//Start filling same character on alternate positions.
//When next character comes, fill it on immediate next position (not on alternate)
//By the end of first pass on character array, you would fill half of characters.
//In second pass fill non-filled positions.
public string ShuffleLetters(string str)
{
var dict = new Dictionary<Char, int>();
var maxCount = 0;
//Build Dictionary.
foreach (var c in str)
{
if (dict.ContainsKey(c))
dict[c]++;
else
dict.Add(c, 1);
if (dict[c] > maxCount)
maxCount = dict[c];
}
if (maxCount > (str.Length - maxCount) + 1)
return "Not Possible";
var fixedArray = new Char[str.Length];
int nextIndex = 0;
//First pass: Fill alternate boxes (if same)
//fill adjacent boxes if different.
while (nextIndex <= str.Length - 1)
{
var key = dict.ElementAt(0).Key;
fixedArray[nextIndex] = key;
dict[key]--;
if (dict[key] == 0)
{
dict.Remove(key);
nextIndex++;
}
else
{
nextIndex += 2;
}
}
//Fill Remaining.
for (var i = 0; i < str.Length; i++)
{
if (fixedArray[i] != '\0')
continue;
var key = dict.ElementAt(0).Key;
fixedArray[i] = key;
dict[key]--;
if (dict[key] == 0)
{
dict.Remove(key);
}
}
return new String(fixedArray);
}
public string ShuffleLetters(string str)
{
var dict = new Dictionary<Char, int>();
var maxCount = 0;
//Build Dictionary.
foreach (var c in str)
{
if (dict.ContainsKey(c))
dict[c]++;
else
dict.Add(c, 1);
if (dict[c] > maxCount)
maxCount = dict[c];
}
if (maxCount > (str.Length - maxCount) + 1)
return "Not Possible";
var fixedArray = new Char[str.Length];
int nextIndex = 0;
//First pass: Fill alternate boxes (if same)
//fill adjacent boxes if different.
while (nextIndex <= str.Length - 1)
{
var key = dict.ElementAt(0).Key;
fixedArray[nextIndex] = key;
dict[key]--;
if (dict[key] == 0)
{
dict.Remove(key);
nextIndex++;
}
else
{
nextIndex += 2;
}
}
//Fill Remaining.
for (var i = 0; i < str.Length; i++)
{
if (fixedArray[i] != '\0')
continue;
var key = dict.ElementAt(0).Key;
fixedArray[i] = key;
dict[key]--;
if (dict[key] == 0)
{
dict.Remove(key);
}
}
return new String(fixedArray);
}
public string ShuffleLetters(string str)
{
var dict = new Dictionary<Char, int>();
var maxCount = 0;
//Build Dictionary.
foreach (var c in str)
{
if (dict.ContainsKey(c))
dict[c]++;
else
dict.Add(c, 1);
if (dict[c] > maxCount)
maxCount = dict[c];
}
if (maxCount > (str.Length - maxCount) + 1)
return "Not Possible";
var fixedArray = new Char[str.Length];
int nextIndex = 0;
//First pass: Fill alternate boxes (if same)
//fill adjacent boxes if different.
while (nextIndex <= str.Length - 1)
{
var key = dict.ElementAt(0).Key;
fixedArray[nextIndex] = key;
dict[key]--;
if (dict[key] == 0)
{
dict.Remove(key);
nextIndex++;
}
else
{
nextIndex += 2;
}
}
//Fill Remaining.
for (var i = 0; i < str.Length; i++)
{
if (fixedArray[i] != '\0')
continue;
var key = dict.ElementAt(0).Key;
fixedArray[i] = key;
dict[key]--;
if (dict[key] == 0)
{
dict.Remove(key);
}
}
return new String(fixedArray);
Swap duplicate with a new character found on right and then repeat from right to left if the previous scanning could not solve.
#include <iostream>
#include <string.h>
using namespace std;
void shuffle(char* a)
{
bool done=true;
int index = 0;
int n = strlen(a);
for(int i=0; i<n-1; i++)
{
if(a[i] == a[i+1])
{
bool found = false;
for(int j=i+2; j<n; j++)
{
if(a[j] != a[i+1])
{
char r = a[j];
a[j] = a[i+1];
a[i+1] = r;
found = true;
break;
}
}
if(!found)
{
done = false;
}
}
}
if(!done)
{
for(int i=n-1; i>0; i--)
{
if(a[i] == a[i-1])
{
bool found = false;
for(int j=i-2; j>=0; j--)
{
if(a[j] != a[i-1])
{
char r = a[j];
a[j] = a[i-1];
a[i-1] = r;
found = true;
break;
}
}
if(!found)
{
done = false;
cout << "not possible\n";
}
}
}
}
}
int main() {
// your code goes here
char s[100];
cin >> s;
cout << "input: " << s <<endl;
shuffle(s);
cout << "output: " << s << endl;
return 0;
}
1. Store the chanracters in Hashtable against the count
2. Iterate the hashtable one by one.
3. Append the result array after checking the character for the quality check.
4. if found to be equal , swap between the current position and the two character behind the current character.
5. Once the character count in the Hashtable is 0 , remove the entry.
6. Traverse till the Hashtable is empty.
ABCDAA -> ABCDA
-> ABADAC
AAAACCCCBB -> ACBACBACAC
ABCCC -> ABC -> Removed A , B after the count become 0.
-> ABCC Next comes found the conflict .Swapped current(C) and current-2 -> CBCA
-> CBCAC
1. Store the chanracters in Hashtable against the count
2. Iterate the hashtable one by one.
3. Append the result array after checking the character for the quality check.
4. if found to be equal , swap between the current position and the two character behind the current character.
5. Once the character count in the Hashtable is 0 , remove the entry.
6. Traverse till the Hashtable is empty.
Eg:
ABCDAA -> ABCDA
-> ABADAC
AAAACCCCBB -> ACBACBACAC
ABCCC -> ABC -> Removed A , B after the count become 0.
-> ABCC Next comes found the conflict .Swapped current(C) and current-2 -> CBCA
-> CBCAC
so many bug on that one.
- eile March 14, 2016try to test those.
AAAACCCCBB, ACBACBACBA, ABCCC