Company/Google

Problem Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Definition Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Examples int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; Output: No element appearing more than n/2 times ...

Problem Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". OR Given a sentence, give Longest Sequence Of Prefix Shared By All The Words In A String Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2. ...

Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. ...

Problem Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the MyStack class: void push(int x) Pushes element x to the top of the stack. int pop() Removes the element on the top of the stack and returns it. int top() Returns the element on the top of the stack. boolean empty() Returns true if the stack is empty, false otherwise. Notes: ...

Problem 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. Examples Example 1 Input: "filetestbuffer" read(6) read(5) read(4) read(3) read(2) read(1) read(10) Output: 6, buf = "filete" 5, buf = "stbuf" 3, buf = "fer" 0, buf = "" 0, buf = "" 0, buf = "" 0, buf = "" ...

Problem Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf. The return value is the number of actual characters read. Note that read4() has its own file pointer, much like FILE *fp in C. ...

Problem Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head. The steps of the insertion sort algorithm: Insertion sort iterates, consuming one input element each repetition and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain. The following is a graphical example of the insertion sort algorithm. ...

Problem A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into: ...

Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Follow up: what if duplicates are allowed? ...

Problem Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and add. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity. ...