ankushbindlish
BAN USERvoid Run()
{
int m = 5;
int n = 5;
var matrix = GenerateMatrix(m, n, new int[4] {1,2,3,4 });
PrintMatrix(matrix, m, n);
}
private static void PrintMatrix(int[,] matrix, int m, int n)
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
Console.Write(matrix[i,j] + "\t");
}
Console.WriteLine();
}
}
private static int getRandomNumber(int[] numbers)
{
return numbers[new Random().Next(0, numbers.Length - 1)];
}
private static int[,] GenerateMatrix(int m, int n, int[] numbers)
{
var result = new int[m, n];
var rowPossibleOffender = -1;
var colPossibleOffender = new int[n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
int newNumber = default(int);
while ((newNumber = getRandomNumber(numbers)) == rowPossibleOffender
&& newNumber == colPossibleOffender[j]) ;
result[i, j] = newNumber;
//Set row offender
if (i > 0 && result[i, j] == result[i - 1, j])
{
rowPossibleOffender = result[i, j];
}
else
{
rowPossibleOffender = -1;
}
// set col offender
if (j > 0 && result[i, j] == result[i, j - 1])
{
colPossibleOffender[j] = result[i, j];
}
else
{
colPossibleOffender[j] = -1;
}
}
}
return result;
}
#TODO : Add validation for error scenarios
private static readonly int MaxPathsAllowed = 256;
private static readonly char PathSeparator = '/';
private static string[] directoryTokens = new string[MaxPathsAllowed];
private static int currentDirectoryIndex = -1;
private static void ProcessFile(string fileName)
{
foreach (var line in File.ReadAllLines(fileName))
{
ProcessLine(line);
}
}
private static void ProcessLine(string line)
{
int localTabCount = -1;
while (line[++localTabCount] == '\t') ;
var name = line.TrimStart('\t');
if (IsDirectory(name))
{
directoryTokens[localTabCount] = name;
currentDirectoryIndex = localTabCount;
} else if (IsImage(name))
{
PrintPath(name);
}
}
private static void PrintPath(string name)
{
PrintPath(name, directoryTokens, currentDirectoryIndex, PathSeparator);
}
private static void PrintPath(string name, string[] paramDirectoryTokens, int tabIndex, char separator)
{
var result = string.Empty;
for (int index = 0; index <= tabIndex; index++)
{
result += paramDirectoryTokens[index];
}
result += PathSeparator + name;
Console.WriteLine(result);
}
private static string[] imagePathExtensions = new string[] { ".img", ".png", ".jpg" };
private static bool IsImage(string name)
{
var result = false;
int index = name.LastIndexOf('.');
if (index != -1)
{
return imagePathExtensions.Contains(name.Substring(index));
}
return result;
}
private static bool IsDirectory(string name)
{
return name[0] == PathSeparator;
}
1. Pack string with a delimiter and escape the delimiter in the data.
2. Consider data compression including data dedupe
3. Consider data security to not let any decode the string easily.
1. Add a data field with childcount which helps in visible bit and subtree rule scheme.
2. perform post order traversal ,
3. If we encountered a node , whose value is defined and also defined as subtree ( i.e >=3) , terminate and declare it as solution.
4. Set current node child count as 1+ left + right child count.
1. Create 2 linked list with root as tail.
2. Find the merging point of these 2 linked list
3. declare as ancestor else null.
// Handling Odd/Even length pallindrom
bool IsPallindrom(Node head){
return head != null && IsPallindrom(head,head->next) != null;
}
Node IsPallindrom(Node left,Node right)
{
// Boundary condition
if(left == null || right == null) return null;
// Terminating condition
// Recurring condition
var newRight = null;
if(right->next == null)
newRight = left->Next;
else if(right->next->Next == null)
newRight = left->Next->Next;
else {
newRight = IsPallindrom(left->Next, right->Next->Next);
}
// Fail condition
if(newRight == null ) return null;
// Success condition
if( left->data == newRight->data) return newRight->Next;
return null;
}
bool IsPallindrom(Node head){
return head != null && IsPallindrom(head,head->next) != null;
}
Node IsPallindrom(Node left,Node right)
{
// Boundary condition
if(left == null || right == null) return null;
// Terminating condition
// Recurring condition
var newRight = right->next == null ? left->Next : IsPallindrom(left->Next, right->Next->Next);
// Fail condition
if(newRight == null ) return null;
// Success condition
if( left->data == newRight->data) return newRight->Next;
return null;
}
Node reverseKAlt(Node head, int k){
if(head == null ) return head;
Node p = head;
Node q = head->next;
p->next = null;
while(q!= null){
var r = q->next;
p = q;
if( (k/3) % 2 != 0)
q->next = p;
q = r
}
return p;
}
List<int> GetMinimums(List<int> stream , int totalMinElements){
int [] results = new int(n);
int minElementsSoFar = 0;
foreach(var num in stream){
var pivotIndex = FindPivot(result,0,minElementsSoFar-1,num);
for(int j=pivotIndex;j<minElementsSoFar && j<totalMinElements-1;j++)
results[j+1] = result[j];
results[pivotIndex] = num;
}
return results;
}
int FindPivot(int[] result,int low, int high,int key){
if(low > high) return low;
var mid = (low+high)/2;
if(result[mid] < key)
return FindPivot(result,mid+1,high,key);
else
return FindPivot(result,low,mid-1,key);
}
Create a window using hashing and keeping VisitCount. Slide windows with leftmost character match to obtain all possible positive windows. Capture minimum window at each stage.
- ankushbindlish November 29, 2015Trie containing frequency and Min Heap of max 100 elements
New word update frequency > heap root , Eligible for top 100 candidates
ProcessTokens(@"15#9#6#4#6#8#0#7#1#5".ToCharArray());
ProcessTokens(@"5#9#6#4#6#8#0#7#1".ToCharArray());
ProcessTokens(@"5#9##4#6#8#0#7#1".ToCharArray());
private static void ProcessTokens(char[] tokens)
{
int maxPerRowSoFar=0, rowCount = 1, unprocessedElementsPerRow;
int? num;
int streamIndex = 0, overallSum = 0;
unprocessedElementsPerRow = rowCount;
while ((num = GetToken(tokens, ref streamIndex)) != null)
{
// row break condition
if (unprocessedElementsPerRow == 0)
{
rowCount++;
unprocessedElementsPerRow = rowCount;
overallSum += maxPerRowSoFar;
}
maxPerRowSoFar = (rowCount == unprocessedElementsPerRow) ? num.Value : Math.Max(maxPerRowSoFar, num.Value);
unprocessedElementsPerRow--;
}
if (unprocessedElementsPerRow == 0 && streamIndex == tokens.Length)
{
overallSum += maxPerRowSoFar;
Console.WriteLine(overallSum);
}
else
{
Console.WriteLine("Invalid");
}
}
private static int? GetToken(char[] tokens, ref int i)
{
int? number = null;
while (i < tokens.Length && tokens[i] != '#')
{
if (tokens[i] < '0' && tokens[i] > '9')
throw new ArgumentException("Invalid");
number = (number ?? 0) * 10 + (tokens[i] - '0');
i++;
}
if (i < tokens.Length)
{
i++;
}
return number;
}
I am bit confused with the question. Isnt desc order sequence will yield in a desired result ? any examples to the above question
- ankushbindlish November 16, 2015private static List<string> GetChunks(string message, int messageLimit)
{
var result = new List<string>();
int mbX = 0, mbY = -1;
do
{
mbX = mbY + 1;
mbY = mbX + messageLimit;
while (mbY >= mbX && mbY < message.Length && message[mbY--] != ' ' );
if (mbY < mbX) throw new Exception("Cannot chunk.");
if (mbY >= message.Length) mbY = message.Length;
result.Add(message.Substring(mbX, mbY - mbX));
} while (mbY >= message.Length -1);
return result;
}
iosrjen.org/Papers/vol4_issue4%20(part-1)/A04410107.pdf
Secant Method over other methods
private static List<int> GenerateSums(int number)
{
List<int> result = null;
int pCount = 1;
while (pCount++ != number / 2)
{
var median = number / pCount;
var currentResult = new List<int>();
currentResult.Add(median);
var remaining = number - median;
// populate data around median
int k = 0;
while (remaining > 0 && ++k > 0)
{
if (remaining < median && median > k)
{
currentResult.Insert(0, median - k);
remaining -= median - k;
}
if (remaining < 2 * median)
{
currentResult.Insert(currentResult.Count, median + k);
remaining -= median + k;
}
else
{
if (median > k)
{
currentResult.Insert(0, median - k);
}
currentResult.Insert(currentResult.Count, median + k);
remaining -= 2 * median;
}
if (remaining == 0 && currentResult.Count > 1)
{
//Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
result = currentResult;
}
}
//Console.WriteLine("pCount = {0} Median {1} Remaining = {2} Impossible", pCount, median, remaining);
}
Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
return result;
}
private static List<int> GenerateSums(int number)
{
List<int> result = null;
int pCount = 1;
while (pCount++ != number / 2)
{
var median = number / pCount;
var currentResult = new List<int>();
currentResult.Add(median);
var remaining = number - median;
// populate data around median
int k = 0;
while (remaining > 0 && ++k > 0)
{
if (remaining < median && median > k)
{
currentResult.Insert(0, median - k);
remaining -= median - k;
}
if (remaining < 2 * median)
{
currentResult.Insert(currentResult.Count, median + k);
remaining -= median + k;
}
else
{
if (median > k)
{
currentResult.Insert(0, median - k);
}
currentResult.Insert(currentResult.Count, median + k);
remaining -= 2 * median;
}
if (remaining == 0 && currentResult.Count > 1)
{
//Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
result = currentResult;
}
}
//Console.WriteLine("pCount = {0} Median {1} Remaining = {2} Impossible", pCount, median, remaining);
}
Console.WriteLine(string.Join(" = ", number, string.Join(" + ", result)));
return result;
}
If I relax stream and array keyword from the question , it translates into common problem of merging 2 sorted linked list.
// Program to merge 2 sorted list
Node Merge(Node head1 , Node head2){
if(head1 == null) return head2;
if(head2 == null) return head1;
if(head1.Data < head2.Data) {
head1-> next = Merge(head1.Next,head2);
return head1;
}
else if( head1.Data > head2.Data){
head2-> next = Merge(head1,head2->Next);
return head2;
}
else {
head2->Next = Merge(head1->Next,head2->Next);
head1 -> Next = head2;
return head1;
}
}
I am certain that I am missing something as it cannot be trivial.
Assuming we know k before hand
// Program to find k-average where the number is extracted from a stream one by one.
// if n<k , Compute n-average where n is the numbers extracted so far.
// Given a provider with GetNextNumber , IsEmpty signatures
// Average = (a1+ a2 + a3 + a4 +.....am)/m , m= Min(m,k)
// Average = Sum/Count
// SumSofar , First , Next , Count {increment only if count < k }
public class MovingAverage
{
float SumSoFar {get;set;}
float First {get;set;}
int Count {get;set;}
const int AverageLimit = 10 ;// k
void Insert(float next){
if(Count < AverageLimit) Count++;
else SumSoFar -= First;
SumSoFar += next;
}
public void Process(){
while(!provider.IsEmpty())
Insert(provider.GetNextNumber());
}
public void Average(){
return SumSoFar/Count;
}
}
// if we do not know k before hand , then we need to store whole stream and manipulate average based on k
// Program to assignments based on the index value of a given array
// A[0...n-1] with elements [0,n-1] shuffle across array
// for example Input : A[5] = { 2,4,3,1,0}
// Output : A[5] = { 3,0,1,4,2}
// Solution 1 : Another array B[A[i]] = A[i]
// Solution 2 : In case of inplace
int[] Modify(int input[], int n){
// Boundary conditions
if(input == null || n<=0) return null;
// Declaration
int pIndex=0 , qIndex=0,counter = 0;
// Initialization
do{
pIndex= qIndex;
qIndex= input[pIndex];
//Swap(input,pIndex,qIndex);
input[pIndex] = input[pIndex] + input[qIndex] ;
input[qIndex] = input[pIndex] - input[qIndex] ;
input[pIndex] = input[pIndex] - input[qIndex] ;
}while(++counter != n);
// Returning function
return input;
}
Without a preprocessing knowledge and limited control over legal words data structures, we can optimize the iterations
1. Short Circuit when first match for specific word length found,
2. Terminate program when first legal word found.
3. Start with longest word to shortest word.
public static string LongestWord(string word){
string result= default(string);
if(string.IsNullOrEmpty(word)) { return word;}
for(int wl = word.Length; wl > 1; wl--){
for(int si = 0; si <= word.Length - wl ; si++){
var eword = word.Substring(si,wl);
if(IsLegalWord(eword)){
result = eword;
break;
}
}
if(result != default(string)) break;
}
return result;
}
1. Hashing with remaining 2 non collided elements will start,end , which can be differentiated with augmented data or further search. If 0 non collided elements -> circular.
2. Adjacency matrix with a row/column with all zeroes, if it not exists circular.
3. Graph traversal in incoming and outgoing direction to terminate when you have a node with 1 directed edge. Keep a visited flag to disambiguate circular path.
1. O(n2) comparison
2. O(n) Hashing with key value and -value
Multiway tree with data containing Value and LastMultiplier. Proceed with node only if currentValue is less than equal to LastMultiplier.
- ankushbindlish November 01, 2015BinarySearch2D(int inputArray[][], int m , int n, int key){
int low=0;
int high=n-1;
int mid;
do{
mid = low + (high-low)/2;
if (inputArray[mid][mid] > key){
high = mid;
} else if (inputArray[mid][mid] < key){
low = mid;
} else{
return true;
}
}while(low<high);
return BinarySearch1D(inputArray,key,mid,true) || BinarySearch1D(inputArray,key,mid,false);
}
BinarySearch1D(int inputArray[][],int key, int maxIndex, bool rowConstant){
int low=0;
int high = maxIndex-1;
do{
int mid = low + (high-low)/2;
int midValue = rowConstant ? inputArray[maxIndex][mid] : inputArray[mid][maxIndex];
if (midValue > value){
high = mid-1;
} else if (midValue < value){
low = mid+1;
} else{
return true;
}
}while(low<high);
return false;
}
BinarySearch2D(int inputArray[][], int m , int n, int key){
int low=0;
int high=n-1;
int mid;
do{
mid = low + (high-low)/2;
if (inputArray[mid][mid] > key){
high = mid;
} else if (inputArray[mid][mid] < key){
low = mid;
} else{
return true;
}
}while(low<high);
return BinarySearch1D(inputArray,key,mid,true) || BinarySearch1D(inputArray,key,mid,false);
}
BinarySearch1D(int inputArray[][],int key, int maxIndex, bool rowConstant){
int low=0;
int high = maxIndex-1;
do{
int mid = low + (high-low)/2;
int midValue = rowConstant ? inputArray[maxIndex][mid] : inputArray[mid][maxIndex];
if (midValue > value){
high = mid-1;
} else if (midValue < value){
low = mid+1;
} else{
return true;
}
}while(low<high);
return false;
}
Please ignore this solution.
- ankushbindlish January 14, 2011O( logm * logn )
1. Find a row which might have a key, by looking at first column using modified binary search which will look for interval match.
2. Conventional binary search on the row returned from step 1
Please let me know for any query
Cheers
Ankush
- Invalid character
- Overflow exception
- Positive and Negative numbers.
int MyAtoi(char *inputParam){
if(*inputParam == 0) throw new FormatException();
int result = 0;
bool isNegative = false;
if(*inputParam == '-'){
inputParam++;
isNegative = true;
}
if(*inputParam == 0) throw new FormatException();
while(*inputParam){
if(*inputParam >= 0x32 && *inputParam < 0x3C){
int tempResult = (result
+ (*inputParam - 0x32)
)
* ((*(inputParam + 1) == 0) ? 1 : 10);
if(tempResult < result) throw new OverflowException();
result = tempResult;
} else {
throw new FormatException();
}
}
return result * (isNegative ? -1:1);
}
Solution already provided
1. Finding Intersection, followed by recursive addition
Deepak on May 19, 2010
2. Reverse, Addition , Reverse.
Anonymous on May 21, 2010
Please correct me if I missed any other genuine solution.
Just thought to share an alternative solution.
Step 1 : Initialization of linked list with adding the degree of the integer.
7541
(7,3) -> (5,2) -> (4,1) -> (1,0) -> NULL
O(m+n)
Step 2 : Recursive addition
Every recurring code snippet wait for carry to return from next call, so as to augment with the node in resultant list.
O(n) , wlog, n>m
Please comment.
Odd or Even length string
null string
normal string
naming convention
xml summary comments
Proper Indentation
Dry Run of the program
Case sensitive or insensitive comparison
All Return paths need to be validated.
I am still confused. Can someone help ?
"You are then given a set of words coming from the language in the sorted order"
- List of word sorted ( acb,cba, bca) or word itself is sorted (abc,bc, c) or both (a, ab,bc, abc) ???
Case 1 :
Traversing the array and create an edge between two alphabet with distance 1 or infinite(if unknown)
Traversing the array would give you a acyclic traversal with covering all nodes., other there is no unique solution to the problem.
Case 2 Assuming words are sorted
Then each word is a graph, clubbed together all the word to form a unified graph.
Perform topological sort
Please help me understand the question and its probable solution.
Thanks
Ankush
Correct solution.
Though I believe the above solution is recommended, still thought to share its recursive version.
Things need to be considered in this problem
1. Checking valid input.
2. Checking overflow.
3. Minimum memory allocation for local variables.
4. More usage of bitwise than arithmetic operators.
int atoi(char *inputParam){
int result = 0;
static int factor = 1;
if(*inputParam == 0) return 0; // Terminating condition
if( (*inputParam <'0') || (*inputParam > '9')) // Validation
throw new ArgumentException("Given string cannot be parsed into integer");
// Recurring code snippet.
int intermediateResult = atoi(inputParam + 1);
result = (*inputParam & 0xF) * factor * intermediateResult;
factor *=10;
return result;
}
Can someone help me understanding the overflow checking ?
- ankushbindlish May 05, 2010- char * header memory is used to create a pointer. There is no memory used to store data characters.
void Remove(char *inputParam, char delimitor) {
char *header = inputParam;
while(inputParam){
if(*inputParam != deimitor){
*header = inputParam;
header++;
}
inputParam++;
}
*header = 0;
}
#define TrimCharacter '-'
char * Trim(char * inputString,int l)
{
char *p,*q;
q = p = inputString;
while(*p){
if((*p != TrimCharacter) || (*q != TrimCharacter)) {
*q = *p;
q++;
}
p++;
}
*q = 0;
return inputString;
}
Hi,
Just thought to summarize the possible motivation behind this question.
- Check to handle negative number.
- Check for minimum iteration
- Check for recursion concepts.
- Check for bitwise operators
- Check for O(Log N) solution by n/2 recursive solution
- Check for basic ideology of multiply, which is addition.
- Check for overflow condition handling. ( For C#, One can also read about checked keyword)
There are multiple variants of this question depending on the exact problem statement from interviewer. One can easily fit subset of above check's into the problem and come up with a robust source code.
Please feel free to add more analytic to the motivation behind the question.
Thanks
Ankush
Hi,
Just thought to summarize the possible motivation behind this question.
- Check to handle negative number.
- Check for minimum iteration
- Check for recursion concepts.
- Check for bitwise operators
- Check for O(Log N) solution by n/2 recursive solution
- Check for basic ideology of multiply, which is addition.
- Check for overflow condition handling. ( For C#, One can also read about checked keyword)
There are multiple variants of this question depending on the exact problem statement from interviewer. One can easily fit subset of above check's into the problem and come up with a robust source code.
Please feel free to add more analytic to the motivation behind the question.
Thanks
Ankush
Its same as "The Emperor " Problem
+folj.
+com
+ /puzzles/very-difficult-analytical-puzzles
+.htm
1 The Emperor
You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.
The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.
You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.
You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.
What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
Its same as "The Emperor " Problem
+folj.
+com
+ /puzzles/very-difficult-analytical-puzzles
+.htm
1 The Emperor
You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.
The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.
You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.
You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.
What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
You must be kidding around here.
number % 9
987 % 9 = 6 = 9 + 8 + 7 = 2 + 4 = 6
int TreeCount = 0;
bool IsBST(TreeNode root)
{
return (NULL == root) ? true:
(TreeCount++ , (!root->left || (root->left->info <= root->info)) &&
(!root->right || (root->right->info <= root->info)) &&
IsBST(root->left) &&
IsBST(root->right));
}
Time complexity?
- ankushbindlish May 02, 201033 comparisons
for i = 1 to 99 step 3
print i is odd.
print i+1 is even.
If ((i+2) MOD 2) = 0
print i+2 is divisible by 2 and 3.
Else
print i+2 is divisible by 3.
End For
print 100 is even.
Consumer
Consumer Identifier
Details
Table
Table Identifier
NumberOfSeats
Category
Restaurant Identifier
IsOccupied
Restaurant
Restaurant Identifier
Reservation
StartTime
EndTime
Restaurant Identifier
Table Identifier
Is Cancelled
Consumer Identifier
Enabled - This would use to enter record for customer who were not given the reservation due to occupied seats at this particular slot. It can be used to inform the consumer to reserve the slot again as its free now.
Is Defaulter - On closing reservation, This field could be use to list out cases where the reservation were not consumed and there was no communication for cancellation.
QuerySlot
Reserve Table
Cancel Table
ContactConsumer
Close Reservation
GetAvailableSlots - This will show enumerated list of all the tables with timestamp of given date. It depicts free/occupied slot.
Elevator
Floor/Location Identifier
Number of steps
Rotation speed
Daterange
InstallationDate
MaintainenceDate
Department Identifier
AllowedWeight
Detail / Description
Start
Stop
SetDirection
SetRotationSpeed
EmergencyStop = Stop + Alert
EmergencyAccidentSenser Handler
1. K-Selection Sort. O(n + KlogK),
2. Max-Heap sort for K elements. O(nlogK)
TreeNode Mirror(TreeNode root)
{
if(NULL == root) return root;
TreeNode temp = root->left;
root->left= Mirror(root->right);
root->right = Mirror(temp);
return root;
}
All are writing same code, same logic, and adding one their own trademark defect. For instance - function returning integer doesn't return anything.
I believe we are good to close this thread and all understand the solution.
Thanks
Ankush
That is for adding 48 to make it character.
- ankushbindlish May 01, 2010
1. Use Power function in log time
- ankushbindlish January 22, 2017int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
2. Use hash for duplicate numbers in the set.
I am still trying to understand the rationale behind this question.