Microsoft Interview Question for SDE-2s


Team: Office
Country: India
Interview Type: In-Person




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

#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

- praveen pandit March 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I used Doubly linked list so it allowed me the free movement and non recursive solution.

- rajnikant12345 March 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

so many bug on that one.
try to test those.
AAAACCCCBB, ACBACBACBA, ABCCC

- eile March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Sid March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

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.

- Sid March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try your algorithm with AAAAABBBC. It doesn't work, although the string can be reconstructed to ABABABACA .

- kojino November 27, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try your algorithm with AAAAABBBC. It doesn't work, although the string can be reconstructed to ABABABACA.

- kojino November 27, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Sid March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- rajnikant12345 March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vivek J Joshi March 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- allen.lipeng47 March 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous March 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var s = "AABCDAABCCD";
var a = s.split("");

for (var i = 0; i < a.length; i++) {

	if (a[i] == a [i+1]) {
		var temp = a[i+2];
		a[i+2] = a[i+1];
		a[i+1] = temp;

	}
}
var res = a.join("");

- Anonymous March 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var s = "AABCDAABCDDD";
var a = s.split("");

for (var i = 0; i < a.length-1; i++) {

	if (a[i] == a [i+1]) {
  	if (i != a.length-2){
    	var temp = a[i+2];
			a[i+2] = a[i+1];
			a[i+1] = temp;
    }
    else{
    	var temp = a[i+1];
			a[i+1] = a[0];
			a[0] = temp;
      i=0;
    }
  }
}
var res = a.join("");

- Anonymous March 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var s = "AABCDAABCDDD";
var a = s.split("");

for (var i = 0; i < a.length-1; i++) {

	if (a[i] == a [i+1]) {
  	if (i != a.length-2){
    	var temp = a[i+2];
			a[i+2] = a[i+1];
			a[i+1] = temp;
    }
    else{
    	var temp = a[i+1];
			a[i+1] = a[0];
			a[0] = temp;
      i=0;
    }
  }
}
var res = a.join("");

- Anonymous1 March 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. put character and it count into hashtable.
2. get max character from hashtable, if the char is not previous one.

- ante April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Dhruv April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It wont work when repetitive characters are towards end of string. (e.g. ABCCC)
Ideally, there is an answer as CACBC but this cannot get that.

- sumitgupta153 November 22, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Dhruv April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kundan94.mnnit April 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Death striker April 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Roiht August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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")

- mkdivis07 September 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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')

- kojino November 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ash December 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ash December 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ash December 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Compute counts of each char. Put the chars in a priority Q/max heap with the count as the priority. Now always remove the char with highest and second highest priority to generate the output.

- krishna March 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
private String shuffle(String str) {
char[] arr = str.toCharArray();
int n = arr.length;

int i = 0, j = 0;

while (j < n) {
if (arr[i] != arr[j]) {
swap(arr, ++i, j);
} else {
j++;
}
}

return new String(arr);
}
}}

- amit March 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- swetank June 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Sid March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Sid March 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

ABCDAA ---> test this input

- rajnikant12345 March 13, 2016 | Flag


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