shrimpy
BAN USERO (n* n)
define pattern = "w1, w2, w3";
string smallestStr = null;
for word in Document
{
if word is w1
{
string str = FindPatternString(Document, currentPosiiton);
if(smallestStr is null or str.Length < smallestStr.Length)
{
smallestStr = str;
}
}
}
string FindPatternString(doc, pos)
{
string left = FindString(doc, 0, pos);
string right = FindString(doc. pos, doc.length -1);
if(left == null && right == null)
return null;
else if (left == null)
return right;
else if (right == null)
return left;
else
return left.length > right.length ? right : left;
}
string FindString(doc, from, to)
{
HashtableFromPattern<Word, Count> table = {<w1, 1>, <w2, 1>, <w3, 1>};
bool isFromSmaller = (to > from);
while(from != to) {
if(table.Count ==0){break;}
if(table.contains(doc[from])
{
table[from]--;
if(table[from] ==0)
table.remove(doc[from]);
}
if(isFromSmaller )
from++;
else
from--;
}
if(table.count ==0)
return doc.substring(from, to);
else
return null;
}
two pointer and one counter
1) one pointer keep moving till the end, everyone move, counter will increase one
2) when counter is >= Nth (e.g 5), the second pointer will starting pointing from head, since then, every since first pointer move, second pointer will also move
3) when first move till the end of list, return second pointer
using System;
namespace ConsoleApplication1
{
class NTHElementFromTailFromList
{
static void Main(string[] args)
{
Node node = new Node
{
value = "1",
next = new Node
{
value = "2",
next = new Node
{
value = "3",
next = new Node
{
value = "4",
next = new Node
{
value = "5",
next = new Node
{
value = "6",
next = new Node
{
value = "7",
next = null
}
}
}
}
}
}
};
Node nTh = FindNthElementTail(node, 2);
Console.WriteLine(nTh);
}
static Node FindNthElementTail(Node n, int nth)
{
Node nThElement = null;
Node head = n;
int count = 0;
while (n != null)
{
count++;
if (count >= nth)
{
if (nThElement == null)
{
nThElement = head;
}
else
{
nThElement = nThElement.next;
}
}
n = n.next;
}
return nThElement;
}
}
class Node
{
public Node next { get; set; }
public string value { get; set; }
public override string ToString()
{
return this.value;
}
}
}
O(m+n)
static void Main(string[] args)
{
int[] array1 = { 1, 2, 3, 4, 5, 5, 6, 7 };
int[] array2 = { 5, 5, 6, 7, 8, 9 };
var result = FindCommonSet(array1, array2);
foreach (var item in result)
{
Console.Write("{0} ", item);
}
Console.WriteLine();
}
static HashSet<int> FindCommonSet(int[] array1, int[] array2)
{
int array1Index = 0;
int array2Index = 0;
HashSet<int> result = new HashSet<int>();
while (array1Index < array1.Length && array2Index < array2.Length)
{
if (array1[array1Index] > array2[array2Index])
{
array2Index++;
}
else if (array1[array1Index] < array2[array2Index])
{
array1Index++;
}
else
{
result.Add(array1[array1Index]);
array1Index++;
array2Index++;
}
}
return result;
}
two binary search
1) left edge : array[pos] == target && array[pos -1] < target
2) right edge:array[pos] == target && array[pos -1] > target
static void Main(string[] args)
{
int[] array = { 1, 2, 3, 3, 3, 3, 3, 4, 5, 6 };
int target = 3;
Console.WriteLine(FindEdge(array, 0, array.Length - 1, target, true));
Console.WriteLine(FindEdge(array, 0, array.Length - 1, target, false));
}
static int FindEdge(int[] array, int from, int to, int target, bool isLowerEdge)
{
int pos = from + (to - from) / 2;
if (pos == from && array[pos] >= target)
{
return -1;
}
if (pos == to - 1 && array[to] <= target)
{
return -1;
}
if (array[pos] == target && ((isLowerEdge && array[pos - 1] < target) || (!isLowerEdge && array[pos + 1] > target)))
{
return isLowerEdge ? pos - 1 : pos + 1;
}
else
{
if (array[pos] < target)
{
return FindEdge(array, pos + 1, to, target, isLowerEdge);
}
else if (array[pos] == target)
{
return Math.Max(FindEdge(array, from, pos, target, isLowerEdge), FindEdge(array, pos + 1, to, target, isLowerEdge));
}
else
{
return FindEdge(array, from, pos, target, isLowerEdge);
}
}
}
Repgeraldgloria02, Android test engineer at Achieve Internet
I am a personal trainer. I design programs and provide nutritional advice and coaching. I wanted to share my knowledge ...
Rephamishleeh, Blockchain Developer at ASAPInfosystemsPvtLtd
Property custodian with a reputed organization and help in keeping accurate check over the supplies and inventory of materials and ...
why not toString and then concat two string?
- shrimpy January 04, 2014