CareerCup

@penchief: Do you have a answer/idea to this outside of using probability as Chris suggested.

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 max-valued-indices 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);
  
});

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?

- 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

Maybe someone could come up with a more optimized solution here.

- Greed solution won't return the optimal result
- Try every 2 set combination and return the best combination?

Anyone have ideas/hints on this?

A decent read -- en.wikipedia.org/wiki/Recommender_system
With that information you might be able to come up with a simple system that uses the collaboration or content based filtering technique. Content Based Filtering might be easier technique to apply.

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 re-render 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) );  
})

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) );
});

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"]
})

-hash with uid as key rest as value
-simple liner loop to find max consumption

@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?

I 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;

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 );

@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 min-heap. 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?

I 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?

*cough *cough * I hate this site broken functionalities *cough *cough

Actually 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 8-ball, 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 weigh-in 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.

I have no idea what this question is, can you provide more details on the question?

Another solution

while array is not empty
- Print first row and remove it
- rotate array 90 to left

Although not efficient, but can be really short solution in some languages (ex python)

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.

- 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

@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 2-3 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/kth-largest-element-in-a-stream/

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

@coder: Sure, post your code.

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.

@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;

@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, c-1, end,v),
        //cost to move up
        getMinCost(field, r-1, 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, c-1]); }
      //up neigh if valid
      if (r > 0) { neighbors.push([r-1, 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;
}

@CC:

No not the last elements in target but the the first. For example

starting point can be : [0,0], [0,n-1], [m-1, 0], [m-1,n-1] #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:

I think youd have to check all corner against the first target to find the best starting point. Note you don't have to check all corner against all the target, just the first target.

@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.

@CC:

This part of code

var starting = [0,0];

sets the initial starting point, which you can change. But note because of problem rules set, the starting point has to have '1' which means walkable, else it will return -1.

@CC:

[1,1,0,1]
[1,1,5,1];

Starting from (0,0) to get to (1,2) it takes 3 steps, so it outputs 3. I assume that offset is why you got 17 instead of 14 on the first input as well.

@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 2-dimension, 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

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"

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, c-1, end,v),
        //cost to move up
        getMinCost(field, r-1, 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;
}

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('->') );

@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.

@anaghakr89 -- this question was asked in a recent phone interview( one that I haven't seen before ).

The 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....
	}
   }
}

- Linear search finding begin and end index for values who lies within [K-C, K+C]
- Since data is sorted we can use binary search to find begin/end index of values that lies within [K-C, K+C]

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.

Forgive for a naive question but wouldn't generating a random index from range (0,rectangle.length] and using that as the selectedIndex work?

Allowed to use language's json parser or have to manually create our own?

- Adjecency List
- BFS