tnutty2k8
BAN USER 0of 0 votes
AnswersGiven two strings s1, s2, write a function that returns true if s2 is a special substring s1. A special substring s2 is such that the s1 contains s2 where each character in s2 appears in sequence in s1, but there can be any characters in s1 in between the sequence.
 tnutty2k8 in United States
Example:
isSpecialSubstring('abcdefg', 'abc') => true
isSpecialSubstring('abcdefg', 'acg') => true
isSpecialSubstring('abcdefg', 'acb') => false;
The first two are abc and acg appears in 'abcdefg' in that order, although there might be multiple chars between the next character in s2.
The last one is false, because in 'acb' the character 'b' appears before the character 'c' in 'abcdefg'
Hope thats clear. Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersDesign a text based rpg.
 tnutty2k8 in United States
 Player can enter room.
 Room has 4 walls and items
 a wall can have door
 user can enter a different room if they chose a wall which has door.
 There is also a Enemy, which walks around different rooms. If present in the same room, takes away all your items
 A player has an inventory which has list of items
 a item can be food or weapon
User should be able to start a game and be given set options(in text) of what command to execute, like pick up item in current room, walk north, east, south, or west, or undo action to return to previous state. Report Duplicate  Flag  PURGE
Data Structures  0of 0 votes
AnswersGiven a matrix which each element can be the following:
0: not walkable
1: walkable
n: Integer > 1 and is distinct in matrix
Find the minimum number of path it takes to visit each n in ascending order starting from matrix[0][0]. Note matrix[0][0] will always be 1. Allowed moves are (up,right,down,left);
Example:input: [ [1,1,0,5] [0,1,1,4] ] Output: 5.
Starting from position (0,0) we need to visit next smallest n which is 4. Min Distance from (0,0) to (1,3) is 4.
 tnutty2k8 in United States
Starting from position (1,3) we need to visit next smallest n which is 5. Min Distance from (1,3) to (0,3) is 1.
Total Min Distance is 4 + 1 = 5
Edit:
Allowed moves are [up,right,down,left] Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersGiven the following input:
 tnutty2k8 in United States
Array: array of integer coordinates(x,y) of length N
return a integer M that represents the maximum number of points that falls within the same line.
Example:
Array: [ [0,0], [1,1], [3, 12] ]
Output: 2# [0,0] and [1,1] falls in the same line. [3,12] falls on a different line. Thus the maximum number of points that falls on the same line is 2 Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersGiven the following inputs:
 tnutty2k8 in United States
Array: Array of positive non repetitive integers of length N.
K: Integers in range of [2,N)
Target: A Target integer
return any subset of Array with K elements that sums up to target.
Example:
Array: [1,2,3,4,5]
K: 2
T: 6
Output: [1,5]
Array: [1,2,3,4,5]
K: 3
T: 6
Output: [1,2,3]
Array: [1,2,3,4,5]
K: 4,
T: 11
Output: [1,2,3,5] Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersGiven a tree print in level zigzag order.
 tnutty2k8 in United StatesExample suppose we have the given tree structure: 1 2 3 4 5 6 it should print: 1 3 2 4 5 6 First level prints left to right. Then next level prints right to left. Alternating for each level. Assume the following node structure: Node { data: Integer, left: Node, right: Node, parent: Node, }
 Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswerDesign a system that supports updating table with options to discard the updates. It should have the following functions:
 create(String: rowName) #cannot be called until startTransaction has been called  delete(String: rowName) #cannot be called until startTransaction has been called  update(String: rowName) #cannot be called until startTransaction has been called  startTransaction() #start transaction operations( create/delete/update)  commitTransaction() #apply transaction to the actual Table( can be arrayofobjects )  discardTransaction() #discard any transaction applied thus far
Rough impl is acceptable as long as the design is displayed correctly.
 tnutty2k8 in United States Report Duplicate  Flag  PURGE
Data Structures  0of 0 votes
AnswersCompress String with character and its count.
 tnutty2k8 in United States
Example: "aaabbba" > compress > "a3b3a1” Report Duplicate  Flag  PURGE
Web Developer Algorithm
If I'm reading the problem correctly and assuming we are allowed to modify the input array.
 Then we can simply find all max valued indices and Infinity index( will only be one Infinity)
 If no Infinity index, set the first index in maxvaluedindices to Infinity and return that value
else cycle using the Infinity max valued index
The approach is the following.
 Parse each infix token
 If we find operator add to operator stack and set state to be operandAState
 If we find a character and if the state is operandAState, push character to operandA stack and set state to operandBState
 If we find a character and if the state is operandBState, then we found operandB, so take last operandA plus this new operandB character and the last operator then create a new operandA token
 Repeat until end of prefix character.
function isOperator(c) {
return "*+/".indexOf(c) !== 1;
}
function prefixToPostfix(prefixArray) {
var operators = [];
var operandAs = [];
var operandBs = [];
var state = 0;
for(var c of prefixArray) {
if (isOperator(c)) {
operators.push(c);
state = 1;
}else if(state === 1) { //operand A found
operandAs.push(c);
state = 2;
}else { //operand B found
//found operandB, means we have operandA and operator
//so group them to be the new operandA (+AB) => (AB+)
var operator = operators.pop();
var operandA = operandAs.pop();
var operandB = c;
var newOperandA = operandA + operandB + operator;
operandAs.push(newOperandA)
state = 2;
}
}
return operandAs.concat(operators).join('');
}
var tests = [
{ input: '+AB', expected: 'AB+'},
{ input: '+A*BC', expected: 'ABC*+'},
{ input: '*+ABC', expected: 'AB+C*'},
{ input: '*+AB+CD', expected: 'AB+CD+*'},
{ input: '+*AB*CD', expected: 'AB*CD*+'},
{ input: '+++ABCD', expected: 'AB+C+D+'},
].forEach( (test, index) => {
var postfix = prefixToPostfix(test.input);
var isExpected = postfix === test.expected;
console.log('Test: ' + index + ' passed = ' + isExpected);
});

tnutty2k8
September 19, 2017 Can you clarify the problem with input and expected output? At first glance, a hashmap would be efficient for findStockPriceAtGivenTimeStamp, but for deleteAndGetMinimumStockPriceForToday I need some input/out examples to detail its implementation( i.e minHeap or even extra min variable in each hash entry might suffice, or another hashMap to hold day's min). Can you clarify the problem more?
 tnutty2k8 September 19, 2017 O(n^2)
 Given s1 and s2
 For each substring(i, s2.length) check if substring is in s1
 if so print substring
 O(n) #on average
 Given s1 and s2
 Create suffix hash of s1
 Ex: s1 = 'abc'
 suffix hash = { 'a': 'a', 'abc' : 'abc': 'b': 'b', 'bc': 'bc': 'c': 'c' }
 For each suffix in s2, check hash if exist print

tnutty2k8
September 15, 2017 You can long poll but for interview a better answer would be to use sockets such that you create a connection from client to server, and now server can push notification to you when events happens. This in contrast to long polling is less stressful on client as it does not use up as much resource polling.
Its hard to talk about the design here, but I'll give a general overview of how one might go about implementing this at a general level:
 Visual Layer:
 GameModel: Current GameModel fetched from api (just some json data model)
 GameRender: Given a gameModel will render the chess game
 Create connection with api
 onUpdate: update current gameModel and rerender game
 Api Layer
 /get/:create
 Creates a brand new game model and returns the game model
 /get/gameModel/:gameId
 Given game id will query database to get the latest gameModel
 /get/games/:playerId
 Given player id, will return array of gameId that playerId has created
 /post/update/
 Will update the game with the latest game model. Latest game model is stored in the body of the post request
 Persistance Layer
 Can choose between sql or nosql. For simplicity, lets pick mongodb which allows us to store
json models. This data we store can be optimized and will effect how efficient our request per second is in API layer
#General Userflow
1) User creates a opens up app
 App checks if user has any game played via /get/games/playerId
 App shows all games played if any
2) User can either create new game, or click on one of the played game which has a gameId
 If clicking on a played game, we have the game id so call /get/gameModel:gameId
 get the game model and render it
 If creating new game, call /get/create, which returns a new gameModel
 get the game model and render it
3) Once game model is rendered wait for user to make move
 Store the move in the game model
 call /post/:gameId with the current gameId and its gameModel in body of the request
4) Backend accepts the /post/update request
 Updates database with the new gameModel for the given gameId
 Updates database with { gameId: gameId, lastPlayer: gameMode.playerId }
 For gameId get all players in the game from Database (we may have {gameId: [array of playerid]} in db)
 Now we have gameModel.playerId and allPlayerId, with that we can get the next playerId
 Check socket if next playerId is connected, if so, send update gameModel
 If not then when next playerId connects, it will be their turn
There are few details I haven't talked about, like what exactly does the gameModel look like?
Here is one way it could look :
GameModel:
playerId: String #a unique player id
gameId: String #a unique game id
historyOfMoves: Array #Array of moves which we can use to render the chessGame
There is obviously more to this, but thats a general overview. As for scaling, the default answer is to create multiple clusters of API which is gated by a load balancer. So when client request api endpoint, the load balancer intercepts the request, and delegates to a proper server which handles our restful request. And if we need to scale we can simply increase the number of clusters we have to handle more request.
I hope that was helpful to start.
To not use extra space we can simply use the array as the visited map. Each time we visit a element we can overwrite it with a special value marking it visited.
function hasCycles(input) {
var visitedMarker = 1;
var currentIndex = 0;
for(var i = 0; i < input.length; ++i) {
var nextIndex = input[currentIndex];
if (input[nextIndex] === visitedMarker) {
return true;
}
input[currentIndex] = visitedMarker;
currentIndex = nextIndex;
}
return false;
}
var tests = [
[0,1,5,4,3,5], //true
[1,2,3,4,5,0], //true
[1,2,3,4,5,5], //false
[1,2,4,4,5,5] //false
].forEach(function(test) {
console.log(test + ' hasCycles => ' + hasCycles(test) );
})

tnutty2k8
September 14, 2017 Here is a non recursive solution:
function mult(input) {
var left = input.length ? input.shift() : [];
while(input.length) {
var temp = [];
for(var i = 0; i < left.length; ++i) {
for(var j = 0; j < input[0].length; ++j) {
var item = (left[i] + input[0][j]);
temp.push(item);
}
}
input.shift();
left = temp;
}
return left;
}
var tests = [
[],
[
['a', 'b'],
['c', 'd']
],
[
['a', 'b'],
['c', 'd'],
['e', 'f']
],
];
tests.forEach(function(test) {
console.log( mult(test) );
});

tnutty2k8
September 14, 2017 Similar idea:
function mult(left, rest, index) {
if (rest.length === index) {
console.log(left);
return;
}
var current = rest[index];
for(var i = 0; i < current.length; ++i) {
left.push(current[i]);
mult(left, rest, index + 1);
left.pop();
}
}
var tests = [
[],
[
['a', 'b'],
['c', 'd']
],
[
['a', 'b'],
['c', 'd'],
['e', 'f']
],
];
tests.forEach(function(test) {
mult([], test, 0);
//0: []
//1: ["a", "c"] ["a", "d"] ["b", "c"] ["b", "d"]
//2: ["a", "c", "e"] ["a", "c", "f"]["a", "d", "e"]["a", "d", "f"]["b", "c", "e"]["b", "c", "f"]["b", "d", "e"]["b", "d", "f"]
})

tnutty2k8
September 14, 2017 @markarand, is that O(nlogn)?
Maybe I'm misinterpreting the problem, if each element is K length away from its sorted position, wouldn't a first easy solution be, find minimum element index, its index is K, then we just have to shift each element K position.
From N stones, if use can select [1,L] number of stones, I believe whichever user is left with the L + 1, stones is the loser. For example:
N = 5; L = 2; x = stone; L + 1 = 3
 xxxxx
 lets put visual group to see better
 (xx)x(xx)
 Starting from left, whichever user empties the first group (xx) first, will win.
 ex: user1 picks 2 stone so we have: x(xx). User1 emptied first group.
 Now user2 can pick 1 or 2 stones but will lose
 ex: user1 picks 1 stone so we have: (x)x(xx).
 Now user2 can pick 1 stone to win; he would empty group first.
 Using the same idea lets try it for higher N
 N = 8
 L = 2
 xxxxxxxx
 (xx)x(xx)x(xx)
 With the same idea, whichever user leaves group1 first can win if played perfect.
Trying it with different parameter:
 N = 8
 L = 3
 x(xxx)x(xxx)
 with the above since we don't start in a group, the first user can lose. Assume user2 emptied group first.
I think with the above idea would work, we just need to calculate whether the current user is in first group or not, and from that can deduce if he can win if played perfectly.
Below is a sample code
function stonePlay(N, L) {
var numberOfStonesInPlay = N;
var maxPickCount = L;
var i = 0;
var isInGroup = true;
var direction = 1;
while(i < numberOfStonesInPlay) {
if (direction === 1) { //sum group
i += maxPickCount;
isInGroup = true;
direction = 2;
}else {
i++;
isInGroup = false;
direction = 1;
}
}
return isInGroup;
}
console.log('can player1 win: ' + stonePlay(5, 2) ); //true
console.log('can player1 win: ' + stonePlay(8, 2) ); //true
console.log('can player1 win: ' + stonePlay(8, 3) ); //false
I compared the result with the result of @tiandiao123 shows, and it seems to match up for the few adhoc input I've tested with. Note I ignored K because for this problem I don't think K is relevant. Maybe someone can comment further. The above might be totally naive, in that case I apologize. I just dont think we need to apply recursion here.
Best.
What does K the torch represent? What does 'maximum of x people time' mean? Is it the maximum time a person in group takes?
But it seems like what we want to do is minimize the time required for all people to cross the bridge. If we let T = [a1,a2,...,an], we can sort T in descending order. Since x number of people can cross the bridge at a time, we can simply group T into T/x groups and move each group one at a time. To make it more clear, take the following instance:
N = 7 #number of people
T = [1,2,3,1,2,5,4] #time each person takes to cross
x = 3; #number of people that can pass per round
 sort T: [5,4,3,2,2,1,1]
 group T into T/x groups
 group1: [5,4,3]
 group2: [2,2,1]
 group3: [1]
 Now group1 crosses bridge, it takes Max([5,4,3]) = 5
 Now group2 crosses bridge, it takes Max([2,2,1]) = 2
 Now group3 crosses bridge, it takes Max([1]) = 1
 Total time: 5 + 2 + 1 = 7
The above is just a greed approach. But I maybe misinterpreting the question, @neer any more details or comments?
 tnutty2k8 August 31, 2017I would go with simple approach to start:
//using psuedo code
class Seat
 id: int
 occupied: String
class Row
 seats[] : Seat #array of Seat
 nextAvailableSeatIndex
 hasConsecutive(int k);
 seat(int numberOfPeople)
 fit(int numberOfPeople)
class Bus:
 rows[]: Row #array of Row
 booker: Booker
class Booker:
 rows[]: Row #reference to the row
 book(int K)
 for each row in rows
 if row.hasConsecutive(K)
 row.seat(K);
 return row;
 var rowIndex : 0
 var result: []
 var count = K;
 while (count > 0 && rowIndex < rows.length
 result += rows[rowIndex].fit( count ); //fit much as possible. Returns seats filled
 count = K  result.length
 ++rowIndex;
 return result;

tnutty2k8
August 31, 2017 Can a city have multiple paths to different cities or just one path to a city? I would assume based on the question it only has one path, else we need more information because if city1 goes to city3, and city2 goes to city1 and city3, then how do we know which path user chooses to get to city3 from city2, since it can be (city2>city1>city3) or (city2>city3)?
With that said I think the question basically describes a directed graph with only one outgoing edge and multiple incoming edges and no cycle.
If the above assumptions are correct then we basically have visit each node and its children summing up the incoming people count.
 Assume a node has three property: {city:String, nPeople:Integer, totalVisitor: Integer}
 for each node in tree
 currentSum: node.nPeople
 visitChildren( node, currentSum)
 visitChildren( node, currentSum )
 var current = node;
 while current != null
 currentSum += current.nPeople;
 current.totalVisitor += currentSum;
 current.children.forEach child
 visitChildren( child, currentSum );

tnutty2k8
August 31, 2017 @koustav, would you mind explaining your algo at a high level? I think your algo is creating max heap and simulating the arrangement?
The idea I had was to use minheap. Basic idea is to count the frequencies of chars, then create create min heap based on those frequency. With the min heap, we would then check if the difference of the children with current is <= 1, else its not possible for such arrangement.
For example:
 input: "AAABBCCDEF"
 calculate frequency of each character: [3,2,2,1,1,1]
 create min heap: [1,2,1,3,2,1]
1
2 1
3 2 1
 now for each node calculate Math.abs( (leftChild+rightChild)  current ) and return that value.
 At root node, the tree is arrangable only if the Math.abs( (leftChild+rightChild)  current ) <= 1
That seems like it would work, any thoughts? I'll test it out the idea in bit, but wondering if anyone had thoughts?
 tnutty2k8 August 31, 2017I feel like theres O(n) solution to this, but currently I'm only able to come up with two solutions:
 O(n^2): for each item in A, loop in B finding smaller elements
 O(nlogn):
 Sort array B: O(nlogn)
 for each item in A O(n)
 use modified binary search to find first index less than or equal to current item O(logn)
 the number of items lower than or equal to is the index value.
Anyone have a more efficient algo in mind?
 tnutty2k8 August 31, 2017Actually I found the problem statement which I believe is the same problem asked here:
8 ball problem. if given 8 balls with only one ball being a
lighter weight and all other 7 being the same weight and
given a scale, how will you find the light weight ball. do
this in minimum number of steps
My initial thought is to divide an conquer which gives
log(N)/log(2)
so in case of 8ball, it would be
log(8)/log(2) = 3 steps
, but you mentioned it can be done in two steps.
The above would be true depending on the meaning of 'scale'.
 If scale allows you to weigh one group at a time( ex Think of weighing yourself on scale, only one person at a time makes sense ), then I believe
log(8)/log(2)
would be true.
 If scale allows you to weight two group at a time( another type of scale ) then (after cheating and reading answer (see /question?id=8119690) ) they mention the answer is
ceil(log(N)/log(3))
But its only that because they skip the last ball weighin using slick process of elimination. So technically they don't weight all the balls.
While this problem is interesting, I'm not a fan of it, especially for a programming interview position( assuming ).
Best.
What are we designing for? Space? Time?
If space is available and we can keep all data:
Solution #1
 Simple solution keep sorted list O(nlogn)
 return proper slice of list for the queried time O(logN)
Solution #2
 Create BST and insert into tree O(logN)
 return subtree whos time is less than the queried time O(logN)
If for space, assume were feed the hashtags one at time
Solution #1
 N = 10
 Create three sorted bins of size N elements. For 1min, 10min, 1hr
 create helper function refresh:
 In bin1Min, remove expired items, and bubble up to bin10Min or bin1hr if applicable
 in bin10Min, remove expired items, and bubble up to bin1hr if applicable
 in bin1hr, remove expired items.
 on insert
 call refresh()
 insert new item into proper bin based on current time difference
 find insert position( selection sort since N is small )
 if over threshold of elements, insert new item in front, and pop last
 if poped, bubble up if applicable
Do you guys think the above solution would work? Would love some feedback.
 tnutty2k8 August 29, 2017 Parse the input
 Build a directed graph ( which might have cycles )
 Figure out the start node
 Transverse from the start node until null next while printing the node value
In code here is a sample implementation:
function Node(val, next, parent) {
this.val = val;
this.next = next;
this.parent = parent;
}
function buildGraphFromInput(input) {
var instanceMap = {};
for(var i = 0; i < input.length; ++i) {
var entry = input[i];
var image = entry[0];
var dep = entry[1];
var node = instanceMap[image]  new Node(image);
var next = instanceMap[dep]  new Node(dep);
node.next = next;
next.parent = node;
instanceMap[image] = node;
instanceMap[dep] = next;
}
return instanceMap;
}
function getStartNode(input, instanceMap) {
var isVisited = {};
for(var i = 0; i < input.length; ++i) {
var image = input[i][0];
var node = instanceMap[image];
if (!isVisited[node.val]) {
var ancestor = getAncestorIfNoCycle(node, isVisited);
if (ancestor) {
return ancestor;
}
}
}
return null;
}
function getAncestorIfNoCycle(node, isVisited) {
var rootParent = getAncestor(node);
var current = rootParent;
while(current) {
if (!isVisited[current.val]) {
isVisited[current.val] = true;
current = current.next;
}else {
//cycle
return null;
}
}
return rootParent;
}
function getAncestor(node) {
var seen = {};
while(!seen[node.val] && node.parent) {
seen[node.val] = true;
node = node.parent;
}
return node;
}
function getExecutionOrder(node) {
var result = [];
while(node) {
result.unshift( node.val );
node = node.next;
}
return result;
}
var inputWithCycle = [
['b','c'],
['c','d'],
['a','b'],
['d','e'],
['e','c'],
['f','g']
];
var inputWithCycle2 = [
['python', 'numpy'],
['numpy', 'python'],
['tenstorflow', 'ubuntu']
];
var inputWithoutCycle = [
['master','ubuntu'],
['numpy', 'master'],
['tensorflow', 'numpy']
];
var test = [inputWithoutCycle, inputWithCycle, inputWithCycle2]
test.forEach(function(input, testNumber){
var instanceGraph = buildGraphFromInput( input );
var startNode = getStartNode(input, instanceGraph );
var result = getExecutionOrder( startNode );
console.log('testNumber: ' + testNumber + ' = ' + result.join('<'));
});
Outputs:
"testNumber: 0 = ubuntu<master<numpy<tensorflow"
"testNumber: 1 = g<f"
"testNumber: 2 = ubuntu<tenstorflow"
JSBin: jsbin.com/zaqehej/1/edit?js,console

tnutty2k8
August 28, 2017 @agrawal so bossy :P
Just kidding anyways I was hoping the code was clear enough. The idea is to go to each node and serialize the node with its left subtree or right subtree. For example with the current tree
2
1 3
the serialize algo transverse each node and wraps its pharenthesis with its children, for example in the above tree when we are at node with value 2, we do
"(2 leftSubtree rightSubtree)
, where leftSubTree is serialized result of node with value 1 and rightSubtree is the serialized result of node with value 3, which at end will all result in
(2 (1)(3) )
To deserialize we simple parse the token into three parts [ nodeValue, leftSubtreeToken, rightSubtreeToken] then we deserialize leftSubtreeToken and rightSubtreeToken and use that result as left/right children for the current node. For example with the above serialized token parsing at first iterations would result in [2, "(1)", "(3)"]. Now current node value is 2, and we pass (1) to the same deserialize function and use that result as the left tree and similar for right tree.
Your best best is to step through code if you want to learn more or ask specific question.
Best.
At first pass I would suggest the following algorithm:
1 get (min,max) angle from the two edges
2 see how many points falls within [min,max] angle
3 increment [min,max] by the fixed angle so that next range is [min + fixedAngle, max + fixedAngle]
4 repeat step 23 while the min degree in [min,max] is less than 360.
One key point is in step 2. How do we determine how many points fall within [min,max] angle?
 1 go through each points, find its angle, if its in between [min,max] save that point in list
 2 or preprocess points into bins of [min + fixedAngle * i, max + fixedAngle * i].
 2.a then simply check the proper bin
geeksforgeeks.org/kthlargestelementinastream/
Edit:
Although as pointed out k is not the index but the number of elements, we can apply the same concept:
Solution #1 O(k)
 Keep sorted array of size K descending
 on every new element
 check if larger than last
 if so pop last( smallest ) and insert new item
Solution #2 O(logk)
 Use Binary Search Tree
 on insert check if item is larger than smallest
 if so remove smallest and insert new item
Solution #3 O(logk) but faster min lookup
 Use MinHeap
 on insert check if item is larger than smallest
 if so remove smallest and insert new item

tnutty2k8
August 26, 2017 The idea is just to navigate in a spiral direction using a direction state system.
JSBin: jsbin.com/guhafom/1/edit?js,console
var data = [
[1,2,3,4],
[5,6,7,8],
[9,10,11,12]
];
(function(data) {
var direction = 0;
var result = [];
while(data.length) {
switch(direction) {
case 0: { //right
var row = data.shift();
result = result.concat(row);
direction = 1;
break;
}
case 1: { //down
var cells = [];
data.forEach(function(row) {
row && cells.push( row.pop() );
});
result = result.concat(cells);
direction = 2;
break;
}
case 2: { //left
var row = data.pop();
result = result.concat(row.reverse());
direction = 3;
break;
}
case 3: { //up
var cells = [];
data.forEach(function(row) {
row && cells.push( row.shift() );
});
result = result.concat(cells);
direction = 0;
break;
}
}
}
console.log(result);
})(data);
//outputs: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
Just notice the recursive requirement. One recursive solution is to put direction in param and call the function with the next direction to operate on. The base case is data is not empty else return the sliced data.
 tnutty2k8 August 26, 2017@CC:
Yep, just something like this (although not tested)
var field = [ ... ];
var targets = getTargets();
var startPos = getPossibleStartingPosition();
var startPosWithCost = startPos.map(function(start) {
return { position: start, cost: getMinCostBFS(field, start, targets[0]) };
});
var startPosSortedAsc = startPosWithCost.sort(function(a,b) { return b.cost  a.cost; });
var bestStartPos = startPosSortedAsc[0].position;

tnutty2k8
August 26, 2017 @CC:
Here's BFS solution, its simple enough. Idea is to implement BFS to transverse graph until we hit the target. While transversing, keep a parent hash. Once we hit the target, as chris mentioned it will be one of the shortest path so we exit the loop, and use the parent hash to now just transverse up the parent hash tree. Here's the full code
jsbin.com/tedalux/5/edit?js,console
//see getMinCostBFS
function levelField(field){
var targets = getTargetDescending(field);
var totalCost = 0;
var starting = [0,0];
for(var i = 0; i < targets.length; ++i) {
var ending = targets[i];
var v = {};
//var cost = getMinCost(field, starting[0], starting[1], ending, v);
var cost = getMinCostBFS(field, starting, ending);
if (cost < 0) {
return 1; //no valid path!
}else {
totalCost += cost;
field[ending[0]][ending[1]] = 1;
}
starting = ending;
}
return totalCost  1;
}
var data = [
[1,1,0,5],
[0,1,1,4],
]
console.log( 'total cost: ' + levelField(data) );
function getMinCost(field, r, c, end,v) {
var k = r.toString() + c.toString();
if (v[k] === 1) { return Infinity; }
//if out of range return
if (!isRange(r, 0, field.length)) {
return Infinity;
}else if(!isRange(c, 0, field[0].length)) {
return Infinity;
}else if (r === end[0] && c === end[1]) { //found
return 0;
}else if(field[r][c] !== 1) { //cant move here
return Infinity;
}else {
v[k] = 1;
var min = 1 + Math.min(
//cost to move right
getMinCost(field, r, c+1, end,v),
//cost to move down
getMinCost(field, r+1, c, end,v),
//cost to move left
getMinCost(field, r, c1, end,v),
//cost to move up
getMinCost(field, r1, c, end,v)
);
v[k] = min;
return v[k];
}
}
function getMinCostBFS(field, start, end) {
var queue = [start];
var parent = {start: null};
var visited = {start: true};
var rowSize = field.length;
var colSize = field[0].length;
while (queue.length) {
var node = queue.shift();
var neighbors = [];
var r = node[0];
var c = node[1];
visited[node] = true;
if (node === end) {
//we found target
break;
}else {
//right neigh if valid
if (c < colSize  1) { neighbors.push([r,c+1]);}
//down neigh if valid
if (r < rowSize  1) { neighbors.push([r+1, c]);}
//left neigh if valid
if (c > 0) { neighbors.push([r, c1]); }
//up neigh if valid
if (r > 0) { neighbors.push([r1, c]); }
//add unvisited neighbor
neighbors.forEach(function(neighbor) {
if (!visited[neighbor] && field[neighbor[0]][neighbor[1]] >= 1) {
queue.push( neighbor );
parent[neighbor] = node.slice();
}
});
}
}
var cost = 0;
var target = end;
target.length = 2; //keep only (x,y)
if (!parent[target]) {
cost = 1; //target never reached so no path exists
}else {
while(parent[target]) {
target = parent[target];
++cost;
}
}
return cost;
}
function isRange(target,x,y) {
return x <= target && target < y;
}
function getTargetDescending(field) {
var result = [];
for(var r = 0; r < field.length; ++r) {
var row = field[r];
for(var c = 0; c < row.length; ++c) {
if (row[c] > 1) {
result.push([r,c, row[c] ]);
}
}
}
result = result.sort(function(b, a) {
return a[2] < b[2] ? 1 : a[2] > b[2] ? 1 : 0;
});
return result;
}

tnutty2k8
August 25, 2017 @CC:
No not the last elements in target but the the first. For example
starting point can be : [0,0], [0,n1], [m1, 0], [m1,n1] #mxn grid
targets can be : [ [1,1], [3,5], [2,2] ]; #assume valid index
We need to see which is the shortest path from each of starting point to [1,1]. From that we found the best starting position, then can use that as the starting path for each targets going forward.
I dont think memoization would help here. We only transverse all walkable path. A better solution as suggested by chris can be to use BFS. Are you finding the solution to timeout for certain inputs?
@CC: That's changing the problem rules. If we're able to pick a starting position, we can simply pick the first smallest target ( ex. (1,2) in your input ). If we're given a choice starting from any walkable corner, we have to find the min cost from each walkable corner to the first target and pick the min cost corner. We have to actually find the mincost because although a corner might be walkable, there might not exist a path from corner to the target, so have to transverse.
 tnutty2k8 August 25, 2017@CC: What input are you using? If there isn't a valid path from X to Y, then it will return 1.
@chris: Definitely fair point, also since its 2dimension, wouldn't (x,y) key be always unique in this case. I'll definitely take look at your suggestions, my main focus is solving problems at the moment, then will dive into optimizations.
The simple solution is to use recursion here. The basic thought is the max sum is current element plus next element or current element plus one after next element.
In code :
jsbin.com/pixinad/edit?js,console
function maxSumHelper(data, index) {
if (index >= data.length) {
return 0;
}else {
var n1 = data[index];
return Math.max(
n1 + maxSumHelper(data, index + 1), //sum with the current plus next
n1 + maxSumHelper(data, index + 2) //sum with the current plus one after next
);
}
}
function maxSum(data) {
return Math.max(
maxSumHelper(data, 0), //sum with the first element
maxSumHelper(data, 1) //sum without the first element
);
}
var data1 = [10, 20, 30, 10, 50, 40, 50, 1, 3];
console.log('maxSum: ' + maxSum(data1)); //outputs 89
var data2 = [1, 2, 3, 4, 5];
console.log('maxSum: ' + maxSum(data2)); //outputs 6

tnutty2k8
August 25, 2017 Just sample, albiet not the cleanest implementation:
JSBin: jsbin.com/habamet/2/edit?js,console
function Node(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}
var root = new Node(
1,
new Node(2, new Node(3, null, new Node(4)) ),
new Node(5, new Node(6) )
);
function printTree(node) {
if (node) {
var left = printTree(node.left);
var mid = [node.val];
var right = printTree(node.right);
return mid.concat(left).concat(right);
}else return [];
}
function serializeTree(node) {
if (node) {
var s0 = node.val;
var left = serializeTree(node.left);
var right = serializeTree(node.right)
var s1 = left.length ? '(' + left + ')' : '';
var s2 = right.length ? '(' + right + ')' : '';
var s = s1.length  s2.length ? '(' + s0 + s1 + s2 + ')' : '' +s0;
return s;
}else {
return '';
}
}
function deserializeTree(serialized) {
if (!serialized.length) {
return null;
}else {
var token = parse(serialized);
//console.log(token);
var left = deserializeTree(token.left);
var right = deserializeTree(token.right);
var node = new Node(token.val, left, right);
return node;
}
}
function parse(serialized) {
function getToken(s, offset) {
if (!s.length  s[offset] !== '(') return '';
var count = 0;
var r = '';
for(var i = offset; i < serialized.length; ++i) {
var c = serialized[i];
if (c === '(') ++count;
else if (c === ')') count;
r+= c;
if (count <= 0) break;
}
offset = i;
return r;
}
var offset = serialized.match(/\d/).index;
var val = serialized[offset];
var left = getToken(serialized, offset + 1);
var right = getToken(serialized, offset + 1 + left.length );
return {val: val, left: left, right: right};
}
var serialized = serializeTree(root);
console.log('serialized: ' + serialized );
var copyNode = deserializeTree( serialized );
console.log( 'deserialized: ' + printTree(copyNode) );
Output:
"serialized: (1((2((3(4)))))((5(6))))"
"deserialized: 1,2,3,4,5,6"

tnutty2k8
August 24, 2017 Pretty much ended doing something similar, without any optimizations.
function levelField(field){
var targets = getTargetDescending(field);
var totalCost = 0;
var starting = [0,0];
for(var i = 0; i < targets.length; ++i) {
var ending = targets[i];
var v = {};
var cost = getMinCost(field, starting[0], starting[1], ending, v);
if (cost < 0) {
return 1; //no valid path!
}else {
totalCost += cost;
field[ending[0]][ending[1]] = 1;
}
starting = ending;
}
return totalCost  1;
}
var data = [
[1,1,0,5],
[0,1,1,4],
]
console.log( 'total cost: ' + levelField(data) );
function getMinCost(field, r, c, end,v) {
var k = r.toString() + c.toString();
if (v[k] === 1) { return Infinity; }
//if out of range return
if (!isRange(r, 0, field.length)) {
return Infinity;
}else if(!isRange(c, 0, field[0].length)) {
return Infinity;
}else if (r === end[0] && c === end[1]) { //found
return 0;
}else if(field[r][c] !== 1) { //cant move here
return Infinity;
}else {
v[k] = 1;
var min = 1 + Math.min(
//cost to move right
getMinCost(field, r, c+1, end,v),
//cost to move down
getMinCost(field, r+1, c, end,v),
//cost to move left
getMinCost(field, r, c1, end,v),
//cost to move up
getMinCost(field, r1, c, end,v)
);
v[k] = min;
return v[k];
}
}
function isRange(target,x,y) {
return x <= target && target < y;
}
function getTargetDescending(field) {
var result = [];
for(var r = 0; r < field.length; ++r) {
var row = field[r];
for(var c = 0; c < row.length; ++c) {
if (row[c] > 1) {
result.push([r,c, row[c] ]);
}
}
}
result = result.sort(function(b, a) {
return a[2] < b[2] ? 1 : a[2] > b[2] ? 1 : 0;
});
return result;
}

tnutty2k8
August 24, 2017 Good idea Chris. Here's simple implementation.
JSBin: jsbin.com/gilemoq/edit?js,console
function Node(word, friends) {
this.word = word;
this.friends = friends;
}
function createGraph(start, dict, visited) {
visited[start] = true;
var friendWords = getFriendsWords(start, dict);
var friends = friendWords.reduce(function(f, fWord) {
if (!visited[fWord]) {
f = f.concat( createGraph(fWord, dict, Object.create(visited)) );
}
return f;
}, []);
var node = new Node(start, friends);
return node;
}
function getFriendsWords(word, dict) {
var result = [];
for(var i = 0; i < dict.length; ++i) {
var charDiffCount = getCharDiffCount(word, dict[i]);
if (charDiffCount === 1) {
result.push( dict[i] );
}
}
return result;
}
function getCharDiffCount(a, b) {
var count = Math.abs(a.length  b.length);
for(var i = 0; i < a.length; ++i) {
if (a[i] !== b[i] ) ++count;
}
return count;
}
function printGraph(node) {
if (node) {
console.log(node.word);
node.friends.forEach(printGraph);
}
}
function findShortestPath(root, target, path, result) {
if (!root) {
return;
}else if(root.word === target) {
var currentMinLength = result.minPath ? result.minPath.length : Infinity;
result.minPath = path.length < currentMinLength ? path.slice() : result.minPath;
}else {
var currentPath = [root.word];
var friends = root.friends;
for(var i = 0; i < friends.length; ++i) {
var friend = friends[i];
path.push( friend.word );
findShortestPath(friend, target, path, result);
path.pop();
}
}
}
var start = 'SAT';
var end = 'PAN';
var dict = ['RAT', 'PAT'].concat( end );
var root = createGraph(start, dict, {});
var result = {};
findShortestPath(root, end, [], result);
console.log( 'minPath: ' + start + '>' + result.minPath.join('>') );

tnutty2k8
August 24, 2017 @fernando,
Youre right, I didn't implement the full details in that code, it was more meant to be a demonstration of the logic, but yea, it would still need to handle duplicates. There are few way we can enforce unique solution. One is to actually splice on the actual input array, example
array.splice(i, 1);
That way on each iteration we remove the current element which will not be present for next iteration. This also prunes some premutations.
 tnutty2k8 August 19, 2017The solution i came up with during the interview was something of this sort:
function sumTwo(array, target) { ... } //O(n) using hashing to return [x,y] such that x+y=target
function sumNK(array, k, target) {
if (k === 2 ) {
return sumTwo(array, target);
}else {
for(var i = 0; i < array.length; ++i) {
var subTarget = target  array[i];
var subArray = array.slice().splice(i, 1); //make copy and remove currently used elem
var subResult = sumNK(subArray, k  1, subTarget);
//save possible subResult if valid and return it....
}
}
}

tnutty2k8
August 18, 2017 Three core ideas since the create/delete/update relies on structure of start/commit/discard
1) When startTransaction is started, operate on a copy of the table then set or discard depending on commit/discard has been called
2) When startTransaction is started, queue up the operations, then only apply the operations if commit has been called else discard the operations
3) Have each operation have commit/discard feature. Each create operation keeps the rowName previous state before modifying the table. If commit is called, it discards the previous rowState and keeps the applied changes. Else if discard is called, it reapplies the prevRow state to the table. The higherLevel class would call commit/discard on each operations. Need to keep track of what operations has been applied.
Open Chat in New Window
@penchief: Do you have a answer/idea to this outside of using probability as Chris suggested.
 tnutty2k8 September 20, 2017