Sort an array of size N made of numbers from 0 to K Problem statement In this article we will be discussing another (see the previous article) very popular programming interview question. This time we are asked to sort an array of size N whose elements are in the range [0,K). Problem statement Given an array $A=[a_1,a_2,…a_n],\: 1 \leq a_i \leq K$ modify A s.t. it is sorted. As usual you should ask your interviewer some clarifying questions. For example a sensible question to ask could be: What is the maximum value of $K$ and of $N$? Let's assume that $N \leq 10^7$ and $K\leq… Read More »The most asked programming interview questions - #3
In this lesson we will talk about a way of returning values from threads, more precisely we will talk
A future represents an asynchronous task, i.e. an operation that runs in parallel to the current thread and which the latter can wait (if it needs to) until the former is ready.
You can use a future all the time you need a thread to wait for a one-off event to happen. The thread can check the status of the asynchronous operation by periodically polling the future while still performing other tasks, or it can just wait for the future to become ready.
In the previous
This lesson discusses the tools that we can use to achieve such behavior efficiently
Programming Interview Question
Question: given two string write a method to decide if one is a permutation of the other.
This is a common question that could be easily solved if we know in advance which is the size of the alphabeth. A straightforward approach could be to sort both strings and then compare them. This approach has complexity due to sorting. We can do better and lower the complexity to if we reason as follows: given a boolean sequence of the same size of the alphabet initially false initialized. Then what happen if for each char we found in the string we negate the value of the correnspoding bool in the sequence? We end up having the at position if the char appeared an odd number of times and otherwise. Now if the other string is a permutation of the first one, we all agree that for each char in it contains the same number of occurrences. This means that if we apply the same process as before on the boolean sequence using as input the string each bool is being negated an even number of times and this means that its value would be the same as the beginning of the process (all ). So if the sequence does not contains any true value, than it means that the strings contains the same elements i.e. they are permutation of each other.
- "abbccd" , "cbdabc" ,
- Apply negation using s
- Apply negation using v
A possible C++ implementation is shown here
Programming Intervew Question: Unique Characters in a String
Question: implement an algorithm to determine if a string has all unique characters
The idea behing this (fairly easy) question is that whenever we found that any chars is repeated at least twice we should return false. In order to do that we have to look at each char we are loloking for a solution which complexity is at least . We are free to use any support data structure. is the size of the ASCII charset.
Programming Question: Given an integer, compute its parity(easy) The parity of an integer is true iff number of set bits (1) is odd, false otherwise. Example: has 5 set bits and hence its parity is true. Solutions: