Interview Question for Software Development Engineer at Microsoft:

Given a string "1800RENTCAR" can have spaces in any where, output the "1 800 7368-227" Can't use any additional memory for mapping chars to intergers. You need a math formula to convert them. The output must be exactly the same as the example. (4th) Given HTML file <foo> encode it as <foo>. Improve complexity from O(n) to O(logn) to constant time (5th interview)