CareerCup

right. somehow I did not consider the order of the strings in the set.

javascript:

//var input = ['abc', 'cde', 'edf','fga'];
var input = ['abc' , 'cba', 'dfg']

var result = true;
for(var i=0;i<input.length;i++){
  var prevString = input[i];
  var nextString = i==input.length - 1 ? input[0] : input[i+1];
  var c1 = prevString[prevString.length - 1];
  var c2 = nextString[0];
  if(c1!=c2){
    result = false;
    break;
  }
}
console.log(result);

As I understand the Kadane's algorithm works only when the input array containing at least one positive number. The question does not tell anything about it..So I would start with clarifying..

Cool, one minor improvement would be just decreasing the number of recursive calls and getting rid of extra memory, here is my version(not working for a corner cases like "hello","*" but the idea seems to be right:

function match_internal(s1, s2, s1Index, s2Index){
  if(s1Index==s1.length && s2Index==s2.length)
    return true;
  while(s2[s2Index]!='*' && s2[s2Index]!='?' && s1Index < s1.length && s2Index < s2.length){
    if(s1[s1Index]!=s2[s2Index])
      return false;
    s1Index++;
    s2Index++;
  }
  if(s2[s2Index]=='?')
    return match_internal(s1, s2, s1Index, s2Index+1) || match_internal(s1,s2,s1Index+1, s2Index+1);
  if(s2[s2Index]=='*'){
    var zeroMatch = match_internal(s1, s2, s1Index, s2Index+1);
    if(zeroMatch)
      return true;
    var match = false;  
    for(var i=s1Index+1; i<s1.length;i++){
      match = match || match_internal(s1, s2, i, s2Index+1);
    }
    return match;
  }  
}

Yeah maybe u are right, thanks again!

Thanks for your valuable comment, Mr. Artist, I am glad that someone is tracking my messages :) So good to not feel lonely.

Strictly speaking this code is invalid as well. The output should be the array, not the array list because the input is array. At least you should call output.toArray() or something like that.

Then, this code is ignoring the fact that all the elements of the input array are 10 bit integers and is using Integer type(32 bit), so 40Mb of extra memory instead of 10Mb(or 20Mb for 16-bit integers) is being used.
Finally your code is 1) invalid 2) not-optimal. I would be shocked if you were hired with this level of answer :P

Okay, the code you have posted seems to be the 1st part of the counting sort(the code below copied from wikipedia article)

# allocate an array Count[0..k] ; THEN
# initialize each array cell to zero ; THEN
for each input item x:
    increment Count[key(x)]

You didn't complete the code, so strictly speaking it IS invalid

Then, the counting algorithm analysis clearly stays that because it uses arrays of length k + 1 and n, the total space usage of the algorithm is also O(n + k).

okay. counting sort is not in place algorithm, it needs O(N) extra memory. shouldn't it be considered as the stop sign?

Sorting usually implies that all the data from the input exist in the output.
The problem says that there are 10 million integers but the solution Mike provided gives 1024 integers, so it just loses the data and therefore seems to be incorrect. Am I missing something?
Also, consider the input that consists of 5 million of number 512 and 5 millions of number 3. The proposed solution does not produce the correct answer, doesn't it?

For a fixed w_set, can't we just keep all the letters contained in w_set(in form of sorted string). It's fixed so we don't need to calculate it each time. Then merge c_set input to sorted string(O(n * log n) and check if wset sting starts with cset string?

just realized that we need to output the positions of elements, not their values.

var m  = [
  [1,4,7],
  [2,5,8],
  [3,6,9]
  ];
  
var rows = m.length;
var cols = m[0].length;

var maxColumnsInRows = []; // index = row num, value: col num
var minRowsInColumns = [];

for(var i=0; i<rows;i++){
  maxColumnsInRows[i] = 0;
  minRowsInColumns[i] = 0;
}

for(var ri=0;ri<rows;ri++){
  for(var ci=0; ci<cols;ci++){
    var currentRowMaxColumn = maxColumnsInRows[ri];
    var currentColumnMinRow = minRowsInColumns[ci];
    var currentValue = m[ri][ci];
    if(currentValue > m[ri][currentRowMaxColumn])
      maxColumnsInRows[ri] = ci;
    if(currentValue < m[currentColumnMinRow][ci])
      minRowsInColumns[ci] = ri;
  }
}

for(ri=0; ri<rows;ri++){
  var maxCol = maxColumnsInRows[ri];
  var minRow = minRowsInColumns[maxCol];
  if(ri == minRow){
    console.log('row: ' + ri +' ,col: ' + maxCol);
  }
}

Javascript DP solution

var m = [
  [1,1,0],
  [0,1,1],
  [1,0,1]
  ];

var cutRows = 1, cutCols = 1;

function getNumberOfPaths(ri,ci){
  var paths = 0;
  if(ri<=cutRows - 1 && ci>=cols - cutCols)
    return 0;
  if(ri-1>=0) paths += m[ri-1][ci];
  if(ci-1>=0) paths += m[ri][ci-1];
  return paths;
}

var rows = m.length;
var cols = m[0].length;

m[0][0]=1;

for(var ri=0;ri<rows;ri++){
  for(var ci=0;ci<cols;ci++){
    if(ri===0 && ci===0) continue;
    m[ri][ci] = getNumberOfPaths(ri,ci);
}
}

console.log(m[rows-1][cols-1]);

This answer is correct, but this algorithm works for any input array, including the max-heap(min-heap). I suppose that the ideal answer should use the fact that input array is the max-heap(min-heap). The primitive optimization would be selecting the largest index from the two child because we know that they are both greater than(or less than) the parent item, so the code could be simplified, like:

maxChild = arr[left] > arr[right] ? left: right;
//swap values at rootIndex, maxChild

right..thanks for the comment

Agree, but, I think that tree of heap guarantees that the values of the next level nodes are all greater than the values on the nodes of the previous level and this is the key point; Here is the example of the code(JavaScript):

var array = [];

tree.breadthWalk(function(node){
  array.push(node);
  });

var size = array.length;
for(var i=size-1;i>=0;i--){
  var left = size - 2 - (size - 1 - i ) * 2;
  var right = left - 1;
  array[i].left = left < 0 ? null : array[left];
  array[i].right = right < 0 ? null : array[right];
}

tree.root = array[size-1];

Heap is binary tree where each child of a node has a value less than or equal to the node's own value(or greater or equal for min heap), so :
1. Perform breadth - first walk adding the heap values in the array. In the end you should get the sorted array.
2. Starting from the end of the array set the nodes value so that.
rootNode.Value = array[array.length-1]
rootNode.left.Value = array[array.length - 2];
rootNode.right.Value = array[array.length - 3];
etc..
the efficiency is O(n).

Build Ci-Di array and find the element from which we should start summing of all the array items so that the current sum is always greater than 0:

var stationsCapacity = [1,4,4,7];
var distances = [2,3,5,6];

var remainingGas = [];

for(var i=0; i<stationsCapacity.length;i++)
  remainingGas.push(stationsCapacity[i] - distances[i]);


var startStation;
for(var i=0; i<remainingGas.length;i++){
  var sum = remainingGas[i];
  if(sum < 0)
    continue;
  var fits = true;
  for(var j=i+1;j<remainingGas.length;j++){
    sum+=remainingGas[j];
    if(sum < 0){
      fits = false;
      break;
    }
  }
  if(sum>0){
    for(j=0;j<i;j++){
      sum+=remainingGas[j];
      if(sum < 0){
        fits = false;   
        break;
      }
    }
  }
  if(fits){
    startStation = i;
    break;
  }
}

console.log(startStation);

Javascript code:

function isBalanced(str){
  var stack = new Stack();
  for(var c=0;c<str.length;c++){
    var chr = str[c];
    if(isOpenBracket(chr)){
      stack.push(chr);
    }
    else if(isCloseBracket(chr)){
      var openBracket = stack.pop();
      if(!bracketsMatch(openBracket, chr))
        return false;
    }
  }
  return true;
}