helloru
I'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 preprocessing with a hash map so that getMaxTraffic runs in constant time. Preprocessing 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!"

helloru
August 10, 2016 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

helloru
August 10, 2016 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
}

helloru
August 09, 2016 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"

helloru
August 08, 2016 @ricardolira48: Your method fails for every case where n >= 3 and the n2nd and n1st 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)

helloru
August 07, 2016 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

helloru
August 04, 2016 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"]

helloru
August 03, 2016 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 SE0003
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"]

helloru
August 02, 2016 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]

helloru
August 01, 2016 Open Chat in New Window
Swift 2.2. Doesn't account for overflow.
 helloru August 16, 2016