I think we need to think about filesystems and other OS components.
Not everything in computer is implemented using hast table.
In case of spotlight if you see wiki the underlying data structure is B trees.
Think in that direction what factor apart from B trees would be a performance hit.
Hint: think about filesystems
2. Explain Differentiate between Google search and local computer search?
google search is global serach engine based on out side information,local computer search is with in computer area data or information search.
After retrospective, I think intent of this question was to check if I knew these sorting in and out or not including very details.
Two methods must be applied. First, the simulator must conform to the system specification for the hardware. Every instruction that retires must behave exactly as the hardware expects, including every result, and every control register. Unit tests can be written for these individual cases and used to maintain the simulator. Next, real world programs and applications should be ported to run on the simulator. Instrumentation code can be added to provide some kind of checksum section to ensure that the simulator is outputting results the same as hardware.
5. What is B trees and its applications?
A B-tree is just another tree data structure mostly used within file systems and databases. Common file systems that use B-trees are HFS+ (OSX), ext4 (Linux) and NTFS (Windows).
6. How to design spotlight search feature in Mac OS?
B-tree or Hash Table
7. Do you know Which sorting algo you would like to implement as unix library and why?
I think more than the answer, the reason would be important. Quick sort for example is important because its average runtime is O(nlog(n)) and in most cases its better than other logarithmic algorithms ( Merge Sort and Heap Sort ). I would ask him though, why would you want to stop at implementing just one algorithm. How about an API that can use sort based on input size ( strategy design pattern ); because for different values of n different sorting algorithms can be usefule
char * setEmpty(int len){
if (0>len) return NULL;
char * c = (char *) malloc(len+1);
memset(c, 0, len+1);
return c;
}
9. How to parse a phone number from a huge database of a n billion webpages in 30 minutes
The numbers do have sematic meaning, eg: location. Hence, if the database is distributed, that helps. Additionally, the DB must be stored in a N-nary search tree where N is large, reducing the height of the tree significantly.
10. Designed a similar API like malloc, which has a similar functionality. How do you test the API?
1) Give a very large size(1000000000) and check if its able to allocate
2) Provide number values 1,3,0,100
3) Give a character in size to api
4) GIve blank spaces
5) NUll value for size field in api
6) Call the api from multiple sessions
How about this? For multithreading, put mutex in write
template<typename T>
class writeandread
{
public:
writeandread(T* s, int n):start(s), writePtr(s),readPtr(s), maxbytes(n), numofeles(0) {}
T* getStartPtr(){return start;}
T* getwritePtr(){return writePtr;}
T* getreadPtr(){return readPtr;}
bool write(T* input, int n);
T* read(int n);
private:
T* start, *writePtr, *readPtr;
size_t maxbytes, numofeles;
};
template<typename T>
bool writeandread<T>::write(T* input, int n)
{
if (input == NULL && n > 0)
return false;
if (maxbytes-numofeles < n*sizeof(T)/sizeof(char))
return false;
numofeles += n*sizeof(T)/sizeof(char);
for (int i = 0; i < n; ++i)
{
*writePtr = *input;
++writePtr;
++input;
}
return true;
}
template<typename T>
T* writeandread<T>::read(int n)
{
if (n <= 0)
return NULL;
T* res = (T*) malloc(n);
T* t = res;
int count = 0;
while (writePtr != readPtr)
{
*t = *readPtr;
++t;
readPtr += sizeof(T);
++count;
}
if (count < n)
readPtr = start;
return res;
}
Poll after some constant time
If T1 has priority p always set T2 priority lesser then T1 that is p+1
13. Design a chess game. Basics of a chess game was explained and a player could be human or AI?
Follow-up questions:
* What are the main objects?
* How do the main objects interact with each other?
* Which object or objects own the current game state information?
* Implement the method to move a piece to another position on the board. method must communicate if the move is legal or not.
* How do you test the move piece method?
Chessboard: contains a matrix of chess pieces objects
Player: contains a list of references to his/her active chesspieces
Chess piece: contanis color or player, and what type of piece is it (tower, horse...)
boolean canMove(pieceType, start_x_pos, end_x_pos, start_y_pos, end_y_pos){
if (type equals horse){
canMoveHorse (pieceType, start_x_pos, end_x_pos, start_y_pos, end_y_pos);
}
else if (type equals horse){...}
...
}
test1: the piece is at the indicated position
test2: the piece has the same color at before it was moved
test3: if there was another piece at the end position, now it has been removed from the chessboard and from its player's list
test4: if it is a queen, tower, ... check that before the movement there wasn't any other piece in the path
test5: check that the other pieces are at the same places where they were before the movement
IPhone is a combination of internet and multimedia enabled smart phone developed by Apple Inc.
iPhone functions as a camera phone, including text messaging, and visual voice mail
iPhone is a portable media player that resembles a video iPod
It has user interface that is built around the multi-touch screen including virtual keyboard.
App Store , which launched in the mid 2008 has over 1,00,000 applications with functionalities including games, references, GPS navigation, advertising, television shows, films, reference, celebrities.
iPhone OS runs on iPhone and iPod touch devices.
Hardware devices are managed by iPhone OS and provides the technologies needed for implementing native applications on the phone.
The OS ships with several system applications such as Mail, Safari, Phone, which provide standard services to the user.
iPhone SDK is available with tools and interfaces needed for developing, installing and running custom native applications.
Native applications are built using the iPhone OS's system frameworks and Objective-C language and run directly on iPhone OS.
Native applications are installed physically on a device and can run in presence or absence of network connection.
17. Explain sensors in iphone?
The proximity sensor immediately turns off the display when the iPhone is lifted to ear. With this sensor the power is saved and accidental dialing is prevented.
The display is automatically brightens the iPhone by the ambient light sensor when the sunlight or bright rooms and dims in darker places.
18. Define the features of iphone 3gs?
Video: Videos can be edited, shared. High quality VGA video can be shot in portrait or landscape.
3 Megapixel Camera:
Still photos with greater quality can be taken
Voice control:
It recognizes the names in contacts and recognizes the music on iPod.
Compass:
iPhone 3GS has built-in digital compass, used to point the way.
Internet Tethering: Internet surfing can be done from anywhere. A 3G connection can be shared on Iphon3 with Mac notebook or laptop.
19. Explain iphone reference library?
iPhone reference library is a set of reference documents for iPhone OS .
It can be downloaded by subscribing to the iPhone OS Library doc set.
Select Help>Documentation from Xcode, and click the subscribe button next to the iPhone OS Library doc set, which appears in the left column.
20. Define the location services?
Applications such as Maps, camera and compass are allowed to use the information from cellular, Wi-Fi and Global Positioning System networks for determining the approximate locations.
The location is displayed on the screen, using a blue marker.
21. Explain the functionality of accelerometer of an iphone?
iPhone responds to motion using a built-in accelerometer.
The accelerometer detects the movement and changes the display accordingly, at the time of rotating iPhone from portrait to landscape.
A struct is a special C data type that encapsulates other pieces of data into a single cohesive unit. Like an object, but built into C.
An iPhone app is a program that runs on our iPhone/iPod Touch. It enables us to accomplish a certain task. They could be utility apps, games, enterprise apps, entertainment apps, apps to access our bank account etc.
The frame of a view is the rectangle, expressed as a location (x,y) and size (width,height) relative to the superview it is contained within. The bounds of a view is the rectangle, expressed as a location (x,y) and size (width,height) relative to its own coordinate system (0,0).
