Serengeti
BAN USER- 1of 1 vote
AnswersGiven a graph, write a method to check if it is bipartite
- Serengeti in United States| Report Duplicate | Flag | PURGE
Spotify Software Engineer / Developer Coding
There's a duplicate version of this question, could not post a link to the original post since careercup.com does not allow links in comments but the Question ID is 12011927.
Here's my version in C#:
// Iterate through the string and for each character,
// if the character is a '(' or any of the operators
// push it to the stack
// If the character is a ')', then pop any operators and the
// matching '('. However when you try to pop if you only find a '('
// then this means it is a duplicate paranthesis.
static int GetNumberOfDuplicateParanthesis(string input)
{
int countOfDuplicates = 0;
input = input.Replace(" ", "");
Stack<char> chars = new Stack<char>();
for (int i = 0; i < input.Length; i++)
{
if ((input[i] == '(') ||
(input[i] == '+') ||
(input[i] == '*') ||
(input[i] == '-') ||
(input[i] == '/'))
{
chars.Push(input[i]);
}
else if (input[i] == ')')
{
if (chars.Peek() == '(')
{
countOfDuplicates++;
Console.WriteLine("Duplicate paranthesis found at {0}", i);
}
else
{
bool done = false;
while (!done)
{
if (chars.Peek() == '(')
{
done = true;
}
chars.Pop();
}
}
}
}
return countOfDuplicates;
}
Thanks for the explanation! I was struggling with this problem but this post helped me out. I wrote some code(C#) for a part of the problem. I did test this with a couple of use cases but was hoping to get your thoughts on the code below/if you see any bugs with it
static bool IsWordMadeOfSymbols(string word)
{
int i = 0;
while(i < word.Length)
{
string twoLetteredPrefix = null;
string oneLetteredPrefix = null;
if ((i + 1) < word.Length)
{
twoLetteredPrefix = word.Substring(i, 2);
}
oneLetteredPrefix = word[i].ToString();
if (!string.IsNullOrEmpty(twoLetteredPrefix) && symbolSet.Contains(twoLetteredPrefix))
{
i += 2;
}
else if (symbolSet.Contains(oneLetteredPrefix))
{
i += 1;
}
else
{
// since the current character didnt match, just check if current + previous works
// for example 'afg' when 'af' and 'fg' are symbols but g alone is not and 'i' currently points to 'g'
twoLetteredPrefix = word.Substring(i - 1, 2);
return symbolSet.Contains(twoLetteredPrefix);
}
}
return true;
}
- Serengeti September 15, 2014