stanislav.khalash
BAN USER
Here's the simple C# code for both recursive and iterative in-order traversals. The maximum stack size is equal to the tree height. For an arbitrary tree it is equal to O(n) in the worst case. For a perfectly balanced BST it is equal to O(lgN).
using System;
using System.Collections.Generic;
namespace CareerCup
{
public class TreeNode
{
private readonly int _key;
private readonly int _value;
public TreeNode(int key, int value)
{
_key = key;
_value = value;
}
public int Key
{
get
{
return _key;
}
}
public int Value
{
get
{
return _value;
}
}
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
}
public class InorderTraversal
{
public void TraverseRecursively(TreeNode node, Action<TreeNode> callback)
{
if (node == null)
{
return;
}
TraverseRecursively(node.Left, callback);
callback(node);
TraverseRecursively(node.Right, callback);
}
public void TraverseIteratively(TreeNode node, Action<TreeNode> callback)
{
if (node == null)
{
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while (stack.Count > 0 || node != null)
{
if (node == null)
{
TreeNode parent = stack.Pop();
callback(parent);
node = parent.Right;
}
else
{
stack.Push(node);
node = node.Left;
}
}
}
}
}
using System;
using System.Collections.Generic;
namespace CareerCup
{
public class BuildOrder
{
private const int Undiscovered = 1;
private const int Discovered = 2;
private const int Processing = 4;
public void ResolveBuildOrder(string input)
{
var adjLists = Parse(input);
var buildQueue = TopologicalSort(adjLists);
foreach (var item in buildQueue)
{
Console.WriteLine(item);
}
}
private Dictionary<char, LinkedList<char>> Parse(string input)
{
var result = new Dictionary<char, LinkedList<char>>();
var tokens = input.Split(' ');
foreach (var token in tokens)
{
char from = token[0], to = token[3];
if (!result.ContainsKey(from))
{
result[from] = new LinkedList<char>();
}
if (!result.ContainsKey(to))
{
result[to] = new LinkedList<char>();
}
result[from].AddLast(to);
}
return result;
}
private Queue<char> TopologicalSort(Dictionary<char, LinkedList<char>> adjLists)
{
var states = new Dictionary<char, int>();
foreach (var vertice in adjLists.Keys)
{
states[vertice] = Undiscovered;
}
var queue = new Queue<char>();
foreach (var vertice in adjLists.Keys)
{
if ((states[vertice] & Discovered) != Discovered)
{
DfsVisit(vertice, adjLists, states, queue);
}
}
return queue;
}
private void DfsVisit(
char root,
Dictionary<char, LinkedList<char>> adjLists,
Dictionary<char, int> states,
Queue<char> postorderQueue)
{
states[root] |= Processing;
states[root] |= Discovered;
foreach (var child in adjLists[root])
{
if ((states[child] & Processing) == Processing)
{
throw new Exception("Cycle found!");
}
if ((states[child] & Discovered) != Discovered)
{
DfsVisit(child, adjLists, states, postorderQueue);
}
}
states[root] ^= Processing;
postorderQueue.Enqueue(root);
}
}
}
Naive approach is used to find a substring (which is OK if both words are short). If I had more time, I would something more advanced (e.g. Rabin–Karp algorithm).
using System;
namespace InterviewTasks
{
internal static class MinLengthBetweenWords
{
public static int FindMinLength(string input, string x, string y)
{
if (string.IsNullOrEmpty(input))
{
throw new ArgumentException("input");
}
if (string.IsNullOrEmpty(x))
{
throw new ArgumentException("x");
}
if (string.IsNullOrEmpty(y))
{
throw new ArgumentException("y");
}
int whitespacesCount = 0;
int lastXOccurence = -1;
for (int i = 0; i < input.Length - x.Length + 1; ++i)
{
bool isSubstring = true;
for (int j = 0; j < x.Length; ++j)
{
if (input[i + j] != x[j])
{
isSubstring = false;
break;
}
}
if (isSubstring)
{
lastXOccurence = i;
}
}
if (lastXOccurence == -1)
{
return -1;
}
for (int i = lastXOccurence + x.Length; i < input.Length - y.Length + 1; ++i)
{
if (input[i] == ' ')
{
whitespacesCount++;
continue;
}
bool isSubstring = true;
for (int j = 0; j < y.Length; ++j)
{
if (input[i + j] != y[j])
{
isSubstring = false;
break;
}
}
if (isSubstring)
{
return whitespacesCount;
}
}
return -1;
}
}
}
using System;
namespace CareerCup
{
public class ShortestPalindrome
{
public int GetShortestPalindromeLength(string input)
{
if (string.IsNullOrEmpty(input))
{
throw new ArgumentNullException("input");
}
int leadingCharsNumber = 0;
while (leadingCharsNumber < input.Length)
{
bool flag = true;
for (int i = 0, j = input.Length - 1 - leadingCharsNumber;
i < j;
i++, j--)
{
if (input[i] != input[j])
{
flag = false;
break;
}
}
if (flag)
{
break;
}
leadingCharsNumber++;
}
return leadingCharsNumber + input.Length;
}
}
}
using System;
using System.Collections.Generic;
namespace InterviewTasks
{
internal static class QuotationMarks
{
public static string[] GetAllStrings(string pattern)
{
if (string.IsNullOrEmpty(pattern))
{
throw new ArgumentException("Pattern should be a non-empty string");
}
List<int> quotationMarks = new List<int>();
for (int i = 0; i < pattern.Length; ++i)
{
if (pattern[i] == '?')
{
quotationMarks.Add(i);
}
}
string[] result = new string[1 << quotationMarks.Count];
for (int i = 0; i < result.Length; ++i)
{
char[] chars = pattern.ToCharArray();
for (int j = 0; j < quotationMarks.Count; ++j)
{
var quotationMarkPosition = quotationMarks[j];
chars[quotationMarkPosition] = ((i >> j) & 1) == 1 ? '1' : '0';
}
result[i] = new string(chars);
}
return result;
}
}
}
Repjimbtam, Backend Developer at ASAPInfosystemsPvtLtd
I was extremely into photography for a number of years.My father was also interested in photography, so I was ...
RepTristaRJohn, Reverse Engineering and System Developer at BT
I am an Ophthalmic medical assistant in bluefield USA, I assist in retinal exams and procedures. Referred patients to outside ...
Repjuliaaperez05, Cloud Support Associate at ABC TECH SUPPORT
I Performed extensive web research to collect pertinent data and gather images related to the assigned articleIts act of writing ...
Repjoewfeder, Apple Phone Number available 24/7 for our Customers at ADP
I am a Golf course architect in PriceRite Warehouse Club company. I am a positive person and a sense of ...
Reptaniajclover, Analyst at Amdocs
Hi, I am Tania from Tuckahoe USA, I am working as a Public relations representative in Gamble-Skogmo company. I like ...
Repcarlaapepin, Area Sales Manager at Atmel
Hello, I am Carla and I live in San Bernardino, USA. I am working as a bookkeeper in a library ...
Repnancysimms14, Backend Developer at ASAPInfosystemsPvtLtd
I am Nancy from California,Handling project development and documentation is my job. Passionate determined.Looking for an open project ...
Repritahmixon, Analyst at ADP
Hi, I am a physiotherapy to help people handle everyday problems. I also assist peoples who have issues caused by ...
Repjd5636176, Area Sales Manager at Achieve Internet
I am currently in the tool and die maker in Titania to start my career. I work from engineering drawings ...
I assume that making use of regular expressions, Socket API and system parse methods is a bit of overhead. At least, it's not what interviewers usually expect. Here's the code that gets the job done with one simple linear scan.
- stanislav.khalash January 24, 2015