DEQUE
Double-ended queue (or Deque pronounced as “Deck”)
is an data structure where items can be added to or removed from any end. It is
implemented as Linked List with head and tail. Deque is used for maintaining a
LRU cache.
Tuesday, October 4, 2016
Data structures - Binary Search Trees (BST)
BINARY SEARCH TREES (BSTs)
Useful for searching, inserting, deleting in
O(logn) time.
BST property – ALL nodes (not just immediate) left
of a particular intermediate node (x) will be smaller than x.
ALL nodes (not just immediate) right of a
particular intermediate node (x) will be greater than x.
Sorted Arrays (Binary Search) are good for searching
but bad for insertion (requires shifting of elements). Linked Lists are good
for insertions but searching is bad/slow. BST offers best of both worlds where
searching as well as addition/deletion happens in O(logn) time. It also solves
the next greater (successor) and next smaller (predecessor) problem.
Another use case for BST – Designing a Runway
management system. You need to manage landing times of an incoming aircraft.
There is a pool of times (numbers). You can only add (or allow the aircraft) the
incoming time/number if there is NO existing numbers within ‘k’ limit. These
kind of problems require insertion/deletion/searching. Even a dictionary will
not solve this problem because of the ‘k’ margin. Dictionaries are good of
searching ONLY A PARTICULAR VALUE. (NOT CHECK WHETHER IT LIES IN A RANGE).
Taken from - https://www.youtube.com/watch?v=9Jry5-82I68
Successor
(or next big) – Successor of x can be found be looking right. If the right of x
(lets call it r) does not have any left child i.e. ‘r’ might have a long list
of right children but if it doesn’t have a left child – then r is the successor
of x.
Otherwise – left of left of left of left of left………
till NULL IS THE successor x. (LAST node along left direction).
If there is nothing on right of ‘x’…go parent of
parent of parent of…… UNTIL YOU GET A FORWARD SLASH.(/)
Predecessor
(or next small) – SIMILAR approach as above. Start by looking left. If it has a
right child. Go right of right of right of… till NULL.
If there is nothing on left, go parent of parent
of parent of….UNTIL YOU GET A BACKWARD SLASH (\).
INORDER TREE WALK – x.left,x,x.right
PREORDER TREE WALK – x,x.left,x.right
POSTORDER TREE WALK – x.left,x.right,x
PRINTING LEVEL BY LEVEL – can be done using a
Queue.
Diameter –
max(u,v) {{{ where u and v are leaf nodes }}}
Formula – max( (lheight+rheight+1) ,
(ldiameter + rdiameter) )
DELETION OF
NODE IN A BST– (MOST COMPLEX)
There are 3 cases. The third case has 2 subcases.
Case 1 – The node being deleted is a leaf node.
(easy)
Case 2 – The node being deleted has only 1 child
(i.e either left child or right child). This needs JUST TRANSPLANT (no pointer update).
Case 3 -
The node being deleted has BOTH left and right children. In this case, pictorially, we replace the node with
its successor (defined
above). Pictorially that is it. Algorithmically it is tough.
Case 3 has 2 sub-cases.
a)
The right child itself IS THE SUCCESSOR.
b)
The SUCCESSOR is different from the right child
and is SOMEWHERE IN THE LEFT (left of
left of left…. TILL NULL). This will happen IF THE RIGHT CHILD HAS A LEFT
CHILD.
For case a – We need a TRANSPLANT and updating pointers of
the node being replaced.
For case b – We need to do couple things –
§
TRANSPLANT SUCCESSOR WITH SUCCESSOR.RIGHT
§
get the SUCCESSOR to the TOP
§
Run steps for case a
NOTE
– TRANSPLANTING TAKES CARE OF UPDATING PARENT POINTERS BUT YOU NEED TO TAKE
CARE OF LEFT/RIGHT CHILD POINTERS YOURSELF.
Case 3a and 3b can be pictorially represented by –
Algorithms - Quicksort
QUICKSORT
Excellent explanation at https://www.youtube.com/watch?v=3DV8GO9g7B4
The fundamentals of Quicksort lies in finding the PIVOT
(done using the partition method). At the end of partition call, the “pivot”
number is PUT IN THE CORRECT LOCATION IN THE ARRAY. i.e To the left of pivot
all elements are smaller or equal to it and to the right of the pivot, all
elements are bigger than it. The same is repeated on left of the pivot and
right of the pivot recursively.
Best case – O(nlogn)
Worst case – O(n2). This can be mitigated by doing a randomization of the array before the operation. (so that its not sorted by chance).
UNLIKE
MERGESORT WHERE BOTH BEST AND WORST CASE IS O(nlogn)
Python implementation –
def partition(A,p,r):
x = A[r]
i = p-1
j = p
while
(j<=r-1):
if A[j] <= x:
i=i+1
A[i],A[j] = A[j],A[i]
j=j+1
A[i+1],A[r] = A[r],A[i+1]
return
i+1
def quicksort(A,p,r):
if
(p<r):
q =
partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
inputlist =
[343,454,232,56565,3432,1,444,454,232,233,4,5,78,]
quicksort(inputlist,0,len(inputlist) - 1)
print inputlist
Practical application of Quicksort -
1)
Find the kth largest element in an array (known
as QUICKSELECT). Quickselect is LINEAR on average.
2)
Quicksort (randomized) is 39% faster than
Mergesort and doesn’t use any auxiliary extra space.
Program
for QuickSelect (find kth largest value)
def partition(A, p, r):
j = p
i = j -
1;
x = A[r]
while (j
<= r - 1):
if
(A[j] <= x):
i += 1
A[i], A[j] = A[j], A[i]
j +=
1
A[i +
1], A[r] = A[r], A[i + 1]
return i
+ 1;
def quickselect(A, p, r, k, output): #to find kth
largest number using quicksort like technique.
if (p
<= r):
q =
partition(A, p, r)
if
(q == k -1):
output = A[q]
elif (k - 1 < q):
output = quickselect(A, p, q - 1, k, output)
else:
output = quickselect(A, q + 1, r, k, output)
return
output
A = [12, 4, 45, 2, 1, 88, 90, 15, 18]
kthvalue = quickselect(A, 0, len(A) - 1, 3,
"Not found") #find the kth
largest value
print(kthvalue)
Tool to create Parameters.xml and SetParameters.xml for MS Web deploy
Tool to create Parameters.xml and SetParameters.xml for MS Web deploy
While automating builds and deployments, there is a need to create two xml files used by MS web deploy. Using the below program in a console application, can produce the desired files in output. It needs a sample web.config for its input. Both of them are configurable items.
--------------------------------------------program.cs----------------------------------------------
using System;
using System.Collections.Generic;
using System.Configuration;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Xml.Linq;
namespace WebDeployParamsFileCreation
{
class Program
{
static void Main(string[] args)
{
string paramFile = String.Concat(ConfigurationManager.AppSettings["WebDeployParamFileLocation"], "Parameters.xml");
string setParamFile = String.Concat(ConfigurationManager.AppSettings["WebDeployParamFileLocation"], "SetParameters.xml");
string paramFileContents = GetParamFileContents().Item1;
string setParamFileContents = GetParamFileContents().Item2;
File.WriteAllText(paramFile, paramFileContents);
File.WriteAllText(setParamFile, setParamFileContents);
}
private static Tuple<string, string> GetParamFileContents()
{
StringBuilder sbParamFileContents = new StringBuilder();
sbParamFileContents.AppendLine("<?xml version=\"1.0\" encoding=\"utf-8\" ?>");
sbParamFileContents.AppendLine("<parameters>");
StringBuilder sbSetParamFileContents = new StringBuilder();
sbSetParamFileContents.AppendLine("<?xml version=\"1.0\" encoding=\"utf-8\" ?>");
sbSetParamFileContents.AppendLine("<parameters>");
var webconfig = XDocument.Load(ConfigurationManager.AppSettings["WebConfigFileLocation"]);
#region AppSettings
sbParamFileContents.AppendLine("<!--AppSettings START-->");
sbSetParamFileContents.AppendLine("<!--AppSettings START-->");
var appSettings = from c in webconfig.Root.Descendants("appSettings").Descendants()
select c;
foreach (var item in appSettings)
{
var keyName = item.Attribute("key").Value;
var val = item.Attribute("value").Value;
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"AppSettings - " + keyName + "\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/appSettings/add[@key='" + keyName + "']/@value\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
sbSetParamFileContents.AppendLine("<setParameter name=\"AppSettings - " + keyName + "\" value=\"" + val + " \"/>");
}
sbParamFileContents.AppendLine("<!--AppSettings END-->");
sbSetParamFileContents.AppendLine("<!--AppSettings END-->");
#endregion
sbParamFileContents.AppendLine("");
sbSetParamFileContents.AppendLine("");
#region Client EndPoints
sbParamFileContents.AppendLine("<!--Client EndPoint START-->");
sbSetParamFileContents.AppendLine("<!--Client EndPoint START-->");
var clientEndpoints = from c in webconfig.Root.Descendants("system.serviceModel").Descendants("client").Descendants()
select c;
foreach (var item in clientEndpoints)
{
var endpointName = item.Attribute("name").Value;
var address = item.Attribute("address").Value;
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"Client Endpoint - " + endpointName + "\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/system.serviceModel/client/endpoint[@name='" + endpointName + "']/@address\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
sbSetParamFileContents.AppendLine("<setParameter name=\"Client Endpoint - " + endpointName + "\" value=\"" + address + "\" />");
}
sbParamFileContents.AppendLine("<!--Client EndPoint END-->");
sbSetParamFileContents.AppendLine("<!--Client EndPoint END-->");
#endregion
sbParamFileContents.AppendLine("");
sbSetParamFileContents.AppendLine("");
#region Log4Net
sbParamFileContents.AppendLine("<!--Log4net START-->");
sbSetParamFileContents.AppendLine("<!--Log4net START-->");
var log4netAppender = from c in webconfig.Root.Descendants("log4net").Descendants()
where c.Name == "appender"
select c;
foreach (var item in log4netAppender)
{
var appenderType = item.Attribute("type").Value;
var appenderName = item.Attribute("name").Value;
if (appenderType == "log4net.Appender.RollingFileAppender")
{
//Parameters.xml
if (item.Descendants("file").Count() != 0) //two ways of representing the same thing in log4net.
{
sbParamFileContents.AppendLine("<parameter name=\"Log4net - " + appenderName + " - File Location\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/log4net/appender[@name='" + appenderName + "']/file/@value\" />");
sbParamFileContents.AppendLine("</parameter>");
}
else
{
sbParamFileContents.AppendLine("<parameter name=\"Log4net - " + appenderName + " - File Location\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/log4net/appender[@name='" + appenderName + "']/param[@name='File']/@value\" />");
sbParamFileContents.AppendLine("</parameter>");
}
//SetParameters.xml
string val = "";
if (item.Descendants("file").Count() != 0)
{
val = item.Descendants("file").First().Attribute("value").Value;
}
else
{
val = item.Descendants("param").Where(x => x.Attribute("name").Value == "File").First().Attribute("value").Value;
}
sbSetParamFileContents.AppendLine("<setParameter name=\"Log4net - " + appenderName + " - File Location\" value=\"" + val + "\" />");
}
else if (appenderType == "log4net.Appender.AdoNetAppender")
{
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"Log4net - " + appenderName + " - ConnectionString\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/log4net/appender[@name='" + appenderName + "']/connectionString/@value\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
var val = item.Descendants("connectionString").First().Attribute("value").Value;
sbSetParamFileContents.AppendLine("<setParameter name=\"Log4net - " + appenderName + " - ConnectionString\" value=\"" + val + "\" />");
}
else if (appenderType == "log4net.Appender.SmtpAppender")
{
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"Log4net - " + appenderName + " - MailTo\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/log4net/appender[@name='" + appenderName + "']/to/@value\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
var val1 = item.Descendants("to").First().Attribute("value").Value;
sbSetParamFileContents.AppendLine("<setParameter name=\"Log4net - " + appenderName + " - MailTo\" value=\"" + val1 + "\" />");
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"Log4net - " + appenderName + " - MailFrom\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/log4net/appender[@name='" + appenderName + "']/from/@value\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
var val2 = item.Descendants("from").First().Attribute("value").Value;
sbSetParamFileContents.AppendLine("<setParameter name=\"Log4net - " + appenderName + " - MailFrom\" value=\"" + val2 + "\" />");
}
else
{
throw new Exception("Code generation failed as there is no configuration for " + appenderType);
}
}
sbParamFileContents.AppendLine("<!--Log4net END-->");
sbSetParamFileContents.AppendLine("<!--Log4net END-->");
#endregion
sbParamFileContents.AppendLine("");
sbSetParamFileContents.AppendLine("");
#region EL Logging
sbParamFileContents.AppendLine("<!--EL Logging START-->");
sbSetParamFileContents.AppendLine("<!--EL Logging START-->");
var elLoggingListeners = from c in webconfig.Root.Descendants("loggingConfiguration").Elements()
where c.Name == "listeners"
select c;
elLoggingListeners = elLoggingListeners.Descendants();
foreach (var item in elLoggingListeners)
{
var listenerType = item.Attribute("type").Value;
var listenerName = item.Attribute("name").Value;
if (listenerType.Contains("Microsoft.Practices.EnterpriseLibrary.Logging.TraceListeners.RollingFlatFileTraceListener"))
{
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"EL - " + listenerName + " - File Location\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/loggingConfiguration/listeners[@add='" + listenerName + "']/@fileName\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
var val = item.Attribute("fileName").Value;
sbSetParamFileContents.AppendLine("<setParameter name=\"EL - " + listenerName + " - File Location\" value=\"" + val + "\" />");
}
else if (listenerType.Contains("Microsoft.Practices.EnterpriseLibrary.Logging.TraceListeners.EmailTraceListener"))
{
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"EL - " + listenerName + " - MailTo\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/loggingConfiguration/listeners[@add='" + listenerName + "']/@toAddress\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
var val = item.Attribute("toAddress").Value;
sbSetParamFileContents.AppendLine("<setParameter name=\"EL - " + listenerName + " - MailTo\" value=\"" + val + "\" />");
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"EL - " + listenerName + " - MailFrom\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/loggingConfiguration/listeners[@add='" + listenerName + "']/@fromAddress\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
var val2 = item.Attribute("fromAddress").Value;
sbSetParamFileContents.AppendLine("<setParameter name=\"EL - " + listenerName + " - MailFrom\" value=\"" + val2 + "\" />");
//Parameters.xml
sbParamFileContents.AppendLine("<parameter name=\"EL - " + listenerName + " - SubjectLineStarter\" description=\"\" defaultValue=\"\">");
sbParamFileContents.AppendLine("<parameterEntry kind=\"XmlFile\" scope=\"Web.config\" match=\"/configuration/loggingConfiguration/listeners[@add='" + listenerName + "']/@subjectLineStarter\" />");
sbParamFileContents.AppendLine("</parameter>");
//SetParameters.xml
var val3 = item.Attribute("subjectLineStarter").Value;
sbSetParamFileContents.AppendLine("<setParameter name=\"EL - " + listenerName + " - SubjectLineStarter\" value=\"" + val3 + "\" />");
}
else
{
throw new Exception("Code generation failed as there is no configuration for " + listenerType);
}
}
sbParamFileContents.AppendLine("<!--EL Logging START END-->");
sbSetParamFileContents.AppendLine("<!--EL Logging START END-->");
#endregion
sbParamFileContents.AppendLine("");
sbSetParamFileContents.AppendLine("");
#region ConnectionStrings-SetParameters Only
sbSetParamFileContents.AppendLine("<!--Connection String START-->");
var connectionStrings = from c in webconfig.Root.Descendants("connectionStrings").Descendants()
select c;
foreach (var item in connectionStrings)
{
var connectionStringName = item.Attribute("name").Value;
var connectionStringValue = item.Attribute("connectionString").Value;
connectionStringValue = connectionStringValue.Replace("\"", @""");
//SetParameters.xml
sbSetParamFileContents.AppendLine("<setParameter name=\"" + connectionStringName + "-Web.config Connection String\" value=\"" + connectionStringValue + " \"/>");
}
sbSetParamFileContents.AppendLine("<!--Connection String END-->");
#endregion
sbParamFileContents.AppendLine("</parameters>");
sbSetParamFileContents.AppendLine("</parameters>");
return new Tuple<string, string>(sbParamFileContents.ToString(), sbSetParamFileContents.ToString());
}
}
}
----------------------------------------------config file--------------------------------------------
<?xml version="1.0" encoding="utf-8" ?>
<configuration>
<startup>
<supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.5" />
</startup>
<appSettings>
<add key="WebDeployParamFileLocation" value="c:\\temp2\\"/>
<add key="WebConfigFileLocation" value="c:\\temp2\\web.config"/>
</appSettings>
</configuration>
----------------------------------------------------------------------------------------------------
Subscribe to:
Posts (Atom)