helloru
BAN USERI'll admit that I missed that tidbit when I read over it. But even then so, it doesn't really seem possible to do it in O(n) time. Only thing I can think of us pre-processing with a hash map so that getMaxTraffic runs in constant time. Pre-processing will take O(n^2) time, though. Bottom line, in order to determine the max traffic for a city, you NEED to check the other cities, and you just can't do that in O(1) time.
And yes, we can add some identifiers to ensure the cities are unique regardless of population. But for this problem, I made the assumption that the populations were unique. Something that you obviously want to ask your interviewer about.
Swift 2.2
func isSwapSortPossible(array: [Int]) -> String {
if (array.count <= 1) {
return "Possble!"
} else if (array.count % 2 == 0) {
return "Not Possible"
}
let sortedArray = array.sort({ return $0 < $1 })
let mid = array.count / 2
for i in 1 ..< mid {
let left = array[mid - i]
let right = array[mid + i]
let sortedLeft = sortedArray[mid - i]
let sortedRight = sortedArray[mid + i]
// If left and right don't pair up and match
if ((left != sortedLeft || right != sortedRight) &&
(left != sortedRight || right != sortedLeft)) {
return "Not Possible!"
}
}
return "Possible!"
}
isSwapSortPossible([1, 6, 3, 4, 5, 2, 7]) // "Possible!"
isSwapSortPossible([2, 6, 5, 1, 7, 5, 4]) // "Not Possible!"
EDIT: This solution is O(n^2). I didn't correctly read the problem before coding it. mrsurajpoudel.wordpress.com's answer is correct.
Pretty straightforward using recursion. There's two situations for a city:
1. If the game is at the city, get the maximum out of all of your neighbors.
2. If the game is at another city, get the sum of all of your neighbors not in the direction of the game and yourself. Return that sum to the neighbor in the direction of the game.
Swift 2.2
class City {
var pop: Int
var neighbors: [City]
init() {
self.pop = 0
self.neighbors = []
}
init(pop: Int) {
self.pop = pop
self.neighbors = []
}
init(pop: Int, neighbors: [City]) {
self.pop = pop
self.neighbors = neighbors
}
}
func getMaxTraffic(city: City, gameCity: City) -> Int {
var total = 0
if (city.pop == gameCity.pop) {
// If the game is at our city, get get the largest neighbor.
for neigh in city.neighbors {
total = max(getMaxTraffic(neigh, gameCity: city), total)
}
} else {
// If game is in another city, add all other traffic including ourself.
for neigh in city.neighbors {
if (neigh.pop != gameCity.pop) {
total += getMaxTraffic(neigh, gameCity: city)
}
}
total += city.pop
}
return total
}
func getAllTraffic(cities: [City]) {
print("Cities: ")
for city in cities {
print("\(city.pop), \(getMaxTraffic(city, gameCity: city))")
}
}
// First example
var city5 = City(pop: 5)
var city1 = City(pop: 1, neighbors: [city5])
var city2 = City(pop: 2, neighbors: [city5])
var city3 = City(pop: 3, neighbors: [city5])
var city4 = City(pop: 4, neighbors: [city5])
city5.neighbors = [city1, city2, city3, city4]
getAllTraffic([city1, city2, city3, city4, city5]) // tested and works
// Second example
var city7 = City(pop: 7, neighbors: [city2])
var city15 = City(pop: 15, neighbors: [city2])
city2.neighbors = [city5, city7, city15]
getAllTraffic([city1, city2, city3, city4, city5, city7, city15]) // tested and works
You say to store them as we wish, but then you talk in terms of indexes, leading us to use an array.
But really, what's the catch? Is there something you're not telling us?
Swift 2.2
// TODO: Maybe add some bulbs.
var bulbs = [Bool]()
func toggleBulbs(start: Int, end: Int) {
if (start >= 0 && end < bulbs.count) {
for i in start ... end {
bulbs[i] = !bulbs[i]
}
}
}
func isLightOn(bulbIndex: Int) -> Bool? {
if (bulbIndex >= 0 && bulbIndex < bulbs.count) {
return bulbs[bulbIndex]
}
return nil
}
Let's keep this example at 8 bits for simplicity.
Let's start with our sample input: input = 10101010
Create another number i which will start at 1: i = 00000001
Shift it k times. (Let's say k = 3): i = 00001000
Negate it with XOR by performing i ^ Int.max: i = i ^ 11111111 = 11110111
Return i & number: 10100010
Swift 2.2
func flip(k: Int, number:Int) -> String {
var operand = 1
operand = operand << k
operand = operand ^ Int.max
return String(operand & number, radix: 2)
}
flip(0, number: 0b101) // "100"
flip(1, number: 0b101) // "101"
flip(2, number: 0b101) // "1"
@ricardolira48: Your method fails for every case where n >= 3 and the n-2nd and n-1st digits are greater than the nth digit.
@Dinesh Pant: It's not possible to remove the 6 because both of its adjacent numbers are smaller. Remember, for any adjacent pair, you remove the smaller and retain the larger of the two.
Brute method
Swift 2.2
extension Int {
var array: [Int] {
var number = self
var result = [Int]()
while (number != 0) {
result.insert(number % 10, atIndex: 0)
number = number / 10
}
return result
}
}
extension Array {
var int: Int {
var result = 0
var multiplier = 1
for i in self.reverse() {
if let digit = i as? Int {
result += digit * multiplier
multiplier *= 10
}
}
return result
}
}
func smallestSwap(num: Int) -> Int {
var min = Int.max
for i in 1 ..< num.array.count {
var numArray = num.array
if (numArray[i - 1] < numArray[i]) {
numArray.removeAtIndex(i - 1)
} else {
numArray.removeAtIndex(i)
}
let newNum = numArray.int
if (newNum < min) {
min = newNum
}
}
return min
}
smallestSwap(233614)
I'm going to make the assumption that there won't be any duplicate characters in the ordering. i.e, in your first example, pattern "hlol!" wouldn't make since sine the first 'l' in the pattern accounts for ALL instances of 'l' in the input.
Swift 2.2
func lastInstanceOf(phrase: String, letter: Character) -> Int? {
for i in (0 ..< phrase.characters.count).reverse() {
if (phrase[phrase.startIndex.advancedBy(i)] == letter) {
return i
}
}
return nil
}
func matchPattern(phrase: String, pattern: String) -> Bool {
for i in 0 ..< pattern.characters.count {
if (i < pattern.characters.count - 1) {
let currentIndex = lastInstanceOf(phrase, letter: pattern[pattern.startIndex.advancedBy(i)])
for j in i + 1 ..< pattern.characters.count {
let compareIndex = lastInstanceOf(phrase, letter: pattern[pattern.startIndex.advancedBy(j)])
if (compareIndex < currentIndex) {
return false
}
}
}
}
return true
}
matchPattern("hello world!", pattern: "hlo!") // false
matchPattern("hello world!", pattern: "!od") // false
matchPattern("hello world!", pattern: "he!") // true
matchPattern("aaaabbbcccc", pattern: "ac") // true
Swift 2.2
func getNumberedPattern(word: String) -> [Int] {
var identifier = 0;
var patternHash = [Character: Int]()
var pattern = [Int]()
for character in word.characters {
if (patternHash[character] == nil) {
patternHash[character] = identifier
identifier += 1
}
pattern.append(patternHash[character]!)
}
return pattern
}
func match(pattern: String, words:[String]) -> [String]{
var matches = [String]()
for word in words {
if (getNumberedPattern(word) == getNumberedPattern(pattern)) {
matches.append(word)
}
}
return matches;
}
match("abc", words: ["cdf", "too", "hgfdt", "paa"]) // ["cdf"]
match("acc", words: ["cdf", "too", "hgfdt", "paa"]) // ["too", "paa"]
Swift 2.2
// Determines if a character is capitalized.
func isCapital(c:Character) -> Bool {
return ("A"..."Z").contains(c)
}
// Splits a CamelCaseNotation string into sections.
func getSections(camelCaseString: String) -> [String] {
var sections = [String]()
var section = ""
for character in camelCaseString.characters {
if (isCapital(character)) {
if (section.characters.count > 0) {
sections.append(section)
}
section = String(character)
} else {
section.append(character)
}
}
if (section.characters.count > 0) {
sections.append(section)
}
return sections
}
// Returns an array of CamelCaseNotation strings whos prefixes match
// the CamelCaseNotation of the key.
func camelCaseNotation(words:[String], key: String) -> [String] {
// Because SE-0003
var words = words
var keySections = getSections(key)
for i in (0 ..< words.count).reverse() {
var wordSections = getSections(words[i])
// Remove the word if it has less sections than the key.
if (wordSections.count < keySections.count) {
words.removeAtIndex(i)
continue
}
// Remove the word if its section doesn't match the key's corresponding section.
for j in 0 ..< keySections.count {
if (wordSections[j].hasPrefix(keySections[j]) == false) {
words.removeAtIndex(i)
break;
}
}
}
return words;
}
var words = ["HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"]
camelCaseNotation(words, key: "H") // ["HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"]
camelCaseNotation(words, key: "HW") // ["HelloWorld", "HelloWorldMars"]
camelCaseNotation(words, key: "Ho") // []
camelCaseNotation(words, key: "HeWorM") // ["HelloWorldMars"]
Swift 2.2
func sumOfItems(array:[Int]) -> Int {
var sum = 0;
for i in 0 ..< array.count {
sum += array[i]
}
return sum
}
func getEquils(array:[Int], n:Int) -> [Int] {
var result = [Int]()
var leftSum = 0
var rightSum = sumOfItems(array) - array[0]
if (leftSum == rightSum) {
result.append(0)
}
for i in 1 ..< n {
leftSum += array[i - 1]
rightSum -= array[i]
if (leftSum == rightSum) {
result.append(i)
}
}
return result
}
getEquils([-1, 3, -4, 5, 1, -6, 2, 1], n: 8) // [1, 3, 7]
Swift 2.2. Doesn't account for overflow.
- helloru August 16, 2016