SDE - 1

You are given a string S of words. Your task is to count the occurrence of each word present in the string S. A word is a sequence of one or more non-space characters, and there can be multiple spaces between two words, and also there can be leading or trailing spaces in a string S.

For Example:

For the given string  “what we think we become”

“what”,” think”, and “become” occurs 1 time, and “we” occurs 2 times in the given string.

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

For a given string(str), remove all the consecutive duplicate characters.

Example:

Input String: "aaaa"
Expected Output: "a"

Input String: "aabbbcc"
Expected Output: "abc"

You are given an arbitrary binary tree consisting of 'N' nodes numbered from 1 to 'N'. Your task is to print all the root to leaf paths of the binary tree.

A leaf of a binary tree is the node which does not have a left child and a right child.

For Example :

Given a binary tree :

All the root to leaf paths are :
1 2 4
1 2 5 
1 3

Note :

1. Two nodes may have the same value associated with it.
2. The root node will be fixed and will be provided in the function.
3. Note that the nodes in a path will appear in a fixed order. For example, 1 2 3 is not the same as 2 1 3.
4. Each path should be returned as a string consisting of nodes in order and separated by a space.
5. The path length may be as small as ‘1’.

It was a Low Level Design problem. It was similar to an open ended problem of designing the backened APIs for generating some real world data like news feed of a social media site. It was more of a discussion around what data structure should be used to store different data according to the use case .

It can be asked to implement methods related to getting the data and to design the classes for creating objects that will be used.

Ninja has enrolled in a system design course at Coding Ninjas, and his first assignment is to create a search autocomplete system for a search engine.

Ninja is given ‘N’ sentences ‘SENTENCES’ and ‘N’ integers ‘TIMES’, where ‘TIMES’[i] is the number of times the ‘SENTENCES’[i] was typed. Now, the instructor will input a test sentence(at least one word and end with ‘#’). As Ninja’s best friend, can you help him with the assignment?

Your task is to implement the AutocompleteSystemclass:

• AutocompleteSystem(String[] sentences, int[] times)Initializes the object with the sentences and times arrays.
• List input(char c)This indicates that the user typed the character c.
  • Returns an empty array [], if c == '#' and stores the inputted sentence in the system.
  • Returns the top 3 historical hot sentences with the same prefix as the sentence already typed. If there are fewer than 3matches, return them all.

Here are the specific rules:

• A sentence’s hot degree is defined as the number of times a user typed the same sentence before.
• The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
• If less than three hot sentences exist, return as many as possible.
• When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

For Example:

Input:
["AutocompleteSystem","input","input","input"]
[[["i want to join faang","icecream","i love coding ninjas"],[4,3,1],["i"],["s"],["#"]]

Output:
[null,["i want to join faang","icecream","i love coding ninjas"],[],[]]

Explanation:
* AutocompleteSystem obj = new AutocompleteSystem(["i want to join faang","icecream","i love coding ninjas"],[4,3,1]); 
* obj.input(“i”); // return ["i want to join faang","icecream","i love coding ninjas"]. There are three sentences that have prefix "I".
* obj.input(“s”); // return []. There is no sentence with prefix “is”
* obj.input(“#”); // return [].

A binary tree is a tree where each node has at most two children i.e left child and right child.

You are given a binary tree, where the structure of the node is as follow -:

class BinaryTreeNode {
 int data;      // Value of the node.
 BinaryTreeNode *left;  // Pointer to left child node.
 BinaryTreeNode *right; // Pointer to right child node.
 BinaryTreeNode *next;  // Pointer to next right node at same level. 
}

Your task is to connect all the adjacent nodes at the same level in the given binary tree. You can do this by populating each 'next' pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all the next pointers are set to NULL.

For Example:

Consider the figure shown below. The left part represents the initial binary tree and right part represents the binary tree after connecting adjacent nodes at the same level.

In the tree shown in the picture above -:
The ‘next’ pointer of the node having value 2 is connected to the node having value 3.
The ‘next’ pointer of the node having value 4 is connected to the node having value 5.
The ‘next’ pointer of the node having value 5 is connected to the node having value 6.
The ‘next’ pointer of nodes having value 1, 3, 6 will have a value NULL as there are no next right nodes in their cases.

Note:

1. The structure of the ‘Node’ of a binary tree is already defined. You should not change it.   
2. The root of the binary tree is known to you.  
3. There is at least one node in the given binary tree.
4. You may only use constant extra space.