Microsoft Interview Question
InternsCountry: United States
function length (A) {
return A.length
}
function peek (A) {
return A[length(A) - 1]
}
function push (A, x) {
return A.push(x)
}
function pop (A) {
return A.pop()
}
module.exports = function (A) {
var B = []
if (length(A) === 1) {
// A is trivially sorted...
return A
}
push(B, pop(A))
// B is trivially sorted in descending order
while (length(A)) {
var a = pop(A)
var b = peek(B)
var i = 0
while (b < a) {
push(A, pop(B))
b = peek(B)
++i
}
push(B, a)
for (; i > 0; --i) {
push(B, pop(A))
}
}
// A is empty, B is in descending order
while (length(B)) {
push(A, pop(B))
}
return A
}
var A = module.exports([4, 7, 2, 8, 1, 6, 5])
console.log(A)
Ruby
def stack_sort stack1
stack2 = []
held = nil
until stack1.empty?
until stack1.length == 1 || stack1[-2] < stack1[-1]
stack2 << stack1.pop
end
stack2 << stack1.pop
held = stack1.pop
until stack2.empty? || held.nil? || stack2[-1] < held
stack1 << stack2.pop
end
stack2 << held unless held.nil?
end
[stack1, stack2]
end
Ruby
def stack_sort stack1
stack2 = []
held = nil
until stack1.empty?
until stack1.length == 1 || stack1[-2] < stack1[-1]
stack2 << stack1.pop
end
stack2 << stack1.pop
held = stack1.pop
until stack2.empty? || held.nil? || stack2[-1] < held
stack1 << stack2.pop
end
stack2 << held unless held.nil?
end
[stack1, stack2]
end
Here it is : [ stackoverflow.com/questions/26974160/sorting-a-stack-using-another-stack ]
- NoOne December 18, 2016