ashish.kaila
BAN USER- 1of 1 vote
AnswersDesign a collaborative text editor where each participant has infinite undo/redo. Consider the scenario where a user goes offline and then comes online and tries to undo/redo.
- ashish.kaila in United States| Report Duplicate | Flag | PURGE
Twitter Software Engineer / Developer Distributed Computing - 1of 1 vote
AnswersGiven a sorted array that is sorted by rotated, find a given number. For example take an array: 1 3 8 10 12 56 and rotate it so you have 10 12 56 1 3 8 and then find a candidate e.g. 3 in it.
- ashish.kaila in United States| Report Duplicate | Flag | PURGE
Twitter Software Engineer / Developer Arrays - 0of 0 votes
AnswersGiven a string representing sorted numbers with spaces print the count of each number. For example if the input string is: "1 1 2 3 4 4" then you should print 1:2, 2:1, 3:1, 4:2
- ashish.kaila in United States
Then the question was modified so there could be invalid number in the string which must be skipped.
Then an added requirement to handle hex numbers in the string.| Report Duplicate | Flag | PURGE
Twitter Software Engineer / Developer Arrays
If you need to preserve the subarray then you cannot sort to begin with ! Then it completely invalidates the above solution as it will change the order of entries !
- ashish.kaila October 23, 2015Sorry I meant [2, 30] [3, 41] [4, 26]
- ashish.kaila October 22, 2015This is incorrect solution. For example: [2, 30] [3, 21] [4,26]
In above solution, [4,26] should be absorbed by [2, 30] but the sorted sequence will never compare [4, 26] to [2, 30]
My approach is to first get a frequency hash for characters and then for each character place it in the first available position using greedy approach:
function getFreqOfChars(str) {
var chars = str.split("");
var result = {};
for (var i = 0; i < chars.length; i++) {
if (result[chars[i]]) {
result[chars[i]]++;
} else {
result[chars[i]] = 1;
}
}
return result;
}
function noAdjChars(str) {
var freq = getFreqOfChars(str);
var array = [];
for (var char in freq) {
array.push({char: char, freq: freq[char]});
}
array.sort(function(a, b) { return a.freq - b.freq;});
var result = new Array(str.length);
while (array.length > 0) {
var char = array.pop();
var placed = 0;
for (var i = 0; i < str.length && placed < char.freq; i++) {
if ((!result[i]) && (result[i - 1] !== char.char)) {
result[i] = char.char;
placed++;
}
}
if (placed < char.freq) {
return null;
}
}
return result.join("");
}
I wonder what the interviewer had in mind when he asked this question. This is a question where Skeina got in argument with other algorithmic experts (see Nik's link). And for people who pasted pages of code above: "your code is garbage if you don't explain it first to others".
- ashish.kaila October 10, 2015function maximumDrop(arr) {
var maxDiff = -1;
var max = arr[arr.length - 1];
var min = max;
for (var i = arr.length - 1; i >= 0; i--) {
if (arr[i] > max) {
max = arr[i];
var newDiff = max - min;
maxDiff = maxDiff < newDiff ? newDiff : maxDiff;
}
if (arr[i] < min) {
max = arr[i];
min = arr[i];
}
}
console.log(maxDiff);
}
maximumDrop([4, 670, 1200, 340, 220, 4300])
1 = 0x0000000000000001 (4 byte integer)
-1 = 0xFFFFFFFFFFFFFFFF
-1 >> 2 = 0x3FFFFFFFFFFFFFFF
Now you are taking a byte out of it. Depending on endienness either this will be 3FFF(big) or FFFF (little)
First of all above solutions fail when base value is zero and power is negative. They will also fail when base value is 0 and power is 0. As an interviewer I would look for these base handling in the code.
- ashish.kaila April 21, 2012Let me give you a hint. You can solve this by scanning each character once and you don't need to keep compound character sets like IV, IX etc. Think about addition and subtraction. You are thinking too complex.
- ashish.kaila March 11, 2012Your code is both inefficient and incorrect. For starters try and understand the problem, take a few examples and then write the code. You calculate string length for all possible combinations each time. Whereas this problem can be solved using one pass linear scan.
- ashish.kaila March 09, 2012
Create trie out of the list and navigate the nodes as you read from stream in linear time.
- ashish.kaila November 05, 2015