Rajesh Kumar
BAN USERyou can split target into int collection.
// Get All Digit in collection
public static List<int> AllDigit(int number)
{
List<int> allDigits = new List<int>();
int reminder = number;
while(reminder != 0)
{
allDigits.Add(reminder%10);
reminder=reminder/10;
}
return allDigits;
}
//Check path available or not
//startNode = find the first node from where you have to start.
public static bool checkPath(BNode startNode, List<int> targetNumber, int index)
{
if(index < 0)
return true;
if(startNode == null)
return false;
if(startNode.data == targetNumber[index])
{
bool left = checkPath(startNode.left, targetNumber, index-1);
bool right = checkPath(startNode.right, targetNumber, index-1);
return left || right;
}
else
return false;
}
int[,] m = new int[3,3]
FindMinimumPath(m, 0, 0, 3, 3)
public static int FindMinimumPath(int[,] m, int x, int y, int tx, int ty)
{
int path1 = int.MaxValue;
int path2 = int.MaxValue;
int path3 = int.MaxValue;
if(x+1 == tx && y+1 == ty)
return m[x,y];
if(x+1 < tx)
path1 = FindMinimumPath(m, x+1, y, tx, ty);
if(y+1 < ty)
path2 = FindMinimumPath(m,x,y+1, tx,ty);
if(x+1 < tx & y+1 < ty)
path3 = FindMinimumPath(m, x+1, y+1, tx, ty);
return m[x,y] + Math.Min(path1, Math.Min(path2, path3));
}
int[,] m = new m[3,3]
FindMinimumPath(m, 0, 0, 3, 3)
public static int FindMinimumPath(int[,] m, int x, int y, int tx, int ty)
{
int path1 = int.MaxValue;
int path2 = int.MaxValue;
int path3 = int.MaxValue;
if(x+1 == tx && y+1 == ty)
return m[x,y];
if(x+1 < tx)
path1 = FindMinimumPath(m, x+1, y, tx, ty);
if(y+1 < ty)
path2 = FindMinimumPath(m,x,y+1, tx,ty);
if(x+1 < tx & y+1 < ty)
path3 = FindMinimumPath(m, x+1, y+1, tx, ty);
return m[x,y] + Math.Min(path1, Math.Min(path2, path3));
}
you can solve this problem by recursion.
Question is : check for mirror image. Step for that
1) Go for BFS at each depth
2) Add Null node also at each depth
3) Check at each depth Data must be Palindrome.
If at each depth, data is palindrome than tree will be mirror image.
For me (C#) : Value of : Log(125)/Log(5) is coming as :
temp = 3.0000000000000004
and Ceiling value (4) not equal to temp.
your solution will not work for 125 (example): this number not perfect square but represent as 5 power 3.
my solution to check p power q presentation is (this solution checking any power is available. also trick to minimize the operation is i*i <= n):
static bool IsPowerPresented(int n)
{
if (n == 0)
throw new Exception("wrong input");
if (n == 1)
return true;
if (n == 2)
return true;
int temp = n;
for(int i=2; i*i <= n; i++)
{
temp = n;
while(temp > 1)
{
if (temp % i != 0)
break;
temp = temp / i;
}
if (temp == 1)
return true;
}
return false;
}
use hash function as define in RobinK. Use Quadent as 13 or any prime number to get better value:
private int Hash(string text)
{
int hashVal = 0;
for (int i = 0; i < patternLength; i++)
hashVal = (10 * hashVal + text[i]) % Quadent;
return hashVal % Quadent;
}
If string is tree, you have to travel the tree (each node once) and check length. if length equal than you will match first and last char. What extra complexity you are thinking.
- Rajesh Kumar December 12, 2014This problem will be divide in 3 sub problem.
1) find same length word in dictionary
2) First char must be equal
3) last char must be equal
If any dictionary word match with this condition than word NOT unique.
Complexcity: O(n) n= dictionary word list
You can write a Reverse function of link list on node (default is head). algo:
1) Count linklist (O(n))
2) ReverseNumber = Count - 5
3) Move to ReverseNumber and set pointer suppose P1 (O(n-5) ==> O(n))
4) pass P1.next to reverse function (O(5) because only 5 to reverse)
5) P1.Next = Return of reverse function
So: Complexity = O(n)
Code:
public SingleNode Reverse(SingleNode head)
{
if (head == null)
return head;
SingleNode curr = head;
SingleNode prev = null;
while(curr != null)
{
SingleNode next = curr.Next;
curr.Next = prev;
prev = curr;
curr = next;
}
return prev;
}
static void Main(string[] arg)
{
SingleLinkList list = new SingleLinkList();
list.AddNodeAtLast(1);
list.AddNodeAtLast(2);
list.AddNodeAtLast(3);
list.AddNodeAtLast(4);
list.AddNodeAtLast(5);
list.AddNodeAtLast(6);
list.AddNodeAtLast(7);
int count = list.Count;
int ReverseNumber = 5;
SingleNode reverseNode = new SingleNode(null);
if (count <= ReverseNumber)
{
//If count less than 5 then reverse at head
reverseNode = list.Reverse(list.Head);
}
else
{
int nodeToTravel = count - ReverseNumber;
SingleNode startNode = list.Head;
// Traverse to n-5 node
for (int i = 0; i < nodeToTravel; i++)
startNode = startNode.Next;
//Reverse last 5
reverseNode = list.Reverse(startNode.Next);
// link last 5 back to link list
startNode.Next = reverseNode;
// Print all link list data
list.Print(list.Head);
}
}
For low to high level, you have to implement 1 stack also. After dequeue from queue, don't print that node, just push that node in stack. When queue empty, start printing node from stack. This will print lower level first to top level.
- Rajesh Kumar December 07, 2014go for Breadth-first traversal of the tree and implement with Queue
- Rajesh Kumar December 07, 2014main point in this problem is:
1) sub array of equal number of 0 and 1. So the length of sub array is even. So, we discard any sub array of odd length.
2) if sub array have equal number of 0 and 1 then sum of all element is must be equal to LengthOfArray/2 .. because length is even and have equal number of 1 and 0.
If we split this problem is this 2 part and only checking subarray of even size having sum equal to ArraySize/2 ...
main point in this problem is:
1) sub array of equal number of 0 and 1. So the length of sub array is even. So, we discard any sub array of odd length.
2) if sub array have equal number of 0 and 1 then sum of all element is must be equal to LengthOfArray/2 .. because length is even and have equal number of 1 and 0.
If we split this problem is this 2 part and only checking subarray of even size having sum equal to ArraySize/2 ...
static List<ArrayList> GetAllArray(int[] intData)
{
List<ArrayList> AllArray = new List<ArrayList>();
//Create 20 Array in array collection
for (int i = 0; i < 20; i++)
AllArray.Add(new ArrayList());
//Read each data
for (int i = 0; i < intData.Length; i++ )
{
AllArray[i % 20].Add(intData[i]);
}
return AllArray;
}
In this solution provide O(n) solution
- Rajesh Kumar August 29, 2014you can find this by using rolling hash. Code in C#:
public void FindAnagram(string strText, string strPattern)
{
int patternL = strPattern.Length;
int textL = strText.Length;
int Quad = 13; // Take prime number for better result
int patternHash = HashFunction(strPattern, patternL, Quad,0);
int textHash = HashFunction(strText, patternL, Quad,0);
for (int i = 0; i < textL - patternLength + 1; i++)
{
//Check whether the exact matching pattern and text
textHash = HashFunction(strText, patternL, Quad, i);
if (patternHash == textHash && VerifyString(strText, i))
Console.WriteLine(i);
}
}
private int HashFunction(string text, int patternL, int Quad, int offset)
{
int hashVal = 0, sum =0;
for (int i = 0; i < patternL; i++)
sum = sum + text[offset + i];
hashVal = (10 * hashVal + sum) % Quad;
return hashVal;
}
private bool VerifyString(string text, int offset)
{
string sliceSort = SortString(text.Substring(offset, patternLength));
string patternSort = SortString(Pattern);
for (int i = 0; i < patternLength; i++)
{
if (patternSort[i] != sliceSort[i])
return false;
}
return true;
}
static string SortString(string s)
{
// Convert to char array, then sort and return
char[] a = s.ToCharArray();
Array.Sort(a);
return new string(a);
}
Check number is divided by 2 to given number Quare Root. This is the minimum number of division to get prime number. In code, you will use square as below
static bool CheckPrime(int number)
{
for (int i = 2; i*i <= number; i++)
if (number % i == 0)
return false;
return true;
}
In this situation, you will develop your own encryption key and use that key for decryption. I have develop a simple encryption key. So, at time of encryption, you will generate output and key and use that output and key, you simply decrypt the data. code may be like below:
static Dictionary<int, string> digit = new Dictionary<int, string>() { { 1, "A" }, { 2, "B" }, { 3, "C" }, { 4, "D" }, { 5, "E" }, { 6, "F" }, { 7, "G" }, { 8, "H" }, { 9, "I" }, { 10, "J" }, { 11, "K" }, { 12, "L" }, { 13, "M" }, { 14, "N" }, { 15, "O" }, { 16, "P" }, { 17, "Q" }, { 18, "R" }, { 19, "S" }, { 20, "T" }, { 21, "U" }, { 22, "V" }, { 23, "W" }, { 24, "X" }, { 25, "Y" }, { 26, "Z" } };
static string Encrypt(string input, out string encriptionKey)
{
string decript = string.Empty;
encriptionKey = string.Empty;
int encryptPart;
foreach (char part in input.ToArray())
{
encryptPart = digit.FirstOrDefault(x => x.Value == part.ToString()).Key;
decript = decript + encryptPart.ToString();
if (encryptPart >= 10)
encriptionKey = encriptionKey + "1";
else
encriptionKey = encriptionKey + "0";
}
return decript;
}
static string Decrpt(string input, string key)
{
string outPut = string.Empty;
int keyPart;
foreach(char part in key.ToArray())
{
if(part == '0')
{
keyPart = Convert.ToInt32(input.Substring(0, 1));
input = input.Substring(1);
}
else
{
keyPart = Convert.ToInt32(input.Substring(0, 2));
input = input.Substring(2);
}
outPut = outPut + digit[keyPart];
}
return outPut;
}
static void Main(string[] args)
{
string input = "ABCEZYAR";
string key;
string output = Encrypt(input, out key);
string inputReturn = Decrpt(output, key);
}
Suggest to use Hash data structure with defined Hash function based on time stamp. So, when we start recording of traffic, hash function map traffic count to defined time stamp. You can easily take max value from Hash table.
- Rajesh Kumar May 21, 2014House Number: 600
- Rajesh Kumar May 21, 2014Logic be:
1) Check pointer value with new value to be added
2) If pointer value is greater than new value Than: store pointer value in temp and replace pointer value with new value
3) add a node by using temp value next to pointer node.
duplicate parenthesis means: ((c+d)) here () is extra which is duplicate. here only required (c+d) but due to duplicate parenthesis, you will find ((c+d)) ... So, you have to find such duplicate parenthesis ...
- Rajesh Kumar May 05, 2014You can use stack, start pushing each character from input string till you not hit close parenthesis. When you hit close parenthesis, start pop the element till you not hit open parenthesis. If the immediate pop hit open parenthesis than that is duplicate parenthesis.
Note: this algo will fail, if one put false parenthesis in string like: () .... Code as:
public void FindDuplicateparenthesis(string input)
{
Stack<char> inputStack = new Stack<char>();
foreach (char inputChar in input.ToCharArray())
{
if (inputChar != ')')
{
inputStack.Push(inputChar);
}
else
{
char popChar = inputStack.Pop();
if (popChar == '(')
Console.WriteLine("Duplicate Find ");
else
{
while (popChar != '(')
{
popChar = inputStack.Pop();
}
}
}
}
}
Best way to start from root and check both node available in subTree. Then mode to Left child and check same Otherwise move to right child and check same. Otherwise root is Deepest Ancestor. Algorithm:
DeepestAncestor = Root
DeepestAncestor = Root.Left => Verify that both Node is SubChild of This. If Yes, move forward and forget Right Child
Otherwise
DeepestAncestor = Root.Right => Verify that both Node is SubChild of This. If Yes, move forward and forget Left Child
If both Left and Right child DONT have both nodes as subchild then RETURN DeepestAncestor. Parent ....
static void GetResult(string InputData, int StartAt, StringBuilder Result)
{
if (StartAt >= InputData.Length)
return;
string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;
GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
}
static void GetResult(string InputData, int StartAt, StringBuilder Result)
{
if (StartAt >= InputData.Length)
return;
string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;
GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
}
By using Regular expression and recursion you can solve this problem easily. My answer is:
You can call the GetResult("pqaaaaabbbcccc", 0, result); from any method :)
static void GetResult(string InputData, int StartAt, StringBuilder Result)
{
if (StartAt >= InputData.Length)
return;
string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;
GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
}
By using Regular expression and recursion you can solve this problem easily. My answer is:
You can call the GetResult("pqaaaaabbbcccc", 0, result); from any method :)
static void GetResult(string InputData, int StartAt, StringBuilder Result)
{
if (StartAt >= InputData.Length)
return;
string matchResult = new Regex(@"((.)\2*)").Match(InputData, StartAt).Value;
GetResult(InputData, StartAt + matchResult.Length, Result.Append(string.Format("{0}{1}", matchResult.Length, matchResult.ToCharArray()[0])));
}
use simple javascript sort function.
- Rajesh Kumar June 05, 2017