Skip to content

Commit cc5b0c4

Browse files
paramagparamag
paramag
authored and
paramag
committed
Data structures project restore and algorithm problems.
1 parent 2a316f7 commit cc5b0c4

33 files changed

Lines changed: 1267 additions & 25 deletions

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

23.5 KB
Binary file not shown.

‎Algorithm/Algorithms.sln‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -7,14 +7,14 @@ Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "DataStructures.Dependencies
77
EndProject
88
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.BinarySearchTree", "Trees\Algorithms.Problem.BinarySearchTree.csproj", "{4E1F8D95-0BD5-4CA2-A116-56005544A96B}"
99
EndProject
10-
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "DataStructures.Libraries.Trees", "..\DataStructures\Trees\DataStructures.Libraries.Trees.csproj", "{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}"
11-
EndProject
1210
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.BinaryTree", "BinaryTree\Algorithms.Problem.BinaryTree.csproj", "{4A8C3BE7-A268-451A-9B8F-234ED3789866}"
1311
EndProject
1412
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.Arrays", "Arrays\Algorithms.Problem.Arrays.csproj", "{AC223693-B652-483D-A17B-A7A3C2E7BBA6}"
1513
EndProject
1614
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Algorithms.Problem.Strings", "Strings\Algorithms.Problem.Strings.csproj", "{EF581F2B-BBBC-48E2-A6A6-A0E6077A3812}"
1715
EndProject
16+
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "DataStructures.Libraries.Trees", "..\DataStructures\Trees\DataStructures.Libraries.Trees.csproj", "{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}"
17+
EndProject
1818
Global
1919
GlobalSection(SolutionConfigurationPlatforms) = preSolution
2020
Debug|Any CPU = Debug|Any CPU
@@ -25,10 +25,6 @@ Global
2525
{4E1F8D95-0BD5-4CA2-A116-56005544A96B}.Debug|Any CPU.Build.0 = Debug|Any CPU
2626
{4E1F8D95-0BD5-4CA2-A116-56005544A96B}.Release|Any CPU.ActiveCfg = Release|Any CPU
2727
{4E1F8D95-0BD5-4CA2-A116-56005544A96B}.Release|Any CPU.Build.0 = Release|Any CPU
28-
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
29-
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Debug|Any CPU.Build.0 = Debug|Any CPU
30-
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Release|Any CPU.ActiveCfg = Release|Any CPU
31-
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Release|Any CPU.Build.0 = Release|Any CPU
3228
{4A8C3BE7-A268-451A-9B8F-234ED3789866}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
3329
{4A8C3BE7-A268-451A-9B8F-234ED3789866}.Debug|Any CPU.Build.0 = Debug|Any CPU
3430
{4A8C3BE7-A268-451A-9B8F-234ED3789866}.Release|Any CPU.ActiveCfg = Release|Any CPU
@@ -41,6 +37,10 @@ Global
4137
{EF581F2B-BBBC-48E2-A6A6-A0E6077A3812}.Debug|Any CPU.Build.0 = Debug|Any CPU
4238
{EF581F2B-BBBC-48E2-A6A6-A0E6077A3812}.Release|Any CPU.ActiveCfg = Release|Any CPU
4339
{EF581F2B-BBBC-48E2-A6A6-A0E6077A3812}.Release|Any CPU.Build.0 = Release|Any CPU
40+
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
41+
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Debug|Any CPU.Build.0 = Debug|Any CPU
42+
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Release|Any CPU.ActiveCfg = Release|Any CPU
43+
{845E0CA8-AC51-4BAE-95D7-60680CB4A44B}.Release|Any CPU.Build.0 = Release|Any CPU
4444
EndGlobalSection
4545
GlobalSection(SolutionProperties) = preSolution
4646
HideSolutionNode = FALSE

‎Algorithm/Arrays/Algorithms.Problem.Arrays.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="MergeSets.cs" />
4748
<Compile Include="FindInMatrix.cs" />
4849
<Compile Include="KthLargestElement.cs" />
4950
<Compile Include="RotateArray.cs" />

‎Algorithm/Arrays/KthLargestElement.cs‎

Lines changed: 10 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -22,25 +22,23 @@ public int FindKthLargestElementInArray(int[] array, int firstIndex, int lastInd
2222
{
2323
return this.FindKthLargestElementInArray(array, pivot + 1, array.Length - 1, kValue);
2424
}
25-
else
26-
{
27-
return array[pivot];
28-
}
25+
26+
return array[pivot];
2927
}
3028

31-
private int FindPivotValue(int firstIndex, int indexLast, int[] array )
29+
private int FindPivotValue(int firstIndex, int lastIndex, int[] array )
3230
{
3331
// alternatively, we can take even the mid point value
34-
int partitionIndex = new Random().Next(firstIndex, indexLast);
32+
int partitionIndex = new Random().Next(firstIndex, lastIndex);
3533

3634
// choose the partition value and swap with the last index value.
3735
int temp = array[partitionIndex];
38-
array[partitionIndex] = array[indexLast];
39-
array[indexLast] = temp;
36+
array[partitionIndex] = array[lastIndex];
37+
array[lastIndex] = temp;
4038

41-
for(int i= firstIndex; i< indexLast; i++)
39+
for(int i= firstIndex; i< lastIndex; i++)
4240
{
43-
if(array[i] > array[indexLast])
41+
if(array[i] > array[lastIndex])
4442
{
4543
int temp1 = array[i];
4644
array[i] = array[firstIndex];
@@ -52,8 +50,8 @@ private int FindPivotValue(int firstIndex, int indexLast, int[] array )
5250

5351
// Swap the parition back to originial place
5452
int temp2 = array[firstIndex];
55-
array[firstIndex] = array[indexLast];
56-
array[indexLast] = temp2;
53+
array[firstIndex] = array[lastIndex];
54+
array[lastIndex] = temp2;
5755

5856
return firstIndex;
5957
}

‎Algorithm/Arrays/MergeSets.cs‎

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
using Microsoft.VisualStudio.TestTools.UnitTesting;
2+
using System;
3+
using System.Collections.Generic;
4+
using System.Linq;
5+
using System.Text;
6+
using System.Threading.Tasks;
7+
8+
namespace Algorithms.Problem.Arrays
9+
{
10+
public class Set
11+
{
12+
public int LowerBound { get; set; }
13+
14+
public int UpperBound { get; set; }
15+
16+
public Set(int lowerBound, int upperBound)
17+
{
18+
this.LowerBound = lowerBound;
19+
this.UpperBound = upperBound;
20+
}
21+
}
22+
23+
[TestClass]
24+
public class MergeSets
25+
{
26+
/// <summary>
27+
/// Assumption : The sets are in sorted list.
28+
/// If set1 = {{1,2},{2,3},{6,7},{7,8}}
29+
/// If set2 = {{3,4}, {8,9}, {11,12}}
30+
/// output: set1 = {{1,4}, {6,9}}
31+
/// output: set2 = {{11,12}}
32+
/// </summary>
33+
/// <param name="setList1"></param>
34+
/// <param name="setList2"></param>
35+
/// <returns>Returns the merged set for the given two lists of sets.</returns>
36+
public List<Set> PerformMergeSet(List<Set> setList1, List<Set> setList2)
37+
{
38+
List<Set> output = new List<Set>();
39+
40+
int setList1Counter = 0;
41+
int setList2Counter = 0;
42+
43+
while (setList1Counter <= setList1.Count -1 &&
44+
setList2Counter <= setList2.Count - 1)
45+
{
46+
while(setList1Counter <= setList1.Count - 1 &&
47+
setList2Counter <= setList2.Count - 1 &&
48+
setList1[setList1Counter].UpperBound <= setList2[setList2Counter].LowerBound)
49+
{
50+
this.PerformMergeSetHelper(output, setList1[setList1Counter]);
51+
setList1Counter++;
52+
}
53+
54+
while (setList2Counter <= setList2.Count - 1 &&
55+
setList1Counter <= setList1.Count - 1 &&
56+
setList2[setList2Counter].UpperBound <= setList1[setList1Counter].LowerBound)
57+
{
58+
this.PerformMergeSetHelper(output, setList2[setList2Counter]);
59+
setList2Counter++;
60+
}
61+
}
62+
63+
// remaining items of set1
64+
while (setList1Counter <= setList1.Count - 1)
65+
{
66+
this.PerformMergeSetHelper(output, setList1[setList1Counter]);
67+
setList1Counter++;
68+
}
69+
70+
// remaining items of set2
71+
while (setList2Counter <= setList2.Count - 1)
72+
{
73+
this.PerformMergeSetHelper(output, setList2[setList2Counter]);
74+
setList2Counter++;
75+
}
76+
77+
return output;
78+
}
79+
80+
public void PerformMergeSetHelper(List<Set> output, Set set)
81+
{
82+
Set set1 = output.LastOrDefault();
83+
84+
if(set1 != null && set1.UpperBound == set.LowerBound)
85+
{
86+
set1.UpperBound = set.UpperBound;
87+
}
88+
else
89+
{
90+
Set newSet = new Set(set.LowerBound, set.UpperBound);
91+
output.Add(newSet);
92+
}
93+
}
94+
95+
[TestMethod]
96+
public void TestMergeSets()
97+
{
98+
List<Set> set1List = new List<Set>{ new Set(1, 2), new Set(2, 3), new Set(6, 7), new Set(7, 8), new Set(9,10) };
99+
List<Set> set2List = new List<Set> { new Set(3, 4), new Set(8, 9), new Set(11, 12) };
100+
101+
List<Set> actualSetList = this.PerformMergeSet(set1List, set2List);
102+
103+
List<Set> expectedSetList = new List<Set> { new Set(1, 4), new Set(6, 10), new Set(11, 12) };
104+
105+
Assert.AreEqual(expectedSetList.Count, actualSetList.Count);
106+
107+
foreach (Set expectedSet in expectedSetList)
108+
{
109+
Assert.IsTrue(actualSetList.Where((actual) =>
110+
actual.LowerBound == expectedSet.LowerBound
111+
&& actual.UpperBound == expectedSet.UpperBound).Any());
112+
}
113+
}
114+
}
115+
}

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -50,15 +50,15 @@
5050
<Compile Include="PathRootToLeaf.cs" />
5151
<Compile Include="Properties\AssemblyInfo.cs" />
5252
</ItemGroup>
53+
<ItemGroup>
54+
<Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
55+
</ItemGroup>
5356
<ItemGroup>
5457
<ProjectReference Include="..\..\DataStructures\Trees\DataStructures.Libraries.Trees.csproj">
5558
<Project>{845e0ca8-ac51-4bae-95d7-60680cb4a44b}</Project>
5659
<Name>DataStructures.Libraries.Trees</Name>
5760
</ProjectReference>
5861
</ItemGroup>
59-
<ItemGroup>
60-
<Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
61-
</ItemGroup>
6262
<Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
6363
<!-- To modify your build process, add your task inside one of the targets below and uncomment it.
6464
Other similar extension points exist, see Microsoft.Common.targets.

‎Algorithm/Strings/Palindromes.cs‎

Lines changed: 44 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,49 @@ public Palindrome()
1414
{
1515
}
1616

17+
public int FindLongestPalindromeTrivial(string palindromeString)
18+
{
19+
// odd length.
20+
int longPalindrome = 1;
21+
int palindromeLength = 0;
22+
23+
int start = 0;
24+
int end = 0;
25+
26+
for(int i=0; i< palindromeString.Length - 1; i++)
27+
{
28+
start = i;
29+
end = i + 1;
30+
31+
while (start > 0 && end <= palindromeString.Length - 1 &&
32+
palindromeString[start] == palindromeString[end])
33+
{
34+
start--;
35+
end++;
36+
37+
palindromeLength += 2;
38+
}
39+
40+
longPalindrome = Math.Max(longPalindrome, palindromeLength);
41+
42+
start = i - 1;
43+
end = i + 1;
44+
45+
palindromeLength = 1;
46+
while (start > 0 && end <= palindromeString.Length - 1 &&
47+
palindromeString[start] == palindromeString[end])
48+
{
49+
start--;
50+
end++;
51+
52+
palindromeLength += 2;
53+
}
54+
55+
longPalindrome = Math.Max(longPalindrome, palindromeLength);
56+
}
57+
58+
return longPalindrome;
59+
}
1760

1861
public int FindMaximumPalindromeString(string palindromeString)
1962
{
@@ -91,7 +134,7 @@ public void TestLongestPalindromeString()
91134
{
92135
string palindromeString = "abbababba";
93136

94-
int longestPalindrome = this.longestPalindromeSubstringEasy(palindromeString.ToCharArray());
137+
int longestPalindrome = this.FindMaximumPalindromeString(palindromeString);
95138

96139
Assert.AreEqual(longestPalindrome, 9);
97140
}

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -48,15 +48,15 @@
4848
<Compile Include="LowestCommonAncestor.cs" />
4949
<Compile Include="Properties\AssemblyInfo.cs" />
5050
</ItemGroup>
51+
<ItemGroup>
52+
<Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
53+
</ItemGroup>
5154
<ItemGroup>
5255
<ProjectReference Include="..\..\DataStructures\Trees\DataStructures.Libraries.Trees.csproj">
5356
<Project>{845e0ca8-ac51-4bae-95d7-60680cb4a44b}</Project>
5457
<Name>DataStructures.Libraries.Trees</Name>
5558
</ProjectReference>
5659
</ItemGroup>
57-
<ItemGroup>
58-
<Service Include="{82A7F48D-3B50-4B1E-B82E-3ADA8210C358}" />
59-
</ItemGroup>
6060
<Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
6161
<!-- To modify your build process, add your task inside one of the targets below and uncomment it.
6262
Other similar extension points exist, see Microsoft.Common.targets.

‎DataStructures/.vs/Algorithm/v14/.suo‎

32 KB
Binary file not shown.

‎DataStructures/.vs/DataStructures/v14/.suo‎

94 KB
Binary file not shown.

0 commit comments

Comments
 (0)