maksymas
BAN USER- 1of 1 vote
AnswersA company is looking for algorithm to show item recommendations.
- maksymas in United States
If a customer bought A and B items and another buys A item, B should come as recommendations.
There are two types of recommendations based on the connections
1) Two items are strongly connected if a customer buys those items.
2) Two items are weakly connected if each items are strongly/weakly connected to another third item.
Provided the sample input
ABC
10
first:ABC
first:HIJ
sec:HIJ
sec:KLM
third:NOP
fourth:ABC
fourth:QRS
first:DEF
fifth:KLM
fifth:TUV
first, sec, third.. represents the customer names
ABC, HIJ... represents the item codes
For the Input item Id "ABC", since "ABC" is strongly connected to HIJ, DEF, QRS
and whereas ABC is weakly connected to KLM and TUV
the output should be count of strong and weak connection i.e., [3,2]| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 0of 0 votes
Answers--Suppose that we have an array of m by n size. Each element is binary, so it can either be 1 or 0. Design an algorithm that for a given array, the return is a set arrays containing the nodes that are adjecent to each other.
- maksymas in United States
For example:
1 2 3 4 5 6 7 8
---------------
1|0 0 0 0 0 0 0 1
2|0 0 0 0 1 0 0 1
3|0 0 0 1 0 0 0 0
4|0 1 1 1 1 0 0 0
5|0 0 0 0 1 0 0 0
Returns:
Array1 {(8,1) (8,2)}
Array2 {(5,2) (4,3) (2,4) (3,4) (4,4) (5,4) (5,5)}| Report Duplicate | Flag | PURGE
Amazon Development Support Engineer Algorithm
O(N + M) Time complexity
var removeStrings = function (str1, str2) {
var arrayA = str1.split(' ');
var arrayB = str2.split(' ');
var hashB = {};
var result = [];
for (var i = 0; i < arrayB.length; i++) {
hashB[arrayB[i]] = 1;
}
for (var i = 0; i < arrayA.length; i++) {
if (hashB[arrayA[i]] === undefined) {
result.push(arrayA[i]);
}
else {
hashB[arrayA[i]] = undefined;
}
}
$(result);
}
var kSubsequence = function(array, k){
var start = 0; end = 0;
var seq = [];
var sum = 0;
for(var i = 0; i < array.length; i ++){
start = i;
while(start < array.length){
sum += array[start];
seq.push(array[start]);
if(sum % k === 0){
$(seq);
}
start++;
}
seq = [];
sum = 0;
}
}
kSubsequence([1,2,3,4,1], 4)
Bit Manipulation problem (c#)
public bool IsMetaString(char[] A, char[] B)
{
count = 0;
var bitsA = 0;
var bitsB = 0;
for (int i = 0; i < A.Length; i++)
{
var valA = A[i] - 'a';
var valB = B[i] - 'a';
bitsA |= (1 << valA);
bitsB |= (1 << valB);
var xOr = (1 << valA) ^ (1 << valB);
if (xOr > 0)
count++;
}
return (bitsA ^ bitsB) == 0 && count == 2;
}
Simple and elegant c# - O(N) time and O(1) space
public void Adding2LinkedList(LinkedListNode<int> one = null, LinkedListNode<int> sec = null)
{
int sum = 0;
int carry = 0;
var wholeSize = Math.Max(LengthOfLinkedList(one), LengthOfLinkedList(sec));
var result = new LinkedList<int>();
for (int i = 0; i < wholeSize; i++)
{
count = 0;
var elemOne = FindTheKthLastElement(one, i);
count = 0;
var elemSec = FindTheKthLastElement(sec, i);
sum = (elemOne + elemSec + carry) % 10;
carry = (elemOne + elemSec + carry) / 10;
result.AddFirst(sum);
}
}
public int FindTheKthLastElement(LinkedListNode<int> list, int k)
{
int num = 0;
if (list == null) return num;
num = FindTheKthLastElement(list.Next, k);
if (count++ == k)
return list.Value;
return num;
}
public int LengthOfLinkedList(LinkedListNode<int> list)
{
if (list == null) return 0;
return 1 + LengthOfLinkedList(list.Next);
}
C# using kadane's algorithm
public void LargestSumOfContiguousArray(int[] array)
{
var ans = 0;
var maxAtElement = 0;
var isAllNegative = true;
var minNumberOfArray = int.MinValue;
for (var i = 0; i < array.Length; i++)
{
isAllNegative &= array[i] < 0;
minNumberOfArray = Math.Max(minNumberOfArray, array[i]);
maxAtElement = Math.Max(maxAtElement + array[i], array[i]);
ans = Math.Max(maxAtElement, ans);
}
if (isAllNegative)
Console.WriteLine(minNumberOfArray);
else
Console.WriteLine(ans);
}
pretty easy in recursion - DP - C#.
public void RecursionColumnWise(int[,] matrix, int rowSize, int colSize, int row = 0, int col = 0)
{
if (col > colSize) return;
if (matrix[row, col] == 1)
{
Console.WriteLine("{0}, {1}", row + 1, colSize - col + 1); //Adding 1 to prime the index
if (row >= rowSize)
return;
}
if (row >= rowSize && col < colSize)
// Only when it scanned all of the rows and still columns left to scan - jump to next column from the beginning.
// Beginning means row = 0 and next column
RecursionColumnWise(matrix, rowSize, colSize, 0, col + 1);
else
// else scan across all the element in the row
RecursionColumnWise(matrix, rowSize, colSize, row + 1, col);
}
Can be further improved using binary Search
public class BracketAnalysis
{
public class Brakets
{
public int NumberOfOpen { get; set; }
public int NumberOfClose { get; set; }
}
public int result { get; set; }
public void FindIndexOfEqualBrakets(string input)
{
for (var i = 1; i < input.Length; i++)
{
var obj = ReadString(input, 0, i);
var obj1 = ReadString(input, i, input.Length - 1);
if (obj.NumberOfOpen == obj1.NumberOfClose || obj.NumberOfClose == obj1.NumberOfOpen) { result = i; }
}
}
private Brakets ReadString(string input, int startIndex, int endIndex)
{
var obj = new Brakets();
for (var i = startIndex; i < endIndex; i++)
{
if (input[i] == '(')
{
obj.NumberOfOpen++;
}
else if (input[i] == ')')
obj.NumberOfClose++;
}
return obj;
}
}
C# - Recursion
private Stack<int> commonManagers = new Stack<int>();
public int GetClosestCommonManagers()
{
return commonManagers.Pop();
}
public void ClosestManager(BinaryTree<int> tree, int firstEmp, int secEmp)
{
if (tree == null) return;
if (HasChild(tree, firstEmp) && HasChild(tree, secEmp))
commonManagers.Push(tree.Node);
ClosestManager(tree.Right, firstEmp, secEmp);
ClosestManager(tree.Left, firstEmp, secEmp);
}
private bool HasChild(BinaryTree<int> tree, int employee)
{
if (tree == null) return false;
if (tree.Node == employee) return true;
return HasChild(tree.Left, employee) || HasChild(tree.Right, employee);
}
1) Sorting array A
2) Place the minimum of A that can be more that B[i]
3) Repeat till you completed B Count
Seems O(N^2)
public List<int> ShuffleArray(List<int> A, List<int> B)
{
int outerLoop = 0;
int innerLoop = 0;
var s = new Sorting();
var min = int.MaxValue;
var result = new List<int>();
var sortedArray = s.SimpleSorting(A);
for (var i = 0; i < B.Count; i++)
{
//Console.WriteLine("Outer Loop : {0}", ++outerLoop);
outerLoop++;
for (var j = 0; j < sortedArray.Count; j++)
{
//Console.WriteLine("Inner Loop : {0}", ++innerLoop);
innerLoop++;
if (sortedArray[j] > B[i])
{
result.Add(sortedArray[j]);
sortedArray.Remove(sortedArray[j]);
break;
}
else if (min > sortedArray[j])
min = sortedArray[j];
if (j == sortedArray.Count - 1)
{
result.Add(min);
sortedArray.Remove(min);
min = int.MaxValue;
}
}
}
Console.WriteLine("Outer Loop : {0} Inner Loop : {1}", outerLoop, innerLoop);
return result;
}
Using Random Shuffle
public List<int> ShuffleArray(List<int> aArray, List<int> bArray)
{
int aCount = 0;
int bCount = 0;
var rand = new Random();
while(aCount <= bCount)
{
//Random Shuffle
var randomNumber = rand.Next(1, aArray.Count);
var temp = aArray[0];
aArray[0] = aArray[randomNumber];
aArray[randomNumber] = temp;
aCount = 0;
bCount = 0;
for(var i = 0; i < aArray.Count; i ++)
{
if (aArray[i] > bArray[i])
aCount++;
else if (aArray[i] < bArray[i])
bCount++;
}
}
return aArray;
}
- maksymas March 20, 2017Sweet PostOrder in Recursion C#
private int SearchResult { get; set; }
public void FindItsParent(BinaryTree<int> tree, int elementToBeFound, int Parent)
{
if (tree == null) return;
FindItsParent(tree.Left, elementToBeFound, tree.Node);
FindItsParent(tree.Right, elementToBeFound, tree.Node);
if (tree.Node == elementToBeFound)
{
SearchResult = Parent;
}
}
- maksymas March 19, 2017public void MergeIntervals(List<Interval> Intervals)
{
foreach (var interval in Intervals.ToList())
{
if(ListOfInterval == null)
{
ListOfInterval = new List<Interval>
{
new Interval(interval.Start, interval.End)
};
}
else
{
foreach(var existingInterval in ListOfInterval.ToList())
{
if (interval.Start > existingInterval.Start && interval.End < existingInterval.End)
{
interval.IsDealt = true;
continue; // Within a existing range
}
else
if (interval.Start < existingInterval.Start && interval.End > existingInterval.End)
{
ListOfInterval.Remove(existingInterval);
ListOfInterval.Add(new Interval(interval.Start, interval.End));
interval.IsDealt = true;
break;
}
else
if (interval.Start > existingInterval.Start && interval.Start < existingInterval.End
||
interval.End > existingInterval.Start && interval.End < existingInterval.End)
{
ListOfInterval.Remove(existingInterval);
ListOfInterval.Add(new Interval(
Math.Min(interval.Start, existingInterval.Start),
Math.Max(interval.End, existingInterval.End)
));
interval.IsDealt = true;
break;
}
}
if (! interval.IsDealt)
ListOfInterval.Add(new Interval(interval.Start, interval.End));
}
}
}
- maksymas March 19, 2017Using the power of recursion and dynamic programming
public void ReverseALikedList(myLinkedList<int> number)
{
if (number == null) return;
ReverseALikedList(number.Next);
CreateReverseLinkedList(number.data);
}
public LinkedList reversedLinkedList = new LinkedList();
private void CreateReverseLinkedList(int data)
{
reversedLinkedList.AddLast(data);
}
- maksymas March 19, 2017Using DFS in C#
public void maxConsecutiveSequenceOfBTree(BinaryTree<int> tree)
{
if (tree == null) return;
if (!tree.IsVisited)
{
Console.WriteLine(tree.Node);
CollectionMethod(tree.Node);
tree.IsVisited = true;
maxConsecutiveSequenceOfBTree(tree.Left);
maxConsecutiveSequenceOfBTree(tree.Right);
}
}
private List<List<int>> buffer = new List<List<int>>();
private void CollectionMethod(int num)
{
if (buffer.Count == 0)
{
buffer.Add(new List<int>(num));
return;
}
else
{
foreach (var n in buffer.ToList())
{
if (n.Contains(num - 1) || n.Contains(num + 1))
{
n.Add(num);
return;
}
}
}
buffer.Add(new List<int> { num });
}
public int getMaxSize()
{
int sum = 0;
foreach(var n in buffer)
{
if(sum < n.Count)
{
sum = n.Count;
}
}
return sum;
}
- maksymas March 18, 2017Using the power and flexibility of C# ->Used recursion
internal int FindTheBiggestCross(int[,] matrix, int xLength, int yLength)
{
int total = 0;
for (int i = 0; i < xLength; i++)
{
for (int j = 0; j < yLength; j++)
{
if (matrix[i, j] == 1 && i - 1 >= 0 && j - 1 >= 0 && i + 1 < xLength && j + 1 < yLength
&& matrix[i - 1, j] == 1
&& matrix[i + 1, j] == 1
&& matrix[i, j - 1] == 1
&& matrix[i, j + 1] == 1
)
{
var listofAnswer = new List<int>();
listofAnswer.Add(SizeOfCross1(matrix, i, j, xLength, yLength));
listofAnswer.Add(SizeOfCross2(matrix, i, j, xLength, yLength));
listofAnswer.Add(SizeOfCross3(matrix, i, j, xLength, yLength));
listofAnswer.Add(SizeOfCross4(matrix, i, j, xLength, yLength));
if(listofAnswer.Distinct().Count() == 1)
{
if(total < listofAnswer[0])
{
total = listofAnswer[0];
}
}
}
}
}
return total;
}
private int SizeOfCross1(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
{
if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
{
if (matrix[xIndex, yIndex] == 0) return 0;
return 1+ SizeOfCross1(matrix, xIndex, --yIndex, xLength, yLength);
}
return 0;
}
private int SizeOfCross2(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
{
if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
{
if (matrix[xIndex, yIndex] == 0) return 0;
return 1 + SizeOfCross2(matrix, ++xIndex, yIndex, xLength, yLength);
}
return 0;
}
private int SizeOfCross3(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
{
if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
{
if (matrix[xIndex, yIndex] == 0) return 0;
return 1 + SizeOfCross3(matrix, xIndex, ++yIndex, xLength, yLength);
}
return 0;
}
private int SizeOfCross4(int[,] matrix, int xIndex, int yIndex, int xLength, int yLength)
{
if (xIndex >= 0 && xIndex < xLength && yIndex >= 0 && yIndex < yLength)
{
if (matrix[xIndex, yIndex] == 0) return 0;
return 1 + SizeOfCross4(matrix, --xIndex, yIndex, xLength, yLength);
}
return 0;
}
- maksymas March 17, 2017BFS it is.
internal List<string> BFSOnAGridGraph(int[,] matrix, int sizeX, int sizeY)
{
var result = new List<string>();
for (var a = 0; a < sizeX; a++)
{
for (var b = 0; b < sizeY; b++)
{
var tempResult = string.Empty;
if (matrix[a, b] == 1)
{
var queue = new Queue<int[]>();
queue.Enqueue(new int[] { a, b });
matrix[a, b] = 9;
tempResult = string.Format("({0}, {1}) ", a + 1, b + 1);
while (queue.Count != 0)
{
var elem = queue.Dequeue();
for (var i = -1; i <= 1; i++)
{
for (var j = -1; j <= 1; j++)
{
if (elem[0] + i >= 0 && elem[1] + j >= 0 && elem[0] + i < sizeX && elem[1] + j < sizeY)
{
if (matrix[elem[0] + i, elem[1] + j] != 9 && matrix[elem[0] + i, elem[1] + j] == 1)
{
queue.Enqueue(new int[] { elem[0] + i, elem[1] + j });
Console.WriteLine("{0} , {1} ", elem[0] + i + 1, elem[1] + j + 1);
tempResult += string.Format("({0}, {1}) ", elem[0] + i + 1, elem[1] + j + 1);
matrix[elem[0] + i, elem[1] + j] = 9;
}
}
}
}
}
result.Add(tempResult);
}
}
}
return result;
}
- maksymas March 16, 2017Brute forde
private string reverseAString(string str, int startIndex, int length)
{
var repStr = string.Empty;
var subStr = str.Substring(startIndex, length);
foreach (var c in subStr)
repStr = c + repStr;
return str.Replace(subStr, repStr);
}
public string FindtheMinNumber(string pattern)
{
var output = string.Empty;
var startIndex = 0;
var length = 0;
var previous = '@';
for (var i = 0; i < pattern.Length + 1; i++)
{
output = output + (i + 1);
}
for (var c = 0; c < pattern.Length; c++)
{
if (previous == pattern[c])
{
if (pattern[c] == 'D')
length++;
}
else
{
if (length > 1 && previous == 'D')
output = reverseAString(output, startIndex, length + 1);
else if(length > 0 && previous == 'D')
output = reverseAString(output, startIndex, length + 1);
previous = pattern[c];
length = 1;
startIndex = c;
}
}
if(length > 0 && previous == 'D')
output = reverseAString(output, startIndex, length + 1);
Console.WriteLine(output);
return output;
}
- maksymas March 14, 2017Easy as below in C#
public void FindConsecutiveRepetitiveWithNoDict(string input)
{
var previous = '-';
int sum = 0;
var output = 0;
var caught = '*';
foreach (char a in input)
{
if (previous == a)
{
if (sum < ++output)
{
sum = output;
caught = a;
}
}
else
{
output = 1;
}
previous = a;
}
Console.WriteLine("{0} -> {1}", caught,sum);
}
- maksymas March 14, 2017I derived at this brute force but there should be a better way
static int[] determineRecommendation(string itemId, string[] purchases)
{
var Stronglist = new List<string>();
var Weaklist = new List<string>();
var commonList = new List<string>();
var dict = new Dictionary<string, List<string>>();
for (int i = 0; i < purchases.Length; i++)
{
var splitString = purchases[i].Split(':');
var customer = splitString[0];
var item = splitString[1];
if (dict.ContainsKey(customer))
{
dict[customer].Add(item);
}
else
{
var newList = new List<string>();
newList.Add(item);
dict.Add(customer, newList);
}
}
foreach(var customer in dict.Keys)
{
if(dict[customer].Contains(itemId))
{
foreach(var item in dict[customer])
{
if(item != itemId)
Stronglist.Add(item);
}
}
}
var strongCount = Stronglist.Count;
foreach (var customer in dict.Keys)
{
foreach (var strong in Stronglist.ToList())
{
if(dict[customer].Contains(strong))
{
foreach(var item in dict[customer])
{
if (!Stronglist.Contains(item) && !Weaklist.Contains(item) && item != itemId)
{
Weaklist.Add(item);
Stronglist.Add(item);
}
}
}
}
}
return new int[] { strongCount, Weaklist.Count };
}
- maksymas August 29, 2016To me, it sounded like an LinkedList Question. Hence I implemented in LinkedList
public static MyLinkedList output = new MyLinkedList();
public static MyLinkedList stringToLinkedList(string a)
{
if (a.Length == 0)
return null;
else
{
output.AddLast(a.ElementAt(0) - '0');
}
stringToLinkedList(a.Substring(1));
return output;
}
public static string LinkedListSubtract(Node a, Node b)
{
StringBuilder str = new StringBuilder();
var carry = 0;
while (a != null && b != null)
{
if (a.data > b.data)
{
str.Insert(0, (a.data - b.data - carry));
carry = 0;
}
else if (a.data == b.data)
if (carry > 0)
str.Insert(0, (a.data - b.data + 10 - carry));
else
str.Insert(0, (a.data - b.data));
else
{
str.Insert(0, (a.data + 10 - b.data - carry));
carry = 1;
}
a = a.next;
b = b.next;
}
return str.ToString();
}
- maksymas May 31, 2015Thank you all for the code. Find the code below that I came up with. I guess this is similar to zortlord solution. but it works in minimal lines of code. This is written on an assumption that I can modify the array. Please comment
public static void getAdjacent (int[,] array, int x, int y, int M , int N)
{
for(int xaxis = 0 ; xaxis < M ; xaxis ++)
{
for(int yaxis = 0; yaxis < N ; yaxis ++)
{
if(array[xaxis,yaxis] == 1)
{
Console.WriteLine(findImmediateAdjacent(array, xaxis, yaxis, M, N));
overall = string.Empty;
}
}
}
}
public static string overall = string.Empty;
public static string findImmediateAdjacent(int[,] array, int x, int y, int M , int N)
{
if((x>=M || y >=N || y< 0 || x<0))
return null;
if (array[x, y] != 1)
return null;
else
{
overall += "(" + (x + 1) + "," + (y + 1) + ')';
array[x, y] = 0;
}
findImmediateAdjacent(array, x - 1, y -1 , M, N);
findImmediateAdjacent(array, x - 1, y, M, N);
findImmediateAdjacent(array, x - 1, y + 1, M, N);
findImmediateAdjacent(array, x , y - 1, M, N);
findImmediateAdjacent(array, x , y, M, N);
findImmediateAdjacent(array, x, y + 1, M, N);
findImmediateAdjacent(array, x+1 , y + 1, M, N);
findImmediateAdjacent(array, x+1, y - 1, M, N);
findImmediateAdjacent(array, x+1, y, M, N);
return overall;
}
Time O(2N)
- maksymas July 26, 2017