An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

Read More »

Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Read More »

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Read More »

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers.

Read More »

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

Read More »

• Where are the stack and heap stored?
  • They are both stored in the computer’s RAM (Random Access Memory). For a refresher on RAM and virtual memory, read this article: How Virtual Memory Works
• How do threads interact with the stack and the heap? How do the stack and heap work in multithreading?
  • In a multi-threaded application, each thread will have its own stack. But, all the different threads will share the heap. Because the different threads share the heap in a multi-threaded application, this also means that there has to be some coordination between the threads so that they don’t try to access and manipulate the same piece(s) of memory in the heap at the same time.
• Can an object be stored on the stack instead of the heap?
  • Yes, an object can be stored on the stack. If you create an object inside a function without using the “new” operator then this will create and store the object on the stack, and not on the heap. Suppose we have a C++ class called Member, for which we want to create an object. We also have a function called some function(). Here is what the code would look like:
• Code to create an object on the stack:

``` java void somefunction( ) { /* create an object “m” of class Member this will be put on the stack since the “new” keyword is not used, and we are creating the object inside a function */

Read More »

The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file. Note: The read function may be called multiple times.

Read More »

The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Read More »

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Read More »

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

Read More »

Given two strings S and T, determine if they are both one edit distance apart.

Read More »

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges. For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].

Read More »

Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Read More »

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses.

Read More »

Design and implement a TwoSum class. It should support the following operations: add and find.</p>

Read More »

Given a column title as appear in an Excel sheet, return its corresponding column number.

Read More »

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

Read More »

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note: The input string may contain letters other than the parentheses ( and ).

Read More »

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.</p>

Read More »

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Read More »

Reverse bits of a given 32 bits unsigned integer.

Read More »

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Read More »

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Read More »

Write an algorithm to determine if a number is “happy”. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Read More »

Count the number of prime numbers less than a non-negative number, n.

Read More »

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Read More »

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Read More »

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Read More »

Design a data structure that supports the following two operations, search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Read More »

ZZ from

• Explain the main purpose of an operating system?
  • Operating systems exist for two main purposes. One is that it is designed to make sure a computer system performs well by managing its computational activities. Another is that it provides an environment for the development and execution of programs.
• What is demand paging?
  • Demand paging is a system wherein area of memory that are not currently being used are swapped to disk to make room for an application’s need.
• What are the advantages of a multiprocessor system?
  • With an increased number of processors, there is considerable increase in throughput. It can also save more money because they can share resources. Finally, overall reliability is increased as well.
• What is kernel?
  • Kernel is the core of every operating system. It connects applications to the actual processing of data. It also manages all communications between software and hardware components to ensure usability and reliability.
• What are real-time systems?
  • Real-time systems are used when rigid time requirements have been placed on the operation of a processor. It has well defined and fixed time constraints.
• What is virtual memory?
  • Virtual memory is a memory management technique for letting processes execute outside of memory. This is very useful especially is an executing program cannot fit in the physical memory.
• Describe the objective of multiprogramming.
  • The main objective of multiprogramming is to have process running at all times. With this design, CPU utilization is said to be maximized.
• What are time sharing systems?
  • In a Time sharing system, the CPU executes multiple jobs by switching among them, also known as multitasking. This process happens so fast that users can actually interact with each program while it is running.
• What is SMP?
  • SMP is short for Symmetric MultiProcessing, and is the most common type of multiple- processor systems. In this system, each processor runs an identical copy of the operating system, and these copies communicate with one another as needed.
• How are server systems classified?
  • Server systems can be classified as either computer-server systems or file server systems. In the first case, an interface is made available for clients to send requests to perform an action. In the second case, provisions are available for clients to create, access and update files.
• What is asymmetric clustering?
  • In asymmetric clustering, a machine is in a state known as hot standby mode where it does nothing but to monitor the active server. That machine takes the active server’s role should the server fails.
• What is a thread?
  • A thread is a basic unit of CPU utilization. In general, a thread is composed of a thread ID, program counter, register set and the stack.
• Give some benefits of multithreaded programming.
  • there is an increased responsiveness to the user
  • resource sharing within the process
  • economy
  • utilization of multiprocessing architecture
• Briefly explain FCFS.
  • FCFS is short for First-come, first-served, and is one type of scheduling algorithm. In this scheme, the process that requests the CPU first is allocated the CPU first. Implementation is managed by a FIFO queue.
• What is RR scheduling algorithm?
  • RR (round-robin) scheduling algorithm is primarily aimed for time-sharing systems. A circular queue is setup in such a way that the CPU scheduler goes around that queue, allocating CPU to each process for a time interval of up to around 10 to 100 milliseconds.
• What necessary conditions can lead to a deadlock situation in a system?
  • Deadlock situations occur when four conditions occur simultaneously in a system: Mutual exclusion; Hold and Wait; No preemption; and Circular wait.
• Enumerate the different RAID levels.
  • RAID 0 – Non-redundant striping
  • RAID 1 – Mirrored Disks
  • RAID 2 – Memory-style error-correcting codes
  • RAID 3 - Bit-interleaved Parity
  • RAID 4 – Block-interleaved Parity
  • RAID 5 – Block-interleaved distributed Parity
  • RAID 6 – P+Q Redundancy
• Describe Banker’s algorithm
  • Banker’s algorithm is one form of deadlock-avoidance in a system. It gets its name from a banking system wherein the bank never allocates available cash in such a way that it can no longer satisfy the needs of all of its customers.
• What factors determine whether a detection-algorithm must be utilized in a deadlock avoidance system?
  • One is that it depends on how often a deadlock is likely to occur under the implementation of this algorithm. The other has to do with how many processes will be affected by deadlock when this algorithm is applied.
• Differentiate logical from physical address space.
  • Logical address refers to the address that is generated by the CPU. On the other hand, physical address refers to the address that is seen by the memory unit.
• How does dynamic loading aid in better memory space utilization?
  • With dynamic loading, a routine is not loaded until it is called. This method is especially useful when large amounts of code are needed in order to handle infrequently occurring cases such as error routines.
• What are overlays?
  • Overlays are used to enable a process to be larger than the amount of memory allocated to it. The basic idea of this is that only instructions and data that are needed at any given time are kept in memory.
• What is the basic function of paging?
  • Paging is a memory management scheme that permits the physical-address space of a process to be noncontiguous. It avoids the considerable problem of having to fit varied sized memory chunks onto the backing store.
• What is fragmentation?
  • Fragmentation is memory wasted. It can be internal if we are dealing with systems that have fixed-sized allocation units, or external if we are dealing with systems that have variable-sized allocation units.
• How does swapping result in better memory management?
  • During regular intervals that are set by the operating system, processes can be copied from main memory to a backing store, and then copied back later. Swapping allows more processes to be run that can fit into memory at one time.
• Give an example of a Process State.
  • New State – means a process is being created
  • Running – means instructions are being executed
  • Waiting – means a process is waiting for certain conditions or events to occur
  • Ready – means a process is waiting for an instruction from the main processor - Terminate – means a process is done executing
• What is a socket?
  • A socket provides a connection between two applications. Each endpoint of a communication is a socket.
• What is Direct Access Method?
  • Direct Access method is based on a disk model of a file, such that it is viewed as a numbered sequence of blocks or records. It allows arbitrary blocks to be read or written. Direct access is advantageous when accessing large amounts of information.
• When does trashing occur?
  • Trashing refers to an instance of high paging activity. This happens when it is spending more time paging instead of executing.
• What is the best page size when designing an operating system?
  • The best paging size varies from system to system, so there is no single best when it comes to page size. There are different factors to consider in order to come up with a suitable page size, such as page table, paging time, and its effect on the overall efficiency of the operating system.
• When designing the file structure for an operating system, what attributes are considered?
  • Typically, the different attributes for a file structure are naming, identifier, supported file types, and location for the files, size, and level of protection.
• What is root partition?
  • Root partition is where the operating system kernel is located. It also contains other potentially important system files that are mounted during boot time.
• What are device drivers?
  • Device drivers provides a standard means of representing I/O devices that maybe manufactured by different companies. This prevents conflicts whenever such devices are incorporated in a systems unit.
• What are the primary functions of VFS?
  • VFS, or Virtual File System, separates file system generic operations from their implementation by defining a clean VFS interface. It is also based on a file-representation structure known as vnode, which contains a numerical designator needed to support network file systems.
• What are the different types of CPU registers in a typical operating system design?
  • Accumulators
  • Index Registers
  • Stack Pointer
  • General Purpose Registers
• What is the purpose of an I/O status information?
  • I/O status information provides info about which I/O devices are to be allocated for a particular process. It also shows which files are opened, and other I/O device state.
• What is multitasking?
  • Multitasking is the process within an operating system that allows the user to run several applications at the same time. However, only one application is active at a time for user interaction, although some applications can run “behind the scene”.
• What are some pros and cons of a command line interface?
  • A command line interface allows the user to type in commands that can immediately provide results. Many seasoned computer users are well accustomed to using the command line because they find it quicker and simpler. The main problem with a command line interface is that users have to be familiar with the commands, including the switches and parameters that come with it. This is a downside for people who are not fond of memorizing commands.
• What is caching?
  • Caching is the processing of utilizing a region of fast memory for a limited data and process. A cache memory is usually much efficient because of its high access speed.
• What is spooling?
  • Spooling is normally associated with printing. When different applications want to send an output to the printer at the same time, spooling takes all of these print jobs into a disk file and queues them accordingly to the printer.
• What is an Assembler?
  • An assembler acts as a translator for low level language. Assembly codes, written using mnemonic commands are translated by the Assembler into machine language.
• What are interrupts?
  • Interrupts are part of a hardware mechanism that sends a notification to the CPU when it wants to gain access to a particular resource. An interrupt handler receives this interrupt signal and “tells” the processor to take action based on the interrupt request.
• What is GUI?
  • GUI is short for Graphical User Interface. It provides users with an interface wherein actions can be performed by interacting with icons and graphical symbols. People find it easier to interact with the computer when in a GUI especially when using the mouse. Instead of having to remember and type commands, users just click on buttons to perform a process.
• What is preemptive multitasking?
  • Preemptive multitasking allows an operating system to switch between software programs. This in turn allows multiple programs to run without necessarily taking complete control over the processor and resulting in system crashes.
• Why is partitioning and formatting a prerequisite to installing an operating system?
  • Partitioning and formatting creates a preparatory environment on the drive so that the operating system can be copied and installed properly. This includes allocating space on the drive, designating a drive name, determining and creating the appropriate file system structure.
• What is plumbing / piping?
  • It is the process of using the output of one program as an input to another. For example, instead of sending the listing of a folder or drive to the main screen, it can be piped and sent to a file, or sent to the printer to produce a hard copy.
• What is NOS?
  • NOS is short for Network Operating System. It is a specialized software that will allow a computer to communicate with other devices over the network, including file/folder sharing.
• Differentiate internal commands from external commands.
  • Internal commands are built-in commands that are already part of the operating system. External commands are separate file programs that are stored in a separate folder or directory.
• Under DOS, what command will you type when you want to list down the files in a directory, and at the same time pause after every screen output?
  • a) dir /w
  • b) dir /p
  • c) dir /s
  • d) dir /w /p
  • Answer: d) dir /w /p
• How would a filenamed EXAMPLEFILE.TXT appear when viewed under the DOS command console operating in Windows 98?
  • The filename would appear as EXAMPL~1.TXT . The reason behind this is that filenames under this operating system is limited to 8 characters when working under DOS environment.

Read More »