diegum
BAN USER- 1of 1 vote
AnswersYou are asked to code an Android game that shows this board
+——————————+——————————+ |1 | 2| | | | | ♠ | ♣ | | +———+———+ | | | ♥ | ♠ | | +——————+———+———+——————+ | | ♦ | ♣ | | | +———+———+ | | ♥ | ♦ | | | | |3 | 4| +——————————+——————————+
Where the numbers are text but the spades, diamond, etc are graphics.
- diegum in United States for Android
The four squares in the center of the board are buttons. When you press any of these buttons, a popup shows buttons from 1 to 4. You have to click the number that makes your original button to match the quadrant whose symbol is the same.
So, in the figure, if you pressed the spades button, then you should press the button labeled 1. If you pressed the heart button then you should press 3, etc.
When you press the buttons correctly, the figure button is swapped properly so it gets in the quadrant containing that figure, and disabled for further push.
If the number button were incorrect instead, the original figure button is swapped with the figure button at the quadrant whose number you erroneously clicked.
The game finishes when all figure buttons are in their correct quadrants. Last but not least, the figure buttons are initially placed randomly.
Describe how you'd put this board in a layout that doesn't distort the figures neither in quadrants nor in buttons.
Explain how you'd code the most important portions of this game.| Report Duplicate | Flag | PURGE
Starbucks Dev Lead Dev Lead Application / UI Design - 6of 6 votes
AnswersCode a function that receives a string composed by words separated by spaces and returns a string where words appear in the same order but than the original string, but every word is inverted.
Example, for this input string@"the boy ran"
the output would be
@"eht yob nar"
Tell the complexity of the solution.
- diegum in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer String Manipulation - 2of 2 votes
AnswersDesign an HTTP downloader that caches results and doesn't block execution (i.e., enables simultaneous downloads).
- diegum in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Object Oriented Design - 3of 3 votes
AnswersCode a function that gets two strings representing binary numbers (so the only possible characters are '1' and '0', and returns a third string representing the sum of the input. The input strings don't necessarily have of the same length.
- diegum in United States for iOS
Tell the complexity of the solution.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer String Manipulation - 2of 2 votes
AnswersCode a function that receives an array with duplicates and returns a new array keeping the original order of the elements but with the duplicates removed.
For example, if the input were@[ @"dog", @"cat", @"dog", @"fish" ]
the output would be
@[ @"dog", @"cat", @"fish" ]
Tell the complexity of the solution.
- diegum in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Arrays
My impression is that this solution, like others posted here, produces an output whose most significant character is at the end of the string.
For example, summing "11" and "1" should produce "100". But this approach will produce "001" if I'm not misunderstanding something.
Solution in Objective-C leveraging categories. Worst case complexity is O(n + n/2) = O(n).
Tests first:
//
// CSPWordInverterTests.m
//
#import <XCTest/XCTest.h>
#import "NSString+WordInverter.h"
@interface CSPWordInverterTests : XCTestCase
@end
@implementation CSPWordInverterTests
- (void)setUp
{
[super setUp];
// Put setup code here. This method is called before the invocation of each test method in the class.
}
- (void)tearDown
{
// Put teardown code here. This method is called after the invocation of each test method in the class.
[super tearDown];
}
- (void)testSimpleCase
{
XCTAssertEqualObjects(@"eht yob nar", [@"the boy ran" invertWords]);
}
- (void)testNullOrEmptyData
{
XCTAssertNil([(NSString*)nil invertWords]);
XCTAssertEqualObjects(@"", [@"" invertWords]);
XCTAssertEqualObjects(@" ", [@" " invertWords]);
}
- (void)testStringWithNoWords
{
XCTAssertEqualObjects(@" %^& *$@", [@" %^& *$@" invertWords]);
XCTAssertEqualObjects(@"$", [@"$" invertWords]);
}
- (void)testStringsWithOneWord
{
XCTAssertEqualObjects(@"one", [@"eno" invertWords]);
}
- (void)testPalindromes
{
XCTAssertEqualObjects(@"ema a ame", [@"ame a ema" invertWords]);
XCTAssertEqualObjects(@"dabalearrozalazorraelabad",
[@"dabalearrozalazorraelabad" invertWords]);
}
- (void)testAMoreComplexSentence
{
XCTAssertEqualObjects(@"ehT ecnednepednI fo aciremA saw deralced " \
@"a ht4 fo yluJ fo 6771.",
[@"The Independence of America was declared " \
@"a 4th of July of 1776." invertWords]);
}
@end
Category header:
//
// NSString+WordInverter.h
//
#import <Foundation/Foundation.h>
/**
* Category over NSString that features a method to reverse the order of
* characters in all words of a string.
*/
@interface NSString (WordInverter)
/**
* Reverses the order of the characters in all words of the string.
*/
- (NSString*)invertWords;
@end
Implementation:
//
// NSString+WordInverter.mm
//
#import "NSString+WordInverter.h"
#include <ctype.h>
void invertWord(unichar* buffer, NSUInteger begin, NSUInteger end)
{
// Defensive coding: attention to the case end is 0 (beginning of sentence)
if (end) {
for (--end; begin < end; ++begin, --end) {
// swapping via XOR
buffer[begin] = (buffer[begin] ^ buffer[end]);
buffer[end] = (buffer[begin] ^ buffer[end]);
buffer[begin] = (buffer[begin] ^ buffer[end]);
}
}
}
@implementation NSString (WordInverter)
- (NSString*)invertWords
{
NSString* result = nil;
NSUInteger length = [self length];
if (length) {
unichar* buffer = new unichar[length];
@try {
NSUInteger foreRunner = 0, backRunner = 0;
BOOL traversingWord = YES;
while (foreRunner < length) {
buffer[foreRunner] = [self characterAtIndex:foreRunner];
if (traversingWord) {
if (!(traversingWord = isalnum(buffer[foreRunner]))) {
// we are past-the-word-end, we must invert the word
invertWord(buffer, backRunner, foreRunner);
}
} else {
if ((traversingWord = isalnum(buffer[foreRunner]))) {
// end of non-alpha segment: beginning of word
backRunner = foreRunner;
}
}
++foreRunner;
}
// border condition: string may end while traversing a word
if (traversingWord) invertWord(buffer, backRunner, foreRunner);
result = [NSString stringWithCharacters:buffer length:length];
}
@finally {
delete[] buffer;
}
} else {
result = [NSString string];
}
return result;
}
@end
I believe you're missing to turn carry off (carry = 0) right after consuming it:
curVal += carry;
carry = 0; // <-- this line added by me
Otherwise, correct me if I'm wrong, once you carry for the first time, you'll keep adding 1 to curVal for all the remaining iterations.
- diegum June 11, 2014This is an elegantly concise approach! I still fill like you missed to tell the complexity of the approach. Apparently would be O(n) but I feel like it's actually O(n^2) because of the use of StringBuffer.insert(...) method. In the first iteration will shift 0 characters, in the second iteration will shift 1, and so on until the n-th iteration, when it will shift n-1 characters. In summary, all StringBuffer.insert(...) will have a complexity of O(0+1+...+(n-1)), equivalent to O(n * (n-1) / 2), equivalent to O(n^2).
Just a slight tweak using a primitive char array instead of a StringBuffer, filled from the bottom frontward would turn this elegant approach complexity to linear. Then, just return new String(myPrimitiveArrayOfChars);
Solution in Objective-C, leveraging the "category" feature of such language, that enables to aggregate methods to existing classes. In this case, the approach consists in aggregating a sumBinaryString:(NSString*) instance method to class NSString. The complexity is linear --i.e., O(n).
Tests first:
#import <XCTest/XCTest.h>
#import "NSString+Binary.h"
@interface CSPBinaryStringSumTests : XCTestCase
@end
@implementation CSPBinaryStringSumTests {
NSError* error_;
}
- (void)setUp
{
[super setUp];
error_ = nil;
}
- (void)tearDown
{
error_ = nil;
[super tearDown];
}
- (void)testNormalCase
{
NSString *op1 = @"101", *op2 = @"11";
XCTAssertEqualObjects(@"1000", [op1 sumBinaryString:op2]);
}
- (void)testNullCase
{
XCTAssertNil([@"1" sumBinaryString:nil]);
}
- (void)testUnusualYetValidInput
{
NSString *op1 = @"0000000000000101", *op2 = @"0000000000000000000000000011";
XCTAssertEqualObjects(@"1000", [op1 sumBinaryString:op2]);
}
- (void)testZeroes
{
NSString *op1 = @"0000000000000", *op2 = @"0000000000000000000000000011";
XCTAssertEqualObjects(@"11", [op1 sumBinaryString:op2]);
op1 = @"0000000000000101", op2 = @"00000000000000000000000000";
XCTAssertEqualObjects(@"101", [op1 sumBinaryString:op2]);
op1 = @"0000000000000", op2 = @"00000000000000000000000000";
XCTAssertEqualObjects(@"0", [op1 sumBinaryString:op2]);
}
- (void)testInvalidBinaries
{
NSString *op1 = @"I'm not a binary string";
XCTAssertNil([op1 sumBinaryString:@"101" error:&error_]);
XCTAssertNil([@"101" sumBinaryString:@"I'm not either" error:&error_]);
}
- (void)testHugeInput
{
NSString *op1 = @"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101",
*op2 = @"101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101010" \
@"0101010101010101010101010101010101010101" \
@"1010101010101010101010101010101010101011",
*expected = @"10000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000" \
@"0000000000000000000000000000000000000000";
XCTAssertEqualObjects(expected, [op1 sumBinaryString:op2 error:&error_]);
}
@end
Category header:
#import <Foundation/Foundation.h>
extern NSString * const NSStringBinaryErrorDomain;
@interface NSString (Binary)
/**
* Sums the operand to the self string, assuming both contain only binary chars.
* @param operand the binary number, represented as a string of '1's and '0's.
* @return a new string containing the binary repressentation of the sum of the
* input. Nil in case some error happens with the input.
*/
- (NSString*)sumBinaryString:(NSString*)operand;
/**
* Sums the operand to the self string, assuming both contain only binary chars.
* @param operand the binary number, represented as a string of '1's and '0's.
* @param error a reference to an NSError* where the reasons for failure will be
* left, if a failure happened at all.
* @return a new string containing the binary repressentation of the sum of the
* input. Nil in case some error happens with the input (check error in such
* case).
*/
- (NSString*)sumBinaryString:(NSString*)operand error:(NSError* __strong *) error;
@end
Category implementation:
#import "NSString+Binary.h"
NSString * const NSStringBinaryErrorDomain = @"NSStringBinaryDomain";
// Convenience function that assigns the longest string to the output parameter
// longest, the shortest to shortest.
// Returns the length of the longest.
NSUInteger assignLongestAndShortest(NSString **longest, NSString **shortest,
NSString *str1, NSString *str2)
{
if ([str1 length] > [str2 length]) {
*longest = str1; *shortest = str2;
} else {
*longest = str2; *shortest = str1;
}
return [*longest length];
}
@implementation NSString (Binary)
- (NSString*)sumBinaryString:(NSString*)operand
{
return [self sumBinaryString:operand error:nil];
}
- (NSString*)sumBinaryString:(NSString*)operand error:(NSError* __strong *)error
{
NSString *result = nil;
NSInteger statusCode = 0;
id statusObject;
if (operand) {
NSString *longest, *shortest;
// we'll work on a temporaty C-array whose length is the length of the
// longest input string plus 1 for a potential carry.
NSUInteger bufferLength = assignLongestAndShortest(&longest, &shortest,
self, operand) + 1;
unichar *buffer = new unichar[bufferLength]();
@try {
NSUInteger index;
BOOL carry;
// this algorithm iterates with O(n) where n is the length of the
// longest string. It iterates backward over the strings, in two
// phases.
// The first phase is while both strings have common positions
// covered, starting from the end.
for (index = 1, carry = NO; index <= [shortest length]; ++index) {
// Both characters are compared to calculate the resulting some
// at that position, taking into account a potential carry from
// the previous iteration.
switch ([longest characterAtIndex:([longest length] - index)]) {
case '0':
switch ([shortest characterAtIndex:([shortest length] - index)]) {
case '0':
buffer[bufferLength - index] = carry ? '1' : '0';
carry = NO;
break;
case '1':
buffer[bufferLength - index] = carry ? '0' : '1';
break; // in this scenario, carry wouldn't change
default:
// If the shortest string has other than 1 or 0,
// the string is a malformed binary.
statusCode = 200;
statusObject = shortest;
break;
}
break;
case '1':
switch ([shortest characterAtIndex:([shortest length] - index)]) {
case '0':
buffer[bufferLength - index] = carry ? '0' : '1';
break;
case '1':
buffer[bufferLength - index] = carry ? '1' : '0';
carry = YES;
break;
default:
statusCode = 200;
statusObject = shortest;
break;
}
break;
default:
// the longest is a malformed binary string
statusCode = 200;
statusObject = longest;
break;
}
// short-circuit if statusCode isn't 0 anymore.
if (statusCode) break;
}
if (!(statusCode)) {
// Second phase of the loop over longest: this portion only covers
// the most-significant section of the longest that doesn't have
// counterpart in the shortest.
for (; index <= [longest length]; ++index) {
switch ([longest characterAtIndex:([longest length] - index)]) {
case '0':
buffer[bufferLength - index] = carry ? '1' : '0';
carry = NO;
break;
case '1':
buffer[bufferLength - index] = carry ? '0' : '1';
carry = YES;
break;
default:
statusCode = 200;
statusObject = longest;
break;
}
if (statusCode) break;
}
if (!(statusCode)) {
// last check after finishing with the longest: is there any
// carry left? If so, turn on the first char.
buffer[0] = carry ? '1' : '0';
carry = NO;
// Now, let's skip all '0' until finding the canonical most
// significant '1'.
for (index = 0;
(buffer[index]) == '0' && (index < bufferLength - 1);
++index);
result =
[NSString stringWithCharacters:buffer+index
length:bufferLength - index];
}
}
}
@finally {
delete[] buffer;
}
} else {
// The operand is nil, sum skipped.
statusCode = 100;
}
if ((statusCode) && (error)) {
[self p_populateError:error forCode:statusCode andObject:statusObject];
}
return result;
}
// Produces an NSError in the NSStringBinaryErrorDomain domain based on the
// status code received as parameter.
- (void) p_populateError:(NSError* __strong *)error
forCode:(NSInteger)code
andObject:(id)object
{
if (error) {
NSMutableDictionary *userInfo = [NSMutableDictionary dictionary];
switch (code) {
case 100:
[userInfo setObject:@"Binary sum skipped."
forKey:NSLocalizedDescriptionKey];
[userInfo setObject:@"Operand is nil"
forKey:NSLocalizedFailureReasonErrorKey];
[userInfo setObject:@"Provide a binary operand"
forKey:NSLocalizedRecoverySuggestionErrorKey];
break;
case 200:
[userInfo setObject:@"Binary sum aborted."
forKey:NSLocalizedDescriptionKey];
[userInfo setObject:[NSString stringWithFormat:
@"Operand isn't binary: \"%@\"", object]
forKey:NSLocalizedFailureReasonErrorKey];
[userInfo setObject:@"Provide a binary operand"
forKey:NSLocalizedRecoverySuggestionErrorKey];
break;
default:
[userInfo setObject:@"Undetermined error"
forKey:NSLocalizedDescriptionKey];
}
*error = [NSError errorWithDomain:NSStringBinaryErrorDomain
code:code userInfo:userInfo];
}
}
@end
My approach, in Objective C, uses a Set as auxiliary structure (NSMutableSet in Objective-C). Insertion and retrieval from Set in Objective-C has O(1) because a hash method is applied.
The entire solution has complexity O(n+n+n+n) = O(4n) = O(n): n iterations across the input array, in which each iteration does:
*) 1 access to the original array O(1).
*) 1 check in the set for existence O(1).
*) 1 insertion to the set O(1).
*) 1 insertion to the destination array O(1).
Tests first:
#import <XCTest/XCTest.h>
#import "CSPArrayOfUniqueObjectsMaker.h"
@interface CSPArrayOfUniqueObjectsMakerTests : XCTestCase
@end
@implementation CSPArrayOfUniqueObjectsMakerTests
- (void)setUp
{
[super setUp];
// Put setup code here. This method is called before the invocation of each test method in the class.
}
- (void)tearDown
{
// Put teardown code here. This method is called after the invocation of each test method in the class.
[super tearDown];
}
- (void)testHappyPath
{
NSArray* expected = @[@2, @1, @3];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[@2, @1, @3, @1, @2]];
XCTAssertEqualObjects(expected, actual);
}
- (void)testNoDuplicates
{
NSArray* expected = @[ @"January", @"February",
@"March", @"April",
@"May", @"June",
@"July", @"August",
@"September", @"October",
@"November", @"December" ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[ @"January", @"February",
@"March", @"April",
@"May", @"June",
@"July", @"August",
@"September", @"October",
@"November", @"December" ]];
XCTAssertEqualObjects(expected, actual);
}
- (void)testAllDuplicates
{
NSArray* expected = @[ @3.1416 ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[ @3.1416, @3.14160,
@3.141600, @3.1416000,
@3.14160000]];
XCTAssertEqualObjects(expected, actual);
}
- (void)testEmptyArray
{
XCTAssertEqualObjects(nil, [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:nil]);
XCTAssertEqualObjects(@[], [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:@[]]);
}
- (void)testDuplicatesAlwaysTogether
{
NSArray* expected = @[ @1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19 ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:
@[ @1, @1, @1, @1, @1, @1, @1, @1, @1, @1, @1, @1, @1,
@2, @2,
@3, @4, @5, @6, @7, @8, @9,
@10, @10, @10, @10,
@20, @21, @22,
@23, @23, @23, @23, @23, @23, @23, @23, @23, @23, @23,
@24, @25, @26, @27, @28, @29,
@11, @12, @13, @14,
@15, @15, @15, @15, @15, @15, @15, @15, @15, @15,
@16, @17, @18, @19 ]];
XCTAssertEqualObjects(expected, actual);
}
- (void)testDuplicatesNeverTogether
{
NSArray* expected = @[ @1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19 ];
NSArray* actual = [CSPArrayOfUniqueObjectsMaker
arrayOfUniqueObjectsWithArray:
@[ @1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19,
@1, @2, @3, @4, @5, @6, @7, @8, @9, @10,
@20, @21, @22, @23, @24, @25, @26, @27, @28, @29,
@11, @12, @13, @14, @15, @16, @17, @18, @19 ]];
XCTAssertEqualObjects(expected, actual);
}
@end
Header:
#import <Foundation/Foundation.h>
@interface CSPArrayOfUniqueObjectsMaker : NSObject
/**
* Receives an array, possibly with duplicated elements. Returns an array that
* keeps the order of the original array but only the first occurrence of a
* repeated element is kept.
* @param array an NSArray with possible duplicates.
* @return an array that keeps the order of elements but doesn't include the
* repeated occurrences of duplicated elements. If the input is nil, the output
* is nil as well.
*/
+ (NSArray*)arrayOfUniqueObjectsWithArray:(NSArray*)array;
@end
Implementation:
#import "CSPArrayOfUniqueObjectsMaker.h"
@implementation CSPArrayOfUniqueObjectsMaker
+ (NSArray*)arrayOfUniqueObjectsWithArray:(NSArray*)array
{
// fail fast: before null input, null answer
if (array == nil) return nil;
// this set will receive objects from the array only once: only if they
// weren't already in the set
NSMutableSet* actualObjects = [NSMutableSet set];
// this array will hold those objects from the array not found in the set
NSMutableArray* retCollection = [NSMutableArray array];
for (const id object in array) {
if (![actualObjects containsObject:object]) {
[retCollection addObject:object];
[actualObjects addObject:object];
}
}
return [retCollection copy];
}
@end
It works, although the complexity seems to be O(n + n*(n-1)/2) = O(n^2).
Explanation, for the original array, n iterations (a whole traversal). In each iteration, you'll have a check for existence in the destination array, which in the first iteration will have 0 elements, in iteration 2 will have 1 element, in iteration 3 will have 2 elements, and in iteration n will have n-1 elements. That checking, then, will have a complexity of O(0+1+2+...+n-1) = O((n-1)*n/2) = O(n^2).
I got a solution using dynamic programming techniques, whose complexity is matrix width by height, both runtime and spatial.
Tests first:
// CSPMaxAreaInMatrixTests.m
#import <XCTest/XCTest.h>
#import "CSPMatrixUtils.h"
@interface CSPMaxAreaInMatrixTests : XCTestCase
@end
@implementation CSPMaxAreaInMatrixTests
- (void)setUp
{
[super setUp];
// Put setup code here. This method is called before the invocation of each test method in the class.
}
- (void)tearDown
{
// Put teardown code here. This method is called after the invocation of each test method in the class.
[super tearDown];
}
- (void)testOriginalCase
{
char matrix[5][5] = { { '\0', '\0', '\0', '\1', '\0' },
{ '\1', '\1', '\1', '\0', '\0' },
{ '\1', '\1', '\1', '\1', '\0' },
{ '\1', '\1', '\0', '\0', '\0' },
{ '\1', '\1', '\0', '\1', '\0' } };
XCTAssertEqual(8, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
- (void)testNullMatrix
{
unsigned char matrix[5][5] = { { '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' } };
XCTAssertEqual(0, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
- (void)testOneOne
{
unsigned char matrix[5][5] = { { '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\1', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' } };
XCTAssertEqual(1, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
- (void)testAllBlack
{
unsigned char matrix[5][5] = { { '\1', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\1', '\1', '\1' } };
XCTAssertEqual(25, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
- (void)testAllWhite
{
unsigned char matrix[5][5] = { { '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' },
{ '\0', '\0', '\0', '\0', '\0' } };
XCTAssertEqual(0, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
- (void)testCheckers
{
unsigned char matrix[5][5] = { { '\0', '\1', '\0', '\1', '\0' },
{ '\1', '\0', '\1', '\0', '\1' },
{ '\0', '\1', '\0', '\1', '\0' },
{ '\1', '\0', '\1', '\0', '\1' },
{ '\0', '\1', '\0', '\1', '\0' } };
XCTAssertEqual(1, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
- (void)testSecondAndThirdRows
{
unsigned char matrix[5][5] = { { '\1', '\1', '\1', '\0', '\1' },
{ '\1', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\1', '\1', '\1' },
{ '\0', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\0', '\1', '\1' } };
XCTAssertEqual(12, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
- (void)testSecondToFourthColumns
{
unsigned char matrix[5][5] = { { '\1', '\1', '\1', '\1', '\0' },
{ '\1', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\1', '\1', '\1' },
{ '\0', '\1', '\1', '\1', '\1' },
{ '\1', '\1', '\1', '\1', '\1' } };
XCTAssertEqual(16, [CSPMatrixUtils maxAreaInMatrix:(char*)matrix
withWidth:5 andHeight:5]);
}
@end
Header of the solution:
// CSPMatrixUtils.h
#import <Foundation/Foundation.h>
@interface CSPMatrixUtils : NSObject
/**
* Given a matrix of ones and zeroes, returns the area of the maximum rectangle
* composed by ones inside the matrix.
* @param matrix a matrix of chars
* @param width the matrix width
* @param height the matrix height
* @return the area of the maximum rectangle of ones contained in the matrix
*/
+ (NSUInteger)maxAreaInMatrix:(char*)matrix withWidth:(NSUInteger)width
andHeight:(NSUInteger)height;
@end
Implementation (in Objective-C++) using dynamic programming:
// CSPMatrixUtils.mm
#import "CSPMatrixUtils.h"
#include <math.h>
// For each cell (i, j) in the matrix, we'll keep the max area of ones in the
// submatrix determined by (0, 0) and (i, j), provided that (i, j) is contained
// in that max area.
typedef struct {
unsigned row, column; // top/left corner of the max area
unsigned height, width; // dimensions
} MaxArea;
MaxArea newMaxArea(int row, int col)
{
MaxArea maxArea{};
maxArea.row = row; maxArea.column = col;
maxArea.width = maxArea.height = 1;
return maxArea;
}
// Given two rectangles, returns a new one as the minimum area that contains
// both rectangles
MaxArea outterArea(MaxArea* leftTopArea, MaxArea* currentArea)
{
MaxArea outterArea = *currentArea;
if ((leftTopArea->width > 0) && (leftTopArea->height > 0) &&
(currentArea->width > 0) && (currentArea->height > 0)) {
outterArea.row = MIN(leftTopArea->row, currentArea->row);
outterArea.height = MAX(leftTopArea->row + leftTopArea->height,
currentArea->row + currentArea->height)
- outterArea.row;
outterArea.column = MIN(leftTopArea->column, currentArea->column);
outterArea.width = MAX(leftTopArea->column + leftTopArea->width,
currentArea->column + currentArea->width)
- outterArea.column;
}
return outterArea;
}
// Given two rectangles, returns the intersection of these
MaxArea innerArea(MaxArea* leftArea, MaxArea* topArea)
{
MaxArea innerArea{};
if ((leftArea->width > 0) && (leftArea->height > 0) &&
(topArea->width > 0) && (topArea->height > 0) &&
(topArea->row + topArea->height > leftArea->row) &&
(leftArea->column + leftArea->width > topArea->column)){
innerArea.row = MAX(leftArea->row, topArea->row);
innerArea.height = leftArea->row - innerArea.row + 1;
innerArea.column = MAX(leftArea->column, topArea->column);
innerArea.width = topArea->column - innerArea.column + 1;
}
return innerArea;
}
// Given three areas, returns the largest.
MaxArea maxArea3Way(MaxArea* a1, MaxArea* a2, MaxArea* a3)
{
NSUInteger area1 = a1->width * a1->height,
area2 = a2->width * a2->height,
area3 = a3->width * a3->height;
return (area1 > area2) ?
((area1 > area3) ? *a1 : *a3) :
((area2 > area3) ? *a2 : *a3);
}
// Given a cell (i, j), calculates the maximum rectangle of ones in the submatrix
// between (0, 0) and (i, j). Returns the area of that maximum rectangle.
NSUInteger calculateMaxArea(char *currentCell, NSUInteger width, NSUInteger height,
MaxArea *maxAreaCurrentCell, int row, int col)
{
MaxArea maxArea = newMaxArea(row, col), maxAreaTop{}, maxAreaLeft{};
// the max area on top of the current cell is restricted to the current
// column, with the height adjusted in one unit to contain the current cell
if ((row > 0) && (*(currentCell - width) != 0)) {
maxAreaTop = *(maxAreaCurrentCell - width);
++(maxAreaTop.height);
maxAreaTop.column = col;
maxAreaTop.width = 1;
}
// likewise, the max area on the left of the current cell is the max area for
// the cell before, but with its height restricted to 1 and its width
// increased to contain the current cell
if ((col > 0) && (*(currentCell - 1) != 0)) {
maxAreaLeft = *(maxAreaCurrentCell - 1);
++(maxAreaLeft.width);
maxAreaLeft.row = row;
maxAreaLeft.height = 1;
}
// finally, if the max area on the cell above current and the cell left to
// current have some intersection, we try to expand that intersection to
// the current cell
if ((row > 0) && (col > 0)) {
MaxArea inner = innerArea(maxAreaCurrentCell - width,
maxAreaCurrentCell - 1);
maxArea = outterArea(&inner, &maxArea);
}
// the max area will be the max between these three
*maxAreaCurrentCell = maxArea3Way(&maxArea, &maxAreaLeft, &maxAreaTop);
return (maxAreaCurrentCell->width) * (maxAreaCurrentCell->height);
}
@implementation CSPMatrixUtils
+ (NSUInteger)maxAreaInMatrix:(char*)matrix withWidth:(NSUInteger)width
andHeight:(NSUInteger)height
{
NSUInteger maxAreaFound = 0;
// fail-fast: null matrix can't have any area
if ((width == 0) || (height == 0)) return 0;
// the spatial complexity is O(width * height)
MaxArea *maxAreaMatrix = new MaxArea[width * height]();
MaxArea *maxAreaCurrentCell = maxAreaMatrix;
char *currentCell = matrix;
@try {
// the runtime complexity is O(width * height) as well
for (int row = 0; row < width; ++row) {
for (int col = 0; col < height; ++col, ++currentCell, ++maxAreaCurrentCell) {
if (*currentCell) {
// we dinamically calculate the maximum rectangle between
// (0, 0) and the current cell, using info from the cell
// above and the cell on the left
NSUInteger maxAreaForCurrentCell =
calculateMaxArea(currentCell, width, height,
maxAreaCurrentCell, row, col);
// at all times we keep the maximum area found
if (maxAreaForCurrentCell > maxAreaFound) {
maxAreaFound = maxAreaForCurrentCell;
}
}
}
}
} @finally {
delete [] maxAreaMatrix;
}
return maxAreaFound;
}
@end
I believe that I solved. My cornerstone was in keeping updated a non-public reference to the last element of the list at all times.
Unit tests first:
//
// CSPQuickListMergeTests.m
//
#import <XCTest/XCTest.h>
#import "CSPQuickMergeList.h"
@interface CSPQuickListMergeTests : XCTestCase
@end
@implementation CSPQuickListMergeTests {
CSPQuickMergeList *_list1, *_list2;
}
- (void)setUp
{
[super setUp];
_list1 = [CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4 ]];
_list2 = [CSPQuickMergeList listWithArray:@[ @5, @6, @7, @8, @9 ]];
}
- (void)tearDown
{
_list1 = _list2 = nil;
[super tearDown];
}
- (void)testSingleMerge
{
CSPQuickMergeList *expected =
[CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @5, @6, @7, @8, @9 ]];
XCTAssertEqualObjects(expected, [_list1 merge:_list2]);
}
- (void)testDoubleMergeTakeOne
{
CSPQuickMergeList *expected =
[CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @5, @6, @7, @8, @9,
@10, @11, @12, @13, @14 ]];
CSPQuickMergeList *list3 =
[CSPQuickMergeList listWithArray:@[ @10, @11, @12, @13, @14 ]];
XCTAssertEqualObjects(expected, [_list1 merge:[_list2 merge:list3]]);
}
- (void)testDoubleMergeTakeTwo
{
CSPQuickMergeList *expected =
[CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @5, @6, @7, @8, @9,
@10, @11, @12, @13, @14 ]];
CSPQuickMergeList *list3 =
[CSPQuickMergeList listWithArray:@[ @10, @11, @12, @13, @14 ]];
XCTAssertEqualObjects(expected, [[_list1 merge:_list2] merge:list3]);
}
- (void)testNullInput
{
XCTAssertEqualObjects(_list1, [_list1 merge:nil]);
}
- (void)testMergeSame
{
XCTAssertEqualObjects(_list1, [_list1 merge:_list1]);
}
- (void)testOneElementListMerge
{
CSPQuickMergeList *list3 = [CSPQuickMergeList listWithObject:@100];
CSPQuickMergeList *expected =
[CSPQuickMergeList listWithArray:@[ @100, @0, @1, @2, @3, @4 ]];
XCTAssertEqualObjects(expected, [list3 merge:_list1]);
list3 = [CSPQuickMergeList listWithObject:@100];
expected =
[CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @100 ]];
XCTAssertEqualObjects(expected, [_list1 merge:list3]);
CSPQuickMergeList *listA = [CSPQuickMergeList listWithObject:@('a')];
CSPQuickMergeList *listB = [CSPQuickMergeList listWithObject:@('b')];
expected = [CSPQuickMergeList listWithArray:@[ @('b'), @('a') ]];
XCTAssertEqualObjects(expected, [listB merge:listA]);
}
@end
The list interface:
//
// CSPQuickListMerge.h
//
#import <Foundation/Foundation.h>
/**
* Single-linked list implementation that features O(1) merge.
*/
@interface CSPQuickMergeList : NSObject
@property (nonatomic, readonly) id data;
/**
* Constructor that creates a 1-element list.
* @param object
* @return nil if object is nil, a new list otherwise
*/
+ (instancetype)listWithObject:(id)object;
/**
* Constructor that creates a list whose elements come from the array passed as
* parameter.
* @param array
* @return nil if the array is nil or has no elements, a new list otherwise
*/
+ (instancetype)listWithArray:(NSArray*)array;
- (instancetype)initWithObject:(id)object;
/**
* Default initializer.
*/
- (instancetype)initWithArray:(NSArray*)array;
/**
* Appends the received list at the end of this list. This method is optimized
* for constant complexity.
* @param list
* @return the original list with the parameter appended. If the input is the
* same list that this list, just returns this list without changes (i.e.,
* doesn't append the list to itself).
*/
- (instancetype)merge:(CSPQuickMergeList*)list;
/**
* Returns the next element (eventually nil).
*/
- (instancetype)next;
@end
The list implementation:
//
// CSPQuickListMerge.m
//
#import "CSPQuickMergeList.h"
@implementation CSPQuickMergeList {
CSPQuickMergeList *_next;
CSPQuickMergeList *_last; // at all times, a reference to the last element
// of the list is kept. This will help merge lists
// with O(1).
}
@synthesize data = _data;
+ (instancetype)listWithObject:(id)object
{
return [[CSPQuickMergeList alloc] initWithObject:object];
}
+ (instancetype)listWithArray:(NSArray*)array
{
return [[CSPQuickMergeList alloc] initWithArray:array];
}
- (instancetype)initWithObject:(id)object
{
if (!object) return nil; // fail-fast
if ((self = [super init])) {
_data = object;
_next = nil;
_last = self;
}
return self;
}
- (instancetype)initWithArray:(NSArray*)array
{
if ((!array) || (![array count])) return nil; // fail-fast
if ((self = [self initWithObject:[array objectAtIndex:0]])) {
for (NSUInteger i = 1; i < [array count]; ++i) {
[self merge:[CSPQuickMergeList
listWithObject:[array objectAtIndex:i]]];
}
}
return self;
}
- (instancetype)next
{
// here's the trick: the last element is propagated is the list is
// traversed
if (_next) [_next setLast:_last];
return _next;
}
- (instancetype)merge:(CSPQuickMergeList*)list
{
// skips empty lists or self-concatenation
if ((list) && (list != self)) {
// the original last element becomes predecessor of the new list
[_last setNext:list];
// And the last element of the resulting merged list is the last element
// of the appended list
_last = [list last];
}
return self;
}
// Notice that this method don't belong to the public interface
- (void)setNext:(CSPQuickMergeList*)next
{
_next = next;
}
// Notice that this method don't belong to the public interface
- (instancetype)last
{
return _last;
}
// Notice that this method don't belong to the public interface
- (void)setLast:(CSPQuickMergeList*)last
{
_last = last;
}
- (BOOL)isEqual:(id)object
{
if (self == object) return YES;
if (![object isKindOfClass:[CSPQuickMergeList class]]) return NO;
return [self isEqualToList:(CSPQuickMergeList*)object];
}
- (BOOL)isEqualToList:(CSPQuickMergeList*)list
{
if (!list) return NO;
CSPQuickMergeList *thisOne = self, *theOtherOne = list;
while (thisOne) {
if ((!theOtherOne) || (![[thisOne data] isEqual:[theOtherOne data]])) return NO;
thisOne = [thisOne next];
theOtherOne = [theOtherOne next];
}
return !theOtherOne;
}
- (NSUInteger)hash
{
return (_last == self) ? [_data hash] : ([_data hash] ^ [[_last data] hash]);
}
- (NSString*)description
{
NSMutableString *ret = [NSMutableString stringWithFormat:@"[ %@", [_data description]];
CSPQuickMergeList *thisList = _next;
while (thisList) {
[ret appendFormat:@", %@", [thisList data]];
thisList = [thisList next];
}
[ret appendFormat:@" ]"];
return ret;
}
@end
I respectfully disagree that the function applied to 212 should return false. A 2 flips into a 2 in the same way a 5 flips into a 5 or a 1 into a 1.
Here's my approach:
CSPFlippingNumber.h:
@interface CSPFlippingNumber : NSObject
/**
* This method returns YES if its input, when flipped over, results in the same
* number. Example: flipping over 66 gives 99, which is different. But 69 flipped
* over is still 69.
* @param number an NSUInteger to check
* @return YES if the input flips onto itself
*/
+ (BOOL)isFlippingNumber:(NSUInteger)number;
@end
CSPFlippingNumber.m:
#import "CSPFlippingNumber.h"
#include <math.h>
@implementation CSPFlippingNumber
+ (BOOL)isFlippingNumber:(NSUInteger)number
{
// Iterarion of O(n/2) (or O(n) linear), where n is the number of digits of
// the input. Each iteration will check if the most significant digit flips
// onto the least one. Then removes both from the number before looping
// again.
for (int numberLength = (int)log10(number); numberLength >= 0; numberLength-= 2) {
// Base case, when the number of digits in the input is an odd number.
// In such case, this case evaluates
if (numberLength == 0) {
return (number == 0) || (number == 1) || (number == 2) || (number == 5) || (number == 8);
} else {
// Regular case. msd: most significant digit. lsd: least one.
unsigned msd = number / pow(10, numberLength), lsd = number % 10;
// If msd flips into lsd...
if (((msd == 1) && (lsd == 1)) || ((msd == 2) && (lsd == 2)) ||
((msd == 5) && (lsd == 5)) || ((msd == 6) && (lsd == 9)) ||
((msd == 8) && (lsd == 8)) || ((msd == 9) && (lsd == 6))) {
// Remove both from the input
number-= (msd * pow(10, numberLength));
number/= 10;
} else {
// Otherwise, the number isn't flippable
return NO;
}
}
}
return YES;
}
@end
Test cases:
#import <XCTest/XCTest.h>
#import "CSPFlippingNumber.h"
@interface CSPFlippingNumberTests : XCTestCase
@end
@implementation CSPFlippingNumberTests
- (void)testTrue
{
XCTAssert([CSPFlippingNumber isFlippingNumber:818]);
XCTAssert([CSPFlippingNumber isFlippingNumber:1691]);
XCTAssert([CSPFlippingNumber isFlippingNumber:88]);
XCTAssert([CSPFlippingNumber isFlippingNumber:68189]);
XCTAssert([CSPFlippingNumber isFlippingNumber:0]);
XCTAssert([CSPFlippingNumber isFlippingNumber:212]);
XCTAssert([CSPFlippingNumber isFlippingNumber:5]);
}
- (void)testFalse
{
XCTAssertFalse([CSPFlippingNumber isFlippingNumber:8018]);
XCTAssertFalse([CSPFlippingNumber isFlippingNumber:215]);
XCTAssertFalse([CSPFlippingNumber isFlippingNumber:7]);
}
@end
No sorting algorithm has linear complexity O(n). Perhaps you assume that because the sorted function is given, you don't need to worry about its complexity. You must because it's your solution.
- diegum June 23, 2014Another issue is the original order. You should keep it.