Skip to content

Commit fcfef46

Browse files
paramagparamag
paramag
authored and
paramag
committed
Trie implementation
1 parent 6aeff63 commit fcfef46

File tree

17 files changed

+541
-10
lines changed

17 files changed

+541
-10
lines changed

‎.gitignore‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,3 +46,5 @@
4646
/Algorithm/InterviewCake/obj/Debug
4747
/Algorithm/Queues/bin/Debug
4848
/Algorithm/Queues/obj/Debug
49+
/Algorithm/Tries/bin/Debug
50+
/Algorithm/Tries/obj/Debug

‎Algorithm/.vs/Algorithms/v14/.suo‎

22.5 KB
Binary file not shown.

‎Algorithm/Algorithms.sln‎

Lines changed: 37 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@ Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "DataStructures.Libraries.Tr
1717
EndProject
1818
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.Stacks", "Stacks\Algorithms.Problem.Stacks.csproj", "{BA9B0DFD-92C0-4571-A021-ED24D430212B}"
1919
EndProject
20-
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Alogrithms.Problem.DynamicProgramming", "DynamicProgramming\Alogrithms.Problem.DynamicProgramming.csproj", "{8B3944E0-3499-4543-B381-A2E99C3D5D8D}"
20+
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.DynamicProgramming", "DynamicProgramming\Algorithms.Problem.DynamicProgramming.csproj", "{8B3944E0-3499-4543-B381-A2E99C3D5D8D}"
2121
EndProject
2222
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problems.LeetCode", "LeetCode\Algorithms.Problems.LeetCode.csproj", "{C66BCA6A-F2B5-467B-89E9-61C228639298}"
2323
EndProject
@@ -27,6 +27,10 @@ Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "DataStructures.Libraries.Gr
2727
EndProject
2828
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.Queues", "Queues\Algorithms.Problem.Queues.csproj", "{1640C6C1-4B49-45C3-9EB1-FB57E64B405F}"
2929
EndProject
30+
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.Tries", "Tries\Algorithms.Problem.Tries.csproj", "{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}"
31+
EndProject
32+
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Games.Problem.Library", "..\Games\Games.Problem.Library.csproj", "{34D7921E-5474-4F24-91F9-A87CFEBFAACF}"
33+
EndProject
3034
Global
3135
GlobalSection(SolutionConfigurationPlatforms) = preSolution
3236
Debug|Any CPU = Debug|Any CPU
@@ -215,6 +219,38 @@ Global
215219
{1640C6C1-4B49-45C3-9EB1-FB57E64B405F}.Release|x64.Build.0 = Release|Any CPU
216220
{1640C6C1-4B49-45C3-9EB1-FB57E64B405F}.Release|x86.ActiveCfg = Release|Any CPU
217221
{1640C6C1-4B49-45C3-9EB1-FB57E64B405F}.Release|x86.Build.0 = Release|Any CPU
222+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
223+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|Any CPU.Build.0 = Debug|Any CPU
224+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|ARM.ActiveCfg = Debug|Any CPU
225+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|ARM.Build.0 = Debug|Any CPU
226+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|x64.ActiveCfg = Debug|Any CPU
227+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|x64.Build.0 = Debug|Any CPU
228+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|x86.ActiveCfg = Debug|Any CPU
229+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Debug|x86.Build.0 = Debug|Any CPU
230+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|Any CPU.ActiveCfg = Release|Any CPU
231+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|Any CPU.Build.0 = Release|Any CPU
232+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|ARM.ActiveCfg = Release|Any CPU
233+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|ARM.Build.0 = Release|Any CPU
234+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|x64.ActiveCfg = Release|Any CPU
235+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|x64.Build.0 = Release|Any CPU
236+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|x86.ActiveCfg = Release|Any CPU
237+
{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}.Release|x86.Build.0 = Release|Any CPU
238+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
239+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|Any CPU.Build.0 = Debug|Any CPU
240+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|ARM.ActiveCfg = Debug|Any CPU
241+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|ARM.Build.0 = Debug|Any CPU
242+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|x64.ActiveCfg = Debug|Any CPU
243+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|x64.Build.0 = Debug|Any CPU
244+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|x86.ActiveCfg = Debug|Any CPU
245+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Debug|x86.Build.0 = Debug|Any CPU
246+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|Any CPU.ActiveCfg = Release|Any CPU
247+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|Any CPU.Build.0 = Release|Any CPU
248+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|ARM.ActiveCfg = Release|Any CPU
249+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|ARM.Build.0 = Release|Any CPU
250+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|x64.ActiveCfg = Release|Any CPU
251+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|x64.Build.0 = Release|Any CPU
252+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|x86.ActiveCfg = Release|Any CPU
253+
{34D7921E-5474-4F24-91F9-A87CFEBFAACF}.Release|x86.Build.0 = Release|Any CPU
218254
EndGlobalSection
219255
GlobalSection(SolutionProperties) = preSolution
220256
HideSolutionNode = FALSE

‎Algorithm/BinaryTree/Algorithms.Problem.BinaryTree.csproj‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@
4444
<Reference Include="System.Xml" />
4545
</ItemGroup>
4646
<ItemGroup>
47+
<Compile Include="BalanceTreeChecker.cs" />
4748
<Compile Include="ConnectNextNode.cs" />
4849
<Compile Include="DistanceBetweenTwoNodes.cs" />
4950
<Compile Include="LevelSpiralOrder.cs" />

‎Algorithm/BinaryTree/BalanceTreeChecker.cs‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
using DataStructures.Libraries.Trees;
2+
using Microsoft.VisualStudio.TestTools.UnitTesting;
3+
using System;
4+
using System.Collections.Generic;
5+
using System.Linq;
6+
using System.Text;
7+
using System.Threading.Tasks;
8+
9+
namespace Algorithms.Problem.BinaryTree
10+
{
11+
public class TreeNodeCheck
12+
{
13+
public BinaryTreeNode TreeNode;
14+
public int Depth;
15+
16+
public TreeNodeCheck(BinaryTreeNode node, int depth)
17+
{
18+
this.TreeNode = node;
19+
this.Depth = depth;
20+
}
21+
}
22+
23+
[TestClass]
24+
public class BalanceTreeChecker
25+
{
26+
public bool IsBinaryTreeBalance(BinaryTreeNode root)
27+
{
28+
List<int> depths = new List<int>(3);
29+
Stack<TreeNodeCheck> stack = new Stack<TreeNodeCheck>();
30+
stack.Push(new TreeNodeCheck(root, 0));
31+
32+
while(stack.Any())
33+
{
34+
TreeNodeCheck node = stack.Pop();
35+
int depth = node.Depth;
36+
37+
// if it's leaf node add the depth to the list.
38+
if (node.TreeNode != null &&
39+
node.TreeNode.Left == null && node.TreeNode.Right == null)
40+
{
41+
if (!depths.Contains(depth))
42+
{
43+
depths.Add(depth);
44+
45+
// when adding the items to the list if the number of depth is more than 2 then the tree is not balanced.
46+
// otherwise if there are two items, then the difference should not be greater than 1.
47+
if (depths.Count > 2 ||
48+
(depths.Count == 2 && Math.Abs(depths[0] - depths[1]) > 1))
49+
{
50+
return false;
51+
}
52+
}
53+
}
54+
55+
if (node.TreeNode != null && node.TreeNode.Left != null)
56+
{
57+
stack.Push(new TreeNodeCheck( node.TreeNode.Left, depth + 1));
58+
}
59+
60+
if (node.TreeNode != null && node.TreeNode.Right != null)
61+
{
62+
stack.Push(new TreeNodeCheck(node.TreeNode.Right, depth + 1));
63+
}
64+
}
65+
66+
return true;
67+
}
68+
69+
[TestMethod]
70+
public void TestBinaryTreeChecker()
71+
{
72+
73+
}
74+
}
75+
}

Algorithm/DynamicProgramming/Alogrithms.Problem.DynamicProgramming.csproj renamed to Algorithm/DynamicProgramming/Algorithms.Problem.DynamicProgramming.csproj

File renamed without changes.

‎Algorithm/InterviewCake/PlayGround.cs‎

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -18,21 +18,22 @@ public ISet<string> GetPermutations(string inputString)
1818
return new HashSet<string>(inputString.Select(c => new string(c, 1)));
1919
}
2020

21-
var allCharsExceptLast = inputString.Substring(0, inputString.Length - 1);
21+
string allCharsExceptLast = inputString.Substring(0, inputString.Length - 1);
2222
char lastChar = inputString[inputString.Length - 1];
2323

2424
// Recursive call: get all possible permutations for all chars except last
25-
var permutationsOfAllCharsExceptLast = GetPermutations(allCharsExceptLast);
25+
ISet<string> permutationsOfAllCharsExceptLast = this.GetPermutations(allCharsExceptLast);
2626

2727
// Put the last char in all possible positions for each of the above permutations
2828
var permutations = new HashSet<string>();
29-
foreach (var permutationOfAllCharsExceptLast in permutationsOfAllCharsExceptLast)
29+
foreach (string permutationOfAllCharsExceptLast in permutationsOfAllCharsExceptLast)
3030
{
3131
for (int position = 0; position <= allCharsExceptLast.Length; position++)
3232
{
33-
var permutation = permutationOfAllCharsExceptLast.Substring(0, position)
33+
string permutation = permutationOfAllCharsExceptLast.Substring(0, position)
3434
+ lastChar
3535
+ permutationOfAllCharsExceptLast.Substring(position);
36+
3637
permutations.Add(permutation);
3738
}
3839
}
@@ -43,7 +44,7 @@ public ISet<string> GetPermutations(string inputString)
4344
[TestMethod]
4445
public void TestPermutations()
4546
{
46-
GetPermutations("cats");
47+
this.GetPermutations("cats");
4748
}
4849
}
49-
}
50+
}

‎Algorithm/Trees/Algorithms.Problem.BinarySearchTree.csproj‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@
4848
<Compile Include="InOrderSuccessor.cs" />
4949
<Compile Include="LowestCommonAncestor.cs" />
5050
<Compile Include="Properties\AssemblyInfo.cs" />
51+
<Compile Include="SecondLargestNode.cs" />
5152
</ItemGroup>
5253
<ItemGroup>
5354
<Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />

‎Algorithm/Trees/SecondLargestNode.cs‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
using DataStructures.Libraries.Trees;
2+
using Microsoft.VisualStudio.TestTools.UnitTesting;
3+
using System;
4+
using System.Collections.Generic;
5+
using System.Linq;
6+
using System.Text;
7+
using System.Threading.Tasks;
8+
9+
namespace Algorithms.Problem.Trees
10+
{
11+
[TestClass]
12+
public class SecondLargestNode
13+
{
14+
public BinaryTreeNode FindSecondLargestNode(BinaryTreeNode root)
15+
{
16+
return null;
17+
}
18+
19+
public double FindRightMostNode(BinaryTreeNode currentNode)
20+
{
21+
if (currentNode.Right != null)
22+
{
23+
return this.FindRightMostNode(currentNode.Right);
24+
}
25+
26+
return currentNode.Value;
27+
}
28+
29+
[TestMethod]
30+
public void TestSecondLargetsNode()
31+
{
32+
BinaryTreeNode root = new BinaryTreeNode(5);
33+
root.Left = new BinaryTreeNode(3);
34+
root.Right = new BinaryTreeNode(8);
35+
36+
root.Left.Left = new BinaryTreeNode(1);
37+
root.Left.Right = new BinaryTreeNode(4);
38+
39+
root.Right.Left = new BinaryTreeNode(7);
40+
root.Right.Right = new BinaryTreeNode(9);
41+
root.Right.Right.Right = new BinaryTreeNode(12);
42+
43+
double largest = this.FindRightMostNode(root);
44+
}
45+
}
46+
}

‎Algorithm/Tries/Algorithms.Problem.Tries.csproj‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
<?xml version="1.0" encoding="utf-8"?>
2+
<Project ToolsVersion="14.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3+
<Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
4+
<PropertyGroup>
5+
<Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
6+
<Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
7+
<ProjectGuid>{DE01538C-E927-41B7-AD86-8A4AEBECFAEE}</ProjectGuid>
8+
<OutputType>Library</OutputType>
9+
<AppDesignerFolder>Properties</AppDesignerFolder>
10+
<RootNamespace>Algorithms.Problem.Tries</RootNamespace>
11+
<AssemblyName>Algorithms.Problem.Tries</AssemblyName>
12+
<TargetFrameworkVersion>v4.5.2</TargetFrameworkVersion>
13+
<FileAlignment>512</FileAlignment>
14+
</PropertyGroup>
15+
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
16+
<DebugSymbols>true</DebugSymbols>
17+
<DebugType>full</DebugType>
18+
<Optimize>false</Optimize>
19+
<OutputPath>bin\Debug\</OutputPath>
20+
<DefineConstants>DEBUG;TRACE</DefineConstants>
21+
<ErrorReport>prompt</ErrorReport>
22+
<WarningLevel>4</WarningLevel>
23+
</PropertyGroup>
24+
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
25+
<DebugType>pdbonly</DebugType>
26+
<Optimize>true</Optimize>
27+
<OutputPath>bin\Release\</OutputPath>
28+
<DefineConstants>TRACE</DefineConstants>
29+
<ErrorReport>prompt</ErrorReport>
30+
<WarningLevel>4</WarningLevel>
31+
</PropertyGroup>
32+
<ItemGroup>
33+
<Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL" />
34+
<Reference Include="System" />
35+
<Reference Include="System.Core" />
36+
<Reference Include="System.Xml.Linq" />
37+
<Reference Include="System.Data.DataSetExtensions" />
38+
<Reference Include="Microsoft.CSharp" />
39+
<Reference Include="System.Data" />
40+
<Reference Include="System.Net.Http" />
41+
<Reference Include="System.Xml" />
42+
</ItemGroup>
43+
<ItemGroup>
44+
<Compile Include="AutoComplete.cs" />
45+
<Compile Include="PrintValidWordsInArray.cs" />
46+
<Compile Include="WordBreak.cs" />
47+
<Compile Include="TrieOperation.cs" />
48+
<Compile Include="Properties\AssemblyInfo.cs" />
49+
</ItemGroup>
50+
<ItemGroup>
51+
<Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
52+
</ItemGroup>
53+
<Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
54+
<!-- To modify your build process, add your task inside one of the targets below and uncomment it.
55+
Other similar extension points exist, see Microsoft.Common.targets.
56+
<Target Name="BeforeBuild">
57+
</Target>
58+
<Target Name="AfterBuild">
59+
</Target>
60+
-->
61+
</Project>

0 commit comments

Comments
 (0)