## Microsoft Interview Question for Software Engineer in Tests

Team: Windows Phone
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 6 vote

use bit vector of 95000. He was looking for bit array at that time.

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

How can we use a bit array if the value at a certain position is only 1 and 0?

Comment hidden because of low score. Click to expand.
2

Then we can use 2 bit array. If the first and second is both 1, it means appear >=2. If only the first is 1, it means only appear once.

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

I answered the question with below code and the interviewer was happy with the solution, he also said that using an array with arr as in the code below is not an efficient way. I was not sure how else can I accommodate a UNICODE character set? And he did not tell me what's an efficient way when the interview got over.

``````public void FirstNonRepeatedCharacter(string s)
{
int i;
int[] asc = new int;
char[] ca = s.ToCharArray();
for (i = 0; i < ca.Length; i++)
{
asc[ca[i]] += 1;
}

for (i = 0; i < ca.Length; i++)
{
if (asc[ca[i]] == 1)
{
Console.WriteLine("first non repeating char is: " + ca[i]);
break;
}

}``````

}

Comment hidden because of low score. Click to expand.
2

why to go with array. instead of array you can take hashtable and run the loop till the length of the string.. I guess interview just trying to confuse you.. Here you just need to return only the first non repeat character. in whatever language you take input just run the code till the length of the string and return first non repeat character.

Comment hidden because of low score. Click to expand.
-2

this code will have to traverse the String twice while I think that this code will be better:

``````public void FirstNonRepeatedCharacter(String s){
List<Character> candidates = new ArrayList<>();

for (int i = 0; i < s.length(); i++) {
if(candidates.contains(s.charAt(i))){
Character c = new Character(s.charAt(i));
candidates.remove(c);
}

else
}
}
System.out.println(candidates.get(0));
}``````

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

your candidates list can be quite long, so you might have quadratic runtime with your code whereas iterating twice over the input string has only runtime of 2*n

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

I was not sure if the interviewer was just trying to test my approach or if we really have a way to represent the unicode char set without using an array of size 95000. But if you folks know a way to use the unicode character set without using a large array of size 95000, please do let me know as well.

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

I think the more efficient way is that you can use hash table instead of a long array.You can set the count that the character appears as the value of the hash table.And the hash table size is corresponding to the length of the string.
I don't know about Java so,I give a pseudocode.

``````public void FirstNonRepeatedCharacter(string s)
{
int i;
int[] asc = new int;
char[] ca = s.ToCharArray();
for (i = 0; i < ca.Length; i++)
{
key = CalculateHastKey(ca[i]);
HashTable[key] += 1;
}

for (i = 0; i < ca.Length; i++)
{
key = CalculateHastKey(ca[i]);
if (HashTable[key] == 1)
{
Console.WriteLine("first non repeating char is: " + ca[i]);
break;
}

}
}``````

The time complexity would be same with you,but the space complexity would be much smaller if the string is not very long.

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

int[] asc = new int; this line is not need in above code,a mistake....

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

How about using bool array instead of int array, it will save a lot of space, e.g.
(p.s. not good at JAVA)

``````public void FirstNonRepeatedCharacter(string s)
{
int i;
bool[] asc = new bool;
char[] ca = s.ToCharArray();
for (i = 0; i < ca.Length; i++)
{
asc[ca[i]] = 1;
}

for (i = 0; i < ca.Length; i++)
{
if (asc[ca[i]] == 1)
{
Console.WriteLine("first non repeating char is: " + ca[i]);
break;
}

}
}``````

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

01. In most of the languages bool data is stored as a byte so you are still wasting 7 bits out of 8.
02. this code will not identify duplicates because bool will not tell you if a number has only appeared once or multiple times.
03. Of course this code will NOT return the "first" non repeated character.

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

Using bitset will avoid the waste. To find the first non repeated a second scan of the string is needed.

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

``````public void FirstNonRepeatedCharacter(String s){
List<Character> candidates = new ArrayList<>();

for (int i = 0; i < s.length(); i++) {
if(candidates.contains(s.charAt(i))){
Character c = new Character(s.charAt(i));
candidates.remove(c);
}

else
}
}
System.out.println(candidates.get(0));
}``````

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

``````#!/usr/bin/perl

#Date: 06.10.2013

use strict;

my \$string = qw(wcaowaor);
my @tempArray = split "",\$string;
my @values = qw(0);
my %hashtable ;
my \$count = 0;

foreach (@tempArray)
{
\$values[ord(\$_)] +=1;
}

for(my \$i=0;\$i<\$#values;\$i++)
{
\$hashtable{\$count++} = chr(\$i) if \$values[\$i] == 1;
}

foreach my \$key(sort keys%hashtable)
{
if(defined \$hashtable{\$key})
{
print "the first none reapeating item is :","\$hashtable{\$key}\n";
last;
}
}

#END``````

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

``````string sentence = "am aα software programmer";

char character;

for (int i = 0; i < sentence.Length; i++)
{
character = sentence[i];
string restOfSentence = sentence.Substring(i + 1);

if (!restOfSentence.Contains(character))
{
break;
}
}``````

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

this is to the guy who hs put the question ..... m nt sure but i dont think ur code uld give the first non repeating character what if the string is: abcdeabcdegabcf
now g and f both appear once but ur code i think does not check which comes first...
i ve run the following code but not sure of the efficiency
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
int main()
{
char str;
int i,j,length = 0;
gets(str);
i=0;
while(str[i]!='\0')
{
length = length+1;
i=i+1;
}
for(i=0;i<length;i++)
{
if(str[i]!=7)
{
for(j=i+1;j<length;j++)
{
if(str[i]==str[j])
{
str[j]=7;//ascii for bell
break;
}
}
if(j==length)
{
printf("\n%c",str[i]);
break;
}
}
}
getch();
return 0;
}

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

``````namespace FirstNonRepeatedCharacter
{
class Program
{
public static char FirstNonRepeatedChar(string str)
{
char ch = ' ';

char[] charArray = str.ToCharArray();
Dictionary<char, int> chrHash = new Dictionary<char, int>();

foreach (char chr in charArray)
{
if (!chrHash.ContainsKey(chr))
{
chrHash[chr] = 0;
}
else
{
chrHash[chr]++;
}
}

foreach (KeyValuePair<char, int> kvp in chrHash)
{
if (kvp.Value == 1)
{
ch = kvp.Key;
break;
}
}

return ch;
}
static void Main(string[] args)
{
}
}
}``````

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

python:

map = {}
i ="dsjiodsjdeurenreieiekjkejnmenr"
for j in i:
if not j in map:
map[j] = 1
else:
map[j] +=1
for key in i:
if map[key] ==1:
print key

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

char check(string s)
{
set<char> myset;
unsigned int i=0;
while(i<s.length())
{
if(myset.insert(s[i]).second == 0)
myset.erase(s[i]);
i++;
}
if(myset.size() > 0)
return *(myset.begin());
return '\n'; // you can send any character which represents non-existant of non-repeating character in the string
}

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

#include <iostream>
#include <map>
#include <string>
#include <conio.h>

using namespace std;

int main(int argc, char *argv)
{
map<char, int>input;

string s;
cout<<"Enter the String:";
cin>>s;

for(int i=0; i< s.length(); i++)
input[s[i]]++;

map<char, int>::const_iterator iter;
for(iter=input.begin(); iter!=input.end();iter++)
if(iter->second == 1)
{cout<<iter->first; break;}

getch();
}

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

private static int firstnonrepeat(String target) {
char original =target.charAt(0);

for (int i=1; i< target.length(); i++)
{
if(original==target.charAt(i))
{
return i;
}
original = target.charAt(i);

}
return 0;
}

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

Solution With two Bitsets:

``````char findFirstNonRepeating(char * str){
bitset<95000> bs;
bitset<95000> bsUsed;
int len = strlen(str);
for(int i = 0 ; i < len ; i++){
if(bs.test(str[i])){
bsUsed.set(str[i]);
bs.flip(str[i]);
}
if(!bsUsed.test(str[i])){
bs.set(str[i]);
}
}
for(int i = 0 ; i < len ; i++){
if(bs.test(str[i])){
return str[i];
}
}
}``````

Space complexity is 95000 * 2 Bits, Much better than using an int array wich is 95000 * 32 Bits.

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

``````public static Character noRepeat(String s) {

//The linked hash set preserves insertion order.

char[] str = s.toCharArray();

for (int i = 0; i < s.length(); i++) {

if (chMap.contains(str[i]))
chMap.remove(str[i]);
else

}

Iterator<Character> i = chMap.iterator();

if (i.hasNext())
return i.next();
else
return null;

}``````

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

``````public void FirstNonRepeatedCharacter(String str){
HashSet hs=new HashSet();
boolean bool=false;
for(int i=0;i<str.length();i++){
bool=true;
System.out.println("First Non repitive char is "+str.charAt(i));
break;
}
}
if(!bool)
System.out.println("None of chars are repeating");
}``````

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

``````Use below to get 1st unique value in O(n)

public char FirstDistinctCharacter(string str)
{
Hashtable ht = new Hashtable();
List<char> val = new List<char>();
foreach (char c in str.ToCharArray())
{
try
{
}
catch (Exception) {
if(val.Contains(c))
val.Remove(c);
}
}
return (val.Count!=0)? val : new char();
}``````

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

I have two solutions in Ruby. It seems the author meant to use "non-recurring" in place of "non-repeating". I have implemented both solutions, below:

Non-Repeating:

``````#!/usr/bin/env ruby

# Find the first non-repeating character in a string and return its zero-based position.
# A repeating character is a character that occurs multiple times in succession within
# the same string.

class String
def index_of_first_nonrepeating
j = -1
self.split("").each_with_index do |c,i|
if i == 0
if self.length == 1
j = i
break
end
next
end
if i == self.length - 1
if c != self[i-1]
j = i
end
break
end
if c != self[i-1] && c != self[i+1]
j = i
break
end
end
j
end
end

s = "aaaaabbbdceccccc"

puts "Index of first non-repeating char in \"#{s}\" is i = #{s.index_of_first_nonrepeating}."``````

Non-Recurring:

``````#!/usr/bin/env ruby

# Find the first occurrence of a character that occurs only once in a string.

require 'set'
class String

def index_of_first_non_recurring
h = Hash.new(0)
self.split("").each do |c|
h[c] += 1
end
s = h.each_pair.collect do |k,v|
k if v == 1
end.compact
v = s.min{|v| self =~ /#{v}/}
i = self =~ /#{v}/
end

end

s = "abcdefavcdefgb"
i = s.index_of_first_non_recurring

puts "Index of first non-recurring character in \"#{s}\" is i = #{i} (\"#{s[i]}\")."``````

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

``Nice``

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

good one

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.